Quantum Algorithms and Complexity

A quantum algorithm is not just a circuit diagram. It is a family of executable procedures attached to a computational problem, an input and access model, an output contract, an error guarantee, and a resource convention. This guide develops a compact method for auditing that complete claim and then routes each technical question to its canonical owner. It does not repeat the chapter’s algorithm derivations.

The organizing question is: What problem is being solved, under which access and error model, with which resource accounting and classical comparator, and what evidence supports the claimed conclusion? By the end, a reader should be able to answer every part of that question for a proposed algorithm, complexity statement, experiment, or speedup claim.

Required background. Circuit Model supplies registers, preparations, gates, measurements, classical records, input/output contracts, and logical resource measures. Classical Information Review supplies the matched representation, access, output, error, construction, and total-cost comparison needed for a fair classical baseline.

Helpful background. Quantum Oracles repairs access-interface questions, Probability Amplitudes repairs the probability-amplitude distinction, and the Mathematical Toolkit crosswalk routes asymptotic and mathematical prerequisites.

From Computational Problems to Quantum Procedures

A computational problem specifies what outputs count as correct for a family of inputs. An instance is one member of that family. A circuit is one possible realization of part of a procedure. Complexity describes how declared resources scale across the family. These objects answer different questions, so moving from one to another requires explicit assumptions.

For example, a four-qubit circuit can demonstrate a finite interference pattern without defining how its gates, data access, precision, or output scale. Conversely, an asymptotic query theorem can remain valid while saying little about state preparation, logical depth, fault-tolerant overhead, or wall-clock performance. A complete algorithm claim must connect the layers rather than substituting one for another.

The problem-first workflow is:

1. define the task, its instance size, and any promise;
2. declare how input-dependent information enters the procedure;
3. specify the output and operational success criterion;
4. state the coherent, measured, and classical stages that are actually executed;
5. report resources without merging inequivalent currencies;
6. compare against a classical method under the same boundary; and
7. classify the evidence and its limitations.

That workflow applies to decision, search, relation, estimation, sampling, optimization, and state-preparation tasks. It also distinguishes an algorithmic upper bound from a lower bound, a complexity-class statement from a practical runtime claim, and a device observation from an asymptotic advantage result.

The Ten-Field Algorithm and Complexity Claim Record

Use the following record in order. Every field needs a value or a reason that N/A is genuinely appropriate; “unknown,” “unmeasured,” and “excluded from this model” are not interchangeable with “not applicable.”

1. Problem family and size. Identify whether the task is decision, search, relation, estimation, sampling, optimization, or state preparation, and name both the instance parameter and the asymptotic variable.
2. Promise and instance. State the valid-input domain, promise gap or marked-set condition, distributional assumptions, and the concrete instance under discussion.
3. Access and encoding. Declare the classical data structure, reversible or phase oracle, controlled or powered unitary, Hamiltonian, quantum state, or sample access, including construction and preparation costs.
4. Output and use. Specify the returned bit, string, witness, estimate, sample, state, or decision and the downstream capability that output must support.
5. Success and error. Classify the guarantee as exact, zero-error, bounded-error, approximate, or heuristic, and give its metric, tolerance, failure probability, and confidence.
6. Algorithmic idea. Name the structural source of interference or the reduction being used without treating superposition as simultaneous classical readout.
7. Executable procedure. Include the circuit or pseudocode, hybrid loop, measurements, classical postprocessing, verification, retries, and stopping rule.
8. Resource ledger. Report queries, state preparations, logical gates, depth, width, ancillas, samples, coherent evolution time, classical work, memory, fault-tolerant overhead, and wall-clock cost under declared conventions.
9. Classical comparator. Identify the best relevant dated method under matched input, output, error, success, preprocessing, memory, parallelism, and hardware boundaries.
10. Evidence and limits. Classify the support as a theorem, conditional theorem, oracle separation, numerical result, benchmark, device demonstration, resource estimate, or open conjecture; then state failure modes, scope, and canonical handoffs.

This compact record is a claim-completeness test. Algorithmic Primitives owns the more detailed access–processing–interference–readout vocabulary and reusable multi-currency ledger used to design procedures.

Problems, Promises, Outputs, and Success

A relation problem at size $n$ may be written as

$$R_n\subseteq X_n\times Y_n,$$

with promised input domain $D_n\subseteq X_n$. Given $x\in D_n$, an algorithm must return some $y$ satisfying $(x,y)\in R_n$. If the output $Y$ is random, a worst-case bounded-error statement is

$$\Pr\!\left[(x,Y)\in R_n\mid x\right]\ge 1-\delta \qquad\text{for every }x\in D_n.$$

The quantifier matters. An average over a convenient input distribution is not a worst-case guarantee, and performance outside the promise domain need not be constrained at all. A decision problem is the special case in which the useful output is a bit; a search problem returns a valid index or witness rather than merely asserting that one exists.

For estimation, declare a target $z(x)$, an estimator $\widehat z$, and a metric $d$:

$$\Pr\!\left[d\!\left(\widehat z,z(x)\right)\le\epsilon\right] \ge 1-\delta.$$

Both $\epsilon$ and $\delta$ are accuracy and failure parameters that constrain resource use: decreasing either can require more coherent evolution, repetitions, or classical processing. Bias, variance, confidence, and discretization error should not be hidden inside the word “accurate.”

A sampling task must distinguish one draw from a distribution, estimates of selected expectations, and a classical description of the whole distribution. If an algorithm claims to sample from $q$ close to a target $p$ in total variation distance, the convention is

$$d_{\mathrm{TV}}(p,q) =\frac12\sum_y\left|p(y)-q(y)\right|.$$

One output sample is not enough to reconstruct or certify $q$. Verification is therefore part of the output contract whenever the sample distribution, rather than an individual valid outcome, is the object of interest.

Access, Encoding, and Reusable Quantum Primitives

An input model determines which operations are available and what each one costs. An explicit bit string in classical memory, a reversible value oracle, a phase oracle, a prepared quantum state, and time evolution under a supplied Hamiltonian are not interchangeable encodings. Controlled and powered access are additional capabilities unless a construction and its cost are given.

Quantum Oracles owns the precise domain, promise, full-space extension, phase/value representation, inverse and control permissions, and construction boundary for black-box interfaces. This guide records which interface an algorithm assumes. It does not infer a unit-cost coherent oracle from an efficient classical lookup or silently grant coherent random-access memory.

After access is fixed, coherent processing can arrange relative phases and amplitudes so that an intended measurement is informative. Interference is useful only relative to the declared readout; it is not a license to inspect all computational branches. Uncomputation may be required to remove workspace that would otherwise preserve which-path information. Repetition and classical postprocessing may be just as important as the coherent kernel.

The reusable composition language—including state preparation, access, phase processing, reflections, transforms, block structure, signal processing, measurement, and postselection—belongs to Algorithmic Primitives. Algorithm pages then own the proof that a particular composition solves its stated problem.

Search, Phase, Periodicity, and Spectral Structure

Several prominent algorithms can be organized by the structure they expose, but that organization does not make their costs identical.

Grover Search owns unstructured marked-item search, its two-dimensional rotation, finite success law, stopping choices, and optimal black-box query bound. Its quadratic query improvement is a theorem in a specified oracle model. It does not automatically give a quadratic reduction in logical gates, data-loading time, or wall-clock duration.

Quantum Phase Estimation owns estimation of an eigenphase from an eigenstate and controlled powered evolution. The control register records a phase gradient, and inverse Fourier decoding converts that pattern into a bit string. Precision is tied to maximum evolution time and coherent control; counting only the number of distinct powered calls can conceal that dependence. The transform circuit itself remains with Quantum Fourier Transform.

Shor Algorithm owns the number-theoretic reduction from factoring or discrete logarithms to period finding, the quantum order-finding subroutine, classical continued-fraction recovery, verification, and end-to-end complexity qualifications. The quantum polynomial-time upper bound is established. A classical superpolynomial lower bound for factoring is not.

Across these families, the reusable lesson is to identify the mathematical structure—marked subspace, eigenphase, period, or spectrum—then ask how it is accessed, how it changes the output distribution, and what resources are needed to resolve it at the required accuracy.

Hybrid Algorithms and Scientific Workflows

A hybrid algorithm alternates quantum state preparation and measurement with classical updates. Its executable object is the whole loop, including the optimizer, shot allocation, stopping rule, failed restarts, and final validation. Reporting only the depth of one ansatz circuit omits most of the procedure.

Variational Quantum Algorithms owns the general hybrid-loop architecture, objectives, estimators, gradient methods, geometry, trainability, barren plateaus, noise sensitivity, and evidence standards. VQE owns the Rayleigh–Ritz ground-energy contract, Hamiltonian-term measurement, ansatz choices, energy-error interpretation, excited-state extensions, and validation for that specialization.

A scientific workflow adds another layer. The physical Hamiltonian, encoding, observable, model discrepancy, and validation target must be chosen before an algorithmic output can support a scientific conclusion. What Is Quantum Simulation? owns that task-level contract, while Hamiltonian Simulation owns simulation error and dynamical methods. An accurate energy for the encoded model does not by itself validate the model against nature.

Hybrid evidence is especially selection-sensitive. A best-of-many reported run must retain the cost and failure history of all runs, and any selected parameter vector should be tested on fresh data or fresh shots. A decreasing training objective is neither an accuracy certificate nor a speedup result.

Resource Models and Error Budgets

Complexity must name both the asymptotic variable and the resource. A useful abstract quantum ledger is

$$\mathcal R_Q(n,\epsilon,\delta) =\bigl(Q,G,D,W,A,N_{\mathrm{prep}},N_{\mathrm{samp}}, T_{\mathrm{coh}},T_{\mathrm{cl}},M\bigr),$$

where $Q$ is the declared query count, $G$ logical gate count, $D$ logical depth, $W$ live data width, $A$ ancillas or workspace, $N_{\mathrm{prep}}$ state preparations, $N_{\mathrm{samp}}$ retained samples, $T_{\mathrm{coh}}$ coherent evolution time, $T_{\mathrm{cl}}$ classical processing time, and $M$ memory. Preparation attempts and retained samples are separate currencies: rejection, postselection, or failed runs can make their counts differ. None of these currencies should be collapsed into one number without a conversion model.

Even within a query model, the unit must be explicit. One call to a licensed controlled-$U^{2^j}$ primitive, $2^j$ sequential uses of a base $U$, and physical evolution for time $2^j t$ can be equivalent at the level of an ideal unitary while carrying different depth, control, calibration, and error costs.

Approximation errors should be budgeted against the final output metric. If access, synthesis, algorithmic approximation, sampling, and classical postprocessing contribute certified errors $\epsilon_{\mathrm{acc}}$, $\epsilon_{\mathrm{syn}}$, $\epsilon_{\mathrm{alg}}$, $\epsilon_{\mathrm{samp}}$, and $\epsilon_{\mathrm{cl}}$, a conservative additive allocation may require

$$\epsilon_{\mathrm{acc}}+\epsilon_{\mathrm{syn}}+\epsilon_{\mathrm{alg}} +\epsilon_{\mathrm{samp}}+\epsilon_{\mathrm{cl}}\le\epsilon.$$

The justified composition rule can be sharper, but it must be stated. Likewise, correlated failures cannot automatically be combined as if they were independent.

Physical qubits, code cycles, magic states, factory throughput, routing, control latency, energy, and wall-clock duration belong to lower implementation layers rather than serving as synonyms for $G$. Resource Estimation Tools owns the translation from algorithmic and logical currencies to code, factory, physical-qubit, spacetime, and uncertainty estimates.

Fair Classical Comparison and Speedup Language

For one named resource, or under a declared conversion model, let $C_Q(n,\epsilon,\delta)$ and $C_C(n,\epsilon,\delta)$ denote quantum and classical costs only after both sides share the same problem, input representation and construction, output utility, tolerance, failure probability, preprocessing, memory, parallelism, and excluded-cost boundary. A claim about their ratio is otherwise underdetermined.

The comparator should be the best relevant dated method, not a deliberately weak textbook baseline. If the quantum method receives a prepared state or a unit-cost oracle while the classical method must construct an explicit data structure, that asymmetry must either be part of the stated problem or charged to the quantum side as well. Classical preprocessing reused across many instances should be amortized under the same reuse convention as quantum compilation or calibration.

Big-$O$ notation gives an asymptotic upper bound, not a small-instance timing prediction. A polynomial quantum upper bound plus the absence of a known classical polynomial algorithm is not a proved exponential separation. Query complexity is not gate complexity, logical gate complexity is not fault-tolerant spacetime cost, and a favorable median runtime is not necessarily a favorable cost-to-solution at fixed success probability.

Classical Information Review owns the general matched-comparator method. Algorithmic Benchmarking owns end-to-end benchmark instances, execution records, output-quality estimands, retries, selection accounting, and cost-to-solution. Verification of Quantum Advantage owns the evidence chain from correctness through a dated classical frontier and independent reproduction.

Complexity Classes, Lower Bounds, and Evidence

Complexity classes group problem families by the resources needed by uniform computational models under specified error conventions. Membership is an upper-bound statement: it supplies an allowed algorithmic route. A separation requires a lower bound excluding another route. Those logical roles must not be exchanged.

Quantum Complexity Classes owns languages and promise problems, uniform circuit families, BQP, QCMA, QMA, QIP, containments, reductions, oracle qualifications, and the Local Hamiltonian problem. BQP versus BPP is unresolved. An oracle separation establishes a relativized distinction and may illuminate techniques, but it is not an unrelativized class separation.

Evidence must be classified at the strength actually obtained. An exact proof in a black-box model, a conditional asymptotic theorem, a numerical simulation, a device demonstration, an end-to-end benchmark, a resource projection, and an application claim answer different questions. Claims, Hype, and Evidence Standards owns that general evidence ladder.

Grover’s quadratic black-box separation is proved, but it is not a generic quadratic runtime improvement. Shor’s algorithms give polynomial quantum upper bounds for factoring and discrete logarithms, but no proved classical superpolynomial lower bound. QPE precision consumes controlled evolution and coherent time. Data loading, state preparation, output extraction, sampling, postselection, classical optimization, verification, and failed attempts are not free. These statements are boundaries on conclusions, not objections to studying the algorithms.

Two Worked Claim Audits

Finite Grover query audit

Consider a unique marked item among $N=16$ positions. The interface supplies a unit-cost coherent phase oracle licensed from the corresponding Boolean predicate, uniform state preparation, the standard diffusion reflection, and computational-basis readout.

1. Problem family and size. This is unique-mark search over $N$ positions; the concrete instance has $N=16$ and address length $n=\log_2N=4$.

2. Promise and instance. Exactly one position $x_\star$ is marked. For the finite classical comparison, its location is uniformly distributed among the sixteen positions; the actual $x_\star$ is not revealed.

3. Access and encoding. A supplied coherent phase oracle acts as $O_f|x\rangle=(-1)^{f(x)}|x\rangle$. One call costs one query. Its construction from the Boolean predicate is licensed rather than synthesized, while uniform preparation and the diffusion reflection are separate operations.

4. Output and use. One computational-basis measurement returns a four-bit index intended to equal $x_\star$; the immediate use is locating the marked item.

5. Success and error. With

   $$\theta=\arcsin\sqrt{1/16}=\arcsin(1/4)$$

   and three Grover iterates, the ideal marked-item probability is

   $$P_3=\sin^2(7\theta)=0.9613189697265625.$$

   This is an exact ideal-model probability, not a noise or confidence guarantee.

6. Algorithmic idea. Alternating the marked-state phase reflection and the diffusion reflection rotates the state in the two-dimensional marked/unmarked subspace toward the marked state.

7. Executable procedure. Prepare the uniform four-qubit state, apply exactly three oracle–diffusion iterates, measure once in the computational basis, and stop. Verification, retries, and adaptive stopping are N/A for this declared one-shot procedure.

8. Resource ledger. The query count is three phase-oracle calls, accompanied by three diffusion operations, $N_{\mathrm{prep}}=1$ uniform preparation, four live data qubits, and $N_{\mathrm{samp}}=1$ retained readout. Oracle construction, diffusion synthesis, detailed gate count and depth, extra workspace, coherent duration, fault-tolerant overhead, and wall-clock cost are unspecified rather than zero; ancillas are N/A only at the licensed phase-oracle interface.

9. Classical comparator. The matched classical baseline queries three distinct positions. If all three replies are negative, it outputs one uniformly chosen unqueried position. Under the uniform unique-mark distribution its success is

   $$\frac{3}{16}+\frac{13}{16}\frac{1}{13} =\frac{4}{16}=0.25.$$

   This is a finite query-model comparison, not an implementation-level comparison.

10. Evidence and limits. The probabilities are exact ideal calculations under the declared access model. Grover Search owns the rotation derivation and optimal query bound; Quantum Oracles owns the oracle-equivalence assumptions. Preparation, synthesis, routing, noise, error correction, and time must be added before making an implementation speedup claim.

Calling the procedure “cost three” would therefore be false: three is only its phase-oracle query count.

Powered-phase access audit

Now suppose

$$U|u\rangle=e^{2\pi i(3/8)}|u\rangle$$

for a supplied exact eigenstate $|u\rangle$. Use three control qubits, inverse-QFT decoding, and the most-significant-bit-first output convention in which $3/8$ is 011.

1. Problem family and size. This is eigenphase estimation with three output bits; the concrete phase is $\phi=3/8$. No asymptotic scaling family is supplied for this toy instance.

2. Promise and instance. The input is promised to be an exact eigenstate satisfying $U|u\rangle=e^{2\pi i(3/8)}|u\rangle$, and the phase has an exact three-bit binary expansion.

3. Access and encoding. Controlled-$U$, controlled-$U^2$, and controlled-$U^4$ are separately licensed capabilities. Exact eigenstate preparation and the inverse-QFT circuit are also assumed available; their construction costs are not included in the powered-call count.

4. Output and use. Measuring the three control qubits returns 011, interpreted as the estimate $\widehat\phi=3/8$. No downstream use beyond reporting the phase is specified.

5. Success and error. Under the exact eigenstate, exact powered controls, ideal inverse QFT, and declared bit convention, 011 occurs with probability one. Device noise, synthesis error, and a confidence interval are N/A only for this ideal calculation, not for an experiment.

6. Algorithmic idea. Phase kickback writes the powers of $e^{2\pi i\phi}$ across the control register, and the inverse QFT decodes the exactly representable phase.

7. Executable procedure. Prepare three controls in $|+\rangle$, apply the three licensed controlled powers, apply the inverse QFT, measure the controls, return 011, and stop. Retries and verification are N/A for the stated ideal run.

8. Resource ledger. The abstract powered-call count is three. If each power is synthesized by sequential base-$U$ evolution, the interrogation time is

   $$1+2+4=7$$

   base-$U$ time units. The maximum individual powered-call duration is four units, while the target and control computation in the standard circuit must remain coherent across at least all seven interrogation units, plus decoding and other gates. Using a separated preparation convention, $N_{\mathrm{prep,input}}=1$ records the supplied eigenstate and $N_{\mathrm{init,ctrl}}=1$ records one initialization of the three-control register; they are not silently combined into an implementation-independent scalar. One output sample is retained, $N_{\mathrm{samp}}=1$. The control width is three qubits in addition to the unspecified eigenstate register. Eigenstate construction, inverse-QFT gates and depth, controls, workspace, memory, fault-tolerant overhead, and wall-clock cost require separate accounting.

9. Classical comparator. Not specified for a speedup claim: the relevant comparator depends on whether $U$ is explicit, sparse, classically simulable, physically supplied, or accessible only through an oracle. A comparator is not required to verify this finite ideal calculation, but its absence is a missing speedup premise rather than evidence of an advantage.

10. Evidence and limits. This is an exact ideal circuit calculation for one representable phase. Quantum Phase Estimation owns the probability kernel and precision analysis, Quantum Fourier Transform owns the decoder circuit, and Quantum Oracles owns the licensed powered-access distinction. No classical speedup follows from the instance.

Three powered calls, seven base-$U$ time units, a maximum individual duration of four units, and a standard-circuit coherent horizon of at least seven interrogation units are different resource statements.

Chapter Map, Canonical Owners, and Reader Pathways

Use the following ownership map to prevent a chapter guide from becoming a duplicate derivation.

Question	Canonical owner
Registers, gates, measurements, feedforward, and logical circuit syntax	Circuit Model
Oracle domains, extensions, phase/value forms, controls, powers, and construction	Quantum Oracles
Fixed-cap classical and quantum query measures, reductions, composition theorems, and lower-bound certificates	Query Complexity
Constant-versus-balanced promise, exact one-query Walsh decision proof, and matched exact and randomized query comparison	Deutsch–Jozsa Algorithm
Hidden linear word, specialized character proof, and matched $n$-versus-one query comparison	Bernstein–Vazirani Algorithm
Hidden XOR-period promise, orthogonal-subspace samples, binary recovery, and matched exponential query separation	Simon’s Algorithm
Reusable access–processing–interference–readout composition and detailed abstract ledgers	Algorithmic Primitives
Unstructured search proof, finite rotation law, and optimal query bound	Grover Search
Arbitrary-preparation success amplification, known and unknown schedules, exact and fixed-point regimes, and access-sensitive resource limits	Amplitude Amplification
Coherent probability/expectation estimation, exact output/error laws, QFT-free regimes, and access-sensitive resources	Amplitude Estimation
Eigenphase probability law, precision, and coherent powered-access cost	Quantum Phase Estimation
Period finding, number-theoretic recovery, and factoring or discrete-logarithm qualifications	Shor Algorithm
Matched-access Hamiltonian-simulation method applicability, normalized upper and lower query bounds, and query-to-resource qualifications	Hamiltonian Simulation Algorithms
Quantum linear-systems problem, normalized solution-state output, HHL and modern solver comparison, access-model distinctions, intrinsic versus block conditioning, and readout/verification limits	Quantum Linear Algebra
General block-encoding and projected-unitary-encoding calculus, normalization and error composition, QSVT admissibility and singular-value action, and query/ancilla costs	Block Encodings and QSVT
Discrete- and continuous-time quantum-walk models, graph-access contracts, spectral maps, search, detection, and hitting-time algorithms, matched query bounds, and resource/readout limits	Quantum Walk Algorithms
General hybrid optimization, gradients, trainability, and evidence	Variational Quantum Algorithms
QAOA cost-and-mixer ansatzes, constrained alternating operators, objective estimation, parameter search, proved approximation statements, and resource-qualified optimization claims	QAOA
Ground-energy variational contract, measurement, ansatzes, and validation	VQE
Quantum-learning tasks, classical and quantum data access, feature maps, kernels, variational classifiers, generalization, dequantization, and evidence-bounded advantage claims	Quantum Machine Learning
Cross-domain representation, solver, resource, and evidence choice for finite chemistry and materials tasks	Quantum Algorithms for Chemistry and Materials
Cross-route formulation, output guarantees, algorithm selection, resources, and evidence for discrete and convex optimization	Quantum Algorithms for Optimization
BQP, QCMA, QMA, QIP, reductions, containments, and oracle qualifications	Quantum Complexity Classes
Cross-resource no-fast-forwarding, input and output bottlenecks, matched-access dequantization caveats, noise and overhead, complexity barriers, and query-to-resource implications	Lower Bounds and Limitations
Matched classical representation, access, output, error, and total cost	Classical Information Review
End-to-end executions, retries, selection, output quality, and cost-to-solution	Algorithmic Benchmarking
Logical-to-physical estimates, factories, code cycles, spacetime, and uncertainty	Resource Estimation Tools
Evidence vocabulary and the strength of a public claim	Claims, Hype, and Evidence Standards
Physical target, observable, model error, and scientific validation	What Is Quantum Simulation?

For a first pass through the subject, begin with the Quantum Information overview, What Is Quantum Information?, or the Quantum Information roadmap. Then follow one of these live routes:

• Core algorithm route: Circuit Model → Algorithmic Primitives → Grover Search or Quantum Phase Estimation → Shor Algorithm → Quantum Complexity Classes.
• Hybrid scientific route: Algorithmic Primitives → Variational Quantum Algorithms → VQE → What Is Quantum Simulation?.
• Claim-audit route: the relevant live algorithm owner → Algorithmic Benchmarking → Resource Estimation Tools → Verification of Quantum Advantage.

Topics without a substantive owner are intentionally not linked here. Their eventual pages must establish their own scope, evidence, and reciprocal graph before entering these pathways.

Common Algorithm-Claim Failures

Starting from a circuit instead of a problem. A circuit can establish an identity or finite output distribution. It cannot define the promise, scaling family, output utility, comparator, or evidence boundary that a speedup claim needs.

Hiding access behind “given the data.” State preparation, coherent lookup, powered evolution, and controlled access can dominate the procedure. Name the interface and charge its construction unless the problem definition explicitly supplies it.

Calling a query count the runtime. Queries, gates, depth, preparations, retained samples, coherent time, classical work, fault-tolerant spacetime, and wall-clock duration are different currencies. Report the vector first and convert only under a declared implementation model.

Comparing unmatched outputs or errors. A quantum sample, an expectation estimate, and a full classical description have different utilities. Both algorithms must solve the same task to the same tolerance and success probability.

Treating an upper bound as a separation. Membership in BQP or a polynomial quantum algorithm supplies an upper bound. It does not prove that every classical algorithm needs superpolynomial time.

Promoting a finite demonstration to asymptotic evidence. A device result tests a concrete implementation at particular sizes and noise levels. It does not establish scaling beyond those instances without additional analysis.

Dropping unsuccessful trials and selection costs. Restarts, discarded seeds, mitigation, tuning, and fresh validation belong in the executable procedure and resource ledger. Reporting only the selected run biases both performance and uncertainty.

Confusing model accuracy with algorithm accuracy. Solving an encoded Hamiltonian accurately does not show that the Hamiltonian represents the intended physical system accurately. The model, observable, and validation chain remain separate owners.

Exercises

Exercise 1 — Repair a speedup sentence

Replace “this quantum circuit is exponentially faster” with a complete, defensible statement naming the problem family, input size, access, output, error, quantum resource, classical comparator, and evidence. Explain why a circuit diagram alone cannot establish a speedup.

Solution

One valid repair is: “For unique-mark black-box search over $N$ items, given unit-cost coherent phase-oracle access to the predicate, Grover search returns the marked index with bounded error using $O(\sqrt N)$ oracle queries, whereas randomized classical search requires $\Omega(N)$ value queries under the matched black-box success criterion; this is a proved asymptotic query separation.”

This statement identifies the family, size $N$, access, index output, bounded-error criterion, query resource, classical query comparator, and theorem status. It does not claim an exponential separation, a gate-count separation, or a wall-clock advantage. A circuit diagram by itself supplies none of the required scaling, comparator, construction, or evidence information.

Exercise 2 — Decision, estimation, and sampling outputs

Classify three tasks and write an appropriate success statement for each: bounded-error decision, $\epsilon$-accurate estimation with failure probability $\delta$, and sampling within total-variation distance $\epsilon$. Explain why one sample is not a classical description of a distribution.

Solution

For decision with correct bit $b(x)$, a bounded-error contract is

$$\Pr[\widehat b=b(x)\mid x]\ge\frac23$$

for every promised input. For estimation of $z(x)$ in metric $d$,

$$\Pr\!\left[d(\widehat z,z(x))\le\epsilon\right]\ge1-\delta.$$

For sampling, the generated distribution $q$ should satisfy

$$d_{\mathrm{TV}}(p,q)\le\epsilon$$

under the stated exact or probabilistic certification convention. One draw contains one outcome, not the exponentially many probabilities that may define $q$. Reconstructing or certifying the distribution generally needs repeated preparations and samples plus a declared statistical test.

Exercise 3 — Finite Grover audit

Reproduce $\theta=\arcsin(1/4)$, $P_3=0.9613189697265625$, and the matched three-distinct-query-plus-output classical success $4/16=0.25$. Identify every resource excluded from the query comparison and route its technical derivation.

Solution

For one marked item among sixteen, $\sin\theta=\sqrt{1/16}=1/4$. After three Grover iterates the marked amplitude is $\sin((2\cdot3+1)\theta)=\sin(7\theta)$, hence

$$P_3=\sin^2(7\arcsin(1/4))=0.9613189697265625.$$

Three distinct classical queries hit a uniformly located mark with probability $3/16$. After three negative replies, a uniform guess among the thirteen unqueried items is correct with conditional probability $1/13$. Therefore

$$\frac{3}{16}+\frac{13}{16}\frac{1}{13} =\frac{4}{16}=0.25.$$

The comparison excludes oracle construction, uniform-state preparation, three diffusion operations and their synthesis, routing, ancillas, detailed gate count and depth, coherent duration, readout and retries, classical control, noise, error correction, memory, and wall-clock time. Grover Search owns the rotation and query bound, while Quantum Oracles owns access equivalences and construction boundaries.

Exercise 4 — Input-size audit

A unique-mark search over $N=2^n$ items uses $\Theta(\sqrt N)=\Theta(2^{n/2})$ oracle queries. Explain why this is a quadratic improvement in $N$ but still exponential in the address length $n$, and why neither phrasing is a gate- or wall-clock bound.

Solution

Classical unstructured search has query scaling linear in the number of items, $\Theta(N)$, while Grover scaling is $\Theta(\sqrt N)$. The quantum query count is therefore the square root of the classical scale as a function of $N$, which is the quadratic query improvement.

Because $N=2^n$, the quantum query count is $\Theta(2^{n/2})$, still exponential as a function of the $n$-bit address length. Both statements concern oracle calls. The gate and time costs also depend on preparing the state, implementing the oracle and reflection, routing, correction, and measurement.

Exercise 5 — Powered-query currencies

Reproduce the $3/8$ phase audit. Report three powered calls, seven base-$U$ repetition-equivalent time units, maximum individual powered-call duration four, a standard-circuit coherent horizon of at least seven interrogation units, and the ideal 011 output. Explain why these are not interchangeable cost measures and why no comparator was specified.

Solution

The three control bits call controlled-$U^{2^j}$ for $j=0,1,2$, namely controlled-$U$, controlled-$U^2$, and controlled-$U^4$. Thus the licensed powered-call count is three. Sequential synthesis from base $U$ instead uses

$$1+2+4=7$$

base-$U$ time units. The maximum duration of an individual powered block is four units. In the standard circuit, however, the eigenstate target and the relevant control computation must preserve coherence across at least the full seven interrogation units, plus inverse-QFT decoding and other gates. Since $3/8=0.011_2$, ideal inverse-QFT decoding in the declared bit convention returns 011 with probability one.

A powered primitive may have a different implementation cost from repeated base evolution, and the maximum block duration is not the whole-circuit coherence requirement. No classical comparator is defined until one says whether $U$ is explicitly described, sparse, simulable, physically supplied, or accessible only as an oracle.

Exercise 6 — Class membership versus lower bound

Audit the sentence “factoring is in BQP, so quantum computers are proved exponentially faster.”

Solution

The defensible result is that Shor gives polynomial-time quantum algorithms for factoring and related decision or relation formulations. Strictly, BQP is a class of decision problems, so the function problem should not be identified with the class without specifying a formulation.

No classical superpolynomial lower bound for factoring is known. Therefore the exponential separation does not follow. An oracle separation would be evidence about relativized models, not an unrelativized proof about factoring. Shor Algorithm owns the quantum upper bound and reduction; Quantum Complexity Classes owns formal class and oracle qualifications.

Exercise 7 — Variational evidence ledger

A report gives only the best VQE energy found over twenty random seeds. What must be added before it becomes an auditable algorithm or advantage result?

Solution

The record must include all state-preparation attempts; Hamiltonian terms and grouping; retained shots per estimate; gradient evaluations or optimizer calls; classical processing and memory; mitigation; the outcomes and costs of failed seeds; the selection rule; stopping and retry rules; fresh validation of the selected result; uncertainty; model and encoding error; and a dated classical baseline under matched accuracy and total-cost conventions. Preparation attempts and retained samples must be reported separately, especially if rejection or hardware failures occur.

A decreasing training energy shows optimizer behavior on the measured objective. It is not by itself a certificate of ground-state accuracy, because sampling, optimization, ansatz, Hamiltonian, and model errors remain. Selecting the best of twenty seeds without charging all twenty also understates cost and introduces selection bias. VQE owns the energy contract; Variational Quantum Algorithms owns the general hybrid ledger.

Exercise 8 — Complete ten-field claim record

Audit the sentence “a three-bit phase-estimation experiment proves an exponential speedup.” Use the $3/8$ instance from the worked audit and supply a value or justified N/A for every field.

Solution

1. Problem family and size. Eigenphase estimation with a three-bit output for one fixed unitary; no scaling family in input size or precision has been supplied.
2. Promise and instance. The input is promised to be an exact eigenstate with phase $\phi=3/8$, exactly representable in three binary digits.
3. Access and encoding. The calculation licenses exact eigenstate preparation and controlled-$U$, controlled-$U^2$, and controlled-$U^4$, followed by an ideal inverse QFT. Construction costs are unspecified.
4. Output and use. The output is 011, interpreted as $\widehat\phi=3/8$. Reporting the phase is the only declared use; any further downstream use is unspecified.
5. Success and error. The ideal circuit returns 011 with probability one. Experimental noise, tolerance, confidence, and calibration error are not reported, so they are unknown rather than zero; they are N/A only if the claim is restricted to the ideal calculation.
6. Algorithmic idea. Phase kickback encodes a phase gradient across the controls and inverse-QFT interference decodes the exactly representable phase.
7. Executable procedure. Prepare the exact eigenstate and three $|+\rangle$ controls, apply the three controlled powers, apply the inverse QFT, measure the controls, and stop. Retry, verification, and postselection are N/A for the declared ideal one-shot procedure.
8. Resource ledger. Using the same separated preparation convention as the worked audit, the record contains $N_{\mathrm{prep,input}}=1$ licensed eigenstate preparation and $N_{\mathrm{init,ctrl}}=1$ initialization of the three-control register, rather than an incompatible scalar sum. It also contains three powered calls, $N_{\mathrm{samp}}=1$ retained output sample, inverse-QFT gates, measurement, and classical decoding. Under repeated base evolution it has seven base-$U$ interrogation units, maximum individual powered duration four, and a standard-circuit coherent horizon of at least seven interrogation units plus decoding and other gates. Detailed eigenstate-register width, gate count, depth, workspace, physical overhead, and wall-clock time are unspecified.
9. Classical comparator. Missing or unspecified: no classical access model, output tolerance, failure probability, or cost boundary has been given. This omission prevents a speedup conclusion, although no comparator is needed for the finite ideal-circuit calculation alone.
10. Evidence and limits. The ideal result is an exact finite calculation; an actual run would be a device demonstration at one size. Neither establishes asymptotic scaling or an exponential advantage. Quantum Phase Estimation owns the probability and precision analysis, Quantum Fourier Transform the decoder, Quantum Oracles the powered-access contract, Resource Estimation Tools the physical translation, Algorithmic Benchmarking the execution record, and Verification of Quantum Advantage the comparator and reproduction chain.

The original sentence must therefore be rejected: it supplies neither a scaling family nor a matched classical lower bound.

References

• C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, “Strengths and Weaknesses of Quantum Computing,” SIAM Journal on Computing 26, 1510–1523 (1997), doi:10.1137/S0097539796300933.
• E. Bernstein and U. Vazirani, “Quantum Complexity Theory,” SIAM Journal on Computing 26, 1411–1473 (1997), doi:10.1137/S0097539796300921.
• A. M. Childs and W. van Dam, “Quantum Algorithms for Algebraic Problems,” Reviews of Modern Physics 82, 1–52 (2010), doi:10.1103/RevModPhys.82.1.
• L. K. Grover, “A Fast Quantum Mechanical Algorithm for Database Search,” in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 212–219 (1996), doi:10.1145/237814.237866.
• A. Y. Kitaev, A. H. Shen, and M. N. Vyalyi, Classical and Quantum Computation, Graduate Studies in Mathematics 47, American Mathematical Society (2002), doi:10.1090/gsm/047.
• A. Montanaro, “Quantum Algorithms: An Overview,” npj Quantum Information 2, 15023 (2016), doi:10.1038/npjqi.2015.23.
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press (2010), doi:10.1017/CBO9780511976667.
• J. Preskill, “Quantum Computing in the NISQ Era and Beyond,” Quantum 2, 79 (2018), doi:10.22331/q-2018-08-06-79.
• P. W. Shor, “Algorithms for Quantum Computation: Discrete Logarithms and Factoring,” in Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 124–134 (1994), doi:10.1109/SFCS.1994.365700.