On the public citation graph

Open Problems Related to Quantum Query Complexity

0 signed · 76 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/978-1-4939-2864-4_304openalex-snapshot
Quantum Algorithm for the Collision Problem
inferredcites →https://doi.org/10.1007/bf02122692openalex-snapshot
On the power of interaction
inferredcites →https://doi.org/10.1007/s00220-019-03382-yopenalex-snapshot
Limitations of Semidefinite Programs for Separable States and Entangled Games
inferredcites →https://doi.org/10.1016/0020-0190(88)90199-8openalex-snapshot
Are there interactive protocols for co-NP languages?
inferredcites →https://doi.org/10.1016/j.ipl.2004.01.024openalex-snapshot
The quantum query complexity of the hidden subgroup problem is polynomial
inferredcites →https://doi.org/10.1016/j.jcss.2005.06.006openalex-snapshot
Polynomial degree vs. quantum query complexity
inferredcites →https://doi.org/10.1016/s0304-3975(01)00144-xopenalex-snapshot
Complexity measures and decision tree complexity: a survey
inferredcites →https://doi.org/10.1038/s41534-017-0018-2openalex-snapshot
Quantum sampling problems, BosonSampling and quantum supremacy
inferredcites →https://doi.org/10.1038/s41586-019-1666-5openalex-snapshot
Quantum supremacy using a programmable superconducting processor
inferredcites →https://doi.org/10.1098/rspa.1992.0167openalex-snapshot
Rapid solution of problems by quantum computation
inferredcites →https://doi.org/10.1103/physrevlett.127.180501openalex-snapshot
Strong Quantum Computational Advantage Using a Superconducting Quantum Processor
inferredcites →https://doi.org/10.1109/ccc.2008.5openalex-snapshot
The Power of Unentanglement
inferredcites →https://doi.org/10.1109/ccc.2009.42openalex-snapshot
Quantum Copy-Protection and Quantum Money
inferredcites →https://doi.org/10.1109/focs.2009.36openalex-snapshot
Universal Blind Quantum Computation
inferredcites →https://doi.org/10.1109/focs.2018.00033openalex-snapshot
Classical Verification of Quantum Computations
inferredcites →https://doi.org/10.1109/focs46700.2020.00030openalex-snapshot
Towards Optimal Separations between Quantum and Randomized Query Complexities
inferredcites →https://doi.org/10.1109/sfcs.1986.36openalex-snapshot
On the power of interaction
inferredcites →https://doi.org/10.1109/sfcs.1994.365701openalex-snapshot
On the power of quantum computation
inferredcites →https://doi.org/10.1137/05063235xopenalex-snapshot
Quantum and Classical Strong Direct Product Theorems and Optimal Time‐Space Tradeoffs
inferredcites →https://doi.org/10.1137/s0097539705447311openalex-snapshot
Quantum Walk Algorithm for Element Distinctness
inferredcites →https://doi.org/10.1137/s0097539795293172openalex-snapshot
Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
inferredcites →https://doi.org/10.1137/s0097539796300921openalex-snapshot
Quantum Complexity Theory
inferredcites →https://doi.org/10.1137/s0097539796300933openalex-snapshot
Strengths and Weaknesses of Quantum Computing
inferredcites →https://doi.org/10.1145/1008731.1008735openalex-snapshot
Quantum lower bounds for the collision and the element distinctness problems
inferredcites →https://doi.org/10.1145/146585.146609openalex-snapshot
IP = PSPACE
inferredcites →https://doi.org/10.1145/1806689.1806711openalex-snapshot
BQP and the polynomial hierarchy
inferredcites →https://doi.org/10.1145/237814.237866openalex-snapshot
A fast quantum mechanical algorithm for database search
inferredcites →https://doi.org/10.1145/2491533.2491549openalex-snapshot
Guest column
inferredcites →https://doi.org/10.1145/261342.261346openalex-snapshot
Quantum cryptanalysis of hash and claw-free functions
inferredcites →https://doi.org/10.1145/2897518.2897644openalex-snapshot
Separations in query complexity using cheat sheets
inferredcites →https://doi.org/10.1145/3106234openalex-snapshot
Separations in Query Complexity Based on Pointer Functions
inferredcites →https://doi.org/10.1145/3313276.3316315openalex-snapshot
Oracle separation of BQP and PH
inferredcites →https://doi.org/10.1145/3406325.3451019openalex-snapshot
An optimal separation of randomized and Quantum query complexity
inferredcites →https://doi.org/10.1145/3406325.3451040openalex-snapshot
k-forrelation optimally separates Quantum and classical query complexity
inferredcites →https://doi.org/10.1145/3406325.3451047openalex-snapshot
Degree vs. approximate degree and Quantum implications of Huang’s sensitivity theorem
inferredcites →https://doi.org/10.1145/502090.502097openalex-snapshot
Quantum lower bounds by polynomials
inferredcites →https://doi.org/10.1145/509907.509999openalex-snapshot
Quantum lower bound for the collision problem
inferredcites →https://doi.org/10.1145/780542.780552openalex-snapshot
Exponential algorithmic speedup by a quantum walk
inferredcites →https://doi.org/10.22331/q-2018-08-06-79openalex-snapshot
Quantum Computing in the NISQ era and beyond
inferredcites →https://doi.org/10.4007/annals.2019.190.3.6openalex-snapshot
Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture
inferredcites →https://doi.org/10.4086/toc.2007.v003a007openalex-snapshot
inferredcites →https://doi.org/10.4230/lipics.itcs.2020.56openalex-snapshot
Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture
inferredcites →https://doi.org/10.48550/arxiv.0810.5375openalex-snapshot
Interactive Proofs For Quantum Computations
inferredcites →https://doi.org/10.48550/arxiv.1107.0321openalex-snapshot
Component mixers and a hardness result for counterfeiting quantum money
inferredcites →https://doi.org/10.48550/arxiv.1309.7495openalex-snapshot
The Quantum PCP Conjecture
inferredcites →https://doi.org/10.48550/arxiv.1607.05256openalex-snapshot
The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes
inferredcites →https://doi.org/10.48550/arxiv.2008.10223openalex-snapshot
An Optimal Separation of Randomized and Quantum Query Complexity
inferredcites →https://doi.org/10.48550/arxiv.quant-ph/0210077openalex-snapshot
Quantum NP - A Survey
inferredcites →https://doi.org/10.48550/arxiv.quant-ph/0312230openalex-snapshot
A note on the classical lower bound for a quantum walk algorithm

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/978-3-031-30545-0_5openalex-snapshot
Non-uniformity and Quantum Advice in the Quantum Random Oracle Model
inferred← citeshttps://doi.org/10.1007/s00037-025-00277-4openalex-snapshot
An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree
inferred← citeshttps://doi.org/10.1007/s11128-024-04292-2openalex-snapshot
Randomized decision tree complexity of Deutsch–Jozsa problem and a generalization
inferred← citeshttps://doi.org/10.1007/s11128-025-04689-7openalex-snapshot
Exponential speedup of quantum algorithms for the pathfinding problem
inferred← citeshttps://doi.org/10.1007/s11128-025-04714-9openalex-snapshot
Sensitivity of symmetric Boolean functions
inferred← citeshttps://doi.org/10.1016/j.imavis.2026.106120openalex-snapshot
Quantum computing for computer vision: A comprehensive literature survey
inferred← citeshttps://doi.org/10.1016/j.jocs.2024.102454openalex-snapshot
On the theory of quantum and towards practical computation: A review
inferred← citeshttps://doi.org/10.1038/s41534-024-00835-8openalex-snapshot
Circuit complexity of quantum access models for encoding classical data
inferred← citeshttps://doi.org/10.1088/2058-9565/ad04e5openalex-snapshot
T-depth-optimized quantum search with quantum data-access machine
inferred← citeshttps://doi.org/10.1103/5qsb-5jy5openalex-snapshot
Oracle problems as communication tasks and optimization of quantum algorithms
inferred← citeshttps://doi.org/10.1103/b5d4-m3qcopenalex-snapshot
Generalized Deutsch-Jozsa algorithm for applications in data classification, logistic regression, and quantum key distribution
inferred← citeshttps://doi.org/10.1145/3798129.3800896openalex-snapshot
On the Need for (Quantum) Memory with Short Outputs
inferred← citeshttps://doi.org/10.1287/ijoc.2023.1268openalex-snapshot
Synergies Between Operations Research and Quantum Information Science
inferred← citeshttps://doi.org/10.21203/rs.3.rs-2156463/v1openalex-snapshot
A Prototype For Quantum Database In Hybrid Quantum: A Complete Ecosystem
inferred← citeshttps://doi.org/10.21203/rs.3.rs-2156463/v2openalex-snapshot
A Prototype For Quantum Database In Hybrid Quantum: A Complete Ecosystem
inferred← citeshttps://doi.org/10.21203/rs.3.rs-2156463/v3openalex-snapshot
A Prototype For Quantum Database In Hybrid Quantum: A Complete Ecosystem
inferred← citeshttps://doi.org/10.22331/q-2024-06-17-1377openalex-snapshot
A distribution testing oracle separation between QMA and QCMA
inferred← citeshttps://doi.org/10.22331/q-2024-11-18-1526openalex-snapshot
Grothendieck inequalities characterize converses to the polynomial method
inferred← citeshttps://doi.org/10.22331/q-2025-05-06-1733openalex-snapshot
Multidimensional Electrical Networks and their Application to Exponential Speedups for Graph Problems
inferred← citeshttps://doi.org/10.22331/q-2026-06-30-2144openalex-snapshot
Query and Depth Upper Bounds for Quantum Unitaries via Grover Search
inferred← citeshttps://doi.org/10.25559/sitito.019.202302.298-323openalex-snapshot
Quantum Decision-Making Algorithms Modeling in the Classical Simulator: the Quantum Software Engineering Visualization for the Educational Process
inferred← citeshttps://doi.org/10.36227/techrxiv.20237202openalex-snapshot
A Prototype For Quantum Database in Hybrid Quantum
inferred← citeshttps://doi.org/10.36227/techrxiv.20237202.v4openalex-snapshot
A Prototype For Quantum Database in Hybrid Quantum
inferred← citeshttps://doi.org/10.36227/techrxiv.20237202.v5openalex-snapshot
A Prototype For Quantum Database in Hybrid Quantum
inferred← citeshttps://doi.org/10.36227/techrxiv.20237202.v6openalex-snapshot
A Prototype For Quantum Database in Hybrid Quantum
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2022.5openalex-snapshot
Quantum Search-To-Decision Reductions and the State Synthesis Problem
inferred← citeshttps://doi.org/10.47164/ijngc.v14i4.1121openalex-snapshot
Towards Conceptualization Of A Prototype For Quantum Database: A Complete Ecosystem
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.