Compensating connectivity restrictions in quantum annealers via splitting and linearization techniques

• URL: http://arxiv.org/abs/2507.12536v1
• Date: Wed, 16 Jul 2025 18:00:09 GMT
• Title: Compensating connectivity restrictions in quantum annealers via splitting and linearization techniques
• Authors: Marcel Seelbach Benkner, Zorah Lähner, Vladislav Golyanik, Martin Kliesch, Michael Moeller,
• Abstract summary: We present an iterative algorithm that does not need additional qubits but instead efficiently uses the available connectivity.<n>We present a weak monotonicity proof and benchmark our algorithm against the default minor-embedding algorithm on the D-Wave quantum annealer.<n>We also confirm the practicality of our method with experiments on the D-Wave Advantage quantum annealer.
• Score: 26.214048364226365
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Current quantum annealing experiments often suffer from restrictions in connectivity in the sense that only certain qubits can be coupled to each other. The most common strategy to overcome connectivity restrictions so far is by combining multiple physical qubits into a logical qubit with higher connectivity, which is achieved by adding terms to the Hamiltonian. Practically, this strategy is implemented by finding a so-called minor embedding, which is in itself an NP-hard problem. In this work, we present an iterative algorithm that does not need additional qubits but instead efficiently uses the available connectivity for different parts of the problem graph in every step. We present a weak monotonicity proof and benchmark our algorithm against the default minor-embedding algorithm on the D-Wave quantum annealer and multiple simple local search variants. While most of the experiments to compare the different iterative methods are performed with simulated annealing solvers, we also confirm the practicality of our method with experiments on the D-Wave Advantage quantum annealer.

Related papers

• Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
  Branch-and-bound algorithms effectively solve convex optimization problems, relying on the relaxation the objective function to obtain tight lower bounds.<n>We propose a branch-and-bound digitized counterdiabatic quantum optimization (BB-DCQO) algorithm that addresses the relaxation difficulties.
  arXiv  Detail & Related papers  (2025-04-21T18:19:19Z)
• Ab Initio Transcorrelated Method enabling accurate Quantum Chemistry on near-term Quantum Hardware [0.0]
  Current hardware limitations hamper the straightforward implementation of most quantum algorithms. In quantum chemistry, the limited number of available qubits and gate operations is particularly restrictive. We show that the exact transcorrelated approach not only allows for more shallow circuits but also improves the convergence towards the so-called basis set limit.
  arXiv  Detail & Related papers  (2023-03-03T15:24:22Z)
• 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)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Variational determination of arbitrarily many eigenpairs in one quantum circuit [8.118991737495524]
  A variational quantum eigensolver (VQE) was first introduced for computing ground states. We propose a new algorithm to determine many low energy eigenstates simultaneously. Our algorithm reduces significantly the complexity of circuits and the readout errors.
  arXiv  Detail & Related papers  (2022-06-22T13:01:37Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  We develop new and efficient quantum algorithms for fidelity estimation with provable performance guarantees. Our algorithms use advanced quantum linear algebra techniques, such as the quantum singular value transformation. We prove that fidelity estimation to any non-trivial constant additive accuracy is hard in general.
  arXiv  Detail & Related papers  (2022-03-30T02:02:16Z)
• Interactive Protocols for Classically-Verifiable Quantum Advantage [46.093185827838035]
  "Interactions" between a prover and a verifier can bridge the gap between verifiability and implementation. We demonstrate the first implementation of an interactive quantum advantage protocol, using an ion trap quantum computer.
  arXiv  Detail & Related papers  (2021-12-09T19:00:00Z)
• Quantum amplitude damping for solving homogeneous linear differential equations: A noninterferometric algorithm [0.0]
  This work proposes a novel approach by using the Quantum Amplitude Damping operation as a resource, in order to construct an efficient quantum algorithm for solving homogeneous LDEs. We show that such an open quantum system-inspired circuitry allows for constructing the real exponential terms in the solution in a non-interferometric.
  arXiv  Detail & Related papers  (2021-11-10T11:25:32Z)
• Quantum Causal Unravelling [44.356294905844834]
  We develop the first efficient method for unravelling the causal structure of the interactions in a multipartite quantum process. Our algorithms can be used to identify processes that can be characterized efficiently with the technique of quantum process tomography.
  arXiv  Detail & Related papers  (2021-09-27T16:28:06Z)
• Theoretical survey of unconventional quantum annealing methods applied to adifficult trial problem [2.2209333405427585]
  We consider a range of unconventional modifications to Quantum Annealing (QA) In this problem, inspired by "transverse field chaos" in larger systems, classical and quantum methods are steered toward a false local minimum. We numerically study this problem by using a variety of new methods from the literature.
  arXiv  Detail & Related papers  (2020-11-12T05:54:57Z)
• Advanced unembedding techniques for quantum annealers [0.0]
  We present tailored unembedding techniques for four important NP-hard problems. Our techniques are simple and yet make use of structural properties of the problem being solved.
  arXiv  Detail & Related papers  (2020-09-10T17:49:43Z)

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.