4. Canonical Quantum Algorithms

Introduction and Context

Quantum algorithms are not simply classical procedures executed on unfamiliar hardware. They are computational constructions that exploit interference, entanglement, phase evolution, and measurement in ways for which no general classical analogue exists. Their significance lies less in replacing every classical algorithm than in identifying problem structures for which quantum state space and quantum dynamics provide a provable or potentially decisive advantage.

This chapter develops a group of canonical algorithms that form the conceptual core of quantum computing: the quantum Fourier transform (QFT), quantum phase estimation (QPE), amplitude amplification and estimation, Grover search, Shor factorization, quantum walks, and quantum linear-system methods. These algorithms are closely related. The QFT and phase estimation expose hidden periodicity and eigenphase information; amplitude amplification and estimation manipulate and infer probabilities; quantum walks provide dynamics for graph and search problems; and linear-system algorithms use spectral information to encode solutions of algebraic systems.

A doctoral understanding requires more than memorizing circuit diagrams. Each algorithm must be examined through its assumptions, oracle model, precision requirements, query complexity, gate complexity, data-access assumptions, error sensitivity, and relationship to classical baselines. In particular, headline speedups often depend on conditions that are difficult to satisfy in practice. The central question is therefore not merely whether a quantum algorithm is asymptotically faster, but under what computational model, for which input structure, and at what total system cost.

Learning Objectives

By the end of this chapter, the reader should be able to:

1. Explain the mathematical role of Fourier transforms, eigenphases, amplitudes, and spectral decompositions in quantum algorithms.

2. Derive the principal steps of QFT, QPE, amplitude amplification, Grover search, and Shor’s algorithm.

3. Distinguish query complexity, gate complexity, space complexity, precision cost, and data-loading cost.

4. Evaluate quantum-walk and quantum-linear-system methods under realistic assumptions.

5. Identify sources of error, limitations, misleading speedup claims, and implementation risk.

6. Select appropriate algorithmic approaches for cryptanalysis, search, simulation, graph analysis, and scientific computing.

The Algorithmic Lens: Oracles, Spectra, and Resources

Many quantum algorithms are described using an oracle. An oracle is an abstract operation that supplies access to a function or structured object, such as a Boolean predicate, a graph adjacency relation, or a unitary transformation. Oracle notation is valuable because it isolates the computational query from the remaining circuit. However, it can also conceal the cost of constructing, storing, or implementing the oracle. A claimed query speedup is meaningful only when oracle implementation is comparable across classical and quantum models.

Three mathematical ideas recur throughout the chapter. First, a unitary operator has eigenvectors and eigenvalues of the form $e^{2\pi i\phi}$, where $\phi$ is an eigenphase. Estimating $\phi$ can reveal periods, energies, or spectral properties. Second, quantum amplitudes are complex numbers whose squared magnitudes are probabilities. Algorithms can increase the amplitude of desirable states through controlled interference. Third, many computational problems can be expressed in terms of a spectrum: frequencies for Fourier analysis, eigenphases for unitary operators, eigenvalues for matrices, or eigenvalues of graph operators for walks.

Resource analysis should separate:

• Query complexity, the number of oracle uses.
• Gate complexity, the total number of elementary operations.
• Circuit depth, important when coherence time is limited.
• Qubit complexity, including data, ancilla, and error-correction overhead.
• Precision complexity, the cost of estimating a quantity to a specified accuracy.
• Input and output complexity, especially when classical data must be loaded or a large quantum state must be measured.

These distinctions are essential because a polynomial or quadratic query advantage may disappear after state preparation, arithmetic, verification, or fault-tolerant implementation is included.

The Quantum Fourier Transform and the Discovery of Periodicity

For an integer $N=2^n$, the QFT is the unitary transformation

$$

\mathrm{QFT}_N|x\rangle = \frac{1}{\sqrt{N}}\sum_{y=0}^{N-1}e^{2\pi ixy/N}|y\rangle.

$$

It is the quantum analogue of the discrete Fourier transform, but its output is a quantum state rather than an explicit list of Fourier coefficients. The transformation changes the basis in which periodic structure is expressed. A state concentrated on values separated by a period becomes concentrated, after the QFT, near frequencies related to the reciprocal of that period.

The circuit is constructed from Hadamard gates and controlled phase rotations. A typical decomposition applies a Hadamard to the most significant qubit, followed by controlled rotations from less significant qubits, and continues recursively. The output qubits are then reversed. An exact decomposition requires $O(n^2)$ elementary controlled rotations and Hadamard gates. Approximate QFT circuits omit very small-angle rotations, reducing gate count and depth while introducing a controllable approximation error. The QFT therefore illustrates a recurring engineering trade-off: exact algebraic structure may be less valuable than an approximate circuit compatible with hardware constraints.

The inverse QFT is particularly important. In phase estimation, it converts phase information stored in relative phases into computational-basis bit strings that can be measured. In period-finding, it turns hidden periodicity into observable peaks.

The QFT should not be interpreted as a general-purpose method for reading all Fourier coefficients efficiently. Measurement yields only limited classical information from a quantum state. Its advantage arises when the desired answer is a structured feature, such as a period or eigenphase, rather than the complete transformed vector.

Quantum Phase Estimation

Suppose a unitary $U$ has an eigenvector $|\psi\rangle$ satisfying

$$U|\psi\rangle=e^{2\pi i\phi}|\psi\rangle,$$

where $0\leq \phi<1$. Quantum phase estimation estimates $\phi$. It uses an $m$-qubit counting register, an eigenstate register initialized to $|\psi\rangle$, controlled applications of $U^{2^j}$, and an inverse QFT on the counting register.

After the Hadamard gates and controlled powers, the state has the form

$$

\frac{1}{2^{m/2}}\sum_{k=0}^{2^m-1}e^{2\pi i k\phi}|k\rangle|\psi\rangle.

$$

The inverse QFT transforms the phase progression into an estimate of $\phi$. If $\phi$ has an exact $m$-bit binary representation, the result can be exact in the ideal circuit. Otherwise, measurement produces a distribution concentrated near the best $m$-bit approximation. The precision is approximately $2^{-m}$, while the probability of obtaining a useful estimate can be amplified through repetition or more refined estimation procedures.

The eigenstate assumption is fundamental. If the input is a superposition of eigenstates, phase estimation produces an eigenphase sampled according to the squared overlap with those eigenstates. This can be useful, but it means that state preparation determines which spectral information is accessible. Furthermore, implementing $U^{2^j}$ may dominate the cost. A nominally efficient phase-estimation circuit is not efficient if controlled powers require exponentially expensive recompilation or simulation.

QPE underlies quantum simulation, energy estimation, factoring, and several algorithms for matrix functions. In fault-tolerant settings, phase estimation is often one of the most resource-intensive components because it requires long coherent circuits and precise controlled operations.

Amplitude Amplification, Estimation, and Grover Search

Let $A$ be a state-preparation unitary such that

$$A|0\rangle=\sqrt{a}|\text{good}\rangle+\sqrt{1-a}|\text{bad}\rangle.$$

Amplitude amplification increases the probability of measuring a good state. Define a phase oracle that changes the sign of good states and a reflection about the initial state. Their product is a rotation in the two-dimensional space spanned by the normalized good and bad components. If $\sin^2\theta=a$, one amplification iteration changes the state angle from $\theta$ to approximately $3\theta$; after $k$ iterations, the good-state probability is

$$\sin^2((2k+1)\theta).$$

The optimal iteration count is approximately $\pi/(4\sqrt{a})$. If $a$ is known and small, amplification uses $O(1/\sqrt{a})$ applications of the oracle, compared with $O(1/a)$ classical independent trials.

Grover’s algorithm is the special case in which there is one or a known number of marked items among $N$ possibilities. Beginning with the uniform superposition, the oracle marks solutions and the diffusion operator reflects amplitudes about their mean. For one marked item, approximately $(\pi/4)\sqrt{N}$ iterations maximize the success probability. The quantum query complexity is $\Theta(\sqrt{N})$, and the lower bound for unstructured quantum search is also $\Omega(\sqrt{N})$; thus the quadratic improvement is asymptotically optimal in the query model.

Grover search is not a universal substitute for indexing or database systems. It applies when the search space lacks exploitable structure and when a coherent oracle can evaluate the predicate. If the predicate is expensive, the oracle cost may dominate. If the number of solutions is unknown, fixed iteration counts can overshoot the optimum; adaptive or randomized variants are preferable.

Amplitude estimation estimates $a$ rather than merely amplifying good states. The canonical QPE-based method achieves an additive error $\epsilon$ with query complexity of order $O(1/\epsilon)$, compared with $O(1/\epsilon^2)$ samples for classical Monte Carlo, subject to coherent access to the state-preparation and marking operations. This has attracted interest in risk analysis, option pricing, integration, and machine-learning subroutines. The advantage is meaningful only if the quantum state can be prepared efficiently and if the required coherent oracle is available.

Shor’s Algorithm: Period Finding and Integer Factorization

Shor’s factoring algorithm reduces integer factorization to order finding. Let $N$ be the integer to be factored, and choose an integer $a$ relatively prime to $N$. The order $r$ of $a$ modulo $N$ is the smallest positive integer satisfying

$$a^r\equiv 1\pmod N.$$

If $r$ is even and $a^{r/2}\not\equiv -1\pmod N$, then nontrivial factors of $N$ can often be obtained from

$$\gcd(a^{r/2}-1,N)\quad\text{and}\quad\gcd(a^{r/2}+1,N).$$

The classical part chooses $a$, computes modular arithmetic, and performs the greatest-common-divisor calculations. The quantum part finds $r$ by creating a superposition over exponents, computing modular powers, applying a QFT or inverse QFT, and measuring a value close to a multiple of $Q/r$, where $Q$ is a suitably chosen power of two. Continued-fraction expansion recovers $r$ from the measured rational approximation.

The algorithm is powerful because period finding can be performed in time polynomial in $\log N$ under the standard gate model. This contrasts with the best known general-purpose classical factoring methods, whose complexity is subexponential rather than polynomial. Shor’s algorithm also provides a framework for discrete logarithms, threatening public-key systems based on factoring and discrete-logarithm assumptions.

The result is probabilistic. Some choices of $a$ fail to reveal useful factors, and the quantum measurement may require repetition. Modular multiplication, reversible arithmetic, error correction, and long coherent execution are major implementation costs. The algorithm does not break symmetric cryptography in the same direct way; Grover-type methods generally provide a quadratic, rather than exponential, search improvement against brute-force key search, motivating longer symmetric keys.

Quantum Walks and Spectral Exploration

Quantum walks generalize classical random walks by replacing probability distributions with amplitudes. In a discrete-time walk, a coin or internal-state register determines a conditional shift on a graph. In a continuous-time walk, a Hamiltonian derived from the graph—often its adjacency matrix or Laplacian—drives the evolution.

Interference distinguishes quantum walks from classical diffusion. Amplitudes travelling along different paths can reinforce or cancel, producing faster spreading, localization, or enhanced hitting probabilities. Quantum walks support search algorithms, element distinctness, graph traversal, spatial navigation, and models of physical transport.

Their performance depends strongly on graph structure. Spectral gaps, expansion, hitting times, marked-set geometry, and the choice of discrete- versus continuous-time dynamics determine the advantage. A quantum walk may achieve a quadratic improvement in certain hitting-time or search settings, but there is no universal speedup for arbitrary graphs. Graph loading and the cost of implementing adjacency or transition operators must be counted.

Quantum walks also provide a conceptual bridge between algorithms and physics. The same spectral quantities that determine mixing in classical Markov chains influence quantum propagation, but the interference pattern can be qualitatively different. This makes quantum walks useful both as algorithms and as simulation models for transport, networks, and Hamiltonian dynamics.

Quantum Linear-System Methods

Consider a sparse linear system

$$A\mathbf{x}=\mathbf{b},$$

where $A$ is suitably well-conditioned and the goal is to prepare a quantum state proportional to $\mathbf{x}=A^{-1}\mathbf{b}$. The Harrow–Hassidim–Lloyd (HHL) algorithm provides the canonical framework. It assumes efficient preparation of $|b\rangle$, efficient simulation of $A$, sparsity or another structured representation, and a promise that relevant eigenvalues lie within a controlled range.

The algorithm expands $|b\rangle$ in the eigenbasis of a Hermitian matrix $A$:

$$|b\rangle=\sum_j\beta_j|u_j\rangle,

\qquad A|u_j\rangle=\lambda_j|u_j\rangle.$$

Phase estimation approximates the eigenvalues $\lambda_j$. A controlled rotation maps each component to an amplitude proportional to $1/\lambda_j$. Uncomputing the eigenvalue register leaves a state proportional to

$$A^{-1}|b\rangle=\sum_j\frac{\beta_j}{\lambda_j}|u_j\rangle,$$

provided the inversion is properly normalized and small eigenvalues are controlled. Measurement then estimates selected properties of $|x\rangle$, rather than revealing every coordinate of the classical vector.

The condition number $\kappa=\lambda_{\max}/\lambda_{\min}$ strongly affects complexity. Poor conditioning increases precision requirements and amplifies error. The original HHL analysis suggested favorable dependence on system dimension under idealized assumptions, but later improvements and practical analyses emphasize dependence on sparsity, $\kappa$, precision, state preparation, observable estimation, and fault-tolerant arithmetic.

Linear-system quantum algorithms are therefore best understood as state-preparation and expectation-estimation methods. They are not automatically faster ways to print a classical solution vector. If all $n$ entries of the solution are required, measurement alone may eliminate the apparent advantage. Applications are more plausible when only global properties, correlations, or expectation values are needed—for example, in scientific modeling, regression, finite-element analysis, and portfolio optimization.

An Illustrative Case Study: Quantum Risk Estimation for a Structured Portfolio

Background

Consider a financial-technology research group evaluating whether a quantum algorithm could improve Monte Carlo estimation of a portfolio loss probability. The portfolio contains many correlated assets, and the organization currently uses classical simulation to estimate a tail-risk measure.

Situation and Problem

The research team proposes amplitude estimation because its theoretical sampling complexity scales linearly rather than quadratically with the inverse of the target precision. Management asks whether this constitutes an immediately deployable quantum advantage.

Analysis

The proposed method requires a state-preparation unitary encoding the probability distribution of market factors, a reversible circuit computing portfolio loss, and a marking operation identifying losses above a threshold. The analysis reveals four constraints. First, loading historical correlations into a coherent quantum state is nontrivial. Second, the loss function involves fixed-point arithmetic and conditional logic, producing a large oracle. Third, fault-tolerant amplitude estimation requires deep coherent circuits. Fourth, the organization needs a numerical estimate, so repeated execution and confidence-interval construction remain necessary.

The team compares three models: classical Monte Carlo with optimized variance reduction, a quantum algorithm with idealized oracle costs, and a fault-tolerant estimate including arithmetic and error correction. The idealized model shows the expected asymptotic advantage. The realistic model shows that state preparation and oracle construction dominate for the portfolio sizes under consideration.

Approach and Strategy

Rather than claiming immediate replacement of the classical system, the team develops a hybrid research program. It identifies a reduced synthetic portfolio, implements the marking oracle, benchmarks amplitude estimation against classical quasi-Monte Carlo, and measures total logical operations rather than oracle calls alone. It also investigates iterative amplitude-estimation variants that avoid a full QFT and may reduce circuit depth.

Outcome

The study does not establish present-day operational superiority, but it identifies a credible long-term application if reusable data-loading methods, fault-tolerant arithmetic, and compact financial models become available. The organization retains the classical estimator and creates a quantum-readiness criterion based on total cost, precision, verification, and data-access assumptions.

Learning Points

The case illustrates that an algorithmic speedup is conditional. Amplitude estimation can reduce the number of samples, but it cannot remove the cost of defining the sample distribution, evaluating the payoff, preparing coherent inputs, or validating the output. A sound feasibility study must therefore benchmark the complete computational pipeline.

Assumptions, Risks, and Common Misinterpretations

The most common mistake is to quote asymptotic complexity without specifying the model. A QFT may be efficient as a circuit while its output remains difficult to interpret classically. Grover search may reduce oracle queries while leaving oracle construction unchanged. HHL may have favorable dimension dependence while requiring costly state preparation and yielding only a quantum state. QPE may offer high precision while demanding controlled powers of a unitary and long coherence times.

Noise introduces additional difficulties. Phase errors can shift interference peaks; imperfect reflections reduce amplification; arithmetic errors distort modular computations; and errors in Hamiltonian or matrix simulation accumulate over long circuits. Error mitigation may help near-term experiments, but it does not generally provide the same scalable guarantees as fault-tolerant error correction.

Verification is also nontrivial. A quantum output is often probabilistic, and reproducing a classical answer may require many measurements. For cryptographic algorithms, verification of a factor is easy once a candidate is produced. For expectation estimation, confidence intervals and independent validation are essential. For linear-system algorithms, one must specify which observable is estimated and how estimation error is bounded.

Professional practice requires explicit accounting for oracle assumptions, input encoding, precision, success probability, repetitions, connectivity constraints, compilation, and error correction. Claims should distinguish a mathematical speedup, a fault-tolerant resource estimate, and an experimentally demonstrated advantage.

Governance, Security, and Ethical Considerations

Shor’s algorithm has direct implications for governance because quantum-capable adversaries could compromise vulnerable public-key infrastructure. Organizations should inventory cryptographic dependencies, adopt migration strategies toward post-quantum cryptography, and consider the “harvest now, decrypt later” threat to long-lived confidential data. Quantum algorithms themselves are dual-use technologies: the same techniques may support scientific discovery, optimization, and security analysis while also enabling cryptanalysis.

Research teams should report assumptions transparently, avoid overstating commercial readiness, and preserve reproducibility through circuit specifications, resource models, and benchmark datasets. In financial, medical, and public-sector applications, probabilistic quantum outputs must not bypass established validation, auditability, privacy, or accountability requirements.

Current Directions and Best Practices

Current research is moving toward resource-efficient phase estimation, iterative and maximum-likelihood amplitude estimation, block-encoding and quantum singular-value transformation, improved Hamiltonian simulation, quantum signal processing, and quantum walks tailored to structured graphs. These developments often replace specialized circuits with more general polynomial-transformation frameworks, but they also make oracle and block-encoding costs central to the analysis.

Best practice is to begin with a precise computational task and a classical baseline. Then specify the input model, oracle implementation, output observable, precision, success probability, and complete resource budget. Use small instances for validation, compare ideal and noisy simulations, and report depth and qubit counts in addition to query complexity. Finally, treat quantum algorithms as components in hybrid workflows rather than assuming that a quantum subroutine automatically determines the performance of the entire application.

Chapter Summary

Canonical quantum algorithms exploit a small set of recurring mechanisms: Fourier transformation reveals periodic structure; phase estimation extracts eigenphases; amplitude amplification increases the probability of desired outcomes; amplitude estimation estimates probabilities with improved sampling complexity; quantum walks use interference on graphs; and linear-system methods manipulate spectral decompositions to prepare solution states. Grover’s algorithm provides a quadratic speedup for unstructured search, while Shor’s algorithm uses quantum period finding to factor integers in polynomial time under the standard gate model.

Their resource requirements are conditional. Efficient query complexity does not guarantee efficient implementation, because state preparation, oracle construction, arithmetic, precision, measurement, compilation, and error correction may dominate. The correct doctoral-level evaluation therefore combines derivation with critical resource analysis. Quantum advantage is most credible when the input has exploitable structure, the required operations are coherently implementable, and the desired output is compact enough to extract without excessive measurement cost.

Key Terms

QFT: A unitary transformation that maps computational-basis amplitudes into frequency-domain amplitudes.

Eigenphase: The phase $\phi$ in a unitary eigenvalue $e^{2\pi i\phi}$.

Quantum phase estimation: An algorithm for estimating the eigenphase of a unitary given access to its eigenstate.

Oracle: An abstract or implemented operation that provides access to a function or structured problem instance.

Amplitude amplification: A procedure that increases the amplitude, and therefore probability, of marked states.

Amplitude estimation: A quantum method for estimating the probability associated with a marked component of a prepared state.

Grover diffusion operator: A reflection about the uniform superposition or, more generally, the initial state.

Period finding: Determining the smallest period of a modular or other structured function.

Order: The least positive integer $r$ satisfying $a^r\equiv1\pmod N$.

Shor’s algorithm: A quantum period-finding algorithm with applications to factoring and discrete logarithms.

Quantum walk: A quantum evolution on a graph involving amplitudes, interference, and conditional or Hamiltonian propagation.

Spectral gap: A separation between relevant eigenvalues that influences convergence, propagation, or algorithmic complexity.

Hamiltonian: An operator governing continuous-time quantum evolution.

Condition number: A measure, commonly $\kappa$, of the ratio between largest and smallest relevant singular or eigenvalues.

Quantum linear-system algorithm: A method that prepares a quantum state related to the solution of a structured linear system.

State preparation: The circuit process of creating a quantum state encoding an input distribution or vector.

Query complexity: The number of calls to an oracle or black-box operation.

Gate complexity: The total number of elementary quantum operations in a circuit.

Fault tolerance: Reliable computation using error-correcting methods despite imperfect physical operations.

Block-encoding: A technique for representing a matrix within a larger unitary operator.

Review Questions

Short Answer Questions

1. What information does the QFT make observable in a period-finding algorithm?

2. Why must the input to standard phase estimation be an eigenstate, or a controlled superposition of eigenstates?

3. State the asymptotic query complexity of Grover search for one marked item among $N$ possibilities.

4. Why does the condition number affect quantum linear-system algorithms?

5. Distinguish query complexity from gate complexity.

Long Answer Questions

1. Derive the main state transformation used in quantum phase estimation and explain the role of the inverse QFT.

2. Explain amplitude amplification geometrically and derive the dependence of the optimal iteration count on the initial success probability.

3. Describe how Shor’s algorithm reduces factoring to order finding, including the classical post-processing step.

4. Compare discrete-time and continuous-time quantum walks and discuss the role of graph spectra.

5. Critically evaluate the assumptions behind quantum linear-system algorithms and explain why they do not generally produce a classical solution vector directly.

Analytical / Application Questions

1. A problem has an initial marked-state probability of $10^{-4}$. Estimate the order of magnitude of amplitude-amplification iterations required and identify the assumptions needed for this estimate.

2. A proposed quantum risk-estimation system reports a quadratic sampling advantage but requires a costly circuit to load market data. Design a resource-accounting framework to determine whether the claim remains meaningful.

3. An organization expects a fault-tolerant quantum computer to threaten its long-lived encrypted records. Using the algorithms discussed in this chapter, formulate a technically and organizationally appropriate migration response.

22. Multiple Choice Questions with Answers

Question 1

What is the primary role of the inverse QFT in standard quantum phase estimation?

A. To prepare the eigenstate of the unitary

B. To convert accumulated phase information into a measurable computational-basis estimate

C. To amplify marked database entries

D. To perform modular greatest-common-divisor calculations

Correct Answer: B. To convert accumulated phase information into a measurable computational-basis estimate

Question 2

If the initial probability of a good state is a, the query complexity of amplitude amplification is generally of order

A. O(a)

B. O(1/a)

C. O(1/√a)

D. O(log a)

Correct Answer: C. O(1/√a)

Question 3

Which condition is essential for the standard period-finding explanation of Shor’s algorithm?

A. The chosen base must be equal to the number being factored

B. The modular order must be found with useful probability

C. The input integer must be prime

D. The QFT must output every Fourier coefficient classically

Correct Answer: B. The modular order must be found with useful probability

Question 4

Why can an HHL-type algorithm fail to provide a practical speedup despite favorable dependence on system dimension?

A. It cannot use unitary operations

B. It requires state preparation, matrix simulation, conditioning, and observable extraction to be efficient

C. It works only for Boolean functions

D. It has no dependence on numerical precision

Correct Answer: B. It requires state preparation, matrix simulation, conditioning, and observable extraction to be efficient

Question 5

Which statement best characterizes Grover’s algorithm?

A. It provides an exponential speedup for all database searches

B. It provides a quadratic query improvement for unstructured search

C. It factors integers through eigenvalue inversion

D. It estimates arbitrary Fourier spectra exactly in one measurement

Correct Answer: B. It provides a quadratic query improvement for unstructured search

Question 6

In quantum phase estimation, if the input is a superposition of eigenstates, measurement generally produces

A. The average eigenphase deterministically

B. An eigenphase sampled according to the squared overlap with the corresponding eigenstate

C. No phase information

D. A classical vector containing all eigenvectors

Correct Answer: B. An eigenphase sampled according to the squared overlap with the corresponding eigenstate

Question 7

What is the principal source of interference-based behavior in a quantum walk?

A. Classical probability normalization only

B. Reinforcement and cancellation of amplitudes along different paths

C. Removal of all graph edges

D. Automatic preparation of a uniform classical distribution

Correct Answer: B. Reinforcement and cancellation of amplitudes along different paths

Question 8

Which resource is often hidden when a quantum algorithm is described only by oracle-query complexity?

A. The existence of measurement

B. The cost of implementing the oracle and preparing its input state

C. The number of logical answers

D. The definition of a qubit

Correct Answer: B. The cost of implementing the oracle and preparing its input state

Question 9

For a QFT on N = 2^n basis states, a standard exact circuit uses approximately

A. O(1) gates independent of n

B. O(n) controlled rotations only

C. O(n^2) elementary operations

D. O(2^n) measurements

Correct Answer: C. O(n^2) elementary operations

Question 10

Why are post-quantum cryptographic preparations relevant to Shor’s algorithm?

A. Shor’s algorithm directly increases symmetric-key brute-force security

B. Shor’s algorithm threatens cryptosystems based on factoring and discrete logarithms

C. Shor’s algorithm prevents all data loading

D. Shor’s algorithm applies only to graph traversal

Correct Answer: B. Shor’s algorithm threatens cryptosystems based on factoring and discrete logarithms