Fragmented imaginary-time evolution for early-stage quantum signal
processors
- URL: http://arxiv.org/abs/2110.13180v4
- Date: Wed, 1 Nov 2023 06:59:23 GMT
- Title: Fragmented imaginary-time evolution for early-stage quantum signal
processors
- Authors: Thais de Lima Silva, M\'arcio M. Taddei, Stefano Carrazza, and Leandro
Aolita
- Abstract summary: 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.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Simulating quantum imaginary-time evolution (QITE) is a major promise of
quantum computation. However, the known algorithms are either probabilistic
(repeat until success) with impractically small success probabilities or
coherent (quantum amplitude amplification) but with circuit depths and
ancillary-qubit numbers unrealistically large in the mid term. Our main
contribution is a new generation of deterministic, high-precision QITE
algorithms significantly more amenable experimentally. These are based on a
surprisingly simple idea: partitioning the evolution into several fragments
that are sequentially run probabilistically. This causes a huge reduction in
wasted circuit depth every time a run fails. Indeed, the resulting overall
runtime is asymptotically better than in coherent approaches and the hardware
requirements even milder than in probabilistic ones, remarkably. More
technically, we present two QITE-circuit sub-routines with excellent complexity
scalings. One of them is optimal in ancillary-qubit overhead (one single
ancillary qubit throughout) whereas the other one is optimal in runtime for
small inverse temperature or high precision. The latter is shown by noting that
the runtime saturates a cooling-speed limit that is the imaginary-time
counterpart of the no fast-forwarding theorem of real-time simulations, which
we prove. Moreover, we also make two technical contributions to the quantum
signal processing formalism for operator-function synthesis (on which our
sub-routines are based) that are useful beyond QITE. Our findings are specially
relevant for the early fault-tolerance stages of quantum hardware.
Related papers
- Benchmarking the algorithmic performance of near-term neutral atom
processors [0.0]
We present a characterization of the algorithmic performance of Rydberg atom quantum computers through device simulation.
We consider three different quantum algorithm related tests, exploiting the ability to dynamically update qubit connectivity and multi-qubit gates.
Our results indicate Rydberg atom processors are a highly competitive near-term platform which, bolstered by the potential for further scalability, can pave the way toward useful quantum computation.
arXiv Detail & Related papers (2024-02-03T11:55:02Z) - Nuclear Spectra from Quantum Lanczos Algorithm with Real-Time Evolution
and Multiple Reference States [0.0]
I performed numerical simulations to find the low-lying eigenstates of $20$Ne, $22$Na, and $29$Na to compare imaginary- and real-time evolution.
I present the quantum circuits for the QLanczos algorithm with real-time evolution and multiple references.
arXiv Detail & Related papers (2023-09-01T23:25:57Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - 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) - Quantifying Grover speed-ups beyond asymptotic analysis [0.0]
We consider an approach that combines classical emulation with detailed complexity bounds that include all constants.
We apply our method to some simple quantum speedups of classical algorithms for solving the well-studied MAX-$k$-SAT optimization problem.
This requires rigorous bounds (including all constants) on the expected- and worst-case complexities of two important quantum sub-routines.
arXiv Detail & Related papers (2022-03-09T19:00:00Z) - Quantum algorithms for quantum dynamics: A performance study on the
spin-boson model [68.8204255655161]
Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator.
variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware.
We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
arXiv Detail & Related papers (2021-08-09T18:00:05Z) - Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions.
Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
arXiv Detail & Related papers (2021-06-24T20:16:02Z) - As Accurate as Needed, as Efficient as Possible: Approximations in
DD-based Quantum Circuit Simulation [5.119310422637946]
Decision Diagrams (DDs) have previously shown to reduce the required memory in many important cases by exploiting redundancies in the quantum state.
We show that this reduction can be amplified by exploiting the probabilistic nature of quantum computers to achieve even more compact representations.
Specifically, we propose two new DD-based simulation strategies that approximate the quantum states to attain more compact representations.
arXiv Detail & Related papers (2020-12-10T12:02:03Z) - Compilation of Fault-Tolerant Quantum Heuristics for Combinatorial
Optimization [0.14755786263360526]
We explore which quantum algorithms for optimization might be most practical to try out on a small fault-tolerant quantum computer.
Our results discourage the notion that any quantum optimization realizing only a quadratic speedup will achieve an advantage over classical algorithms.
arXiv Detail & Related papers (2020-07-14T22:54:04Z) - Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
Random quantum circuits are commonly viewed as hard to simulate classically.
We show that approximate simulation of typical instances is almost as hard as exact simulation.
We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
arXiv Detail & Related papers (2019-12-31T19:00:00Z)
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.