Complexity of Quadratic Bosonic Hamiltonian Simulation: $\mathsf{BQP}$-Completeness and $\mathsf{PostBQP}$-Hardness

• URL: http://arxiv.org/abs/2603.26561v1
• Date: Fri, 27 Mar 2026 16:25:41 GMT
• Title: Complexity of Quadratic Bosonic Hamiltonian Simulation: $\mathsf{BQP}$-Completeness and $\mathsf{PostBQP}$-Hardness
• Abstract summary: We introduce a broad class of quadratic bosonic problems for which we prove that they are $mathsfBQP$-complete.<n>We show that extending the aforementioned class to even more general quadratic Hamiltonians results in a $mathsfPostBQP$-hard problem.<n>This reveals a sharp transition in the complexity of simulating large quantum systems on a quantum computer, as well as in the difference in complexity between their simulation on classical and quantum computers.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The computational complexity of simulating the dynamics of physical quantum systems is a central question at the interface of quantum physics and computer science. In this work, we address this question for the simulation of exponentially large bosonic Hamiltonians with quadratic interactions. We present two results: First, we introduce a broad class of quadratic bosonic problems for which we prove that they are $\mathsf{BQP}$-complete. Importantly, this class includes two known $\mathsf{BQP}$-complete problems as special cases: Classical oscillator networks and continuous-time quantum walks. Second, we show that extending the aforementioned class to even more general quadratic Hamiltonians results in a $\mathsf{PostBQP}$-hard problem. This reveals a sharp transition in the complexity of simulating large quantum systems on a quantum computer, as well as in the difference in complexity between their simulation on classical and quantum computers.

Related papers

• Quantum simulation of massive Thirring and Gross--Neveu models for arbitrary number of flavors [40.72140849821964]
  We consider the massive Thirring and Gross-Neveu models with arbitrary number of fermion flavors, $N_f$, discretized on a spatial one-dimensional lattice of size $L$.<n>We prepare the ground states of both models with excellent fidelity for system sizes up to 20 qubits with $N_f = 1,2,3,4$.<n>Our work is a concrete step towards the quantum simulation of real-time dynamics of large $N_f$ fermionic quantum field theories models.
  arXiv  Detail & Related papers  (2026-02-25T19:00:01Z)
• On the Complexity of Decoded Quantum Interferometry [39.951444958798014]
  We study the complexity of Decoded Quantum Interferometry (DQI), a recently proposed quantum algorithm for approximate optimization.<n>We argue that DQI is hard to classically simulate, and that the hardness comes from locating an exponentially large hidden subset.
  arXiv  Detail & Related papers  (2025-09-17T21:31:58Z)
• Quantum algorithms based on quantum trajectories [0.4870012761464388]
  We show that the additive complexity of $O(T + log(1/epsilon))$ is reachable for the simulation of a large class of Lindbladian.<n>In this work we show that the additive complexity of $O(T + log(1/epsilon))$ is reachable for the simulation of a large class of Lindbladian by constructing a novel quantum algorithm based on quantum trajectories.
  arXiv  Detail & Related papers  (2025-09-12T17:27:25Z)
• Improved separation between quantum and classical computers for sampling and functional tasks [3.618534280726541]
  This paper furthers existing evidence that quantum computers are capable of computations beyond classical computers. Specifically, we strengthen the collapse of the hierarchy to the second level if: (i) Quantum computers with postselection are as powerful as classical computers with postselection. We prove that if there exists an equivalence between problems solvable with an exact counting oracle and problems solvable with an approximate counting oracle, then the hierarchy collapses to its second level.
  arXiv  Detail & Related papers  (2024-10-28T11:30:10Z)
• Bosonic Quantum Computational Complexity [1.7499351967216341]
  We lay foundations for such a research program.<n>We introduce natural complexity classes and problems based on bosonic generalizations of BQP.<n>We show that the problem of deciding the boundedness of the spectrum of a bosonic Hamiltonian is co-NP-hard.
  arXiv  Detail & Related papers  (2024-10-05T19:43:41Z)
• 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)
• Quantum Algorithms in a Superposition of Spacetimes [5.475280561991127]
  Quantum computers are expected to revolutionize our ability to process information. We show a first example of a natural computational model based on Quantum Gravity (QG) We show that a quantum computer is able to solve in time two of the fundamental problems in computer science.
  arXiv  Detail & Related papers  (2024-03-05T13:05:07Z)
• Quantum Depth in the Random Oracle Model [57.663890114335736]
  We give a comprehensive characterization of the computational power of shallow quantum circuits combined with classical computation. For some problems, the ability to perform adaptive measurements in a single shallow quantum circuit is more useful than the ability to perform many shallow quantum circuits without adaptive measurements.
  arXiv  Detail & Related papers  (2022-10-12T17:54:02Z)
• Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
  Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
  arXiv  Detail & Related papers  (2022-01-06T03:10:53Z)
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation [55.41644538483948]
  Current generation noisy intermediate-scale quantum (NISQ) computers are severely limited in chip size and error rates. We derive localized circuit transformations to efficiently compress quantum circuits for simulation of certain spin Hamiltonians known as free fermions. The proposed numerical circuit compression algorithm behaves backward stable and scales cubically in the number of spins enabling circuit synthesis beyond $mathcalO(103)$ spins.
  arXiv  Detail & Related papers  (2021-08-06T19:38:03Z)
• Long-Time Error-Mitigating Simulation of Open Quantum Systems on Near Term Quantum Computers [38.860468003121404]
  We study an open quantum system simulation on quantum hardware, which demonstrates robustness to hardware errors even with deep circuits containing up to two thousand entangling gates. We simulate two systems of electrons coupled to an infinite thermal bath: 1) a system of dissipative free electrons in a driving electric field; and 2) the thermalization of two interacting electrons in a single orbital in a magnetic field -- the Hubbard atom. Our results demonstrate that algorithms for simulating open quantum systems are able to far outperform similarly complex non-dissipative algorithms on noisy hardware.
  arXiv  Detail & Related papers  (2021-08-02T21:36:37Z)
• Computational power of one- and two-dimensional dual-unitary quantum circuits [0.6946929968559495]
  Quantum circuits that are classically simulatable tell us when quantum computation becomes less powerful than or equivalent to classical computation. We make use of dual-unitary quantum circuits (DUQCs), which have been recently investigated as exactly solvable models of non-equilibrium physics.
  arXiv  Detail & Related papers  (2021-03-16T17:37:11Z)

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.