Scaling overhead of embedding optimization problems in quantum annealing

• URL: http://arxiv.org/abs/2103.15991v2
• Date: Wed, 3 Nov 2021 17:13:45 GMT
• Title: Scaling overhead of embedding optimization problems in quantum annealing
• Abstract summary: Embedding fully-connected graphs incurs a quadratic space overhead and thus a significant overhead in the time to solution. Our results demonstrate that standard analog quantum hardware is at a disadvantage in comparison to classical digital annealers.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In order to treat all-to-all connected quadratic binary optimization problems (QUBO) with hardware quantum annealers, an embedding of the original problem is required due to the sparsity of the hardware's topology. Embedding fully-connected graphs - typically found in industrial applications - incurs a quadratic space overhead and thus a significant overhead in the time to solution. Here we investigate this embedding penalty of established planar embedding schemes such as minor embedding on a square lattice, minor embedding on a Chimera graph, and the Lechner-Hauke-Zoller scheme using simulated quantum annealing on classical hardware. Large-scale quantum Monte Carlo simulation suggest a polynomial time-to-solution overhead. Our results demonstrate that standard analog quantum annealing hardware is at a disadvantage in comparison to classical digital annealers, as well as gate-model quantum annealers and could also serve as benchmark for improvements of the standard quantum annealing protocol.

Related papers

• Digital Quantum Simulation of the Holstein-Primakoff Transformation on Noisy Qubits [40.8066152850216]
  We study the digital quantum simulation of bosonic modes on a cloud-based superconducting quantum processor.<n>We examine the interplay between algorithmic and hardware-induced errors to identify optimal simulation parameters.
  arXiv  Detail & Related papers  (2026-02-19T20:14:04Z)
• Quantum-accelerated conjugate gradient methods via spectral initialization [0.0]
  A fault-tolerant quantum algorithm is used exclusively to construct a spectrally informed initial guess for a classical conjugate gradient (CG) solver.<n>A central feature of QACG is a controllable decomposition of the condition number between the quantum and the classical solver.<n>Results illustrate a concrete pathway toward the scientific and industrial use of early-stage fault-tolerant quantum computing.
  arXiv  Detail & Related papers  (2026-02-10T11:51:42Z)
• Quantum Annealing for Combinatorial Optimization: Foundations, Architectures, Benchmarks, and Emerging Directions [0.0]
  Critical decision-making issues in science, engineering, and industry are based on optimization.<n>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.<n>We find that overhead in embedding and encoding is the largest of the scalability and performance.
  arXiv  Detail & Related papers  (2026-02-03T04:51:26Z)
• Performance enhancing of hybrid quantum-classical Benders approach for MILP optimization [0.0]
  We present a hardware-agnostic Benders' decomposition algorithm and a series of enhancements with the goal of taking the most advantage of quantum computing.<n>The proposed algorithm is benchmarked against classical approaches using a D-Wave quantum annealer for a scalable family of transmission network expansion planning problems.
  arXiv  Detail & Related papers  (2026-01-20T14:47:50Z)
• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  Multiple-input multiple-output (MIMO) is critical for 6G communication, offering improved spectral efficiency and reliability.<n>This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA) and alternating optimization to address the problem of b-bit quantized phase shifters both at the transmitter and the receiver.<n>We demonstrate that the structure of this quantized beamforming problem aligns naturally with hybrid-classical methods like QAOA, as the phase shifts used in beamforming can be directly mapped to rotation gates in a quantum circuit.
  arXiv  Detail & Related papers  (2025-10-07T17:53:02Z)
• Minimal Quantum Reservoirs with Hamiltonian Encoding [72.27323884094953]
  We investigate a minimal architecture for quantum reservoir computing based on Hamiltonian encoding.<n>This approach circumvents many of the experimental overheads typically associated with quantum machine learning.
  arXiv  Detail & Related papers  (2025-05-28T16:50:05Z)
• Optimized Quantum Embedding: A Universal Minor-Embedding Framework for Large Complete Bipartite Graph [0.5242869847419834]
  Minor embedding is essential for mapping largescale problems onto quantum annealers, particularly in quantum machine learning and optimization. This work presents an optimized, universal minor-embedding framework that efficiently complete bipartite graphs onto the hardware topology of quantum annealers.
  arXiv  Detail & Related papers  (2025-04-29T18:44:12Z)
• QAMA: Scalable Quantum Annealing Multi-Head Attention Operator for Deep Learning [48.12231190677108]
  Quantum Annealing Multi-Head Attention (QAMA) is proposed, a novel drop-in operator that reformulates attention as an energy-based Hamiltonian optimization problem.<n>In this framework, token interactions are encoded into binary quadratic terms, and quantum annealing is employed to search for low-energy configurations.<n> Empirically, evaluation on both natural language and vision benchmarks shows that, across tasks, accuracy deviates by at most 2.7 points from standard multi-head attention.
  arXiv  Detail & Related papers  (2025-04-15T11:29:09Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Parallel Ising Annealer via Gradient-based Hamiltonian Monte Carlo [11.307633403964031]
  Ising annealer is a quantum-inspired computing architecture for optimization problems. Main innovation is the fusion of an approximate gradient-based approach into the Ising annealer. Prototype annealer solves Ising problems of both integer and fraction coefficients with up 200 spins on a single low-cost FPGA board.
  arXiv  Detail & Related papers  (2024-07-14T13:51:35Z)
• Parallel Quantum Computing Simulations via Quantum Accelerator Platform Virtualization [44.99833362998488]
  We present a model for parallelizing simulation of quantum circuit executions. The model can take advantage of its backend-agnostic features, enabling parallel quantum circuit execution over any target backend.
  arXiv  Detail & Related papers  (2024-06-05T17:16:07Z)
• Sparse Quantum State Preparation for Strongly Correlated Systems [0.0]
  In principle, the encoding of the exponentially scaling many-electron wave function onto a linearly scaling qubit register offers a promising solution to overcome the limitations of traditional quantum chemistry methods. An essential requirement for ground state quantum algorithms to be practical is the initialisation of the qubits to a high-quality approximation of the sought-after ground state. Quantum State Preparation (QSP) allows the preparation of approximate eigenstates obtained from classical calculations, but it is frequently treated as an oracle in quantum information.
  arXiv  Detail & Related papers  (2023-11-06T18:53:50Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays [39.76254807200083]
  We experimentally investigate quantum algorithms for solving the Maximum Independent Set problem. We find the problem hardness is controlled by the solution degeneracy and number of local minima. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions.
  arXiv  Detail & Related papers  (2022-02-18T19:00:01Z)
• Simulating the Mott transition on a noisy digital quantum computer via Cartan-based fast-forwarding circuits [62.73367618671969]
  Dynamical mean-field theory (DMFT) maps the local Green's function of the Hubbard model to that of the Anderson impurity model. Quantum and hybrid quantum-classical algorithms have been proposed to efficiently solve impurity models. This work presents the first computation of the Mott phase transition using noisy digital quantum hardware.
  arXiv  Detail & Related papers  (2021-12-10T17:32:15Z)
• Quantum-classical eigensolver using multiscale entanglement renormalization [0.0]
  We propose a variational quantum eigensolver (VQE) for the simulation of strongly-correlated quantum matter. It can have substantially lower costs than corresponding classical algorithms. It is particularly attractive for ion-trap devices with ion-shuttling capabilities.
  arXiv  Detail & Related papers  (2021-08-30T17:46:35Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Error mitigation and quantum-assisted simulation in the error corrected regime [77.34726150561087]
  A standard approach to quantum computing is based on the idea of promoting a classically simulable and fault-tolerant set of operations. We show how the addition of noisy magic resources allows one to boost classical quasiprobability simulations of a quantum circuit.
  arXiv  Detail & Related papers  (2021-03-12T20:58:41Z)
• Integer Programming from Quantum Annealing and Open Quantum Systems [0.8049701904919515]
  We develop an algorithm that solves integer linear programming problems, a classically NP-hard problem, on a quantum annealer. We find that the algorithm outperforms random guessing but is limited to small problems.
  arXiv  Detail & Related papers  (2020-09-24T22:18:01Z)
• Electronic structure with direct diagonalization on a D-Wave quantum annealer [62.997667081978825]
  This work implements the general Quantum Annealer Eigensolver (QAE) algorithm to solve the molecular electronic Hamiltonian eigenvalue-eigenvector problem on a D-Wave 2000Q quantum annealer. We demonstrate the use of D-Wave hardware for obtaining ground and electronically excited states across a variety of small molecular systems.
  arXiv  Detail & Related papers  (2020-09-02T22:46:47Z)
• Model Predictive Control for Finite Input Systems using the D-Wave Quantum Annealer [4.83782736808514]
  The D-Wave quantum annealer has emerged as a novel computational architecture that is attracting significant interest. We present a model predictive control (MPC) algorithm using a quantum annealer. Two practical applications, namely stabilization of a spring-mass-damper system and dynamic audio quantization, are demonstrated.
  arXiv  Detail & Related papers  (2020-01-06T05:11:52Z)

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.