arXiv:2111.03167 · IEEE Transactions on Quantum Engineering
Approximate Solutions of Combinatorial Problems via Quantum Relaxations
Bryce Fuller, Charles F. Hadfield, Jennifer R. Glick, Takashi Imamichi, Toshinari Itoko, Richard J. Thompson, Yang Jiao, Marna M. Kagele, Adriana W. Blom, Rudy Raymond, Antonio Mezzacapo
Combinatorial problems are formulated to find optimal designs within a fixed set of constraints and are commonly found across diverse engineering and scientific domains. Understanding how to best use quantum computers for combinatorial optimization remains an ongoing area of study. Here, we propose new methods for producing approximate solutions to quadratic unconstrained binary optimization problems, which are based on relaxations to local quantum Hamiltonians. We look specifically at approximating solutions for the maximum cut problem and its weighted version. These relaxations are defined through commutative maps, which in turn are constructed borrowing ideas from quantum random access codes. We establish relations between the spectra of the relaxed Hamiltonians and optimal cuts of the original problems, via two quantum rounding protocols. The first one is based on projections to random magic states. It produces average cuts that approximate the optimal one by a factor of least 0.555 or 0.625, depending on the relaxation chosen, if given access to a quantum state with energy between the optimal classical cut and the maximal relaxed energy. The second rounding protocol is deterministic and is based on the estimation of Pauli observables. The proposed quantum relaxations inherit memory compression from quantum random access codes, which allowed us to test the performances of the methods presented for 3-regular random graphs and a design problem motivated by industry for sizes up to 40 nodes, on superconducting quantum processors.
Combinatorial problems are formulated to find optimal designs within a fixed set of constraints and are commonly found across diverse engineering and scientific domains. Understanding how to best use quantum computers for combinatorial optimization remains an ongoing area of study. Here, we propose new methods for producing approximate solutions to quadratic unconstrained binary optimization problems, which are based on relaxations to local quantum Hamiltonians. We look specifically at approximating solutions for the maximum cut problem and its weighted version. These relaxations are defined through commutative maps, which in turn are constructed borrowing ideas from quantum random access codes. We establish relations between the spectra of the relaxed Hamiltonians and optimal cuts of the original problems, via two quantum rounding protocols. The first one is based on projections to random magic states. It produces average cuts that approximate the optimal one by a factor of least 0.555 or 0.625, depending on the relaxation chosen, if given access to a quantum state with energy between the optimal classical cut and the maximal relaxed energy. The second rounding protocol is deterministic and is based on the estimation of Pauli observables. The proposed quantum relaxations inherit memory compression from quantum random access codes, which allowed us to test the performances of the methods presented for 3-regular random graphs and a design problem motivated by industry for sizes up to 40 nodes, on superconducting quantum processors.
To date, research in quantum computation promises potential for outperforming classical heuristics in combinatorial optimization. However, when aiming at provable optimality, one has to rely on classical exact methods like integer programming. State-of-the-art integer programming algorithms can compute strong relaxation bounds even for hard instances, but may have to enumerate a large number of subproblems for determining an optimum solution. If the potential of quantum computing is realized, it can be expected that in particular finding high-quality solutions for hard problems can be done fast. Still, near-future quantum hardware considerably limits the size of treatable problems. In this work, we go one step into integrating the potentials of quantum and classical techniques for combinatorial optimization. We propose a hybrid heuristic for the weighted maximum-cut problem and for quadratic unconstrained binary optimization. The heuristic employs a linear programming relaxation, rendering it well-suited for integration into exact branch-and-cut algorithms. For large instances, we reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. Moreover, we improve the applicability of depth-1 QAOA, a parameterized quantum algorithm, by deriving a parameter estimate for arbitrary instances. We present numerous computational results from real quantum hardware.
There is an increasing interest in quantum algorithms for problems of integer programming and combinatorial optimization. Classical solvers for such problems employ relaxations, which replace binary variables with continuous ones, for instance in the form of higher-dimensional matrix-valued problems (semidefinite programming). Under the Unique Games Conjecture, these relaxations often provide the best performance ratios available classically in polynomial time. Here, we discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of a combinatorial optimization problem and how to analyze properties of the associated quantum algorithms. In particular, this allows the quantum algorithm to inherit the performance guarantees of the classical algorithm. We illustrate this in the context of portfolio optimization, where our results indicate that warm-starting the Quantum Approximate Optimization Algorithm (QAOA) is particularly beneficial at low depth. Likewise, Recursive QAOA for MAXCUT problems shows a systematic increase in the size of the obtained cut for fully connected graphs with random weights, when Goemans-Williamson randomized rounding is utilized in a warm start. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.
Mathematical optimization is a field where the potential of quantum algorithms is actively being explored. The Quantum Approximate Optimization Algorithm (QAOA) serves as a notable quantum-classical hybrid approach aimed at solving combinatorial optimization challenges on Noisy Intermediate-Scale Quantum (NISQ) devices. In QAOA, classical variables find representation in qubits via a one-to-one mapping. A newer entrant, Quantum Random Access Optimization (QRAO), encodes problems using fewer qubits than QAOA by leveraging the Quantum Random Access Code (QRAC) to structure a problem into its Hamiltonian form. Notably, the QRAO Hamiltonian, dubbed the Quantum Relaxation Hamiltonian, boasts of a ground state energy inferior to that of the QAOA Hamiltonian. Nonetheless, the QRAO's ground state exhibits entanglement, making it starkly different from QAOA's ground state. As a workaround, preceding studies formulated solutions to the original problem using a rounding algorithm. Our research introduces the Quantum Relaxation based Branch-and-Bound (QR-BnB) algorithm. This novel method marries Quantum Relaxation and the classical exact solution strategy, Branch-and-Bound. Within the QR-BnB framework, a classical device shoulders the responsibility of the branch-and-bound operation, while its quantum counterpart dedicates itself to determining each ground state energy for the subproblem's Quantum Relaxation Hamiltonian. This fusion eliminates the prerequisite of the rounding algorithm by crafting the optimal solution through branching operations. Preliminary simulations of the QR-BnB approach attest to its capability in accurately solving a MaxCut problem. As future work, exploring its applicability on diverse combinatorial optimization problems holds promise. Our algorithm signals a step forward in harnessing NISQ devices for tackling expansive optimization challenges.
Quantum optimization methods use a continuous degree-of-freedom of quantum states to heuristically solve combinatorial problems, such as the MAX-CUT problem, which can be attributed to various NP-hard combinatorial problems. This paper shows that some existing quantum optimization methods can be unified into a solver to find the binary solution which is most likely measured from the optimal quantum state. Combining this finding with the concept of quantum random access codes (QRACs) for encoding bits into quantum states on fewer qubits, we propose an efficient recursive quantum relaxation method called recursive quantum random access optimization (RQRAO) for MAX-CUT. Experiments on standard benchmark graphs with several hundred nodes in the MAX-CUT problem, conducted in a fully classical manner using a tensor network technique, show that RQRAO not only outperforms the Goemans-Williamson and recursive QAOA methods, but also is comparable to state-of-the-art classical solvers. The code is available at https://github.com/ToyotaCRDL/rqrao.
We introduce a quantum algorithm that produces approximate solutions for combinatorial optimization problems. The algorithm depends on a positive integer p and the quality of the approximation improves as p is increased. The quantum circuit that implements the algorithm consists of unitary gates whose locality is at most the locality of the objective function whose optimum is sought. The depth of the circuit grows linearly with p times (at worst) the number of constraints. If p is fixed, that is, independent of the input size, the algorithm makes use of efficient classical preprocessing. If p grows with the input size a different strategy is proposed. We study the algorithm as applied to MaxCut on regular graphs and analyze its performance on 2-regular and 3-regular graphs for fixed p. For p = 1, on 3-regular graphs the quantum algorithm always finds a cut that is at least 0.6924 times the size of the optimal cut.
The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm that finds approximate solutions to problems in combinatorial optimization, especially those that can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem. In prior work, researchers have considered various ways of "warm-starting" QAOA by constructing an initial quantum state using classically-obtained solutions or information; these warm-starts typically cause QAOA to yield better approximation ratios at much lower circuit depths. For the Max-Cut problem, one warm-start approaches constructs the initial state using the high-dimensional vectors that are output from an SDP relaxation of the corresponding Max-Cut problem. This work leverages these semidefinite warmstarts for a broader class of problem instances by using a standard reduction that transforms any QUBO instance into a Max-Cut instance. We empirically compare this approach to a "QUBO-relaxation" approach that relaxes the QUBO directly. Our results consider a variety of QUBO instances ranging from randomly generated QUBOs to QUBOs corresponding to specific problems such as the traveling salesman problem, maximum independent set, and portfolio optimization. We find that the best choice of warmstart approach is strongly dependent on the problem type.