Cover Image

Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Delavenne, Hugo, Gall, François Le
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

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

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

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

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

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

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

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

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

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

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

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

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

Group Order is in QCMA
by: Gall, François Le, et al.
Published: (2025)

Does there exist a quantum fingerprinting protocol without coherent measurements?
by: Hasegawa, Atsuya, et al.
Published: (2025)

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

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

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

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

Quantum Complexity vs Classical Complexity: A Survey
by: Vaezi, Arash, et al.
Published: (2023)

Bosonic Quantum Computational Complexity
by: Chabaud, Ulysse, et al.
Published: (2024)

On the Complexity of Decoded Quantum Interferometry
by: Marwaha, Kunal, et al.
Published: (2025)

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
by: Grewal, Sabee, et al.
Published: (2022)

Complexity Theory for Quantum Promise Problems
by: Chia, Nai-Hui, et al.
Published: (2024)

Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians
by: Buhrman, Harry, et al.
Published: (2024)

Pseudo-deterministic Quantum Algorithms
by: Aaronson, Hugo, et al.
Published: (2026)

On the Complexity of the Succinct State Local Hamiltonian Problem
by: Waite, Gabriel, 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)

Reordering Method and Hierarchies for Quantum and Classical Ordered Binary Decision Diagrams
by: Khadiev, Kamil, et al.
Published: (2017)

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

A Brief Introduction to Quantum Query Complexity
by: Hamoudi, Yassine
Published: (2025)

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

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

Complexity Classification of Product State Problems for Local Hamiltonians
by: Kallaugher, John, et al.
Published: (2024)

Quantum and Classical Communication Complexity of Permutation-Invariant Functions
by: Guan, Ziyi, et al.
Published: (2023)

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

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

Fine-Grained Complexity via Quantum Natural Proofs
by: Chen, Yanlin, et al.
Published: (2025)

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

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

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
by: Wu, Xudong, et al.
Published: (2025)