Quantum Algorithms and Complexity

Quantum algorithms arrange interference so that a measurement reveals useful information about a problem. The gain depends on the problem’s structure and on how its input is supplied. Searching for a marked item, estimating an eigenphase, preparing a solution state and estimating an energy have different outputs and different costs.

This chapter explains the main algorithmic ideas and the limits of their speedups. Begin by asking three questions: what is the input, what output is needed, and what operations are available? Then follow the probability calculation and count the resources required to obtain that output reliably.

Helpful background. The circuit model supplies gates, measurements and classical control. Classical information explains probability and fair comparisons, while quantum oracles distinguishes different ways to access an input.

Choose a path through the chapter

For a first encounter, begin with algorithmic primitives. Follow Grover search into amplitude amplification to see how reflections rotate amplitude toward useful outcomes. For the second recurring idea, review phase kickback and the Fourier transform before phase estimation: controlled evolution writes a phase into a register, and inverse-Fourier interference decodes it.

Read phase estimation before amplitude estimation, which joins these two routes by estimating the eigenphases of an amplitude-amplification operator. A probability becomes a rotation angle to be inferred, rather than only an outcome to be sampled. The later pages compare the access, precision and repetition costs that make this distinction useful.

What would you like to understand?	Pages to read
How an oracle query becomes interference	Algorithmic primitives, query complexity
The first exact oracle algorithms	Deutsch–Jozsa, Bernstein–Vazirani, Simon
Search and probability estimation	Grover search, amplitude amplification, amplitude estimation
Phases, periods and factoring	Phase estimation, Shor’s algorithm
Evolution, matrices and graph structure	Hamiltonian simulation algorithms, quantum linear algebra, block encodings and QSVT, quantum walks
Optimization with a quantum–classical loop	Variational algorithms, QAOA, VQE
Algorithms for scientific and data tasks	Quantum machine learning, chemistry and materials, optimization
What speedups are proved or still unknown	Quantum complexity classes, lower bounds and limitations

For applications, also ask whether the encoded physical model is appropriate: quantum simulation separates model error from error in solving that model.

Problems, outputs and reliable answers

A promise states which inputs the algorithm must handle. A worst-case guarantee applies to every promised input; an average over a selected distribution is weaker. For an estimate $\widehat z$ of $z$, a common requirement is

$$\Pr[|\widehat z-z|\leq\epsilon]\geq1-\delta.$$

The accuracy $\epsilon$ and failure probability $\delta$ are different parameters. Reducing either can increase the required work. An algorithm returning a quantum state proportional to a solution vector does not automatically return a classical list of all its components. Likewise, one sample from a distribution is different from learning that distribution or estimating an expectation to high precision.

The input description matters just as much. A classical table, a reversible lookup, a prepared state and controlled Hamiltonian evolution are distinct resources. An algorithm may legitimately assume one is supplied, but a practical application must also account for constructing it.

A finite search example

Suppose exactly one of sixteen positions is marked. Both algorithms can query its Boolean predicate; the quantum version can use the reversible query coherently. A target ancilla in $| -\rangle$ converts that query into a phase flip on the marked address.

Starting from the uniform four-qubit state, three Grover iterations give marked-item probability

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

Each iteration uses one predicate query and one diffusion reflection. A final measurement returns one index. The result is not certain, and this one-shot procedure does not include verification or retry.

For a uniformly located mark, three distinct classical queries followed by a guess among the unqueried positions succeed with probability

$$\frac3{16}+\frac{13}{16}\frac1{13}=\frac14.$$

The extra $1/16$ comes from the final guess; omitting it would give an unfair finite comparison. These are query-model probabilities. They do not count oracle construction, state preparation, diffusion synthesis, error correction or elapsed time. The Grover page derives the rotation and explains the optimal asymptotic query scaling.

Why three powered calls can cost seven time units

Suppose a supplied eigenstate obeys $U|u\rangle=e^{2\pi i(3/8)}|u\rangle$. Ideal phase estimation uses three controls with controlled powers $U$, $U^2$, $U^4$, then an inverse Fourier transform. In most-significant-bit-first notation, the result is 011, representing $3/8$, with probability one.

There are three calls if each controlled power is an available primitive. If powers are implemented sequentially from base-$U$ evolution, the total interrogation is $1+2+4=7$ time units, while the longest individual block lasts four. Preparation and decoding add further work. The standard circuit must preserve the phase relationships needed for interference across its schedule; a single hardware coherence-time requirement cannot be inferred from the longest power alone. The target must also remain in the relevant eigenphase sector.

One exactly representable phase tests a finite circuit identity. It establishes no asymptotic speedup, and a classical comparison depends on how $U$ is specified and accessed.

From complexity to practical cost

Query count, gate count, circuit depth, memory, number of preparations and physical time measure different resources. For unique-mark search over $N=2^n$ addresses, $\Theta(\sqrt N)$ queries are a quadratic improvement in $N$ but still exponential in the address length $n$.

An upper bound shows that an algorithm exists. Proving a speedup over every classical algorithm also requires a suitable lower bound. Factoring has a polynomial-time quantum algorithm, but no classical superpolynomial lower bound is known. BQP and BPP have not been proved unequal. Oracle separations answer questions about specified black-box models and do not automatically settle those unrelativized classes.

Hybrid methods add measurement and classical optimization costs. A low VQE training energy alone does not bound the ground-state error: finite sampling, ansatz restrictions, optimization and model errors remain. Selecting the best of many runs also requires counting all those runs and assessing the selected parameters with fresh measurements.

Use algorithmic benchmarking for comparisons at matched output quality, resource estimation tools to translate logical operations into implementation costs, and verification of quantum advantage to distinguish mathematical results from experimental demonstrations. Montanaro’s survey provides a broad introduction to the algorithm families in this chapter.

Exercises

Search size versus address size

Rewrite $\sqrt N$ when $N=2^n$. Does Grover search become polynomial in $n$?

Solution

$\sqrt N=2^{n/2}$, which is exponential in $n$. The improvement is from a number of queries proportional to $N$ to one proportional to $\sqrt N$, under the unstructured-search assumptions. It is not a general polynomial-time solution of exponentially large search spaces.

Include the final classical guess

For one uniformly located mark among $N$ positions, query $q<N$ distinct positions and, after all negative answers, guess uniformly among the rest. Find the total success probability.

Solution

A queried position is marked with probability $q/N$. Otherwise the final guess succeeds with conditional probability $1/(N-q)$. Thus the total is $(q+1)/N$. At $q=N-1$ the promise identifies the last item with certainty without querying it.

Powered access with four bits

If four control qubits use $U,U^2,U^4,U^8$, compare the powered-call count, repeated-base-$U$ count and maximum block duration.

Solution

They are four calls, fifteen base-$U$ units and eight units respectively. None includes state preparation or inverse-Fourier decoding. These counts coincide neither with one another nor with a hardware runtime unless an implementation model connects them.

Sampling versus reconstructing

A circuit produces one $n$-bit sample from $q(x)$. Has it returned a classical description of all $2^n$ probabilities?

Solution

No. It returns one outcome, not the probability attached to every possible outcome. Reconstructing the distribution or estimating selected observables is a different statistical task requiring additional samples and assumptions. A speedup comparison must give both methods the same requested output.

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.
• 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. 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.
• 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.