Quantum optimization using a 127-qubit gate-model IBM quantum computer can outperform quantum annealers for nontrivial binary optimization problems

• URL: http://arxiv.org/abs/2406.01743v4
• Date: Mon, 28 Oct 2024 19:05:24 GMT
• Title: Quantum optimization using a 127-qubit gate-model IBM quantum computer can outperform quantum annealers for nontrivial binary optimization problems
• Authors: Natasha Sachdeva, Gavin S. Hartnett, Smarak Maity, Samuel Marsh, Yulun Wang, Adam Winick, Ryan Dougherty, Daniel Canuto, You Quan Chong, Michael Hush, Pranav S. Mundada, Christopher D. B. Bentley, Michael J. Biercuk, Yuval Baum,
• Abstract summary: We introduce a comprehensive quantum solver for binary optimization problems on gate-model quantum computers. It consistently delivers correct solutions for problems with up to 127 qubits. We benchmark this solver on IBM quantum computers for several classically nontrivial unconstrained binary optimization problems.
• Score: 0.0
• License:
• Abstract: We introduce a comprehensive quantum solver for binary combinatorial optimization problems on gate-model quantum computers that outperforms any published alternative and consistently delivers correct solutions for problems with up to 127 qubits. We provide an overview of the internal workflow, describing the integration of a customized ansatz and variational parameter update strategy, efficient error suppression in hardware execution, and QPU-overhead-free post-processing to correct for bit-flip errors. We benchmark this solver on IBM quantum computers for several classically nontrivial unconstrained binary optimization problems -- the entire optimization is conducted on hardware with no use of classical simulation or prior knowledge of the solution. First, we demonstrate the ability to correctly solve Max-Cut instances for random regular graphs with a variety of densities using up to 120 qubits, where the graph topologies are not matched to device connectivity. Next, we apply the solver to higher-order binary optimization and successfully search for the ground state energy of a 127-qubit spin-glass model with linear, quadratic, and cubic interaction terms. Use of this new quantum solver increases the likelihood of finding the minimum energy by up to $\sim1,500\times$ relative to published results using a DWave annealer, and it can find the correct solution when the annealer fails. Furthermore, for both problem types, the Q-CTRL solver outperforms a heuristic local solver used to indicate the relative difficulty of the problems pursued. Overall, these results represent the largest quantum optimizations successfully solved on hardware to date, and demonstrate the first time a gate-model quantum computer has been able to outperform an annealer for a class of binary optimization problems.

Related papers

• Quantum Optimization for the Maximum Cut Problem on a Superconducting Quantum Computer [0.3518016233072556]
  We investigate the performance of a hybrid quantum-classical algorithm inspired by semidefinite approaches for solving the maximum cut problem. We attain an average performance of 99% over a random ensemble of thousands of problem instances. A runtime analysis shows that the quantum solver on large-scale problems is competitive against Gurobi but short of others.
  arXiv  Detail & Related papers  (2024-04-26T17:59:22Z)
• Performant near-term quantum combinatorial optimization [1.1999555634662633]
  We present a variational quantum algorithm for solving optimization problems with linear-depth circuits. Our algorithm uses an ansatz composed of Hamiltonian generators designed to control each term in the target quantum function. We conclude our performant and resource-minimal approach is a promising candidate for potential quantum computational advantages.
  arXiv  Detail & Related papers  (2024-04-24T18:49:07Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Optimizing quantum gates towards the scale of logical qubits [78.55133994211627]
  A foundational assumption of quantum gates theory is that quantum gates can be scaled to large processors without exceeding the error-threshold for fault tolerance. Here we report on a strategy that can overcome such problems. We demonstrate it by choreographing the frequency trajectories of 68 frequency-tunablebits to execute single qubit while superconducting errors.
  arXiv  Detail & Related papers  (2023-08-04T13:39:46Z)
• NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization [0.0]
  We present an approximate gradient-based quantum algorithm for hardware-efficient circuits with amplitude encoding. We show how simple linear constraints can be directly incorporated into the circuit without additional modification of the objective function with penalty terms.
  arXiv  Detail & Related papers  (2023-05-23T16:17:57Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Efficient Use of Quantum Linear System Algorithms in Interior Point Methods for Linear Optimization [0.0]
  We develop an Inexact Infeasible Quantum Interior Point Method to solve linear optimization problems. We also discuss how can we get an exact solution by Iterative Refinement without excessive time of quantum solvers.
  arXiv  Detail & Related papers  (2022-05-02T21:30:56Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms [0.0]
  We apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach.
  arXiv  Detail & Related papers  (2021-01-19T19:00:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.