Adiabatic quantum optimization in presence of discrete noise: Reducing the problem dimensionality
arXiv:1407.8183 · doi:10.1103/PhysRevA.92.062320
Abstract
Adiabatic quantum optimization is a procedure to solve a vast class of optimization problems by slowly changing the Hamiltonian of a quantum system. The evolution time necessary for the algorithm to be successful scales inversely with the minimum energy gap encountered during the dynamics. Unfortunately, the direct calculation of the gap is strongly limited by the exponential growth in the dimensionality of the Hilbert space associated to the quantum system. Although many special-purpose methods have been devised to reduce the effective dimensionality, they are strongly limited to particular classes of problems with evident symmetries. Moreover, little is known about the computational power of adiabatic quantum optimizers in real-world conditions. Here, we propose and implement a general purposes reduction method that does not rely on any explicit symmetry and which requires, under certain general conditions, only a polynomial amount of classical resources. Thanks to this method, we are able to analyze the performance of "non-ideal" quantum adiabatic optimizers to solve the well-known Grover problem, namely the search of target entries in an unsorted database, in the presence of discrete local defects. In this case, we show that adiabatic quantum optimization, even if affected by random noise, is still potentially faster than any classical algorithm.
arXiv commentVersion published in Physical Review A with an improved/different content selection with respect to the previous version entitled "Dimensionality reduction for adiabatic quantum optimizers: Beyond symmetry exploitation"
References in corpus (40)
- A variational eigenvalue solver on a quantum processor
- Quantum Mechanics helps in searching for a needle in a haystack
- An efficient, multiple range random walk algorithm to calculate the density of states
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Simulated Quantum Computation of Molecular Energies
- Quantum annealing with more than one hundred qubits
- A quantum algorithm providing exponential speed increase for finding eigenvalues and eigenvectors
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Annealing: A New Method for Minimizing Multidimensional Functions
- Quantum Search by Local Adiabatic Evolution
- Defining and detecting quantum speedup
- Bounds for the adiabatic approximation with applications to quantum computation
- Anderson localization casts clouds over adiabatic quantum optimization
- From transistor to trapped-ion computers for quantum chemistry
- Quantum Optimization of Fully-Connected Spin Glasses
- Error corrected quantum annealing with hundreds of qubits
- Quantum Speedup by Quantum Annealing
- Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
- Thermally assisted adiabatic quantum computation
- Noise resistance of adiabatic quantum computation using random matrix theory
- Adiabatic Quantum Computing for Random Satisfiability Problems
- Decoherence in adiabatic quantum computation
- Quantum Adiabatic Evolution Algorithms versus Simulated Annealing
- Effects of Noisy Oracle on Search Algorithm Complexity
- Quantum Adiabatic Evolution Algorithms with Different Paths
- Different Strategies for Optimization Using the Quantum Adiabatic Algorithm
- Exponential complexity of an adiabatic algorithm for an NP-complete problem
- Adiabatic Quantum Computation and Deutsch's Algorithm
- Non-Markovian decoherence in the adiabatic quantum search algorithm
- Algorithm engineering for a quantum annealing platform
- A modified quantum adiabatic evolution for the Deutsch-Jozsa problem
- Construction of Energy Functions for Lattice Heteropolymer Models: A Case Study in Constraint Satisfaction Programming and Adiabatic Quantum Optimization
- Different Adiabatic Quantum Optimization Algorithms for the NP-Complete Exact Cover and 3SAT Problems
- Solving the Graph Isomorphism Problem with a Quantum Annealer
- Feynman's clock, a new variational principle, and parallel-in-time quantum dynamics
- Excitation Gap from Optimized Correlation Functions in Quantum Monte Carlo Simulations
- Complete high-precision entropic sampling
- Continuous-Time Quantum Algorithms for Unstructured Problems
- On the efficiency of Hamiltonian-based quantum computation for low-rank matrices
Cited by in corpus (12)
- Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
- A deceptive step towards quantum speedup detection
- Maximum-Entropy Inference with a Programmable Annealer
- Evaluation of QAOA based on the approximation ratio of individual samples
- Analog Nature of Quantum Adiabatic Unstructured Search
- Faster than Classical Quantum Algorithm for dense Formulas of Exact Satisfiability and Occupation Problems
- Patch-planting spin-glass solution for benchmarking
- Stochastic learning control of adiabatic speedup in a non-Markovian open qutrit system
- Sensitivity of quantum speedup by quantum annealing to a noisy oracle
- Threshold theorem in isolated quantum dynamics with stochastic control errors
- Hard combinatorial problems and minor embeddings on lattice graphs
- Control limit for the quantum state preparation under stochastic control errors