Quantum advantage with shallow circuits

Area of Science:

• Quantum Computing
• Computational Complexity Theory
• Linear Algebra

Background:

• Quantum mechanics offers potential for enhanced information processing and faster computation.
• Proving a definitive quantum advantage or demonstrating it with current quantum devices remains an active research area.

Purpose of the Study:

• To provide an unconditional proof of computational quantum advantage.
• To identify quantum nonlocality as the source of this advantage.
• To propose a quantum algorithm suitable for near-term experimental implementation.

Main Methods:

• Development of parallel quantum algorithms designed to run in constant time.
• Focus on solving linear algebra problems related to binary quadratic forms.
• Utilizing constant-depth quantum circuits with nearest-neighbor gates on a 2D qubit grid.

Main Results:

• Demonstrated that parallel quantum algorithms are strictly more powerful than classical algorithms.
• Provided a provable quantum advantage in solving specific linear algebra problems.
• Established quantum nonlocality as the fundamental reason for the observed computational advantage.

Conclusions:

• An unconditional proof of computational quantum advantage has been established.
• Quantum nonlocality is identified as the key resource enabling this advantage.
• The proposed algorithm is practical for near-future quantum computing experiments.