Quantum Combinatorial Relaxation

"Approximate Solutions of Combinatorial Problems via Quantum Relaxations"

Published by Bryce Fuller et al. (IBM & Boeing), 5th November 2021

Quantum Combinatorial Relaxation

One of the main research interests in quantum computing is solving NP hard combinatorial problems. So far, methods like quantum adiabatic eigenstate evolution and the quantum approximate optimization algorithm (QAOA) have been proposed in order to harness quantum advantage. One limitation of the QAOA framework is that the cost function to be optimized on a quantum computer has a classical maximal eigenstate. This is in contrast to quantum many-body Hamiltonians or quantum chemistry, whose extremal eigenstates often are very entangled in the default or ‘natural’ basis.

The authors in this paper present algorithms which produce approximate solutions of combinatorial problems, searching for extremal eigenstates of local quantum Hamiltonians. These local quantum Hamiltonians are relaxations of the original combinatorial problems which means that for each element in the image of a combinatorial cost function, a quantum state with the same Hamiltonian expectation value can be constructed. A candidate ground state can then be obtained with variational eigensolvers, quantum phase estimation, approximation algorithms for quantum Hamiltonians, or quantum imaginary time evolution. This work uses the variational approach on prototypical NP-hard problems like the maximum cut (MaxCut) problem and weighted MaxCut.

Once a quantum relaxed Hamiltonian is prepared, its relaxed energy is rounded to an admissible value to the highest-energy state associated with the Hamiltonian. This highest-energy state is mapped to the ground state. For almost all graphs, its energy is strictly greater than the energy of the embedding of the optimal configuration of binary variables. To overcome this, candidate configuration was done using two rounding methods, magic state rounding and Pauli rounding. Magic state rounding takes a single-qubit density ρ and uniformly at random selects a measurement basis in which to measure a quantum state, while Pauli rounding is based on the direct estimation of the Pauli operators associated to each vertex.

The work also presents numerical simulations and hardware experiments benchmarking the relaxation methods proposed. To test the two rounding methods, numerical simulations were proposed on random MaxCut instances on 3-regular graphs of increasing size where Pauli rounding obtains better approximation ratios on average. The numerical experiments are conducted using a COBYLA optimizer, while the experiments on the superconducting processor were performed with an adaptive SPSA optimizer using 8192 measurements for each independent basis to estimate the relaxed Hamiltonian. In the case of the superconducting quantum processor the approximation ratio of 0.91 is obtained for 40-node graphs on unweighted 3-regular MaxCut and 0.96 on weighted planar MaxCut. The results establish connections between the energy of a relaxed quantum state and the average value of its rounded MaxCut approximation. Also, rounding from higher relaxed energy states leads to better combinatorial solutions.

A potential direction will be to explore classes of graphs that show large separations between the highest energy states of the relaxed spectrum and the optimal classical cut values. Also, for preparing ground state approximations for the relaxed problems, approximation algorithms for many-body quantum states can be used. Furthermore, other than embeddings based on 1-qubit quantum random access codes, other more sophisticated embeddings can be tested to get improved relaxations. Future scope can be in investigating rounding protocols for relaxed states which could take non-local qubit correlations into account.