Lower bounds for adiabatic quantum algorithms by quantum speed limits
- URL: http://arxiv.org/abs/2207.01604v4
- Date: Wed, 19 Jul 2023 15:40:25 GMT
- Title: Lower bounds for adiabatic quantum algorithms by quantum speed limits
- Authors: Jyong-Hao Chen
- Abstract summary: We introduce a framework for estimating lower bounds on the runtime of adiabatic quantum algorithms.
We analytically obtain lower bounds on adiabatic algorithms for finding k-clique in random graphs.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce a simple framework for estimating lower bounds on the runtime of
a broad class of adiabatic quantum algorithms. The central formula consists of
calculating the variance of the final Hamiltonian with respect to the initial
state. After examining adiabatic versions of certain keystone circuit-based
quantum algorithms, this technique is applied to adiabatic quantum algorithms
with undetermined speedup. In particular, we analytically obtain lower bounds
on adiabatic algorithms for finding k-clique in random graphs. Additionally,
for a particular class of Hamiltonian, it is straightforward to prove the
equivalence between our framework and the conventional approach based on
spectral gap analysis.
Related papers
- Quartic quantum speedups for planted inference [44.820711784498]
We describe a quantum algorithm for the Planted Noisy $k$XOR problem.
Our work suggests that some constructions are susceptible to super-quadratic quantum attacks.
arXiv Detail & Related papers (2024-06-27T17:54:28Z) - A quantum implementation of high-order power method for estimating geometric entanglement of pure states [39.58317527488534]
This work presents a quantum adaptation of the iterative higher-order power method for estimating the geometric measure of entanglement of multi-qubit pure states.
It is executable on current (hybrid) quantum hardware and does not depend on quantum memory.
We study the effect of noise on the algorithm using a simple theoretical model based on the standard depolarising channel.
arXiv Detail & Related papers (2024-05-29T14:40:24Z) - Exploring Ground States of Fermi-Hubbard Model on Honeycomb Lattices with Counterdiabaticity [2.756976915658684]
Shortcuts to adiabaticity by counter-diabatic driving serve to accelerate these processes by suppressing energy excitations.
We develop variational quantum algorithms incorporating the auxiliary counterdiabatic interactions, comparing them with digitized adiabatic algorithms.
These algorithms are then implemented on gate-based quantum circuits to explore the ground states of the Fermi-Hubbard model on honeycomb lattices.
arXiv Detail & Related papers (2024-05-15T10:05:01Z) - Assessing the query complexity limits of quantum phase estimation using symmetry aware spectral bounds [0.0]
computational cost of quantum algorithms for physics and chemistry is closely linked to the spectrum of the Hamiltonian.
We introduce a hierarchy of symmetry-aware spectral bounds that provide a unified understanding of the performance of quantum phase estimation algorithms.
arXiv Detail & Related papers (2024-03-07T18:38:49Z) - Quantum speedup for combinatorial optimization with flat energy
landscapes [0.0]
We develop a theoretical framework to analyze the relative performance of the optimized quantum adiabatic algorithm and a broad class of classical Markov chain Monte Carlo algorithms.
arXiv Detail & Related papers (2023-06-22T18:00:00Z) - A quantum advantage over classical for local max cut [48.02822142773719]
Quantum optimization approximation algorithm (QAOA) has a computational advantage over comparable local classical techniques on degree-3 graphs.
Results hint that even small-scale quantum computation, which is relevant to the current state-of the art quantum hardware, could have significant advantages over comparably simple classical.
arXiv Detail & Related papers (2023-04-17T16:42:05Z) - A Sublinear-Time Quantum Algorithm for Approximating Partition Functions [0.0]
We present a novel quantum algorithm for estimating Gibbs partition functions in sublinear time.
This is the first speed-up of this type to be obtained over the seminal nearly-linear time of vStefankovivc, Vempala and Vigoda.
arXiv Detail & Related papers (2022-07-18T14:41:48Z) - 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) - Numerical Simulations of Noisy Quantum Circuits for Computational
Chemistry [51.827942608832025]
Near-term quantum computers can calculate the ground-state properties of small molecules.
We show how the structure of the computational ansatz as well as the errors induced by device noise affect the calculation.
arXiv Detail & Related papers (2021-12-31T16:33:10Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory.
We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
arXiv Detail & Related papers (2021-11-30T12:21:41Z) - Quantum computing critical exponents [0.0]
We show that the Variational Quantum-Classical Simulation algorithm admits a finite circuit depth scaling collapse when targeting the critical point of the transverse field Ising chain.
The order parameter only collapses on one side of the transition due to a slowdown of the quantum algorithm when crossing the phase transition.
arXiv Detail & Related papers (2021-04-02T17:38:20Z)
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.