Copertina

Beating the natural Grover bound for low-energy estimation and state preparation

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Buhrman, Harry, Gharibian, Sevag, Landau, Zeph, Gall, François Le, Schuch, Norbert, Tamaki, Suguru
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Quantum Physics Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

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

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

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

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

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

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

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)

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

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

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

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)

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

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

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

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

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
di: Aaronson, Scott, et al.
Pubblicazione: (2023)

Formal Framework for Quantum Advantage
di: Buhrman, Harry, et al.
Pubblicazione: (2025)

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

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

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

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

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

Complexity of Quadratic Bosonic Hamiltonian Simulation: $\mathsf{BQP}$-Completeness and $\mathsf{PostBQP}$-Hardness
di: Zschetzsche, Lilith, et al.
Pubblicazione: (2026)

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

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

Beating full state tomography for unentangled spectrum estimation
di: Pelecanos, Angelos, et al.
Pubblicazione: (2025)

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

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

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

Hamiltonians whose low-energy states require $Ω(n)$ T gates
di: Coble, Nolan J., et al.
Pubblicazione: (2023)

Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
di: Rosenthal, Gregory
Pubblicazione: (2021)

Positive bias makes tensor-network contraction tractable
di: Jiang, Jiaqing, et al.
Pubblicazione: (2024)

More-efficient Quantum Multivariate Mean Value Estimator from Generalized Grover Operator
di: Tang, Letian
Pubblicazione: (2025)

Finding dense sub-lattices as low-energy states of a Hamiltonian
di: Barberà-Rodríguez, Júlia, et al.
Pubblicazione: (2023)

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

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