Copertina

Extensively Not P-Bi-Immune promiseBQP-Complete Languages

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Jackson, Andrew
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity Quantum Physics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

The Acrobatics of BQP
di: Aaronson, Scott, et al.
Pubblicazione: (2021)

A Relativizing MIP for BQP
di: Aaronson, Scott, et al.
Pubblicazione: (2026)

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

Plethysm is in #BQP
di: Christandl, Matthias, et al.
Pubblicazione: (2026)

Quantum Threshold is Powerful
di: Grier, Daniel, et al.
Pubblicazione: (2024)

$\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input)
di: Grier, Daniel, et al.
Pubblicazione: (2026)

Quantum SAT Problems with Finite Sets of Projectors are Complete for a Plethora of Classes
di: Cardoso, Ricardo Rivera, et al.
Pubblicazione: (2025)

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

Constructing $\mathrm{NP}^{\mathord{\#}\mathrm P}$-complete problems and ${\mathord{\#}\mathrm P}$-hardness of circuit extraction in phase-free ZH
di: Mitosek, Piotr
Pubblicazione: (2024)

Classically Spoofing System Linear Cross Entropy Score Benchmarking
di: Tanggara, Andrew, et al.
Pubblicazione: (2024)

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

Gate-based quantum simulation of Gaussian bosonic circuits on exponentially many modes
di: Barthe, Alice, et al.
Pubblicazione: (2024)

Deciding Whether a C-Q Channel Preserves a Bit is QCMA-Complete
di: Hutton, Kiera, et al.
Pubblicazione: (2025)

Extensive long-range magic in non-Abelian topological orders
di: Zhang, Yuzhen, et al.
Pubblicazione: (2026)

Efficiently verifiable quantum advantage on near-term analog quantum simulators
di: Liu, Zhenning, et al.
Pubblicazione: (2024)

A Brief Note on a Recent Claim About NP-Hard Problems and BQP
di: Chavrimootoo, Michael C.
Pubblicazione: (2024)

Commuting Local Hamiltonians Beyond 2D
di: Bostanci, John, et al.
Pubblicazione: (2024)

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

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

Dimension Independent Disentanglers from Unentanglement and Applications
di: Jeronimo, Fernando G., et al.
Pubblicazione: (2024)

Two prover perfect zero knowledge for MIP*
di: Mastel, Kieran, et al.
Pubblicazione: (2024)

The Communication Complexity of Approximating Matrix Rank
di: Sherstov, Alexander A., et al.
Pubblicazione: (2024)

On the hardness of cloning and connections to representation theory
di: Havlíček, Vojtěch, et al.
Pubblicazione: (2024)

Local Test for Unitarily Invariant Properties of Bipartite Quantum States
di: Chen, Kean, et al.
Pubblicazione: (2024)

Efficient approximate unitary designs from random Pauli rotations
di: Haah, Jeongwan, 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)

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

Oracle Separation between Noisy Quantum Polynomial Time and the Polynomial Hierarchy
di: Chia, Nai-Hui, et al.
Pubblicazione: (2024)

Computational complexity of isometric tensor network states
di: Malz, Daniel, et al.
Pubblicazione: (2024)

A Quantum Unique Games Conjecture
di: Mousavi, Hamoon, et al.
Pubblicazione: (2024)

Quantum Query-Space Lower Bounds Using Branching Programs
di: Bera, Debajyoti, et al.
Pubblicazione: (2024)

Semi-Classical Subspaces, The No Synchronization Law, and More
di: Epstein, Samuel
Pubblicazione: (2024)

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

Towards a universal gateset for $\mathsf{QMA}_1$
di: Rudolph, Dorian
Pubblicazione: (2024)

Unconditionally separating noisy $\mathsf{QNC}^0$ from bounded polynomial threshold circuits of constant depth
di: Hsieh, Min-Hsiu, et al.
Pubblicazione: (2024)

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

The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
di: Jeronimo, Fernando Granha, et al.
Pubblicazione: (2024)

Improved Circuit Lower Bounds and Quantum-Classical Separations
di: Grewal, Sabee, et al.
Pubblicazione: (2024)

Oracle Separations for the Quantum-Classical Polynomial Hierarchy
di: Agarwal, Avantika, et al.
Pubblicazione: (2024)