Cover Image

Quasi-quantum states and the quasi-quantum PCP theorem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Arad, Itai, Santha, Miklos
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

Beyond Bell sampling: stabilizer state learning and quantum pseudorandomness lower bounds on qudits
by: Allcock, Jonathan, et al.
Published: (2024)

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

Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
by: Allcock, Jonathan, et al.
Published: (2023)

Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
by: Allcock, Jonathan, et al.
Published: (2025)

Area laws and tensor networks for maximally mixed ground states
by: Arad, Itai, et al.
Published: (2023)

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

Guidable Local Hamiltonian Problems with Implications to Heuristic Ansätze State Preparation and the Quantum PCP Conjecture
by: Weggemans, Jordi, et al.
Published: (2023)

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

Local quantum channels giving rise to quasi-local Gibbs states
by: Arad, Itai, et al.
Published: (2024)

Learning stabilizer structure of quantum states
by: Arunachalam, Srinivasan, et al.
Published: (2025)

Quantum Merlin-Arthur proof systems for synthesizing quantum states
by: Delavenne, Hugo, et al.
Published: (2023)

An efficient quantum parallel repetition theorem and applications
by: Bostanci, John, et al.
Published: (2023)

Learning junta distributions, quantum junta states, and QAC$^0$ circuits
by: Bao, Jinge, et al.
Published: (2024)

On quantum functionals for higher-order tensors
by: Botero, Alonso, et al.
Published: (2026)

On the complexity of unique quantum witnesses and quantum approximate counting
by: Anshu, Anurag, et al.
Published: (2024)

Dissipative variational quantum algorithms for Gibbs state preparation
by: Ilin, Yigal, et al.
Published: (2024)

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

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)

Learning a quantum channel from its steady-state
by: Ilin, Yigal, et al.
Published: (2023)

Adversarially robust quantum state learning and testing
by: Aliakbarpour, Maryam, 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)

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

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

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)

On estimating the trace of quantum state powers
by: Liu, Yupan, et al.
Published: (2024)

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

Learning quantum states prepared by shallow circuits in polynomial time
by: Landau, Zeph, et al.
Published: (2024)

The role of shared randomness in quantum state certification with unentangled measurements
by: Liu, Yuhan, 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)

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

Optimal lower bounds for quantum state tomography
by: Scharnhorst, Thilo, et al.
Published: (2025)

Quantum state testing beyond the polarizing regime and quantum triangular discrimination
by: Liu, Yupan
Published: (2023)

Quantum Merlin-Arthur with an internally separable proof
by: Bassirian, Roozbeh, et al.
Published: (2024)

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