Recently, several powerful machines dedicated to solving combinatorial optimization problems through the Ising-model formulation have appeared. The trigger for the paradigm shift to a specialized machine for solving optimization problems was the D-Wave machine, which implements quantum annealing. Quantum annealing employs quantum fluctuations to find an optimal solution to an optimization problem with discrete variables. In particular, we input the optimization problem in the form of the Ising Hamiltonian, which is a specialized form of the quadratic unconstrained binary optimization problem. However, when we employ quantum annealing for a practical optimization problem, there are several issues. One typical issue is absence of the detailed form of the cost function, which characterizes the optimization problem. To input problems into specialized machines for solving an optimization problem, it is necessary to determine the unknown parameters within the Ising model. We propose a method to estimate the unknown parameters in the Ising Hamiltonian using compressed sensing. Furthermore, we analyze the theoretical limitations of our proposed method by employing the replica method, which is a sophisticated tool in statistical mechanics.
Recently, several powerful machines dedicated to solving combinatorial optimization problems through the Ising-model formulation have appeared. The trigger for the paradigm shift to a specialized machine for solving optimization problems was the D-Wave machine, which implements quantum annealing. Quantum annealing employs quantum fluctuations to find an optimal solution to an optimization problem with discrete variables. In particular, we input the optimization problem in the form of the Ising Hamiltonian, which is a specialized form of the quadratic unconstrained binary optimization problem. However, when we employ quantum annealing for a practical optimization problem, there are several issues. One typical issue is absence of the detailed form of the cost function, which characterizes the optimization problem. To input problems into specialized machines for solving an optimization problem, it is necessary to determine the unknown parameters within the Ising model. We propose a method to estimate the unknown parameters in the Ising Hamiltonian using compressed sensing. Furthermore, we analyze the theoretical limitations of our proposed method by employing the replica method, which is a sophisticated tool in statistical mechanics.
The quantum annealing devices, which encode the solution to a computational problem in the ground state of a quantum Hamiltonian, are implemented in D-Wave systems with more than 2,000 qubits. However, quantum annealing can solve only a classical combinatorial optimization problem such as an Ising model, or equivalently, a quadratic unconstrained binary optimization (QUBO) problem. In this paper, we formulate the QUBO model to solve elliptic problems with Dirichlet and Neumann boundary conditions using the finite element method. In this formulation, we develop the objective function of quadratic binary variables represented by qubits and the system finds the binary string combination minimizing the objective function globally. Based on the QUBO formulation, we introduce an iterative algorithm to solve the elliptic problems. We discuss the validation of the modeling on the D-Wave quantum annealing system.
Quantum annealing is getting increasing attention in combinatorial optimization. The quantum processing unit by D-Wave is constructed to approximately solve Ising models on so-called Chimera graphs. Ising models are equivalent to quadratic unconstrained binary optimization (QUBO) problems and maximum cut problems on the associated graphs. We have tailored branch-and-cut as well as semidefinite programming algorithms for solving Ising models for Chimera graphs to provable optimality and use the strength of these approaches for comparing our solution values to those obtained on the current quantum annealing machine, D-Wave 2000Q. This allows for the assessment of the quality of solutions produced by the D-Wave hardware. In addition, we also evaluate the performance of a heuristic by Selby. It has been a matter of discussion in the literature how well the D-Wave hardware performs at its native task, and our experiments shed some more light on this issue. In particular, we examine how reliably the D-Wave computer can deliver true optimum solutions and present some surprising results.
We leverage the idea of a statistical ensemble to improve the quality of quantum annealing based binary compressive sensing. Since executing quantum machine instructions on a quantum annealer can result in an excited state, rather than the ground state of the given Hamiltonian, we use different penalty parameters to generate multiple distinct quadratic unconstrained binary optimization (QUBO) functions whose ground state(s) represent a potential solution of the original problem. We then employ the attained samples from minimizing all corresponding (different) QUBOs to estimate the solution of the problem of binary compressive sensing. Our experiments, on a D-Wave 2000Q quantum processor, demonstrated that the proposed ensemble scheme is notably less sensitive to the calibration of the penalty parameter that controls the trade-off between the feasibility and sparsity of recoveries.
We leverage the idea of a statistical ensemble to improve the quality of quantum annealing based binary compressive sensing. Since executing quantum machine instructions on a quantum annealer can result in an excited state, rather than the ground state of the given Hamiltonian, we use different penalty parameters to generate multiple distinct quadratic unconstrained binary optimization (QUBO) functions whose ground state(s) represent a potential solution of the original problem. We then employ the attained samples from minimizing all corresponding (different) QUBOs to estimate the solution of the problem of binary compressive sensing. Our experiments, on a D-Wave 2000Q quantum processor, demonstrated that the proposed ensemble scheme is notably less sensitive to the calibration of the penalty parameter that controls the trade-off between the feasibility and sparsity of recoveries.
Quantum computers use quantum resources to carry out computational tasks and may outperform classical computers in solving certain computational problems. Special-purpose quantum computers such as quantum annealers employ quantum adiabatic theorem to solve combinatorial optimization problems. In this paper, we compare classical annealings such as simulated annealing and quantum annealings that are done by the D-Wave machines both theoretically and numerically. We show that if the classical and quantum annealing are characterized by equivalent Ising models, then solving an optimization problem, i.e., finding the minimal energy of each Ising model, by the two annealing procedures, are mathematically identical. For quantum annealing, we also derive the probability lower-bound on successfully solving an optimization problem by measuring the system at the end of the annealing procedure. Moreover, we present the Markov chain Monte Carlo (MCMC) method to realize quantum annealing by classical computers and investigate its statistical properties. In the numerical section, we discuss the discrepancies between the MCMC based annealing approaches and the quantum annealing approach in solving optimization problems.
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.