Cover Image

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Aaronson, Scott, Buhrman, Harry, Kretschmer, William
Format:	Preprint
Published:	2023
Subjects:	Quantum Physics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Acrobatics of BQP
by: Aaronson, Scott, et al.
Published: (2021)

Why Philosophers Should Care About Computational Complexity
by: Aaronson, Scott
Published: (2011)

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

Formal Framework for Quantum Advantage
by: Buhrman, Harry, et al.
Published: (2025)

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

A Relativizing MIP for BQP
by: Aaronson, Scott, et al.
Published: (2026)

Improved separation between quantum and classical computers for sampling and functional tasks
by: Marshall, Simon C., et al.
Published: (2024)

Unentanglement and Post-Measurement Branching in Quantum Interactive Proofs
by: Grewal, Sabee, et al.
Published: (2025)

Quantum Pseudorandomness and Classical Complexity
by: Kretschmer, William
Published: (2021)

Quantum Mass Production Theorems
by: Kretschmer, William
Published: (2022)

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

PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements
by: Aaronson, Scott, et al.
Published: (2024)

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

Uncloneable Quantum Advice
by: Broadbent, Anne, et al.
Published: (2023)

On Bounded Advice Classes
by: Marshall, Simon, et al.
Published: (2024)

Pseudoentanglement Ain't Cheap
by: Grewal, Sabee, et al.
Published: (2024)

Quantum-Computable One-Way Functions without One-Way Functions
by: Kretschmer, William, et al.
Published: (2024)

Separating Quantum and Classical Advice with Good Codes
by: Bostanci, John, et al.
Published: (2026)

Virtual Qudits for Simon's Problem: Dimension-Lifted Algorithms on Qubit Hardware
by: Semre, Abed, et al.
Published: (2025)

Lower Bounds for Unitary Property Testing with Proofs and Advice
by: Weggemans, Jordi
Published: (2024)

Quantum Cryptography in Algorithmica
by: Kretschmer, William, et al.
Published: (2022)

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

Solving The Travelling Salesman Problem Using A Single Qubit
by: Goswami, Kapil, et al.
Published: (2024)

Qubit Routing for (Almost) Free
by: de Griend, Arianne Meijer-van
Published: (2026)

Logarithmic Depth Decomposition of Approximate Multi-Controlled Single-Qubit Gates Without Ancilla Qubits
by: Silva, Jefferson D. S., et al.
Published: (2025)

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

Improved Stabilizer Estimation via Bell Difference Sampling
by: Grewal, Sabee, et al.
Published: (2023)

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

The Space Just Above One Clean Qubit
by: Jacobs, Dale, et al.
Published: (2024)

Limitation of Quantum Walk Approach to the Maximum Matching Problem
by: Júnior, Alcides Gomes Andrade, et al.
Published: (2025)

Pauli Measurements Are Near-Optimal for Single-Qubit Tomography
by: Acharya, Jayadev, et al.
Published: (2025)

Multimarked Spatial Search by Continuous-Time Quantum Walk
by: Lugão, Pedro H. G., et al.
Published: (2022)

Classical vs Quantum Advice and Proofs under Classically-Accessible Oracle
by: Li, Xingjian, et al.
Published: (2023)

Quantum Channel Testing in Average-Case Distance
by: Rosenthal, Gregory, et al.
Published: (2024)

Parallel Kac's Walk Generates PRU
by: Lu, Chuhan, et al.
Published: (2025)

A Note on the Complexity of the Spectral Gap Problem
by: Yirka, Justin
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)

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

On the Complexity of the Succinct State Local Hamiltonian Problem
by: Waite, Gabriel, et al.
Published: (2025)

The Guided Local Hamiltonian Problem for Stoquastic Hamiltonians
by: Waite, Gabriel
Published: (2025)