Quantum annealing may provide advantages over simulated annealing on solving some problems such as Kth order binary optimization problem. No feasible architecture exists to implement the high-order optimization problem (K > 2) on current quantum annealing hardware. We propose a two-dimensional quantum annealing architecture to solve the 4th order binary optimization problem by encoding four-qubit interactions within the coupled local fields acting on a set of physical qubits. All possible four-body coupling terms for an N-qubit system can be implemented through this architecture and are readily realizable with the existing superconducting circuit technologies. The overhead of the physical qubits is O(N4), which is the same as previously proposed architectures in four-dimensional space. The equivalence between the optimization problem Hamiltonian and the executable Hamiltonian is ensured by a gauge invariant subspace of the experimental system. A scheme to realize local gauge constraint by single ancillary qubit is proposed.
Quantum annealing may provide advantages over simulated annealing on solving some problems such as Kth order binary optimization problem. No feasible architecture exists to implement the high-order optimization problem (K > 2) on current quantum annealing hardware. We propose a two-dimensional quantum annealing architecture to solve the 4th order binary optimization problem by encoding four-qubit interactions within the coupled local fields acting on a set of physical qubits. All possible four-body coupling terms for an N-qubit system can be implemented through this architecture and are readily realizable with the existing superconducting circuit technologies. The overhead of the physical qubits is O(N4), which is the same as previously proposed architectures in four-dimensional space. The equivalence between the optimization problem Hamiltonian and the executable Hamiltonian is ensured by a gauge invariant subspace of the experimental system. A scheme to realize local gauge constraint by single ancillary qubit is proposed.
Critical decision-making issues in science, engineering, and industry are based on combinatorial optimization; however, its application is inherently limited by the NP-hard nature of the problem. A specialized paradigm of analogue quantum computing, quantum annealing (QA), has been proposed to solve these problems by encoding optimization problems into physical energy landscapes and solving them by quantum tunnelling systematically through exploration of solution space. This is a critical review that summarizes the current applications of quantum annealing to combinatorial optimization and includes a theoretical background, hardware designs, algorithm implementation strategies, encoding and embedding schemes, protocols to benchmark quantum annealing, areas of implementation, and links with the quantum algorithms implementation with gate-based hardware and classical solvers. We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers (Chimera, Pegasus, Zephyr topologies), and emergent architectures (Lechner-Hauke-Zoller systems, Rydberg atom platforms), and hybrids of quantum and classical computation. Through our analysis, we find that overhead in embedding and encoding is the largest determinant of the scalability and performance (this is not just the number of qubits). Minor embeddings also usually have a physical qubit count per logical variable of between 5 and 12 qubits, which limits effective problem capacity by 80-92% and, due to chain-breaking errors, compromises the quality of solutions.
Quantum annealers are physical devices that aim at solving NP-complete optimization problems by exploiting quantum mechanics. The basic principle of quantum annealing is to encode the optimization problem in Ising interactions between quantum bits (qubits). A fundamental challenge in building a fully programmable quantum annealer is the competing requirements of full controllable all-to-all connectivity and the quasi-locality of the interactions between physical qubits. We present a scalable architecture with full connectivity, which can be implemented with local interactions only. The input of the optimization problem is encoded in local fields acting on an extended set of physical qubits. The output is-in the spirit of topological quantum memories-redundantly encoded in the physical qubits, resulting in an intrinsic fault tolerance. Our model can be understood as a lattice gauge theory, where long-range interactions are mediated by gauge constraints. The architecture can be realized on various platforms with local controllability, including superconducting qubits, NV-centers, quantum dots, and atomic systems.
Abstract Quantum annealing provides a way of solving optimization problems by encoding them as Ising spin models which are implemented using physical qubits. The solution of the optimization problem then corresponds to the ground state of the system. Quantum tunneling is harnessed to enable the system to move to the ground state in a potentially high non-convex energy landscape. A major difficulty in encoding optimization problems in physical quantum annealing devices is the fact that many real world optimization problems require interactions of higher connectivity, as well as multi-body terms beyond the limitations of the physical hardware. In this work we address the question of how to implement multi-body interactions using hardware which natively only provides two-body interactions. The main result is an efficient circuit design of such multi-body terms using superconducting flux qubits in which effective N -body interactions are implemented using N ancilla qubits and only two inductive couplers. It is then shown how this circuit can be used as the unit cell of a scalable architecture by applying it to a recently proposed embedding technique for constructing an architecture of logical qubits with arbitrary connectivity using physical qubits which have nearest-neighbor four-body interactions. It is further shown that this design is robust to non-linear effects in the coupling loops, as well as mismatches in some of the circuit parameters.
Speedup of high-order unconstrained binary optimization using quantum Z2 lattice gauge theory
An important and difficult problem in optimization is the high-order unconstrained binary optimization, which can represent many optimization problems more efficiently than quadratic unconstrained binary optimization, but how to quickly solve it has remained difficult. Here, we present an approach by mapping the high-order unconstrained binary optimization to quantum Z2 lattice gauge theory and propose the gauged local quantum annealing, which is the local quantum annealing protected by the gauge symmetry. We present the quantum algorithm and its corresponding quantum-inspired classical algorithm for this problem and achieve algorithmic speedup by using gauge symmetry. By running the quantum-inspired classical algorithm, we demonstrate that the gauged local quantum annealing reduces the computational time by one order of magnitude from that of the local quantum annealing. The authors propose a quantum annealing scheme for solving a higher-order unconstrained binary optimization problem by mapping it to a quantum Z2 lattice gauge theory on a dual graph. This scheme is shown to achieve a speed-up of at least one order of magnitude in finding the ground state compared to other methods.
Quantum annealing is a method based on simulated annealing where temperature variations are replaced by quantum fluctuations that cause qubit state transitions. ISING problems and Quadratic Unconstrained Binary Optimization problems (QUBO) can be tackled by quantum annealing-based machines. We can link the interconnected qubits of the machine and the binaries of our model: qubits are binary variables and each pair of them linked by a coupler has a strong impact on the equality or the non-equality of the two binaries of the associated pair. Quantum annealing is based on the fact that any system tends to seek its minimum energy state. Starting from qubits in a state of superposition where all the solutions to the problem are fairly represented, the machine will apply a magnetic field by targeting the qubits and couplers in such a way as to make their value energetically favorable in the direction of optimization (minimization). For the coupled qubits, it is the quadratic products of the binary variables that are considered here and the physical system will make it energetically favorable for them to take (or not) the same values. To work on these machines based on quantum annealing in order to solve optimization problems with constraints, the latter must be relaxed while penalizing the Objective function. After presenting the case of the Max-Cut problem, we will look at such constrained problems.
Quantum annealing (QA) has the potential to significantly improve solution quality and reduce time complexity in solving combinatorial optimization problems compared to classical optimization methods. However, due to the limited number of qubits and their connectivity, the QA hardware did not show such an advantage over classical methods in past benchmarking studies. Recent advancements in QA with more than 5000 qubits, enhanced qubit connectivity, and the hybrid architecture promise to realize the quantum advantage. Here, we use a quantum annealer with state-of-the-art techniques and benchmark its performance against classical solvers. To compare their performance, we solve over 50 optimization problem instances represented by large and dense Hamiltonian matrices using quantum and classical solvers. The results demonstrate that a state-of-the-art quantum solver has higher accuracy (~0.013%) and a significantly faster problem-solving time (~6561×) than the best classical solver. Our results highlight the advantages of leveraging QA over classical counterparts, particularly in hybrid configurations, for achieving high accuracy and substantially reduced problem solving time in large-scale real-world optimization problems.