The Parametrized Complexity of Quantum Verification
Srinivasan Arunachalam, Sergey Bravyi, et al.
TQC 2022
Quantum effects can enhance information-processing capabilities and speed up the solution of certain computational problems. Whether a quantum advantage can be rigorously proven in some setting or demonstrated experimentally using near-term devices is the subject of active debate. We show that parallel quantum algorithms running in a constant time period are strictly more powerful than their classical counterparts; they are provably better at solving certain linear algebra problems associated with binary quadratic forms. Our work gives an unconditional proof of a computational quantum advantage and simultaneously pinpoints its origin: It is a consequence of quantum nonlocality. The proposed quantum algorithm is a suitable candidate for near-future experimental realizations, as it requires only constant-depth quantum circuits with nearest-neighbor gates on a two-dimensional grid of qubits (quantum bits).
Srinivasan Arunachalam, Sergey Bravyi, et al.
TQC 2022
Sergey Bravyi, David Fattal, et al.
Journal of Mathematical Physics
Ewout van den Berg, Sergey Bravyi, et al.
PRResearch
Sergey Bravyi, Anirban Chowdhury, et al.
PRX Quantum