On the role of coherence for quantum computational advantage

Abstract

Quantifying the resources available to a quantum computer appears to be necessary to separate quantum from classical computation. Among them, entanglement, nonstabilizerness and coherence are arguably of great significance. We introduce path coherence as a measure of the coherent paths interferences arising in a quantum computation. Leveraging the sum-over-paths formalism, we obtain a classical algorithm for estimating quantum transition amplitudes, the complexity of which scales with path coherence. As path coherence relates to the hardness of classical estimation of quantum transition amplitudes, it provides a new perspective on the role of coherence in quantum computational advantage. Beyond their fundamental significance, our results have practical applications for simulating large classes of quantum computations with classical computers.

v2: accepted for publication in PRL; 6 pages + 14 pages of appendices; 1 figure

References in corpus (33)

• Quantum entanglement
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• The density-matrix renormalization group in the age of matrix product states
• Quantifying Coherence
• Supervised learning with quantum enhanced feature spaces
• Efficient classical simulation of slightly entangled quantum computations
• Quantum Coherence as a Resource
• Improved Simulation of Stabilizer Circuits
• Multi-party entanglement in graph states
• Operational Resource Theory of Coherence
• The Resource Theory of Stabilizer Computation
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Building a fault-tolerant quantum computer using concatenated cat codes
• Stabilizer Rényi entropy
• Coherence as a resource in decision problems: The Deutsch-Jozsa algorithm and a variation
• Polynomial-time T-depth Optimization of Clifford+T circuits via Matroid Partitioning
• Coherence depletion in the Grover quantum search algorithm
• Instantaneous Quantum Computation
• Cohering power of quantum operations
• On the CNOT-complexity of CNOT-PHASE circuits
• Fast estimation of outcome probabilities for quantum circuits
• Reducing the Depth of Linear Reversible Quantum Circuits
• A Quantitative Measure of Interference
• Quantum circuits and low-degree polynomials over F_2
• Reducing the CNOT count for Clifford+T circuits on NISQ architectures
• Quantum computation with cat qubits
• Phase polynomials synthesis algorithms for NISQ architectures and beyond
• q-Stirling numbers: A new view
• A simple encoding of a quantum circuit amplitude as a matrix permanent
• Classical simulation of quantum circuits by half Gauss sums
• Optimal Hadamard gate count for Clifford$+T$ synthesis of Pauli rotations sequences
• Classical verification of quantum circuits containing few basis changes
• Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy