:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Karamchedu, Chaitanya, Fox, Matthew, Gottesman, Daniel
Format:	Preprint
Published:	2025
Subjects:	Quantum Physics Computational Complexity
Online Access:	https://arxiv.org/abs/2510.09931
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Criterion for Post-Selected Quantum Advantage
by: Karamchedu, Chaitanya, et al.
Published: (2024)

A Refinement of the McCreight-Meyer Union Theorem
by: Fox, Matthew, et al.
Published: (2024)

The rotation-invariant Hamiltonian problem is QMA$_{\rm EXP}$-complete
by: Nelson, Jon, et al.
Published: (2025)

Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes
by: Cardoso, Ricardo Rivera, et al.
Published: (2025)

Tight Bounds for Quantum Phase Estimation and Related Problems
by: Mande, Nikhil S., et al.
Published: (2023)

Improved Circuit Lower Bounds and Quantum-Classical Separations
by: Grewal, Sabee, et al.
Published: (2024)

Quantum Lovász Local Lemma: Shearer's Bound is Tight
by: He, Kun, et al.
Published: (2018)

Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates
by: Nelson, Jon, et al.
Published: (2024)

The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
by: Kahanamoku-Meyer, Gregory D., et al.
Published: (2024)

Lower Bounds on Relative Error Quantum Compression and Classical Shadows
by: Sankar, Kaushik
Published: (2025)

Quantum Query-Space Lower Bounds Using Branching Programs
by: Bera, Debajyoti, et al.
Published: (2024)

Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
by: Rosenthal, Gregory
Published: (2021)

Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
by: Wang, Qisheng, et al.
Published: (2024)

Improved Quantum Query Upper Bounds Based on Classical Decision Trees
by: Cornelissen, Arjan, et al.
Published: (2022)

Quantum Threshold is Powerful
by: Grier, Daniel, et al.
Published: (2024)

On Bounded Advice Classes
by: Marshall, Simon, et al.
Published: (2024)

The Round Complexity of Proofs in the Bounded Quantum Storage Model
by: Grilo, Alex B., et al.
Published: (2024)

Quantum LDPC Codes with Transversal Non-Clifford Gates via Products of Algebraic Codes
by: Golowich, Louis, et al.
Published: (2024)

Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics
by: Barch, Brian, et al.
Published: (2025)

Gate-based quantum simulation of Gaussian bosonic circuits on exponentially many modes
by: Barthe, Alice, et al.
Published: (2024)

Improved Lower Bounds for QAC0
by: Joshi, Malvika Raj, et al.
Published: (2025)

Bounding the computational power of bosonic systems
by: Upreti, Varun, et al.
Published: (2025)

Quantum Advantage from Sampling Shallow Circuits: Beyond Hardness of Marginals
by: Grier, Daniel, et al.
Published: (2025)

Certificate Games and Consequences for the Classical Adversary Bound
by: Chakraborty, Sourav, et al.
Published: (2022)

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

Logarithmic Depth Decomposition of Approximate Multi-Controlled Single-Qubit Gates Without Ancilla Qubits
by: Silva, Jefferson D. S., et al.
Published: (2025)

Lower Bounds for Unitary Property Testing with Proofs and Advice
by: Weggemans, Jordi
Published: (2024)

A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting
by: Chen, Kean, et al.
Published: (2025)

Generalization Error Bound for Quantum Machine Learning in NISQ Era -- A Survey
by: Khanal, Bikram, et al.
Published: (2024)

Quantum Property Testing for Bounded-Degree Directed Graphs
by: Peng, Pan, et al.
Published: (2026)

Fermionic Independent Set and Laplacian of an independence complex are QMA-hard
by: Rayudu, Chaithanya
Published: (2024)

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)

Locality Bounds for Sampling Hamming Slices
by: Kane, Daniel M., et al.
Published: (2024)

Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions
by: Yamakami, Tomoyuki
Published: (2023)

Quantum Automating $\mathbf{TC}^0$-Frege Is LWE-Hard
by: Arteche, Noel, et al.
Published: (2024)

Quantum Advantage in Decision Trees: A Weighted Graph and $L_1$ Norm Approach
by: Grillo, Sebastian Alberto, et al.
Published: (2026)

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
by: Gharibian, Sevag, et al.
Published: (2021)

New Quantum Algorithms for Computing Quantum Entropies and Distances
by: Wang, Qisheng, et al.
Published: (2022)

A Meta-Complexity Characterization of Quantum Cryptography
by: Cavalar, Bruno P., et al.
Published: (2024)

Optimal Bounds, Barriers, and Extensions for Non-Hermitian Bivariate Quantum Signal Processing
by: Courtney, Joshua M.
Published: (2026)