Fast quantum computation with all-to-all Hamiltonians
ORAL
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 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 O(1/N) (up to factor Nδ with an arbitrarily small constant δ > 0), with polynomially small error 1/poly(N). Immediate consequences include: 1) Certain O(N)-qubit unitaries and entangled states, such as the multiply-controlled Toffoli gate and the GHZ and W states, can be generated in 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 = O(D/√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.
First, we prove that any two-qubit gate can be simulated by all-to-all Hamiltonians on N qubits in time O(1/N) (up to factor Nδ with an arbitrarily small constant δ > 0), with polynomially small error 1/poly(N). Immediate consequences include: 1) Certain O(N)-qubit unitaries and entangled states, such as the multiply-controlled Toffoli gate and the GHZ and W states, can be generated in 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 = O(D/√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.
*We acknowledge support from the Stanford Q-FARM Bloch Postdoctoral Fellowship in Quantum Science and Engineering.
–
Publication: arXiv:2509.25345
Presenters
-
Chao Yin
- Stanford University