Separations in query complexity for total search problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ben-David, Shalev, Kundu, Srijita
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

Oracle separation of QMA and QCMA with bounded adaptivity
by: Ben-David, Shalev, et al.
Published: (2024)

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

Quantum information advantage based on Bell inequalities
by: Jain, Rahul, et al.
Published: (2026)

A Cautionary Note on Quantum Oracles
by: Agarwal, Avantika, et al.
Published: (2025)

Monte Carlo to Las Vegas for Recursively Composed Functions
by: Al-Dhalaan, Bandar, et al.
Published: (2026)

Direct sum theorems beyond query complexity
by: Suruga, Daiki
Published: (2024)

On query complexity measures and their relations for symmetric functions
by: Mittal, Rajat, et al.
Published: (2021)

Quantum and classical query complexities of functions of matrices
by: Montanaro, Ashley, et al.
Published: (2023)

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

On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$
by: Yao, Penghui, et al.
Published: (2023)

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

Learning unitaries with quantum statistical queries
by: Angrisani, Armando
Published: (2023)

Conjugate queries can help
by: Tang, Ewin, et al.
Published: (2025)

The dihedral hidden subgroup problem
by: Chen, Imin, et al.
Published: (2021)

En Route to a Standard QMA1 vs. QCMA Oracle Separation
by: Miloschewsky, David, et al.
Published: (2026)

Finding quantum partial assignments by search-to-decision reductions
by: Weggemans, Jordi
Published: (2024)

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

A note on quantum lower bounds for local search via congestion and expansion
by: Brânzei, Simina, et al.
Published: (2024)

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

Coherence in Property Testing: Quantum-Classical Collapses and Separations
by: Jeronimo, Fernando Granha, et al.
Published: (2024)

Computational complexity of the homology problem with orientable filtration: MA-completeness
by: Hayakawa, Ryu, et al.
Published: (2025)

Exponential Separation Criteria for Quantum Iterative Power Algorithms
by: Czégel, András, et al.
Published: (2025)

Magic and communication complexity
by: Girish, Uma, et al.
Published: (2025)

A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs
by: Apers, Simon, et al.
Published: (2021)

An alternative explicit circuit diagram for the quantum search algorithm by implementing a non-unitary gate
by: Daskin, Ammar
Published: (2024)

Quantum complexity of the Kronecker coefficients
by: Bravyi, Sergey, et al.
Published: (2023)

Toward Separating QMA from QCMA with a Classical Oracle
by: Zhandry, Mark
Published: (2024)

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

Quantum versus Classical Separation in Simultaneous Number-on-Forehead Communication
by: Yang, Guangxu, et al.
Published: (2025)

Direct Product Theorems for Randomized Query Complexity
by: Ben-David, Shalev, et al.
Published: (2025)

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

Exponential Separation of Quantum and Classical One-Way Numbers-on-Forehead Communication
by: Yang, Guangxu, et al.
Published: (2026)

Quantum search by continuous-time quantum walk on t-designs
by: Lugão, Pedro H. G., et al.
Published: (2023)

Quantum computational complexity of matrix functions
by: Cifuentes, Santiago, et al.
Published: (2024)

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

Physical complexity and black hole quantum computers
by: Reilly, Michele, et al.
Published: (2025)

On the complexity of unique quantum witnesses and quantum approximate counting
by: Anshu, Anurag, et al.
Published: (2024)

On the communication complexity of finding a king in a tournament
by: Mande, Nikhil S., et al.
Published: (2024)

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

Unambiguous parity-query complexity
by: Gavinsky, Dmytro
Published: (2024)