A study of heuristic guesses for adiabatic quantum computation
From MaRDI portal
Abstract: Adiabatic quantum computation (AQC) is a universal model for quantum computation which seeks to transform the initial ground state of a quantum system into a final ground state encoding the answer to a computational problem. AQC initial Hamiltonians conventionally have a uniform superposition as ground state. We diverge from this practice by introducing a simple form of heuristics: the ability to start the quantum evolution with a state which is a guess to the solution of the problem. With this goal in mind, we explain the viability of this approach and the needed modifications to the conventional AQC (CAQC) algorithm. By performing a numerical study on hard-to-satisfy 6 and 7 bit random instances of the satisfiability problem (3-SAT), we show how this heuristic approach is possible and we identify that the performance of the particular algorithm proposed is largely determined by the Hamming distance of the chosen initial guess state with respect to the solution. Besides the possibility of introducing educated guesses as initial states, the new strategy allows for the possibility of restarting a failed adiabatic process from the measured excited state as opposed to restarting from the full superposition of states as in CAQC. The outcome of the measurement can be used as a more refined guess state to restart the adiabatic evolution. This concatenated restart process is another heuristic that the CAQC strategy cannot capture.
Recommendations
- scientific article; zbMATH DE number 1984609
- scientific article; zbMATH DE number 5953558
- The travelling salesman problem and adiabatic quantum computation: an algorithm
- Random matrix model of adiabatic quantum computing
- Different adiabatic quantum optimization algorithms for the NP-complete exact cover and 3SAT problems
Cites work
- A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
- Adiabatic Quantum State Generation
- Adiabatic quantum state generation and statistical zero knowledge
- Bounds for the adiabatic approximation with applications to quantum computation
- HOW TO MAKE THE QUANTUM ADIABATIC ALGORITHM FAIL
- scientific article; zbMATH DE number 5953558 (Why is no real title available?)
- scientific article; zbMATH DE number 3167699 (Why is no real title available?)
- scientific article; zbMATH DE number 5595151 (Why is no real title available?)
- scientific article; zbMATH DE number 5305148 (Why is no real title available?)
- scientific article; zbMATH DE number 5320186 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Quantum optimization
- The Complexity of the Local Hamiltonian Problem
- The complexity of the quantum adiabatic algorithm
- The state of SAT
- Unstructured adiabatic quantum search
Cited in
(7)- Entangling problem Hamiltonian for adiabatic quantum computation
- A survey of quantum image representations
- On the role of prior probability in adiabatic quantum algorithms
- A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing
- Why adiabatic quantum annealing is unlikely to yield speed-up
- Grover search inspired alternating operator ansatz of quantum approximate optimization algorithm for search problems
- On the circuit model of two quantum adiabatic search algorithms
This page was built for publication: A study of heuristic guesses for adiabatic quantum computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q632202)
