IBM Research | Cayley path and quantum computational supremacy* @ibmresearch | Uploaded April 2020 | Updated October 2024, 4 days ago.
Presenter: Ramis Movassagh, Research Staff Member, Quantum Theory and Algorithms, IBM Research
A one-parameter unitary-valued interpolation between any two unitary matrices is constructed based on the Cayley transformation, which extends our work. The entries of the interpolated unitaries are shown to be low-degree rational functions in the parameter, which we proved can be efficiently determined using an extension of the Berlekamp-Welch algorithm. We prove that this path provides scrambled unitaries with probability distributions arbitrarily close to the Haar measure. We then prove the simplest known average-case #P-hardness of random circuit sampling (RCS), which is the task of sampling from the output distribution of a quantum circuit whose local gates are random Haar unitaries, and is the lead candidate for demonstrating quantum supremacy in the NISQ era. We show that a previous work based on the truncations of the power series representation of the exponential function does not provide practical robustness. Explicit bounds on noise resilience are proved, which on a grid of sqrt(n)xsqrt(n) qubits with circuit depth sqrt(n) is 2^O(-n^3), and with constant-depth it is 2^O(-n^2). Improvements to O(2^(−n)/poly(n)) would prove the quantum supremacy conjecture, which may be false.
*The Frontiers Foundation and the MIT-IBM collaborative grant
Presenter: Ramis Movassagh, Research Staff Member, Quantum Theory and Algorithms, IBM Research
A one-parameter unitary-valued interpolation between any two unitary matrices is constructed based on the Cayley transformation, which extends our work. The entries of the interpolated unitaries are shown to be low-degree rational functions in the parameter, which we proved can be efficiently determined using an extension of the Berlekamp-Welch algorithm. We prove that this path provides scrambled unitaries with probability distributions arbitrarily close to the Haar measure. We then prove the simplest known average-case #P-hardness of random circuit sampling (RCS), which is the task of sampling from the output distribution of a quantum circuit whose local gates are random Haar unitaries, and is the lead candidate for demonstrating quantum supremacy in the NISQ era. We show that a previous work based on the truncations of the power series representation of the exponential function does not provide practical robustness. Explicit bounds on noise resilience are proved, which on a grid of sqrt(n)xsqrt(n) qubits with circuit depth sqrt(n) is 2^O(-n^3), and with constant-depth it is 2^O(-n^2). Improvements to O(2^(−n)/poly(n)) would prove the quantum supremacy conjecture, which may be false.
*The Frontiers Foundation and the MIT-IBM collaborative grant
