Resource efficient gadgets for compiling adiabatic quantum optimization problems

DOI10.1002/ANDP.201300120MaRDI QIDQ2870496zbMATH OpenOpenAlexFDO

Authors Ryan Babbush, Bryan O'Gorman, Alán Aspuru-Guzik

Publication date 21 January 2014

Published in Annalen der Physik (Search for Journal in Brave)

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

zbMATH Keywords

adiabatic quantum computingoptimizationquantum informationquantum simulation

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum coding (general) (81P70)

Abstract: We develop a resource efficient method by which the ground-state of an arbitrary k-local, optimization Hamiltonian can be encoded as the ground-state of a (k-1)-local optimization Hamiltonian. This result is important because adiabatic quantum algorithms are often most easily formulated using many-body interactions but experimentally available interactions are generally 2-body. In this context, the efficiency of a reduction gadget is measured by the number of ancilla qubits required as well as the amount of control precision needed to implement the resulting Hamiltonian. First, we optimize methods of applying these gadgets to obtain 2-local Hamiltonians using the least possible number of ancilla qubits. Next, we show a novel reduction gadget which minimizes control precision and a heuristic which uses this gadget to compile 3-local problems with a significant reduction in control precision. Finally, we present numerics which indicate a substantial decrease in the resources required to implement randomly generated, 3-body optimization Hamiltonians when compared to other methods in the literature.

Recommendations

• Minor-embedding in adiabatic quantum computation. I: The parameter setting problem
• Treating the independent set problem by 2D Ising interactions with adiabatic quantum computing
• Optimizing adiabatic quantum program compilation using a graph-theoretic framework
• The quantum adiabatic optimization algorithm and local minima
• Adiabatic quantum optimization with qudits

Cites work

• A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem
• A study of a curious arithmetic function
• Proof verification and the hardness of approximation problems
• Pseudo-Boolean optimization

Cited in

(7)

• Greedy randomized search for scalable compilation of quantum circuits
• A case study in programming a quantum annealer for hard operational planning problems
• A comparison of approaches for finding minimum identifying codes on graphs
• Schedule path optimization for adiabatic quantum computing and optimization
• Adiabatic quantum optimization with qudits
• Ising Machines for Diophantine Problems in Physics
• A review on quantum approximate optimization algorithm and its variants

This page was built for publication: Resource efficient gadgets for compiling adiabatic quantum optimization problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2870496)