Algorithms and Complexity Research
Quantum algorithm research asks which structure permits quantum information processing to outperform an appropriate classical method. Complexity research asks what can be proved about that power and its limits. The best starting project states the input, access interface, output, error tolerance and counted resources before proposing a circuit.
Required background. Algorithms and complexity supplies the shared language of promises, queries, gates and outputs.
Choose the kind of contribution
Section titled “Choose the kind of contribution”| Direction | Central question | Feasible first result |
|---|---|---|
| Algorithm discovery | Which structure enables interference to help? | A complete access-to-output cost derivation |
| Hamiltonian simulation | Which representation makes evolution cheaper? | A crossover with compiled oracle costs |
| Chemistry and materials | Which observable defeats useful classical approximations? | Error budget for a scientific decision |
| Optimization | Is performance better on a declared instance distribution? | Reproducible time-to-target comparison |
| Machine learning | What quantum data or feature structure helps? | Held-out comparison with matched data access |
| Complexity, queries | Which promises and reductions permit a theorem? | A proved restricted lemma or sharp small case |
| Cryptanalysis, speedup limits | Do asymptotic gains survive implementation? | Sensitivity study of the dominant cost |
Evidence has two independent axes
Section titled “Evidence has two independent axes”Established: rigorous algorithmic speedups exist in specified models; the overview by Montanaro surveys several mechanisms. A theorem about oracle calls may coexist with an impractical implementation. Active: useful constants, state preparation, data access and verification. Conjectural: generic efficient quantum solutions of hard optimization tasks or a universal advantage from expressive variational circuits. Algorithmic overview.
Empirical success is evidence about sampled instances, not a complexity-class separation. Conversely, worst-case hardness does not show that a physically motivated instance family defeats a good classical approximation. Keep theorem strength and practical relevance as separate assessments.
First project: audit a claimed speedup
Section titled “First project: audit a claimed speedup”Pick one algorithm and write an executable cost ledger for preprocessing, coherent data access, processing, readout and verification. Reproduce its small-instance output. Then implement the strongest classical comparator you can validate, including a structure-aware approximation when appropriate. A laptop is enough for the accounting and initial instances.
The deliverable is a crossover diagram with explicit unresolved inputs, not a single speedup factor. Failure tests replace free state preparation with a circuit, tighten accuracy, and increase requested output size. A research extension improves a dominant term or proves that a suspected advantage cannot survive a particular access model. An unresolved input is a reason to bound a claim, not silently set its cost to zero.
Entry points and scope
Section titled “Entry points and scope”Use the optimization review to see how theory, heuristics and applications meet. Source search date: 11 October 2026. The selected sources span 2016–2024 and provide entry routes rather than an exhaustive contemporary algorithm catalog.