Cover Image

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

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Zschetzsche, Lilith, Mansuroglu, Refik, Schuch, Norbert
Format:	Preprint
Published:	2026
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Acrobatics of BQP
by: Aaronson, Scott, et al.
Published: (2021)

Direct Equivalence between Dynamics of Quantum Walks and Coupled Classical Oscillators
by: Zschetzsche, Lilith, et al.
Published: (2025)

A Relativizing MIP for BQP
by: Aaronson, Scott, et al.
Published: (2026)

Extensively Not P-Bi-Immune promiseBQP-Complete Languages
by: Jackson, Andrew
Published: (2024)

Plethysm is in #BQP
by: Christandl, Matthias, et al.
Published: (2026)

BQP, meet NP: Search-to-decision reductions and approximate counting
by: Gharibian, Sevag, et al.
Published: (2024)

$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)
by: Grier, Daniel, et al.
Published: (2026)

Preparation Circuits for Matrix Product States by Classical Variational Disentanglement
by: Mansuroglu, Refik, et al.
Published: (2025)

Towards a universal gateset for $\mathsf{QMA}_1$
by: Rudolph, Dorian
Published: (2024)

From Worst-Case Hardness of $\mathsf{NP}$ to Quantum Cryptography via Quantum Indistinguishability Obfuscation
by: Morimae, Tomoyuki, et al.
Published: (2025)

A Brief Note on a Recent Claim About NP-Hard Problems and BQP
by: Chavrimootoo, Michael C.
Published: (2024)

On Condensation of Block Sensitivity, Certificate Complexity and the $\mathsf{AND}$ (and $\mathsf{OR}$) Decision Tree Complexity
by: Nalli, Sai Soumya, et al.
Published: (2026)

Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth
by: Hsieh, Min-Hsiu, et al.
Published: (2024)

Search versus Decision for $\mathsf{S}_2^\mathsf{P}$
by: Fortnow, Lance
Published: (2025)

Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation
by: Rudolph, Dorian, et al.
Published: (2024)

Total Variation Distance for Product Distributions is $\#\mathsf{P}$-Complete
by: Bhattacharyya, Arnab, et al.
Published: (2024)

NP-hard problems are not in BQP
by: Czerwinski, Reiner
Published: (2023)

Bosonic Quantum Computational Complexity
by: Chabaud, Ulysse, et al.
Published: (2024)

Total Search Problems in $\mathsf{ZPP}$
by: Fleming, Noah, et al.
Published: (2025)

Improved Hardness Results for the Guided Local Hamiltonian Problem
by: Cade, Chris, et al.
Published: (2022)

The Complexity of Stoquastic Sparse Hamiltonians
by: Grilo, Alex B., et al.
Published: (2026)

Beating the natural Grover bound for low-energy estimation and state preparation
by: Buhrman, Harry, et al.
Published: (2024)

Complexity-theoretic foundations of BosonSampling with a linear number of modes
by: Bouland, Adam, et al.
Published: (2023)

Hyperinvariant Spin Network States -- An AdS/CFT Model from First Principles
by: Otto, Fynn, et al.
Published: (2025)

Coherent-State Propagation: A Computational Framework for Simulating Bosonic Quantum Systems
by: Guseynov, Nikita, et al.
Published: (2026)

On the Complexity of the Succinct State Local Hamiltonian Problem
by: Waite, Gabriel, et al.
Published: (2025)

Entanglement-Dependent Error Bounds for Hamiltonian Simulation
by: Kulkarni, Prateek P.
Published: (2026)

Positive bias makes tensor-network contraction tractable
by: Jiang, Jiaqing, et al.
Published: (2024)

The Complexity of Local Stoquastic Hamiltonians on 2D Lattices
by: Waite, Gabriel, et al.
Published: (2025)

Complexity Classification of Product State Problems for Local Hamiltonians
by: Kallaugher, John, et al.
Published: (2024)

On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity
by: Grewal, Sabee, et al.
Published: (2025)

The $\mathsf{AC}^0$-Complexity Of Visibly Pushdown Languages
by: Göller, Stefan, et al.
Published: (2023)

Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States
by: Cade, Chris, et al.
Published: (2022)

Error Mitigation of BQP Computations using Measurement-Based Verification
by: Harris, Joseph, et al.
Published: (2023)

Problem specific classical optimization of Hamiltonian simulation
by: Mansuroglu, Refik, et al.
Published: (2023)

The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians
by: Waite, Gabriel
Published: (2025)

Exponential improvements to the average-case hardness of BosonSampling
by: Bouland, Adam, et al.
Published: (2024)

On the Unprovability of Circuit Size Bounds in Intuitionistic $\mathsf{S}^1_2$
by: Chen, Lijie, et al.
Published: (2024)

Forrelation is Extremally Hard
by: Girish, Uma, et al.
Published: (2025)

Modern Hopfield Networks Require Chain-of-Thought to Solve $\mathsf{NC}^1$-Hard Problems
by: Cao, Yang, et al.
Published: (2024)