Quantum computing
Provisional editorial order for Top Open Problems: Millennium Prize Problems first, followed by assessed difficulty tiers; the unassessed remainder keeps its previous catalogue order. 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
- Math-39 The Quantum PCP Conjecture
- Math-48 Unconditional Separation of Quantum and Classical Bounded-Error Polynomial Time (BQP != BPP)
- Math-49 Unconditional Separation of BQP from the Polynomial Hierarchy
- Math-50 BQP Versus NP: Complete Language-Class Relation
- Math-52 BQP versus QMA
- Math-150 QMA versus QCMA Problem
- Math-153 Unconditional Single-Prover Classical Verification of BQP Computations
- Math-190 Polynomial-Time Quantum Algorithm for Symmetric-Group Hidden Subgroups
- Math-220 Polynomial-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
- Math-252 Quantum versus Classical Communication Complexity of Total Functions
- Math-2470 Analytical Performance Theory for QAOA and RQAOA
- Math-4434 Exact rank-one decoding and a factorized no-QRAM quantum baseline
- Math-4437 Grover optimality and a tail-profile bound for average-value search
- Math-4439 Finite-window reduction and binary-cost accounting for hidden shift on the integers
- Math-4440 A batch-fidelity obstruction in hidden-shift attacks on unique-SVP
- Math-4441 Exact period-quotient reduction and unary lift cost for hidden shift on Z^d
- Math-4442 Spectral laws for Gaussian multiple-shift states
- Math-4443 The cyclic core of Heisenberg hidden shift
- Math-4444 The real cost of the CSIDH hidden-shift attack
- Math-4447 HHL, Macaulay conditioning, and presentation instability
- Math-4448 Offline Simon, explicit HSP instances, and a classical-transcript obstruction
- Math-4469 Quantum Hardness of Approximate Lattice Problems
- Math-4564 Submultiplicativity Gaps for Stabilizer Extent
- Math-4577 Property Testing for Noncommutative Quantum Functions
- Math-4578 Algebraic and Graph-Property Tests for Quantum Functions
- Math-4580 Good Locally Testable Quantum Codes and Linear-Rate PCPs
- Math-4633 Quantum Advantage in Threefold Repetition of Feige’s Game
- Math-4634 Semidefinite Relaxations for Quantum Equilibria
- Math-4986 Mathematics of Quantum Computing
- Math-5057 Correlation-gap certificates for noisy hidden shift
- Math-5175 Rhetorical Quantum-State Vector-Length Question
- Math-5176 Exponential Tree Size of Cluster States
- Math-5266 Quantum Complexity of High-Precision Matrix Scaling
- Math-5271 Dimension–Complexity Tradeoffs in Quantum-Function Testing
- Math-5305 Quantum Harmonic Analysis of Data Structure
- Math-5343 Reported Quantum Search for Binary Fusion Data
- Math-5345 Iterative Quantum LDPC Constructions from Weaker Seeds