Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial Optimization

2020/07/31 by Yuval R. Sanders, Dominic W. Berry, Pedro C. S. Costa +6
Computer Science · Physics and Astronomy · #Combinatorial optimization #Heuristics #Optimization problem #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum algorithm #Quantum annealing #Quantum computer #Quantum many-body systems #Range (aeronautics) #quant-ph

paper · pdf · doi:10.1103/prxquantum.1.020312

published as PRX Quantum 1, 020312 (2020) · 77 pages, 19 figures, 9 tables. v2 contains new appendix on in-place binary to unary conversion

openalex created_date 2020/07/23 · arxiv created 2020/08/05 · openalex publication_date 2020/11/09 · arxiv updated 2020/11/12 · openalex updated_date 2026/08/05

Abstract

The resources required for implementing a diverse range of fault-tolerant quantum optimization algorithms are rigorously analyzed, elucidating the challenges of realizing a quantum advantage for algorithms giving only a quadratic speedup.

Citations

• Quantum Annealing in the Transverse Ising Model
• Adiabatic approximation with exponential accuracy for many-body systems and quantum computation
• Sherrington-Kirkpatrick model in a transverse field: Absence of replica symmetry breaking due to quantum fluctuations
• Quantum Simulations of Classical Annealing Processes
• Topological quantum memory
• Fault-tolerant quantum computation by anyons
• A variational eigenvalue solver on a photonic quantum processor
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices