Exponential speed-up of quantum annealing via n-local catalysts

• URL: http://arxiv.org/abs/2409.13029v1
• Date: Thu, 19 Sep 2024 18:01:53 GMT
• Title: Exponential speed-up of quantum annealing via n-local catalysts
• Authors: Roopayan Ghosh, Luca A. Nutricati, Natasha Feinstein, P. A. Warburton, Sougato Bose,
• Abstract summary: We show that $n-$local catalysts can re-open the gap or prevent it from closing during the anneal process. Our analysis suggests that non-local quantum fluctuations entangling multiple qubits are key to achieving the desired quantum advantage.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The quantum speedup in solving optimization problems via adiabatic quantum annealing is often hindered by the closing of the energy gap during the anneal, especially when this gap scales exponentially with system size. In this work, we address this by demonstrating that for the Maximum Weighted Independent Set (MWIS) problem, an informed choice of $n-$local catalysts (operators involving $n$ qubits) can re-open the gap or prevent it from closing during the anneal process. By analyzing first-order phase transitions in toy instances of the MWIS problem, we identify effective forms of catalysts and also show that non-stoquasticity is not essential to avoid such phase transitions. While some of the toy problems studied might not be classically NP-hard, they reveal that $n-$local catalysts exponentially improve gap scaling and need to be connected across unfrustrated loops in the problem graph to be effective. Our analysis suggests that non-local quantum fluctuations entangling multiple qubits are key to achieving the desired quantum advantage.

Related papers

• Enhancing the Energy Gap of Random Graph Problems via XX-catalysts in Quantum Annealing [0.0]
  We show that employing multiple XX-catalysts on the edges of a graph significantly enhances the minimum energy gap. Remarkably, our analysis shows that the more severe the first-order phase transition, the more effective the catalyst is in opening the gap.
  arXiv  Detail & Related papers  (2024-09-24T18:00:01Z)
• Anti-crossings occurrence as exponentially closing gaps in Quantum Annealing [0.0]
  We use a perturbative expansion to derive a condition for the occurrence of an avoided level crossing during the annealing process. We show that no exponentially small gaps arise for regular bipartite graphs, implying that QA can efficiently solve MaxCut in that case.
  arXiv  Detail & Related papers  (2023-04-25T14:42:20Z)
• Universality of critical dynamics with finite entanglement [68.8204255655161]
  We study how low-energy dynamics of quantum systems near criticality are modified by finite entanglement. Our result establishes the precise role played by entanglement in time-dependent critical phenomena.
  arXiv  Detail & Related papers  (2023-01-23T19:23:54Z)
• Assessing the performance of quantum annealing with nonlinear driving [0.0]
  We report studies of the diabatic excitations arising from nonlinear protocols applied to the transverse field Ising chain. We find that the paradigmatic Kibble-Zurek behavior can be suppressed with pauses'' in the evolution.
  arXiv  Detail & Related papers  (2022-03-31T13:08:00Z)
• Effects of XX-catalysts on quantum annealing spectra with perturbative crossings [0.0]
  We show that non-stoquastic XX-couplings can significantly reduce the gap closing with system size at an avoided level crossing. We also study how the evolution of the ground-state vector is altered by the presence of the catalyst and find that the negative components of the ground-state vector are key to understanding the response of the gap spectrum.
  arXiv  Detail & Related papers  (2022-03-13T22:28:52Z)
• Enhanced nonlinear quantum metrology with weakly coupled solitons and particle losses [58.720142291102135]
  We offer an interferometric procedure for phase parameters estimation at the Heisenberg (up to 1/N) and super-Heisenberg scaling levels. The heart of our setup is the novel soliton Josephson Junction (SJJ) system providing the formation of the quantum probe. We illustrate that such states are close to the optimal ones even with moderate losses.
  arXiv  Detail & Related papers  (2021-08-07T09:29:23Z)
• Continuous-time dynamics and error scaling of noisy highly-entangling quantum circuits [58.720142291102135]
  We simulate a noisy quantum Fourier transform processor with up to 21 qubits. We take into account microscopic dissipative processes rather than relying on digital error models. We show that depending on the dissipative mechanisms at play, the choice of input state has a strong impact on the performance of the quantum algorithm.
  arXiv  Detail & Related papers  (2021-02-08T14:55:44Z)
• Probing the coherence of solid-state qubits at avoided crossings [51.805457601192614]
  We study the quantum dynamics of paramagnetic defects interacting with a nuclear spin bath at avoided crossings. The proposed theoretical approach paves the way to designing the coherence properties of spin qubits from first principles.
  arXiv  Detail & Related papers  (2020-10-21T15:37:59Z)
• Quantum Statistical Complexity Measure as a Signalling of Correlation Transitions [55.41644538483948]
  We introduce a quantum version for the statistical complexity measure, in the context of quantum information theory, and use it as a signalling function of quantum order-disorder transitions. We apply our measure to two exactly solvable Hamiltonian models, namely: the $1D$-Quantum Ising Model and the Heisenberg XXZ spin-$1/2$ chain. We also compute this measure for one-qubit and two-qubit reduced states for the considered models, and analyse its behaviour across its quantum phase transitions for finite system sizes as well as in the thermodynamic limit by using Bethe ansatz.
  arXiv  Detail & Related papers  (2020-02-05T00:45:21Z)
• Einselection from incompatible decoherence channels [62.997667081978825]
  We analyze an open quantum dynamics inspired by CQED experiments with two non-commuting Lindblad operators. We show that Fock states remain the most robust states to decoherence up to a critical coupling.
  arXiv  Detail & Related papers  (2020-01-29T14:15:19Z)
• Reduction of the energy-gap scaling by coherent catalysis in models of quantum annealing [0.0]
  We show that some Hamiltonians still exhibit unavoidable first-order transitions even with non-stoquastic drivers. This opens up the possibility of using coherent to search for exponential speedups in systems previously thought to be exponentially slow.
  arXiv  Detail & Related papers  (2019-12-27T00:34:09Z)

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.