Quantum computing
The Top Open Problems editorial order restricted to Computer Science, followed by cross-listed economics entries. Existing relative order is retained, with provisional placements for new game-learning questions; most entries have no individual difficulty assessment. About rankings
Browse by subject
Search this collection by problem ID, title, classification, subject, provider, or model.
Search results
No matching problems. Try another search or clear a filter.
37 records · Search and filter
- CS-4 The Quantum PCP Conjecture
- CS-7 Unconditional Separation of Quantum and Classical Bounded-Error Polynomial Time (BQP != BPP)
- CS-8 Unconditional Separation of BQP from the Polynomial Hierarchy
- CS-9 BQP Versus NP: Complete Language-Class Relation
- CS-11 BQP versus QMA
- CS-35 QMA versus QCMA Problem
- CS-36 Unconditional Single-Prover Classical Verification of BQP Computations
- CS-45 Polynomial-Time Quantum Algorithm for Symmetric-Group Hidden Subgroups
- CS-49 Polynomial-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
- CS-55 Quantum versus Classical Communication Complexity of Total Functions
- CS-116 Analytical Performance Theory for QAOA and RQAOA
- CS-245 Exact rank-one decoding and a factorized no-QRAM quantum baseline
- CS-248 Grover optimality and a tail-profile bound for average-value search
- CS-250 Finite-window reduction and binary-cost accounting for hidden shift on the integers
- CS-251 A batch-fidelity obstruction in hidden-shift attacks on unique-SVP
- CS-252 Exact period-quotient reduction and unary lift cost for hidden shift on Z^d
- CS-253 Spectral laws for Gaussian multiple-shift states
- CS-254 The cyclic core of Heisenberg hidden shift
- CS-255 The real cost of the CSIDH hidden-shift attack
- CS-258 HHL, Macaulay conditioning, and presentation instability
- CS-259 Offline Simon, explicit HSP instances, and a classical-transcript obstruction
- CS-280 Quantum Hardness of Approximate Lattice Problems
- CS-375 Submultiplicativity Gaps for Stabilizer Extent
- CS-388 Property Testing for Noncommutative Quantum Functions
- CS-389 Algebraic and Graph-Property Tests for Quantum Functions
- CS-391 Good Locally Testable Quantum Codes and Linear-Rate PCPs
- CS-444 Quantum Advantage in Threefold Repetition of Feige’s Game
- CS-445 Semidefinite Relaxations for Quantum Equilibria
- CS-451 Mathematics of Quantum Computing
- CS-522 Correlation-gap certificates for noisy hidden shift
- CS-640 Rhetorical Quantum-State Vector-Length Question
- CS-641 Exponential Tree Size of Cluster States
- CS-731 Quantum Complexity of High-Precision Matrix Scaling
- CS-736 Dimension–Complexity Tradeoffs in Quantum-Function Testing
- CS-770 Quantum Harmonic Analysis of Data Structure
- CS-808 Reported Quantum Search for Binary Fusion Data
- CS-810 Iterative Quantum LDPC Constructions from Weaker Seeds