Copertina

How hard is it to verify a classical shadow?

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Karaiskos, Georgios, Rudolph, Dorian, Meyer, Johannes Jakob, Eisert, Jens, Gharibian, Sevag
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Quantum Physics Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
di: Aldi, Marco, et al.
Pubblicazione: (2024)

Quantum k-SAT Related Hypergraph Problems
di: Kremer, Simon-Luca, et al.
Pubblicazione: (2025)

Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
di: Agarwal, Avantika, et al.
Pubblicazione: (2024)

The 7 faces of quantum NP
di: Gharibian, Sevag
Pubblicazione: (2023)

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

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

Hardness of approximation for ground state problems
di: Gharibian, Sevag, et al.
Pubblicazione: (2024)

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

The Complexity of Translationally Invariant Problems beyond Ground State Energies
di: Watson, James D., et al.
Pubblicazione: (2020)

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

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

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

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

On the Complexity of Pure-State Consistency of Local Density Matrices
di: Kamminga, Jonas, et al.
Pubblicazione: (2024)

Interactive proofs for verifying (quantum) learning and testing
di: Caro, Matthias C., et al.
Pubblicazione: (2024)

En Route to a Standard QMA1 vs. QCMA Oracle Separation
di: Miloschewsky, David, et al.
Pubblicazione: (2026)

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

Computational relative entropy
di: Meyer, Johannes Jakob, et al.
Pubblicazione: (2025)

The computational two-way quantum capacity
di: Meyer, Johannes Jakob, et al.
Pubblicazione: (2026)

A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization
di: Schreiber, Franz J., et al.
Pubblicazione: (2025)

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

Fault-tolerant compiling of classically hard IQP circuits on hypercubes
di: Hangleiter, Dominik, et al.
Pubblicazione: (2024)

Complexity and hardness of random peaked circuits
di: Zhang, Yuxuan
Pubblicazione: (2025)

On the hardness of cloning and connections to representation theory
di: Havlíček, Vojtěch, et al.
Pubblicazione: (2024)

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

Quantum Max-Cut is NP hard to approximate
di: Piddock, Stephen
Pubblicazione: (2025)

DQC1-hardness of estimating correlation functions
di: Moulik, Subhayan Roy, et al.
Pubblicazione: (2024)

Exact Quantum Circuit Optimization is co-NQP-hard
di: Kjelstrøm, Adam Husted, et al.
Pubblicazione: (2025)

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

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

An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory
di: Pirnay, Niklas, et al.
Pubblicazione: (2022)

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

Quantum and classical query complexities of functions of matrices
di: Montanaro, Ashley, et al.
Pubblicazione: (2023)

On classical advice, sampling advice and complexity assumptions for learning separations
di: Pérez-Guijarro, Jordi
Pubblicazione: (2024)

Quantum algorithms to simulate quadratic classical Hamiltonians and optimal control
di: Krovi, Hari
Pubblicazione: (2024)

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

The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding
di: Gu, Shouzhen, et al.
Pubblicazione: (2026)

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

Classical simulability of quantum circuits followed by sparse classical post-processing
di: Takahashi, Yasuhiro, et al.
Pubblicazione: (2026)