Role of Coherence for Quantum Computational Advantage.

Area of Science:

• Quantum Computing
• Computational Complexity
• Quantum Information Theory

Background:

• Quantifying quantum resources is crucial for distinguishing quantum from classical computation.
• Entanglement, nonstabilizerness, and coherence are key quantum resources.
• Coherence plays a significant role in achieving quantum computational advantage.

Purpose of the Study:

• Introduce "path coherence" as a novel measure of coherent path interferences in quantum computation.
• Establish a connection between path coherence and the difficulty of classical simulation of quantum systems.
• Provide a new perspective on the role of coherence in quantum advantage.

Main Methods:

• Utilize the sum-over-paths formalism to develop a classical algorithm.
• Estimate quantum transition amplitudes using the developed classical algorithm.
• Analyze the complexity scaling of the estimation algorithm with respect to path coherence.

Main Results:

• Developed a classical algorithm for estimating quantum transition amplitudes.
• Demonstrated that the algorithm's complexity scales directly with path coherence.
• Showcased path coherence as a relevant measure for quantum computational advantage.

Conclusions:

• Path coherence offers a new perspective on the role of coherence in quantum advantage.
• The developed classical algorithm has practical applications for simulating quantum computations.
• This work bridges fundamental quantum information theory with practical computational challenges.