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

Lilith Zschetzsche; Norbert Schuch; Refik Mansuroglu

arxiv: 2603.26561 · v2 · submitted 2026-03-27 · 🪐 quant-ph · cs.CC

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

Lilith Zschetzsche , Refik Mansuroglu , Norbert Schuch This is my paper

Pith reviewed 2026-05-14 22:42 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC

keywords BQP-completenessPostBQP-hardnessbosonic Hamiltoniansquadratic interactionsquantum simulationoscillator networksquantum walks

0 comments

The pith

A broad class of quadratic bosonic Hamiltonians can be simulated with the full power of BQP, while more general versions are PostBQP-hard.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that simulating the time evolution of many quadratic bosonic systems is BQP-complete, meaning a quantum computer can solve them efficiently and they are as hard as any problem a quantum computer can solve. This class covers classical oscillator networks and continuous-time quantum walks as special cases. When the Hamiltonians are allowed to take a slightly more general quadratic form, the simulation task becomes PostBQP-hard, which lies beyond what standard quantum computers can achieve even with post-selection. The result identifies a sharp boundary in the complexity of simulating large bosonic systems on quantum hardware.

Core claim

Simulating the dynamics generated by quadratic bosonic Hamiltonians is BQP-complete for a broad class of problems that includes classical oscillator networks and continuous-time quantum walks as special cases; extending the class to more general quadratic interactions yields PostBQP-hard instances.

What carries the argument

Reductions from known BQP-complete problems (oscillator networks and quantum walks) to quadratic bosonic Hamiltonians that preserve the quadratic structure and incur only polynomial overhead in the number of modes and simulation time.

If this is right

Classical oscillator networks can be simulated on a quantum computer with the same resources needed for general quantum circuit simulation.
Continuous-time quantum walks on graphs remain BQP-complete when realized as quadratic bosonic systems.
Slightly broader quadratic bosonic models cannot be simulated by any polynomial-time quantum algorithm unless the polynomial hierarchy collapses.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The identified boundary may limit the reach of quantum advantage for physical systems whose Hamiltonians stay close to the BQP-complete regime.
It raises the question whether intermediate classes of quadratic bosonic models exist that are neither BQP-complete nor PostBQP-hard.
Practical bosonic simulators in the laboratory could be tested for whether their interaction terms fall inside or outside the BQP-complete class.

Load-bearing premise

The reductions from quantum walks and oscillator networks to the bosonic Hamiltonians keep the interactions strictly quadratic and introduce no super-polynomial growth in system size or evolution time.

What would settle it

A classical polynomial-time algorithm that simulates the dynamics of one of the BQP-complete quadratic bosonic instances to within inverse-polynomial error, or a quantum polynomial-time algorithm for a PostBQP-hard instance.

Figures

Figures reproduced from arXiv: 2603.26561 by Lilith Zschetzsche, Norbert Schuch, Refik Mansuroglu.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper cleanly places a broad family of quadratic bosonic simulations at the BQP boundary and shows a sharp jump to PostBQP-hardness for the next natural extension.

read the letter

The core result is that a wide class of quadratic bosonic Hamiltonians is BQP-complete, with classical oscillator networks and continuous-time quantum walks recovered as direct special cases, and that allowing more general quadratic terms makes the problem PostBQP-hard. This gives a precise complexity threshold inside the quadratic regime rather than just another BQP-completeness proof for one more model. The unification is useful because it shows the same complexity class covers physically distinct systems without extra machinery. The PostBQP step is a clean contrast that highlights where classical simulation becomes intractable even before higher-order interactions appear. The reductions appear to map the known BQP-complete instances onto the bosonic quadratic form by direct substitution of the adjacency or coupling matrix into the A_ij coefficients, keeping the number of modes and evolution time polynomial. That avoids the super-polynomial overhead the stress-test worried about, so the hardness direction holds on the terms stated. The membership side follows from standard quantum simulation techniques for quadratic bosonic systems, which stay inside BQP when the quadratic form is fixed. One minor soft spot is that any truncation or cutoff needed for the bosonic Hilbert space must be shown not to introduce hidden exponential cost; the abstract implies the quadratic case stays exact, but the details matter for the claim. Overall the argument is self-contained and rests on explicit reductions rather than fitted parameters. This paper is for researchers working on quantum simulation complexity and bosonic systems. A reader who already knows the BQP-completeness of quantum walks and oscillator networks will see the value in the unified treatment and the PostBQP threshold. It deserves a serious referee because the boundary it draws is sharp enough to be worth checking the technical mappings in detail.

Referee Report

2 major / 2 minor

Summary. The manuscript proves BQP-completeness for simulating the dynamics of a broad class of quadratic bosonic Hamiltonians, with classical oscillator networks and continuous-time quantum walks as special cases obtained by suitable restrictions on the quadratic form. It further shows that allowing more general quadratic terms renders the simulation problem PostBQP-hard, establishing a sharp complexity transition between BQP and PostBQP regimes for bosonic systems.

Significance. If the reductions are polynomial, the work supplies a clean complexity-theoretic demarcation for bosonic Hamiltonian simulation, directly linking two previously known BQP-complete models to a physically motivated bosonic setting and quantifying the jump to PostBQP when the quadratic restriction is relaxed. This strengthens the theoretical foundation for quantum algorithms targeting bosonic systems and clarifies the separation between classical and quantum simulation power for these Hamiltonians.

major comments (2)

[§3] §3 (reduction from continuous-time quantum walks): the explicit mapping that encodes an arbitrary graph adjacency matrix into the quadratic bosonic matrix A_{ij} must be shown to use only polynomially many modes and polynomially bounded evolution time; any super-polynomial blow-up in mode count or truncation error would invalidate the BQP-hardness direction.
[§4] §4 (PostBQP-hardness extension): the precise additional quadratic terms that trigger PostBQP-hardness are load-bearing; the proof must confirm that these terms remain strictly quadratic (no hidden higher-order interactions introduced by the encoding) while still allowing an efficient reduction from a PostBQP-complete problem.

minor comments (2)

[§2] Notation for the bosonic creation/annihilation operators and the quadratic matrix A should be introduced once in §2 and used uniformly thereafter to avoid minor inconsistencies across lemmas.
The abstract states that the class 'includes two known BQP-complete problems as special cases' but does not name the precise parameter restrictions; a single sentence clarifying the restrictions would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments, which help clarify the technical requirements for our complexity results. We address each major comment below and will make the requested clarifications and explicit constructions in the revised manuscript.

read point-by-point responses

Referee: [§3] §3 (reduction from continuous-time quantum walks): the explicit mapping that encodes an arbitrary graph adjacency matrix into the quadratic bosonic matrix A_{ij} must be shown to use only polynomially many modes and polynomially bounded evolution time; any super-polynomial blow-up in mode count or truncation error would invalidate the BQP-hardness direction.

Authors: We agree that an explicit polynomial-resource analysis is essential to establish BQP-hardness. In the revised version of §3 we will add a dedicated subsection providing the explicit mapping: for an n-vertex graph the bosonic system uses exactly n modes (one per vertex), the quadratic matrix A is constructed directly from the adjacency matrix scaled by a polynomial factor (specifically A_{jk} = i Adj(G)_{jk} with a global polynomial prefactor), and the evolution time is bounded by t = O(n^2) to ensure the continuous-time quantum walk dynamics are simulated to inverse-polynomial precision. We further include a truncation-error bound showing that the error incurred by restricting to a finite Fock-space cutoff is at most exp(−Ω(n)), which remains negligible under polynomial-time reductions. These additions confirm that both mode count and total resources are polynomial, preserving the BQP-completeness claim. revision: yes
Referee: [§4] §4 (PostBQP-hardness extension): the precise additional quadratic terms that trigger PostBQP-hardness are load-bearing; the proof must confirm that these terms remain strictly quadratic (no hidden higher-order interactions introduced by the encoding) while still allowing an efficient reduction from a PostBQP-complete problem.

Authors: We appreciate the referee’s emphasis on verifying the strictly quadratic character of the extended Hamiltonians. In the revised §4 we will explicitly state that the additional terms are of the form ∑_{j,k} (α_{jk} a†_j a_k + β_{jk} a_j a_k + h.c.), which are purely quadratic in the bosonic operators and introduce no higher-order interactions. The reduction from a PostBQP-complete problem (a post-selected linear-optical computation) maps directly onto these quadratic coefficients using a polynomial number of modes; the coefficient matrices are computable in polynomial time and the encoding introduces no approximation steps that could generate effective higher-order terms. We will add a short lemma confirming that the resulting Hamiltonian remains exactly quadratic and that the overall reduction is efficient, thereby establishing the PostBQP-hardness result without modification to the claimed complexity transition. revision: yes

Circularity Check

0 steps flagged

No circularity; BQP-completeness established via explicit reductions to independently known problems

full rationale

The paper's core claims rest on defining a broad class of quadratic bosonic Hamiltonians and proving BQP-completeness by exhibiting two known BQP-complete problems (classical oscillator networks and continuous-time quantum walks) as special cases within that class. These reductions are described as preserving the quadratic structure with no super-polynomial overhead in modes or time. The base problems are established independently in prior literature outside this work, and the derivation does not rely on self-definitional mappings, fitted parameters renamed as predictions, or load-bearing self-citations. The PostBQP-hardness extension for more general quadratics is likewise a direct complexity separation without circular reduction to the paper's own inputs. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result relies only on standard definitions of BQP and PostBQP together with the ability to encode known complete problems into quadratic bosonic Hamiltonians; no free parameters, ad-hoc axioms, or new entities are introduced.

axioms (1)

standard math Standard definitions of BQP and PostBQP as complexity classes
The completeness statements are with respect to these established classes.

pith-pipeline@v0.9.0 · 5459 in / 1298 out tokens · 42348 ms · 2026-05-14T22:42:43.736414+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Quantum criticality beyond thermodynamic stability
quant-ph 2026-05 unverdicted novelty 8.0

For dynamically stable quadratic bosonic Hamiltonians, the Krein gap acts as the spectral gap; its closure at exceptional points or Krein collisions produces long-range correlations in the quasiparticle vacuum and is ...

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages · cited by 1 Pith paper

[1]

Kraus, Phys

B. Kraus, Phys. Rev. Lett.107, 250503 (2011)

work page 2011
[2]

Chatziioannou, K

R. Babbush, D. W. Berry, R. Kothari, R. D. Somma, and N. Wiebe, Physical Review X13, 10.1103/phys- revx.13.041041 (2023)

work page doi:10.1103/phys- 2023
[3]

A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, inProceedings of the thirty-fifth an- nual ACM symposium on Theory of computing, STOC03 (ACM, 2003). 6

work page 2003
[4]

A. M. Childs, Physical Review Letters102, 10.1103/physrevlett.102.180501 (2009)

work page doi:10.1103/physrevlett.102.180501 2009
[5]

R. D. Somma, R. King, R. Kothari, T. O’Brien, and R. Babbush, Shadow hamiltonian simulation (2025), arXiv:2407.21775 [quant-ph]

work page arXiv 2025
[6]

Gleinig and T

N. Gleinig and T. Hoefler, in2021 58th ACM/IEEE De- sign Automation Conference (DAC)(2021) pp. 433–438

work page 2021
[7]

Ramacciotti, A.-I

D. Ramacciotti, A.-I. Lefterovici, and A. F. Rotundo, A simple quantum algorithm to efficiently prepare sparse states (2023), arXiv:2310.19309 [quant-ph]

work page arXiv 2023
[8]

Zschetzsche, R

L. Zschetzsche, R. Mansuroglu, A. Moln´ ar, and N. Schuch, Direct equivalence between dynamics of quantum walks and coupled classical oscillators (2025), arXiv:2512.03681 [quant-ph]

work page arXiv 2025
[9]

D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Physical Review Letters114, 10.1103/physrevlett.114.090502 (2015)

work page doi:10.1103/physrevlett.114.090502 2015
[10]

D. W. Berry, A. M. Childs, and R. Kothari, in2015 IEEE 56th Annual Symposium on Foundations of Com- puter Science(IEEE, 2015) p. 792–809

work page 2015
[11]

G. H. Low and I. L. Chuang, Physical Review Letters 118, 10.1103/physrevlett.118.010501 (2017)

work page doi:10.1103/physrevlett.118.010501 2017
[12]

G. H. Low and I. L. Chuang, Quantum3, 163 (2019)

work page 2019
[13]

Barthe, M

A. Barthe, M. Cerezo, A. T. Sornborger, M. Larocca, and D. Garc´ ıa-Mart´ ın, Physical Review Letters134, 10.1103/physrevlett.134.070604 (2025)

work page doi:10.1103/physrevlett.134.070604 2025
[14]

Barthe, private communication (2025)

A. Barthe, private communication (2025)

work page 2025
[15]

Quantum computing, postselection, and probabilistic polynomial-time,

S. Aaronson, Quantum computing, postselection, and probabilistic polynomial-time (2004), arXiv:quant- ph/0412187 [quant-ph]

work page arXiv 2004
[16]

Simon, inMathematical Quantum Theory I: Field Theory and Many-Body Theory, CRM Proceedings and Lecture Notes, Vol

B. Simon, inMathematical Quantum Theory I: Field Theory and Many-Body Theory, CRM Proceedings and Lecture Notes, Vol. 7, edited by J. Feldman, J. Froehlich, and V. Rivasseau (American Mathematical Society, Prov- idence, RI, 1995) pp. 109–149

work page 1995
[17]

Teschl,Jacobi Operators and Completely Integrable Nonlinear Lattices, Mathematical Surveys and Mono- graphs, Vol

G. Teschl,Jacobi Operators and Completely Integrable Nonlinear Lattices, Mathematical Surveys and Mono- graphs, Vol. 72 (American Mathematical Society, Provi- dence, RI, 2000). Appendix A: Post-Processing of Measurement Data In this appendix, we extend the discussion on the read-out of quadrature expectation values and discuss how to reconstruct the expec...

work page 2000
[18]

clock register

PostBQP-completeness Construction PostBQP(Postselected Bounded-Error Quantum Polynomial Time) is the class of decision problems solvable by a polynomial-time quantum algorithm that is allowed to postselect on the outcome of a measurement [15]. The naturalPostBQP-complete problem ispostselected circuit: Consider a quantum register consisting ofnqubits – a ...

work page
[19]

Formal Solution to the Bosonic Problem The equations of motion defined in Eqs. (B2-B5) can be rewritten as the following second order linear differential equation inq: ¨q(l) j = −(A−(E +)2)⟨q⟩ (l) j =: h − ˜A⟨q⟩ i(l) j ,(B8) 9 with ˜A:=A−(E +)2, which ceases to be positive semidefinite for large enoughβ. The momentum coordinatesp (l) j can be transformed ...

work page
[20]

Separation of Quantum Circuit Logic and Dynamics on the Clock Register To analyze the matrix ˜Awhich generates the dynamics, we separate the quantum circuit logic, encoded in the Ul, from the hopping Hamiltonian acting on the clock register{|l⟩} L+2 l=1 . This can be achieved through the basis transformation S= L+2X l=1 |l⟩ ⟨l| ⊗U L+1 · · ·U l .(B12) The ...

work page
[21]

Dynamics of the clock register: Tight binding model The matricesX 0 andX 1 are finite Jacobi matrices. Intuitively,X 0 describes a single particle hopping on a one- dimensional chain; this can also be considered as the lattice discretization of a free particle on a finite line.X 1 differs fromX 0 in that it additionally has a single-site potential well at...

work page
[22]

Time Evolution and Read-Out After evolution for a timet, the state ˙q(t) = cos( √ X t) ˙q(0) , expressed in the quantum register notation, will be |Φ(t)⟩= cos( √ X t) h |l= 1⟩ ⊗U|0 P 0Q0R⟩ i (B15) (B13) = cos( √ X t) h |l= 1⟩ ⊗( p 1−δ 2 |0P Ψ0⟩+δ|1 P Ψ1⟩) i (B16) = p 1−δ 2 h cos( p X0 t)|l= 1⟩ i ⊗ |0P Ψ0⟩+δ h cos( p X1 t)|l= 1⟩ i ⊗ |1P Ψ1⟩.(B17) We now us...

work page
[23]

We solve the spectrum of the matricesX 0 andX 1, defined in Section B 3

Solution of the Tight-Binding Model on the Clock Register The purpose of this Section is to establish the technical bound underlying the amplitude separation induced by the final-layer perturbation. We solve the spectrum of the matricesX 0 andX 1, defined in Section B 3. The spectral prop- erties of the matricesX 0 andX 1 follow from standard results for ...

work page
[24]

There exists a unique negative eigenvalueα 1 = 4−2 cosh(κ1), separated from zero by a constant,α 1 ≤4−β 2 <0

work page
[25]

The corresponding eigenvector|ψ 1⟩has an overlap|⟨l= 1|ψ 1⟩|2 = Ω e−2Lκ1 L+2

work page
[26]

12 Proof.1

The corresponding eigenvector|ψ 1⟩has an overlap|⟨l=L+ 1|ψ 1⟩|2 = Ω(1)that is separated from zero by a constant. 12 Proof.1. We start from Eq. (B27) and bound cosh(κ1) =β 2 −sinh(κ 1) coth((L+ 2)κ1) =β 2 −tanh(κ 1) cosh(κ1) coth((L+ 2)κ1),(B28) substituting sinh(κ1) = tanh(κ1) cosh(κ1). Now, we solve again for cosh(κ 1) to get cosh(κ1) = β2 1 + tanh(κ1) c...

work page
[27]

Thus, |⟨l= 1|ψ 1⟩| ≥ 1√ L+ 2 sinh(κ1) sinh((L+ 2)κ 1) = Θ e−Lκ1 √ L+ 2 .(B31)

Consider the normalized eigenvector corresponding to the eigenvalueα 1 |ψ1⟩=c 1 L+2X l′=1 sinh(l′κ1)|l ′⟩withc 1 = L+2X l′=1 sinh(l′κ1)2 !− 1 2 = 2 sinh((2L+ 5)κ 1) sinh(κ1) −(2L+ 5) − 1 2 ,(B30) We bound the overlap with thel= 1 using the inequalityc 1 ≥ 1√L+2 · 1 sinh((L+2)κ1). Thus, |⟨l= 1|ψ 1⟩| ≥ 1√ L+ 2 sinh(κ1) sinh((L+ 2)κ 1) = Θ e−Lκ1 √ L+ 2 .(B31)

work page
[28]

Using partial sums of the geometric series, one can calculate c1 = 2 sinh((2L+5)κ1) sinh(κ1) −(2L+ 5) − 1 2

The third statement can be similarly bounded. Using partial sums of the geometric series, one can calculate c1 = 2 sinh((2L+5)κ1) sinh(κ1) −(2L+ 5) − 1 2 . With this, we can bound |⟨l=L+ 1|ψ 1⟩|2 = 2 sinh((L+ 1)κ 1)2 sinh((2L+5)κ1) sinh(κ1) −(2L+ 5) ≥2 sinh(κ 1) e2(L+1)κ1 −2 e(2L+5)κ1 ≥2 sinh(κ 1)e−3κ1(1−2e −2κ1),(B32) by dropping positive terms in the nu...

work page
[29]

One might wonder how restrictive the choice of nonzeroE + is forPostBQP-hardness

Alternative PostBQP-hard families of bosonic Hamiltonians At the end of this appendix, let us argue that the hardness result is robust under more general choices ofE +. One might wonder how restrictive the choice of nonzeroE + is forPostBQP-hardness. Indeed,PostBQP-hard instances can be found in a more general class of Hamiltonians. Off-diagonal termsq jp...

work page
[30]

(B3) andZandYare Pauli matrices

(E −)2 =−β 2Π with an adequate projector Π onto the postselected part of the readout layer These conditions can be implemented, for instance, by defining two Feynman-Kitaev dynamics on a doubled system A=A F K ⊗Z(B35) C=1⊗Z(B36) E− =β|L+ 2⟩ ⟨L+ 2| ⊗ |1 P ⟩ ⟨1P | ⊗(iY) (B37) withA F K being the matrix defined in Eq. (B3) andZandYare Pauli matrices. One can...

work page
[31]

Hermitian) partE− contributing with terms of the form 1 2 Ejk(qjpk −qkpj)

Most General Quadratic Bosonic Hamiltonian The most general quadratic Hamiltonian can be written as H= 1 2 q p A E ET C q p ,(C1) where the matrixE=E + +iE − can be split into a real and symmetric partE + contributing with terms 1 2 Ejk(qjpk + qkpj) and an imaginary, antisymmetric (i.e. Hermitian) partE− contributing with terms of the form 1 2 Ejk(qjpk −q...

work page
[32]

If in addition to positivity ofAandC, the matrix elements are derived from positive coupling constants (cf

Positivity of coupling matricesAandC As we show in the main text, coordinates can be chosen asB †qandD †pforA=BB † andC=DD †, such that correlations evolve unitarily in the absence of mixed terms,E= 0. If in addition to positivity ofAandC, the matrix elements are derived from positive coupling constants (cf. Eqs. (17) and (18)), an explicit and efficientl...

work page
[33]

(C2),R-point correlations of⟨iq⟩and⟨p⟩can also be directly simulated (without trans- forming into the coordinatesB †qandD †p) by switching off the non-Hermitian termsE + = ∆ = 0

Symplectic Transformations and Generalized Hopping Upon inspection of Eq. (C2),R-point correlations of⟨iq⟩and⟨p⟩can also be directly simulated (without trans- forming into the coordinatesB †qandD †p) by switching off the non-Hermitian termsE + = ∆ = 0. This extends the family of quantum walk Hamiltonians discussed in the main text (cf. Eq. (16)) by extend...

work page

[1] [1]

Kraus, Phys

B. Kraus, Phys. Rev. Lett.107, 250503 (2011)

work page 2011

[2] [2]

Chatziioannou, K

R. Babbush, D. W. Berry, R. Kothari, R. D. Somma, and N. Wiebe, Physical Review X13, 10.1103/phys- revx.13.041041 (2023)

work page doi:10.1103/phys- 2023

[3] [3]

A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, inProceedings of the thirty-fifth an- nual ACM symposium on Theory of computing, STOC03 (ACM, 2003). 6

work page 2003

[4] [4]

A. M. Childs, Physical Review Letters102, 10.1103/physrevlett.102.180501 (2009)

work page doi:10.1103/physrevlett.102.180501 2009

[5] [5]

R. D. Somma, R. King, R. Kothari, T. O’Brien, and R. Babbush, Shadow hamiltonian simulation (2025), arXiv:2407.21775 [quant-ph]

work page arXiv 2025

[6] [6]

Gleinig and T

N. Gleinig and T. Hoefler, in2021 58th ACM/IEEE De- sign Automation Conference (DAC)(2021) pp. 433–438

work page 2021

[7] [7]

Ramacciotti, A.-I

D. Ramacciotti, A.-I. Lefterovici, and A. F. Rotundo, A simple quantum algorithm to efficiently prepare sparse states (2023), arXiv:2310.19309 [quant-ph]

work page arXiv 2023

[8] [8]

Zschetzsche, R

L. Zschetzsche, R. Mansuroglu, A. Moln´ ar, and N. Schuch, Direct equivalence between dynamics of quantum walks and coupled classical oscillators (2025), arXiv:2512.03681 [quant-ph]

work page arXiv 2025

[9] [9]

D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Physical Review Letters114, 10.1103/physrevlett.114.090502 (2015)

work page doi:10.1103/physrevlett.114.090502 2015

[10] [10]

D. W. Berry, A. M. Childs, and R. Kothari, in2015 IEEE 56th Annual Symposium on Foundations of Com- puter Science(IEEE, 2015) p. 792–809

work page 2015

[11] [11]

G. H. Low and I. L. Chuang, Physical Review Letters 118, 10.1103/physrevlett.118.010501 (2017)

work page doi:10.1103/physrevlett.118.010501 2017

[12] [12]

G. H. Low and I. L. Chuang, Quantum3, 163 (2019)

work page 2019

[13] [13]

Barthe, M

A. Barthe, M. Cerezo, A. T. Sornborger, M. Larocca, and D. Garc´ ıa-Mart´ ın, Physical Review Letters134, 10.1103/physrevlett.134.070604 (2025)

work page doi:10.1103/physrevlett.134.070604 2025

[14] [14]

Barthe, private communication (2025)

A. Barthe, private communication (2025)

work page 2025

[15] [15]

Quantum computing, postselection, and probabilistic polynomial-time,

S. Aaronson, Quantum computing, postselection, and probabilistic polynomial-time (2004), arXiv:quant- ph/0412187 [quant-ph]

work page arXiv 2004

[16] [16]

Simon, inMathematical Quantum Theory I: Field Theory and Many-Body Theory, CRM Proceedings and Lecture Notes, Vol

B. Simon, inMathematical Quantum Theory I: Field Theory and Many-Body Theory, CRM Proceedings and Lecture Notes, Vol. 7, edited by J. Feldman, J. Froehlich, and V. Rivasseau (American Mathematical Society, Prov- idence, RI, 1995) pp. 109–149

work page 1995

[17] [17]

Teschl,Jacobi Operators and Completely Integrable Nonlinear Lattices, Mathematical Surveys and Mono- graphs, Vol

G. Teschl,Jacobi Operators and Completely Integrable Nonlinear Lattices, Mathematical Surveys and Mono- graphs, Vol. 72 (American Mathematical Society, Provi- dence, RI, 2000). Appendix A: Post-Processing of Measurement Data In this appendix, we extend the discussion on the read-out of quadrature expectation values and discuss how to reconstruct the expec...

work page 2000

[18] [18]

clock register

PostBQP-completeness Construction PostBQP(Postselected Bounded-Error Quantum Polynomial Time) is the class of decision problems solvable by a polynomial-time quantum algorithm that is allowed to postselect on the outcome of a measurement [15]. The naturalPostBQP-complete problem ispostselected circuit: Consider a quantum register consisting ofnqubits – a ...

work page

[19] [19]

Formal Solution to the Bosonic Problem The equations of motion defined in Eqs. (B2-B5) can be rewritten as the following second order linear differential equation inq: ¨q(l) j = −(A−(E +)2)⟨q⟩ (l) j =: h − ˜A⟨q⟩ i(l) j ,(B8) 9 with ˜A:=A−(E +)2, which ceases to be positive semidefinite for large enoughβ. The momentum coordinatesp (l) j can be transformed ...

work page

[20] [20]

Separation of Quantum Circuit Logic and Dynamics on the Clock Register To analyze the matrix ˜Awhich generates the dynamics, we separate the quantum circuit logic, encoded in the Ul, from the hopping Hamiltonian acting on the clock register{|l⟩} L+2 l=1 . This can be achieved through the basis transformation S= L+2X l=1 |l⟩ ⟨l| ⊗U L+1 · · ·U l .(B12) The ...

work page

[21] [21]

Dynamics of the clock register: Tight binding model The matricesX 0 andX 1 are finite Jacobi matrices. Intuitively,X 0 describes a single particle hopping on a one- dimensional chain; this can also be considered as the lattice discretization of a free particle on a finite line.X 1 differs fromX 0 in that it additionally has a single-site potential well at...

work page

[22] [22]

Time Evolution and Read-Out After evolution for a timet, the state ˙q(t) = cos( √ X t) ˙q(0) , expressed in the quantum register notation, will be |Φ(t)⟩= cos( √ X t) h |l= 1⟩ ⊗U|0 P 0Q0R⟩ i (B15) (B13) = cos( √ X t) h |l= 1⟩ ⊗( p 1−δ 2 |0P Ψ0⟩+δ|1 P Ψ1⟩) i (B16) = p 1−δ 2 h cos( p X0 t)|l= 1⟩ i ⊗ |0P Ψ0⟩+δ h cos( p X1 t)|l= 1⟩ i ⊗ |1P Ψ1⟩.(B17) We now us...

work page

[23] [23]

We solve the spectrum of the matricesX 0 andX 1, defined in Section B 3

Solution of the Tight-Binding Model on the Clock Register The purpose of this Section is to establish the technical bound underlying the amplitude separation induced by the final-layer perturbation. We solve the spectrum of the matricesX 0 andX 1, defined in Section B 3. The spectral prop- erties of the matricesX 0 andX 1 follow from standard results for ...

work page

[24] [24]

There exists a unique negative eigenvalueα 1 = 4−2 cosh(κ1), separated from zero by a constant,α 1 ≤4−β 2 <0

work page

[25] [25]

The corresponding eigenvector|ψ 1⟩has an overlap|⟨l= 1|ψ 1⟩|2 = Ω e−2Lκ1 L+2

work page

[26] [26]

12 Proof.1

The corresponding eigenvector|ψ 1⟩has an overlap|⟨l=L+ 1|ψ 1⟩|2 = Ω(1)that is separated from zero by a constant. 12 Proof.1. We start from Eq. (B27) and bound cosh(κ1) =β 2 −sinh(κ 1) coth((L+ 2)κ1) =β 2 −tanh(κ 1) cosh(κ1) coth((L+ 2)κ1),(B28) substituting sinh(κ1) = tanh(κ1) cosh(κ1). Now, we solve again for cosh(κ 1) to get cosh(κ1) = β2 1 + tanh(κ1) c...

work page

[27] [27]

Thus, |⟨l= 1|ψ 1⟩| ≥ 1√ L+ 2 sinh(κ1) sinh((L+ 2)κ 1) = Θ e−Lκ1 √ L+ 2 .(B31)

Consider the normalized eigenvector corresponding to the eigenvalueα 1 |ψ1⟩=c 1 L+2X l′=1 sinh(l′κ1)|l ′⟩withc 1 = L+2X l′=1 sinh(l′κ1)2 !− 1 2 = 2 sinh((2L+ 5)κ 1) sinh(κ1) −(2L+ 5) − 1 2 ,(B30) We bound the overlap with thel= 1 using the inequalityc 1 ≥ 1√L+2 · 1 sinh((L+2)κ1). Thus, |⟨l= 1|ψ 1⟩| ≥ 1√ L+ 2 sinh(κ1) sinh((L+ 2)κ 1) = Θ e−Lκ1 √ L+ 2 .(B31)

work page

[28] [28]

Using partial sums of the geometric series, one can calculate c1 = 2 sinh((2L+5)κ1) sinh(κ1) −(2L+ 5) − 1 2

The third statement can be similarly bounded. Using partial sums of the geometric series, one can calculate c1 = 2 sinh((2L+5)κ1) sinh(κ1) −(2L+ 5) − 1 2 . With this, we can bound |⟨l=L+ 1|ψ 1⟩|2 = 2 sinh((L+ 1)κ 1)2 sinh((2L+5)κ1) sinh(κ1) −(2L+ 5) ≥2 sinh(κ 1) e2(L+1)κ1 −2 e(2L+5)κ1 ≥2 sinh(κ 1)e−3κ1(1−2e −2κ1),(B32) by dropping positive terms in the nu...

work page

[29] [29]

One might wonder how restrictive the choice of nonzeroE + is forPostBQP-hardness

Alternative PostBQP-hard families of bosonic Hamiltonians At the end of this appendix, let us argue that the hardness result is robust under more general choices ofE +. One might wonder how restrictive the choice of nonzeroE + is forPostBQP-hardness. Indeed,PostBQP-hard instances can be found in a more general class of Hamiltonians. Off-diagonal termsq jp...

work page

[30] [30]

(B3) andZandYare Pauli matrices

(E −)2 =−β 2Π with an adequate projector Π onto the postselected part of the readout layer These conditions can be implemented, for instance, by defining two Feynman-Kitaev dynamics on a doubled system A=A F K ⊗Z(B35) C=1⊗Z(B36) E− =β|L+ 2⟩ ⟨L+ 2| ⊗ |1 P ⟩ ⟨1P | ⊗(iY) (B37) withA F K being the matrix defined in Eq. (B3) andZandYare Pauli matrices. One can...

work page

[31] [31]

Hermitian) partE− contributing with terms of the form 1 2 Ejk(qjpk −qkpj)

Most General Quadratic Bosonic Hamiltonian The most general quadratic Hamiltonian can be written as H= 1 2 q p A E ET C q p ,(C1) where the matrixE=E + +iE − can be split into a real and symmetric partE + contributing with terms 1 2 Ejk(qjpk + qkpj) and an imaginary, antisymmetric (i.e. Hermitian) partE− contributing with terms of the form 1 2 Ejk(qjpk −q...

work page

[32] [32]

If in addition to positivity ofAandC, the matrix elements are derived from positive coupling constants (cf

Positivity of coupling matricesAandC As we show in the main text, coordinates can be chosen asB †qandD †pforA=BB † andC=DD †, such that correlations evolve unitarily in the absence of mixed terms,E= 0. If in addition to positivity ofAandC, the matrix elements are derived from positive coupling constants (cf. Eqs. (17) and (18)), an explicit and efficientl...

work page

[33] [33]

(C2),R-point correlations of⟨iq⟩and⟨p⟩can also be directly simulated (without trans- forming into the coordinatesB †qandD †p) by switching off the non-Hermitian termsE + = ∆ = 0

Symplectic Transformations and Generalized Hopping Upon inspection of Eq. (C2),R-point correlations of⟨iq⟩and⟨p⟩can also be directly simulated (without trans- forming into the coordinatesB †qandD †p) by switching off the non-Hermitian termsE + = ∆ = 0. This extends the family of quantum walk Hamiltonians discussed in the main text (cf. Eq. (16)) by extend...

work page