Imagen de Portada

Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Gharibian, Sevag, Gall, François Le
Formato:	Preprint
Publicado:	2021
Materias:	Quantum Physics Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Dequantizing Short-Path Quantum Algorithms
por: Gall, François Le, et al.
Publicado: (2026)

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

The 7 faces of quantum NP
por: Gharibian, Sevag
Publicado: (2023)

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

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

Dequantization and Hardness of Spectral Sum Estimation
por: Edenhofer, Roman, et al.
Publicado: (2025)

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

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

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

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

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

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

Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms
por: Gall, François Le
Publicado: (2023)

Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction
por: Delavenne, Hugo, et al.
Publicado: (2024)

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

Maximum Separation of Quantum Communication Complexity With and Without Shared Entanglement
por: Hasegawa, Atsuya, et al.
Publicado: (2025)

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

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

How hard is it to verify a classical shadow?
por: Karaiskos, Georgios, et al.
Publicado: (2025)

An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians
por: Mataraarachchi, Ranitha, et al.
Publicado: (2026)

A Quantum Unique Games Conjecture
por: Mousavi, Hamoon, et al.
Publicado: (2024)

Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions
por: Chia, Nai-Hui, et al.
Publicado: (2026)

Hardness of Quantum Distribution Learning and Quantum Cryptography
por: Hiroka, Taiga, et al.
Publicado: (2025)

Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians
por: Gall, François Le
Publicado: (2024)

Dequantization Barriers for Guided Stoquastic Hamiltonians
por: Hamoudi, Yassine, et al.
Publicado: (2026)

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

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

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
por: Buhrman, Harry, et al.
Publicado: (2025)

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

Multi-Prover Interactive Proof Systems with Leakage
por: Asadi, Vahid R., et al.
Publicado: (2026)

Efficient Quantum Hermite Transform
por: Jain, Siddhartha, et al.
Publicado: (2025)

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

On the Computational Hardness of Quantum One-Wayness
por: Cavalar, Bruno, et al.
Publicado: (2023)

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

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

Quantum Subgradient Estimation for Conditional Value-at-Risk Optimization
por: Skarlatos, Vasilis, et al.
Publicado: (2025)

Quantum Cryptography and Hardness of Non-Collapsing Measurements
por: Morimae, Tomoyuki, et al.
Publicado: (2025)

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

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

A slightly improved upper bound for quantum statistical zero-knowledge
por: Gall, François Le, et al.
Publicado: (2025)