Fast quantum computation with all-to-all Hamiltonians

• URL: http://arxiv.org/abs/2509.25345v1
• Date: Mon, 29 Sep 2025 18:02:00 GMT
• Title: Fast quantum computation with all-to-all Hamiltonians
• Authors: Chao Yin,
• Abstract summary: All-to-all interactions arise naturally in many areas of theoretical physics.<n>We show that all-to-all Hamiltonians can process information on much shorter timescales.
• Score: 1.7763840710724852
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: All-to-all interactions arise naturally in many areas of theoretical physics and across diverse experimental quantum platforms, motivating a systematic study of their information-processing power. Assuming each pair of qubits interacts with $\mathrm{O}(1)$ strength, time-dependent all-to-all Hamiltonians can simulate arbitrary all-to-all quantum circuits, performing quantum computation in time proportional to the circuit depth. We show that this naive correspondence is far from optimal: all-to-all Hamiltonians can process information on much shorter timescales. First, we prove that any two-qubit gate can be simulated by all-to-all Hamiltonians on $N$ qubits in time $\mathrm{O}(1/N)$ (up to factor $N^{\delta}$ with an arbitrarily small constant $\delta>0$), with polynomially small error $1/\mathrm{poly}(N)$. Immediate consequences include: 1) Certain $\mathrm{O}(N)$-qubit unitaries and entangled states, such as the multiply-controlled Toffoli gate and the GHZ and W states, can be generated in $\mathrm{O}(1/N)$ time; 2) Trading space for time, any quantum circuit can be simulated in arbitrarily short time; 3) Information could propagate in a fast way that saturates known Lieb-Robinson bounds in strongly power-law interacting systems. Our second main result proves that any depth-$D$ quantum circuit can be simulated by a randomized Hamiltonian protocol in time $T=\mathrm{O}(D/\sqrt{N})$, with constant space overhead and polynomially small error. The techniques underlying our results depart fundamentally from the existing literature on parallelizing commuting gates: We rely crucially on non-commuting Hamiltonians and draw on diverse physical ideas.

Related papers

• Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions [1.43494686131174]
  We show that the 3-local Hamiltonian problem on $n$ qubits cannot be solved classically in time $O(2(1-varepsilon)n)$ for any $varepsilon>0$ under the Strong Exponential-Time Hypothesis (SETH)<n>We provide a quantum algorithm that runs in $O(sqrt2n)$ time for an arbitrary $1/mathrmpoly(n)$ relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Goss
  arXiv  Detail & Related papers  (2026-02-16T01:11:55Z)
• Hamiltonian Decoded Quantum Interferometry [69.7049555871155]
  We introduce Hamiltonian Decoded Quantum Interferometry (HDQI)<n>HDQI utilizes coherent measurements and the symplectic representation of the Pauli group to reduce Gibbs sampling and Hamiltonian Bellians.<n>We show that HDQI efficiently prepares Gibbs states at arbitrary temperatures for a class of physically motivated commuting Hamiltonians.
  arXiv  Detail & Related papers  (2025-10-09T08:06:15Z)
• Lower Bounds for Learning Hamiltonians from Time Evolution [5.118083299467833]
  We consider the problem of learning Hamiltonians from time evolution.<n>We show that any learning algorithm with inverse time resolution requires super-polynomial total evolution time.
  arXiv  Detail & Related papers  (2025-09-25T01:50:55Z)
• Learning quantum Gibbs states locally and efficiently [7.728643029778198]
  Learning the Hamiltonian underlying a quantum many-body system in thermal equilibrium is a fundamental task in quantum learning theory and experimental sciences.<n>We present a learning algorithm that learns each local term of a $n$-qubit $D$-dimensional Hamiltonian to an additive error $epsilon$ with sample complexity.
  arXiv  Detail & Related papers  (2025-04-03T15:42:23Z)
• Fault-tolerant fermionic quantum computing [39.58317527488534]
  We introduce fermionic fault-tolerant quantum computing, a framework which removes this overhead altogether.<n>We show how our framework can be implemented in neutral atoms, overcoming the apparent inability of neutral atoms to implement non-number-conserving gates.
  arXiv  Detail & Related papers  (2024-11-13T19:00:02Z)
• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  We present a quantum generalization of these tools through a generic bottleneck lemma.<n>This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles.<n>We show how to lift classical slow mixing results in the presence of a transverse field using Poisson Feynman-Kac techniques.
  arXiv  Detail & Related papers  (2024-11-06T22:51:27Z)
• 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.<n>Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model.<n>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)
• A polynomial-time dissipation-based quantum algorithm for solving the ground states of a class of classically hard Hamiltonians [4.500918096201963]
  We give a complexity-time quantum algorithm for solving the ground states of a class of classically hard Hamiltonians. We show that the Hamiltonians that can be efficiently solved by our algorithms contain classically hard instances.
  arXiv  Detail & Related papers  (2024-01-25T05:01:02Z)
• On the Impossibility of General Parallel Fast-forwarding of Hamiltonian Simulation [4.925967492198012]
  Hamiltonian simulation is one of the most important problems in the field of quantum computing. Existing simulation algorithms require running time at least linear in the evolution time $T$. It is intriguing whether we can achieve fast Hamiltonian simulation with the power of parallelism.
  arXiv  Detail & Related papers  (2023-05-21T12:30:00Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Exponentially faster implementations of Select(H) for fermionic Hamiltonians [0.0]
  We present a framework for constructing quantum circuits that implement the multiply-controlled unitary $textSelect(H) equiv sum_ell. $textSelect(H)$ is one of the main subroutines of several quantum algorithms.
  arXiv  Detail & Related papers  (2020-04-08T18:00:04Z)

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.