Cover Image

On the complexity of unique quantum witnesses and quantum approximate counting

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Anshu, Anurag, Haferkamp, Jonas, Hwang, Yeongwoo, Nguyen, Quynh T.
Format:	Preprint
Published:	2024
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Circuit-to-Hamiltonian from tensor networks and fault tolerance
by: Anshu, Anurag, et al.
Published: (2023)

Commuting Local Hamiltonians Beyond 2D
by: Bostanci, John, et al.
Published: (2024)

NLTS Hamiltonians from good quantum codes
by: Anshu, Anurag, et al.
Published: (2022)

On the average-case complexity of learning output distributions of quantum circuits
by: Nietner, Alexander, et al.
Published: (2023)

Gibbs state preparation for commuting Hamiltonian: Mapping to classical Gibbs sampling
by: Hwang, Yeongwoo, et al.
Published: (2024)

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

Efficient witnessing and testing of magic in mixed quantum states
by: Haug, Tobias, et al.
Published: (2025)

Incompressibility and spectral gaps of random circuits
by: Chen, Chi-Fang, et al.
Published: (2024)

Physical complexity and black hole quantum computers
by: Reilly, Michele, et al.
Published: (2025)

Separating QMA from QCMA with a classical oracle
by: Bostanci, John, et al.
Published: (2025)

Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines
by: Lemus, Mariano, et al.
Published: (2023)

Lower bounds for quantum-inspired classical algorithms via communication complexity
by: Mande, Nikhil S., et al.
Published: (2024)

Random unitaries in extremely low depth
by: Schuster, Thomas, et al.
Published: (2024)

On the quantum computational complexity of classical linear dynamics with geometrically local interactions: Dequantization and universality
by: Sakamoto, Kazuki, et al.
Published: (2025)

On the complexity of estimating ground state entanglement and free energy
by: Gharibian, Sevag, et al.
Published: (2025)

Learning quantum Gibbs states locally and efficiently
by: Chen, Chi-Fang, et al.
Published: (2025)

Information-Computation Gaps in Quantum Learning via Low-Degree Likelihood
by: Chen, Sitan, et al.
Published: (2025)

On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$
by: Yao, Penghui, et al.
Published: (2023)

Quasi-quantum states and the quasi-quantum PCP theorem
by: Arad, Itai, et al.
Published: (2024)

A quantum neural network framework for scalable quantum circuit approximation of unitary matrices
by: Sarkar, Rohit Sarma, et al.
Published: (2024)

Classical versus quantum queries in quantum PCPs with classical proofs
by: Buhrman, Harry, et al.
Published: (2024)

Learning quantum states and unitaries of bounded gate complexity
by: Zhao, Haimeng, et al.
Published: (2023)

Efficiently verifiable quantum advantage on near-term analog quantum simulators
by: Liu, Zhenning, et al.
Published: (2024)

Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
by: Anand, Kartik, et al.
Published: (2025)

Symmetric quantum computation
by: Castro-Silva, Davi, et al.
Published: (2025)

Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expanders
by: Iyer, Vishnu, et al.
Published: (2026)

The power of quantum circuits in sampling
by: Blanc, Guy, et al.
Published: (2025)

The 7 faces of quantum NP
by: Gharibian, Sevag
Published: (2023)

Improved quantum data analysis
by: Bădescu, Costin, et al.
Published: (2020)

Space-bounded quantum state testing via space-efficient quantum singular value transformation
by: Gall, François Le, et al.
Published: (2023)

Optimising quantum circuits is generally hard
by: van de Wetering, John, et al.
Published: (2023)

Random regular graph states are complex at almost any depth
by: Ghosh, Soumik, et al.
Published: (2024)

Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes
by: Dinur, Irit, et al.
Published: (2024)

The status of the quantum PCP conjecture (games version)
by: Natarajan, Anand, et al.
Published: (2024)

Space-bounded quantum interactive proof systems
by: Gall, François Le, et al.
Published: (2024)

Even quantum advice is unlikely to solve PP
by: Yirka, Justin
Published: (2024)

Peaked quantum advantage using error correction
by: Deshpande, Abhinav, et al.
Published: (2025)

Finding quantum partial assignments by search-to-decision reductions
by: Weggemans, Jordi
Published: (2024)

Distributed inner product estimation with limited quantum communication
by: Arunachalam, Srinivasan, et al.
Published: (2024)

The membership problem for constant-sized quantum correlations is undecidable
by: Fu, Honghao, et al.
Published: (2021)