Adiabatic quantum unstructured search in parallel

• URL: http://arxiv.org/abs/2502.08594v1
• Date: Wed, 12 Feb 2025 17:32:27 GMT
• Title: Adiabatic quantum unstructured search in parallel
• Authors: Sean A. Adamson, Petros Wallden,
• Abstract summary: We present an optimized adiabatic quantum schedule for unstructured search building. In the errorless adiabatic limit, the probability of successfully obtaining the marked state from a measurement increases directly proportional to time. Our findings suggest that quantum advantage may still be achievable under constrained coherence times.
• Score: 0.0
• License:
• Abstract: We present an optimized adiabatic quantum schedule for unstructured search building on the original approach of Roland and Cerf [Phys. Rev. A 65, 042308 (2002)]. Our schedule adiabatically varies the Hamiltonian even more rapidly at the endpoints of its evolution, preserving Grover's well-known quadratic quantum speedup. In the errorless adiabatic limit, the probability of successfully obtaining the marked state from a measurement increases directly proportional to time, suggesting efficient parallelization. Numerical simulations of an appropriate reduced two-dimensional Schr\"odinger system confirm adiabaticity while demonstrating superior performance in terms of probability compared to existing adiabatic algorithms and Grover's algorithm, benefiting applications with possible premature termination. We introduce a protocol that ensures a marked-state probability at least $p$ in time of order $\sqrt{N}(1+p/\varepsilon)$, and analyze its implications for realistic bounded-resource scenarios. Our findings suggest that quantum advantage may still be achievable under constrained coherence times (where other algorithms fail), provided the hardware allows for them to be sufficiently long.

Related papers

• Unstructured Adiabatic Quantum Optimization: Optimality with Limitations [0.06022769903412461]
  We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches a lower bound for a class of classical local spin Hamiltonians. We show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision.
  arXiv  Detail & Related papers  (2024-11-08T17:51:18Z)
• Constant-Time Quantum Search with a Many-Body Quantum System [39.58317527488534]
  We consider a many-body quantum system that naturally effects parallel queries. We show that its parameters can be tuned to search a database in constant time.
  arXiv  Detail & Related papers  (2024-08-09T22:57:59Z)
• Quantum quench dynamics as a shortcut to adiabaticity [31.114245664719455]
  We develop and test a quantum algorithm in which the incorporation of a quench step serves as a remedy to the diverging adiabatic timescale. Our experiments show that this approach significantly outperforms the adiabatic algorithm.
  arXiv  Detail & Related papers  (2024-05-31T17:07:43Z)
• Single-ancilla ground state preparation via Lindbladians [4.328210085579236]
  We design a quantum algorithm for ground state preparation in the early fault tolerant regime. As a Monte Carlo-style quantum algorithm, our method features a Lindbladian where the target state is stationary. Our algorithm can be implemented using just one ancilla qubit and efficiently simulated on a quantum computer.
  arXiv  Detail & Related papers  (2023-08-30T00:11:19Z)
• Grover Speedup from Many Forms of the Zeno Effect [0.0]
  We show that other manifestations of the Zeno effect can support an optimal speedup in a physically realistic model. We group these algorithms into three families to facilitate a structured understanding of how speedups can be obtained.
  arXiv  Detail & Related papers  (2023-05-18T17:40:32Z)
• Quantum Thermal State Preparation [39.91303506884272]
  We introduce simple continuous-time quantum Gibbs samplers for simulating quantum master equations. We construct the first provably accurate and efficient algorithm for preparing certain purified Gibbs states. Our algorithms' costs have a provable dependence on temperature, accuracy, and the mixing time.
  arXiv  Detail & Related papers  (2023-03-31T17:29:56Z)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• 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)
• Fragmented imaginary-time evolution for early-stage quantum signal processors [0.0]
  Simulating quantum imaginary-time evolution (QITE) is a major promise of quantum computation. Our main contribution is a new generation of deterministic, high-precision QITE algorithms. We present two QITE-circuit sub-routines with excellent complexity scaling.
  arXiv  Detail & Related papers  (2021-10-25T18:02:24Z)
• Long-time simulations with high fidelity on quantum hardware [1.8909337252764988]
  We show that it is possible to implement long-time, high fidelity simulations on current hardware. Specifically, we simulate an XY-model spin chain on the Rigetti and IBM quantum computers. This is a factor of 150 longer than is possible using the iterated Trotter method.
  arXiv  Detail & Related papers  (2021-02-08T16:18:50Z)
• Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
  Google's recent quantum supremacy experiment heralded a transition point where quantum computing performed a computational task, random circuit sampling. We examine the constraints of the observed quantum runtime advantage in a larger number of qubits and gates.
  arXiv  Detail & Related papers  (2020-05-05T20:11:53Z)

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.