Why adiabatic quantum annealing is unlikely to yield speed-up

DOI10.1088/1751-8121/ad0439arXiv2212.13649OpenAlexW4387698200MaRDI QIDQ6059153

Hilbert J. Kappen, Unnamed Author, Aarón Villanueva

Publication date: 2 November 2023

Published in: Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2212.13649

zbMATH Keywords

algorithmic complexityNP-hard problemsadiabatic quantum computingquantum speedup

Mathematics Subject Classification ID

Quantum computation (81P68) Adiabatic invariants for problems in Hamiltonian and Lagrangian mechanics (70H11) Representation and superposition of functions (26B40) Quantum algorithms and complexity in the theory of computing (68Q12)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• A study of heuristic guesses for adiabatic quantum computation
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Quantum stochastic optimization
• How quantum is the speedup in adiabatic unstructured search?
• Efficient diabatic quantum algorithm in number factorization
• Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results
• Eigenvalues of rank-one updated matrices with some applications
• Quantum versus classical annealing of Ising spin glasses
• Quantum Computation and Quantum Information
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Many hard examples for resolution
• HOW TO MAKE THE QUANTUM ADIABATIC ALGORITHM FAIL
• Bounds for the adiabatic approximation with applications to quantum computation
• Exponential algorithmic speedup by a quantum walk
• Cooling Schedules for Optimal Annealing
• Survey propagation: An algorithm for satisfiability
• Computational Complexity
• The performance of the quantum adiabatic algorithm on spike Hamiltonians
• Threshold values of random K‐SAT from the cavity method
• (Sub)Exponential advantage of adiabatic Quantum computation with no sign problem

This page was built for publication: Why adiabatic quantum annealing is unlikely to yield speed-up