Buchumschlag

Lower Bounds for Unitary Property Testing with Proofs and Advice

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Weggemans, Jordi
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Quantum Physics Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Finding quantum partial assignments by search-to-decision reductions
von: Weggemans, Jordi
Veröffentlicht: (2024)

Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians
von: Buhrman, Harry, et al.
Veröffentlicht: (2024)

Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States
von: Cade, Chris, et al.
Veröffentlicht: (2022)

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

Classical versus quantum queries in quantum PCPs with classical proofs
von: Buhrman, Harry, et al.
Veröffentlicht: (2024)

On Bounded Advice Classes
von: Marshall, Simon, et al.
Veröffentlicht: (2024)

Improved Hardness Results for the Guided Local Hamiltonian Problem
von: Cade, Chris, et al.
Veröffentlicht: (2022)

Classical vs Quantum Advice and Proofs under Classically-Accessible Oracle
von: Li, Xingjian, et al.
Veröffentlicht: (2023)

Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
von: Rosenthal, Gregory
Veröffentlicht: (2021)

Uncloneable Quantum Advice
von: Broadbent, Anne, et al.
Veröffentlicht: (2023)

Improved Lower Bounds for QAC0
von: Joshi, Malvika Raj, et al.
Veröffentlicht: (2025)

Improved Circuit Lower Bounds and Quantum-Classical Separations
von: Grewal, Sabee, et al.
Veröffentlicht: (2024)

Separating Quantum and Classical Advice with Good Codes
von: Bostanci, John, et al.
Veröffentlicht: (2026)

Quantum Query-Space Lower Bounds Using Branching Programs
von: Bera, Debajyoti, et al.
Veröffentlicht: (2024)

Lower Bounds on Relative Error Quantum Compression and Classical Shadows
von: Sankar, Kaushik
Veröffentlicht: (2025)

Unitary synthesis with fewer T gates
von: Tan, Xinyu
Veröffentlicht: (2025)

Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations
von: Wang, Qisheng, et al.
Veröffentlicht: (2024)

Random Unitaries in Constant (Quantum) Time
von: Foxman, Ben, et al.
Veröffentlicht: (2025)

Constant-Depth Unitary Preparation of Dicke States
von: Joshi, Malvika Raj, et al.
Veröffentlicht: (2026)

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
von: Aaronson, Scott, et al.
Veröffentlicht: (2023)

Quantum Property Testing for Bounded-Degree Directed Graphs
von: Peng, Pan, et al.
Veröffentlicht: (2026)

The Round Complexity of Proofs in the Bounded Quantum Storage Model
von: Grilo, Alex B., et al.
Veröffentlicht: (2024)

A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting
von: Chen, Kean, et al.
Veröffentlicht: (2025)

Anti-Concentration for the Unitary Haar Measure and Applications to Random Quantum Circuits
von: Fefferman, Bill, et al.
Veröffentlicht: (2024)

Coherence in Property Testing: Quantum-Classical Collapses and Separations
von: Jeronimo, Fernando Granha, et al.
Veröffentlicht: (2024)

Local Test for Unitarily Invariant Properties of Bipartite Quantum States
von: Chen, Kean, et al.
Veröffentlicht: (2024)

How to Construct Random Unitaries
von: Ma, Fermi, et al.
Veröffentlicht: (2024)

Quantum Interactive Oracle Proofs
von: Sun, Baocheng, et al.
Veröffentlicht: (2026)

Two Simple Proofs of Müller's Theorem
von: Epstein, Samuel
Veröffentlicht: (2024)

Unitary Complexity and the Uhlmann Transformation Problem
von: Bostanci, John, et al.
Veröffentlicht: (2023)

On classical advice, sampling advice and complexity assumptions for learning separations
von: Pérez-Guijarro, Jordi
Veröffentlicht: (2024)

Multi-Prover Interactive Proof Systems with Leakage
von: Asadi, Vahid R., et al.
Veröffentlicht: (2026)

The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
von: Jeronimo, Fernando Granha, et al.
Veröffentlicht: (2024)

Unentanglement and Post-Measurement Branching in Quantum Interactive Proofs
von: Grewal, Sabee, et al.
Veröffentlicht: (2025)

The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems
von: Gay, William, et al.
Veröffentlicht: (2026)

Fine-Grained Complexity via Quantum Natural Proofs
von: Chen, Yanlin, et al.
Veröffentlicht: (2025)

Unitary designs in nearly optimal depth
von: Cui, Laura, et al.
Veröffentlicht: (2025)

New Lower-bounds for Quantum Computation with Non-Collapsing Measurements
von: Miloschewsky, David, et al.
Veröffentlicht: (2024)

Lower bounds for quantum-inspired classical algorithms via communication complexity
von: Mande, Nikhil S., et al.
Veröffentlicht: (2024)

Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach
von: Mehraban, Saeed, et al.
Veröffentlicht: (2023)