Randomly Compiled Quantum Simulation with Exponentially Reduced Circuit Depths

• URL: http://arxiv.org/abs/2411.04240v2
• Date: Sat, 25 Jan 2025 18:36:43 GMT
• Title: Randomly Compiled Quantum Simulation with Exponentially Reduced Circuit Depths
• Abstract summary: We develop qFLO, a higher order randomised algorithm for time-evolution.<n> Notably, it requires no ancillary qubits or additional control gates making it especially promising for near-term quantum devices.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The quantum stochastic drift protocol, also known as qDRIFT, has become a popular algorithm for implementing time-evolution of quantum systems using randomised compiling. In this work we develop qFLO, a higher order randomised algorithm for time-evolution. To estimate an observable expectation value at time $T$ to precision $\epsilon$, we show it is sufficient to use circuit depths of $O(T^2\log(1/\epsilon))$ -- an exponential improvement over standard qDRIFT requirements with respect to $\epsilon$. The protocol achieves this using $O(1/\epsilon^2)$ repeated runs of the standard qDRIFT protocol combined with classical post-processing in the form of Richardson extrapolation. Notably, it requires no ancillary qubits or additional control gates making it especially promising for near-term quantum devices. Furthermore, it is well-conditioned and inherits many desirable properties of randomly compiled simulation methods, including circuit depths that do not explicitly depend on the number of terms in the Hamiltonian.

Related papers

• Optimal Lower Bounds for Hamiltonian Simulation [42.227880669333835]
  For Hamiltonian $H = sum_j h_j$, we proveally tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer.<n>Our hold for arbitrary term norms $|h_j|$, time $t$, and trace-distance error $$.
  arXiv  Detail & Related papers  (2026-07-22T07:41:32Z)
• Adiabatic Quantum Phase Estimation [47.3103723337301]
  Quantum phase estimation (QPE) is a central algorithmic primitive that estimates eigenvalues of a Hamiltonian up to precision $$ in Heisenberg-limited time $T= (1/)$.<n>Standard gate-based implementations of QPE require deep controlled time-evolution circuits and are not native to analog hardware.<n>We present a simple adiabatic protocol for QPE that achieves the optimal Heisenberg-limited scaling $T = Oleft( frac1 logleft(-1right)right)$ in both the precision $$
  arXiv  Detail & Related papers  (2026-05-21T17:31:36Z)
• MLMC-qDRIFT: Multilevel Variance Reduction for Randomized Quantum Hamiltonian Simulation [2.847280100380157]
  We introduce a multilevel Monte Carlo framework for qDRIFT that reduces this sampling overhead.<n>We prove that the resultingC-qDRIFT estimator reduces the total gate complexity for fixed-precision observable estimation from the standard qDRIFT scaling $mathcalO(varepsilon-3)$ to $mathcalO(varepsilon-2log2(1/varepsilon)$.
  arXiv  Detail & Related papers  (2026-04-29T16:32:48Z)
• qSHIFT: An Adaptive Sampling Protocol for Higher-Order Quantum Simulation [0.5635658368100682]
  Quantum simulation is a cornerstone application for quantum computing.<n>Standard methods face a trade-off between circuit depth and accuracy.<n>We introduce qSHIFT, an adaptive sampling protocol that overcomes these limitations.
  arXiv  Detail & Related papers  (2026-04-29T03:47:21Z)
• Approximate Hamiltonian Simulation Algorithm for Efficient Fluid Quantum Simulations [7.831166491139832]
  This work aims to address the bottleneck issues of hardware resource limitation and decoherence error in the Hamiltonian simulation of quantum fluids.<n>We propose an approximate operator optimization scheme aimed at reducing the circuit depth in Hamiltonian evolution.
  arXiv  Detail & Related papers  (2026-04-19T15:26:25Z)
• Speculative Decoding Speed-of-Light: Optimal Lower Bounds via Branching Random Walks [39.54576236079211]
  Speculative generation has emerged as a promising technique to accelerate inference in large language models.<n>In this work, we establish the first tight'' lower bounds on the runtime of any deterministic speculative generation algorithm.
  arXiv  Detail & Related papers  (2025-12-12T16:54:33Z)
• Performance Guarantees for Quantum Neural Estimation of Entropies [31.955071410400947]
  Quantum neural estimators (QNEs) combine classical neural networks with parametrized quantum circuits.<n>We study formal guarantees for QNEs of measured relative entropies in the form of non-asymptotic error risk bounds.<n>Our theory aims to facilitate principled implementation of QNEs for measured relative entropies.
  arXiv  Detail & Related papers  (2025-11-24T16:36:06Z)
• Optimizing digital quantum simulation of open quantum lattice models [3.761360709981958]
  We address the problem of simulating geometrically local many-body open quantum systems interacting with a stationary Gaussian environment.<n>We develop near-optimal algorithms that attain a simulation error $delta$ in the system-state with $mathcalO(Nt(Nt/delta)o(1))$ gates, $mathcalO(t(Nt/delta)o(1))$ ancillas.
  arXiv  Detail & Related papers  (2025-09-02T12:44:57Z)
• Accelerating Quantum Reinforcement Learning with a Quantum Natural Policy Gradient Based Approach [36.05085942729295]
  This paper introduces a Quantum Natural Policy Gradient (QNPG) algorithm, which replaces the random sampling used in classicalNPG estimators with a deterministic gradient estimation approach.<n>The proposed QNPG algorithm achieves a sample complexity of $tildemathcalO(epsilon-1.5)$ for queries to the quantum oracle, significantly improving the classical lower bound of $tildemathcalO(epsilon-2)$ for queries to the Markov Decision Process (MDP)
  arXiv  Detail & Related papers  (2025-01-27T17:38:30Z)
• Classically estimating observables of noiseless quantum circuits [36.688706661620905]
  We present a classical algorithm for estimating expectation values of arbitrary observables on most quantum circuits. For non-classically-simulable input states or observables, the expectation values can be estimated by augmenting our algorithm with classical shadows of the relevant state or observable.
  arXiv  Detail & Related papers  (2024-09-03T08:44:33Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose arbitrary exponentials into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions. We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model. We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent [37.59299233291882]
  We propose Q-Newton, a hybrid quantum-classical scheduler for accelerating neural network training with Newton's GD. Q-Newton utilizes a streamlined scheduling module that coordinates between quantum and classical linear solvers. Our evaluation showcases the potential for Q-Newton to significantly reduce the total training time compared to commonly used quantum machines.
  arXiv  Detail & Related papers  (2024-04-30T23:55:03Z)
• Sachdev-Ye-Kitaev model on a noisy quantum computer [1.0377683220196874]
  We study the SYK model -- an important toy model for quantum gravity on IBM's superconducting qubit quantum computers. We compute return probability after time $t$ and out-of-time order correlators (OTOC) which is a standard observable of quantifying the chaotic nature of quantum systems.
  arXiv  Detail & Related papers  (2023-11-29T19:00:00Z)
• Simulation of IBM's kicked Ising experiment with Projected Entangled Pair Operator [71.10376783074766]
  We perform classical simulations of the 127-qubit kicked Ising model, which was recently emulated using a quantum circuit with error mitigation. Our approach is based on the projected entangled pair operator (PEPO) in the Heisenberg picture. We develop a Clifford expansion theory to compute exact expectation values and use them to evaluate algorithms.
  arXiv  Detail & Related papers  (2023-08-06T10:24:23Z)
• Quantum Phase Estimation by Compressed Sensing [0.0]
  We present a new Heisenberg-limited quantum phase estimation algorithm for early quantum computers based on compressed sensing. Our algorithm is able to recover the frequency with a total runtime $mathcalO(epsilon-1textpolylog(epsilon-1))$, where $epsilon$ is the accuracy. We also consider the more general quantum eigenvalue estimation problem (QEEP) and show numerically that the off-grid compressed sensing can be a strong candidate for solving the QEEP.
  arXiv  Detail & Related papers  (2023-06-12T10:21:59Z)
• qSWIFT: High-order randomized compiler for Hamiltonian simulation [0.07980105005277842]
  Hamiltonian simulation is known to be one of the fundamental building blocks of a variety of quantum algorithms. We present qSWIFT, a high-order randomized algorithm for Hamiltonian simulation.
  arXiv  Detail & Related papers  (2023-02-28T18:02:39Z)
• Simulating excited states of the Lipkin model on a quantum computer [0.0]
  We show that the accuracy strongly depends on the fermion to qubit encoding. We use IBM quantum machines to compute the energy spectrum for a system of $N=2, 3$ and $4$ particles.
  arXiv  Detail & Related papers  (2022-03-03T01:43:12Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• A quantum algorithm for training wide and deep classical neural networks [72.2614468437919]
  We show that conditions amenable to classical trainability via gradient descent coincide with those necessary for efficiently solving quantum linear systems. We numerically demonstrate that the MNIST image dataset satisfies such conditions. We provide empirical evidence for $O(log n)$ training of a convolutional neural network with pooling.
  arXiv  Detail & Related papers  (2021-07-19T23:41:03Z)
• Implementing a Fast Unbounded Quantum Fanout Gate Using Power-Law Interactions [0.9634136878988853]
  Power-law interactions with strength decaying as $1/ralpha$ in the distance provide an experimentally realizable resource for information processing. We leverage the power of these interactions to implement a fast quantum fanout gate with an arbitrary number of targets. We show that power-law systems with $alpha le D$ are difficult to simulate classically even for short times, under a standard assumption that factoring is classically intractable.
  arXiv  Detail & Related papers  (2020-07-01T18: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.