λ · Interview preparation

Quantum Algorithms

Study questions and source-based explanations extracted from the supplied PDF. Mathematical expressions are reproduced as text here; use the original PDF for authoritative typesetting and complex formula layout.

Open original PDF All subjects

Filter this subject

3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

Source page 3

Quantum Algorithms Deck 1 Circuit Foundations for Algorithms Circuit Foundations for Algorithms

Q1.1 What is ”quantum parallelism,” and why is it not, by itself, suﬀicient to explain why quantum computers can outperform classical ones?

Applying a quantum operation to a qubit register prepared in an equal superposition of all 2n possible input states (e.g. via Hadamard gates on every qubit) evaluates a function on all 2n inputs simultaneously, encoded within a single quantum state’s amplitudes – this is quantum parallelism. However, this alone is insuﬀicient for computational advantage because a direct measurement of that superposition only ever yields one randomly selected output, with no way to directly read out all 2n results at once – the exponentially many parallel computations are real, but simply reading them out naively destroys nearly all of that parallel information. The actual power of quantum algorithms comes from cleverly using interference to arrange for the specific answer of interest to be amplified in probability before measurement, not from parallelism alone.

Q1.2 What is quantum interference, and why is it the actual mechanism that gives quantum al- gorithms their computational advantage?

Quantum amplitudes are complex numbers that can combine constructively (adding up, increasing the probability of a given measurement outcome) or destructively (canceling out, reducing that probability to near zero) when different computational paths leading to the same final state are combined – a phenomenon with no classical probabilistic ana- logue, since ordinary probabilities are always non-negative and can only add, never cancel. A well-designed quantum algorithm arranges its sequence of gates so that computational paths leading to wrong answers interfere destructively (canceling out) while paths leading to the correct answer interfere constructively (reinforcing) – concentrating the measurement probability onto the desired outcome. This deliberate engineering of interference patterns, not merely the existence of superposition, is the actual source of quantum algorithmic speedups.

Q1.3 What is a quantum oracle, and why do many foundational quantum algorithms (Grover’s, Deutsch-Jozsa, Simon’s) analyze their speedup relative to a ”black-box” oracle rather than a concrete problem?

An oracle is an idealized black-box quantum subroutine that computes some function f(x) reversibly (typically as |x⟩|y⟩→|x⟩|y⊕f(x)⟩) without the algorithm needing to know or exploit how the oracle internally computes it – the algorithm’s performance is analyzed purely in terms of how many times it must query this oracle to solve the problem. This abstraction is useful because it isolates a clean, mathematically rigorous lower bound on query complexity that provably cannot be beaten by any algorithm treating the function as a black box, regardless of the function’s specific √ internal structure – letting researchers prove definitive statements like ”Grover’s algorithm’s O( N) query count is provably optimal for unstructured search” that hold universally, independent of implementation details, though it’s worth noting oracle-based speedups don’t always directly translate to speedups on concrete, fully-specified real-world problems where the function’s structure could potentially be exploited classically too.

Q1.4 What is the Deutsch-Jozsa algorithm, and why is it historically significant despite having little direct practical application?

The Deutsch-Jozsa algorithm solves a specifically constructed promise problem: given a black-box function guaran- teed to be either constant (same output for every input) or balanced (outputs 0 for exactly half of all inputs and 1

Source page 4

Quantum Algorithms Deck 1 for the other half), determine which case holds. Classically, this requires querying the function up to 2n−1 + 1 times in the worst case (in the deterministic, guaranteed-correct sense) to be certain; the Deutsch-Jozsa algorithm solves it with just one single quantum query, using superposition and interference to directly distinguish the two cases. It’s historically significant as one of the very first explicit, clean demonstrations that a quantum algorithm can provide a provable, exponential query-complexity advantage over any deterministic classical algorithm – even though the artificial constant-vs-balanced promise problem itself has essentially no direct real-world application, it served as an important early proof-of-concept establishing quantum query speedups were possible at all.

Q1.5 What does it mean for a set of quantum gates to be ”universal,” and why do the Hadamard, phase (T), and CNOT gates together suﬀice to approximate any quantum computation?

A universal gate set is one from which any arbitrary quantum operation (any unitary transformation on any number of qubits) can be constructed, or at least approximated to arbitrary precision, using only gates from that set – analo- gous to how NAND gates alone are universal for classical Boolean logic. The combination of Hadamard (creates superposition), T-gate (introduces a specific phase rotation), and CNOT (creates entanglement between qubits) is a commonly cited universal set: Hadamard and T together can approximate any single-qubit rotation to arbitrary precision (a consequence of the Solovay-Kitaev theorem), while CNOT provides the necessary two-qubit entangling interaction that no combination of purely single-qubit gates could ever produce – together, this small, discrete gate set is suﬀicient to build a circuit approximating any quantum algorithm whatsoever, which is precisely why real quan- tum hardware is typically engineered to implement just this small set of native gates reliably, rather than needing to directly implement every possible unitary operation in hardware.

Source page 5

Quantum Algorithms Deck 2 Core Algorithmic Primitives Core Algorithmic Primitives

Q2.1 What is the Quantum Fourier Transform (QFT), and how does its circuit complexity com- pare to the classical Fast Fourier Transform?

The QFT is the quantum-circuit analogue of the discrete Fourier transform, mapping a quantum state’s amplitudes into their Fourier-transformed counterparts, implemented as a specific sequence of Hadamard gates and controlled-phase- rotation gates. Its remarkable eﬀiciency is that it can be implemented using only O(n2) quantum gates for an n-qubit register (representing a transform over 2n amplitudes) – compared to the classical Fast Fourier Transform’s already- eﬀicient O(N log N) operations for N = 2n classical data points, the QFT is exponentially faster in terms of gate count for the equivalent-sized transform. Crucially, though, this speedup applies only to transforming the quantum amplitudes themselves – reading out all 2n transformed values classically would still require 2n measurements, so QFT’s power is only unlocked when used as a subroutine within a larger algorithm designed to extract just a small amount of useful information (like a specific period or phase) rather than the full transformed data vector.

Q2.2 What is Quantum Phase Estimation (QPE), and why is it considered one of the most impor- tant algorithmic subroutines underlying many other quantum algorithms?

QPE takes a unitary operator U and one of its eigenstates |ψ⟩(satisfying U|ψ⟩= e2πiθ|ψ⟩) as input, and outputs an estimate of the unknown phase θ to a specified precision, using a register of ancilla qubits, controlled applications of U, and an inverse QFT to extract the phase information. It’s considered foundational because an enormous range of important computational problems can be reformulated as phase estimation problems: Shor’s factoring algo- rithm is fundamentally a period-finding problem solved via phase estimation, and estimating the ground-state energy of a molecule in quantum chemistry simulation is directly a phase-estimation problem applied to the molecule’s time-evolution operator – QPE serves as a unifying algorithmic primitive that many seemingly unrelated quantum algorithms are, underneath, actually built upon.

Q2.3 What is amplitude amplification, and how does it generalize the core technique used inside Grover’s search algorithm to a broader class of problems?

Amplitude amplification is a generalization of the specific ”flip and reflect” iteration at the heart of Grover’s algo- rithm, applicable to any algorithm that can be framed as: prepare some quantum state (not necessarily a uniform superposition), and boost the probability amplitude of a ”marked” subspace of good outcomes relative to the rest, us- ing repeated applications of an oracle (marking good states) and a generalized reflection operator. Just as in Grover’s algorithm specifically, applying this amplification process roughly O(1/√p) times (where p is the initial probability of a good outcome) boosts that probability close to 1, versus the O(1/p) classical repetitions needed to achieve a similar success probability through naive repeated sampling – giving a quadratic speedup for a much broader class of ”amplitude boosting” problems than pure unstructured search alone, including tasks like quantum counting (esti- mating how many marked items exist) and certain Monte-Carlo-style estimation problems.

Q2.4 What is the Hadamard Test, and how is it used to measure the real or imaginary part of an expectation value ⟨ψ|U|ψ⟩without needing to fully reconstruct the quantum state?

The Hadamard Test uses a single extra ancilla qubit prepared in superposition, controlling whether the unitary U is applied to the main register, followed by another Hadamard gate on the ancilla before measuring it – the resulting

Source page 6

Quantum Algorithms Deck 2 probability of measuring the ancilla in a particular state is directly related to the real part of ⟨ψ|U|ψ⟩(a small modification, adding a phase gate, extracts the imaginary part instead). This is valuable because directly computing an expectation value classically would generally require fully characterizing the quantum state |ψ⟩(an exponentially costly task, in general) – the Hadamard Test instead extracts just the single, specific numerical quantity of interest directly from repeated measurement statistics on the ancilla qubit, without ever needing to reconstruct or fully know the underlying state |ψ⟩itself, a mechanism used as a core subroutine in many variational and simulation algorithms.

Source page 7

Quantum Algorithms Deck 3 Shor’s Algorithm Shor’s Algorithm

Q3.1 What is the core mathematical insight that reduces integer factoring to a ”period-finding” problem, which is what Shor’s algorithm actually solves?

To factor an integer N, Shor’s algorithm picks a random integer a coprime to N, and considers the function f(x) = ax mod N – this function is provably periodic, repeating with some period r (i.e. f(x + r) = f(x) for all x). Once this period r is known, elementary number theory shows that (with high probability, for a suitable choice of a) gcd(ar/2 −1, N) and gcd(ar/2 + 1, N) yield non-trivial factors of N – so the hard problem of factoring is reduced entirely to the problem of eﬀiciently finding this period r. Classically, finding this period for a large N requires effectively checking exponentially many candidate values of x, which is exactly as intractable as factoring itself – but a quantum computer can find the period eﬀiciently, which is precisely the speedup Shor’s algorithm provides.

Q3.2 How does Shor’s algorithm actually use Quantum Phase Estimation and the Quantum Fourier Transform to find the period r eﬀiciently?

The algorithm prepares a superposition over many values of x, computes ax mod N into a second register (entan- gling the two registers together based on the periodic structure of f), and then applies an inverse QFT to the first register. Because the underlying state has period r built into its structure, the QFT causes constructive interference concentrated at specific, evenly-spaced frequencies directly related to r (essentially, phase estimation applied to the modular exponentiation operator’s eigenvalues, which directly encode the period) – measuring the first register after this QFT yields, with high probability, a value from which the actual period r can be eﬀiciently recovered classically (typically via the continued-fractions algorithm). This is the concrete mechanism by which the abstract QFT/phase- estimation primitives discussed earlier are put to direct, practical use in solving a specific, famous computational problem.

Q3.3 Why does Shor’s algorithm still require substantial classical post-processing and number theory, rather than being a ”purely quantum” algorithm end-to-end?

The quantum portion of the algorithm’s job is specifically and only to eﬀiciently find the period r of the modular expo- nentiation function – everything else (choosing the random base a, reducing the factoring problem to period-finding via number theory, and, after the quantum measurement yields a candidate value, using the classical continued frac- tions algorithm to extract the actual period r from that measurement result, then computing the final gcd calculations to recover the actual prime factors) is all handled by conventional classical computation. This division of labor is actually typical of quantum algorithms generally, not a special weakness of Shor’s specifically: quantum computers are used surgically for the specific sub-computation where they provide a genuine, provable speedup (period-finding, in this case), while classical computers eﬀiciently handle everything else in the overall pipeline where they’re already perfectly adequate.

Q3.4 What is the difference in resource requirements between running Shor’s algorithm to factor a cryptographically relevant 2048-bit RSA key versus the small-number factoring demon- strations (e.g. factoring 15 or 21) that have actually been run on real quantum hardware to date?

Small demonstrations (factoring numbers like 15 or 21) have been run on early, small-scale, noisy quantum pro-

Source page 8

Quantum Algorithms Deck 3 cessors using only a handful of physical qubits, sometimes even exploiting problem-specific shortcuts that wouldn’t scale to larger numbers. Factoring an actual cryptographically relevant 2048-bit RSA modulus is estimated to re- quire several thousand stable, error-corrected logical qubits (translating to potentially millions of noisy physical qubits given current quantum error correction overhead) and a circuit depth requiring billions of reliable quantum gate operations executed with very low error rates throughout – a gap of many orders of magnitude beyond both the qubit count and the achievable gate fidelity/circuit depth of any quantum computer that exists today, which is pre- cisely why cryptographically-relevant factoring is still assessed to be years to decades away despite the small-number demonstrations already having been achieved.

Source page 9

Quantum Algorithms Deck 4 Grover’s Algorithm Grover’s Algorithm

Q4.1 What problem does Grover’s algorithm solve, and why is its quadratic (rather than expo- nential) speedup still considered highly significant?

Grover’s algorithm solves unstructured search: given a black-box function that marks exactly one (or a known number of) ”correct” item among N total unsorted, unstructured items, find that marked item. Classically, this requires checking items one by one, taking O(N) queries on average (and in the worst case) since there’s no structure √ to exploit. Grover’s algorithm finds the marked item using only O( N) oracle queries – a quadratic, not exponential, speedup. This is still highly significant because, unlike many quantum algorithms that require exploiting special mathematical structure in the problem (like Shor’s reliance on periodicity), Grover’s speedup applies to essentially any unstructured search problem with no special structure required at all – and, crucially, this quadratic speedup √ has been proven optimal: no quantum algorithm can solve unstructured search faster than O( N) queries, making Grover’s algorithm not just a useful technique but a fundamental, provable limit on how much quantum computing can ever help with this extremely general class of problem.

Q4.2 What is the geometric intuition behind Grover’s algorithm’s repeated ”oracle + diffusion” iteration, often visualized as a rotation in a two-dimensional subspace?

The algorithm’s full N-dimensional state space can be reduced, for analysis purposes, to just a two-dimensional subspace spanned by the (unknown) marked state and the uniform superposition of all the unmarked states. Starting from an equal superposition over all N items, the state vector begins very close to the ”unmarked” axis of this 2D plane; each Grover iteration (an oracle reflection combined with a ”diffusion” reflection about the average amplitude) geometrically rotates this state vector by a small, fixed angle, closer and closer toward the ”marked” axis. After ap- √ proximately O( N) such rotations, the state vector has rotated close enough to the marked-item axis that measuring the state yields the correct marked item with very high probability – this elegant geometric picture is why the algo- √ rithm requires roughly N iterations (each contributing a small angular rotation) rather than needing to check items one at a time.

Q4.3 What happens if you run ”too many” Grover iterations beyond the optimal number, and why does this matter for correctly implementing the algorithm?

Because each Grover iteration acts as a fixed rotation in the two-dimensional subspace described above, the success probability doesn’t simply keep monotonically increasing forever with more iterations – it oscillates. Continuing √ to apply Grover iterations past the optimal point (roughly π4 N iterations) rotates the state vector past the marked- item axis, actually decreasing the probability of measuring the correct answer again, in a periodic, oscillating pattern. This means correctly implementing Grover’s algorithm requires knowing (or accurately estimating) the right number of iterations to stop at – overshooting isn’t merely ”extra wasted work” the way over-iterating a classical algorithm might be, it can actively make the result worse, which is an important, somewhat counterintuitive practical detail for correctly implementing the algorithm.

Q4.4 Why does Grover’s algorithm not provide the same kind of dramatic threat to symmetric cryptography (like AES) that Shor’s algorithm poses to RSA?

Grover’s algorithm can be applied to brute-force a symmetric cipher’s key by treating ”checking whether a candidate

Source page 10

Quantum Algorithms Deck 4 key correctly decrypts the message” as the oracle – providing a quadratic speedup, reducing the effective brute- force search cost for an n-bit key from O(2n) down to O(2n/2). Crucially, this is only a quadratic speedup (not exponential, unlike Shor’s algorithm against RSA), and a quadratic speedup can be fully and simply compensated for by doubling the key length – AES-256 retains roughly AES-128-equivalent security even against a Grover- equipped quantum attacker, which remains considered strong by current standards. This is precisely why the post- quantum cryptographic transition effort focuses overwhelmingly on replacing public-key algorithms (vulnerable to Shor’s exponential break) rather than symmetric algorithms (which just need modestly longer keys to remain secure against Grover’s more modest speedup).

Source page 11

Quantum Algorithms Deck 5 Quantum Simulation Algorithms Quantum Simulation Algorithms

Q5.1 What did Richard Feynman originally propose as the motivating application for quantum computing, and why is it considered one of the most promising near-to-medium-term prac- tical use cases?

Feynman observed in 1982 that simulating quantum mechanical systems (molecules, materials, chemical reactions) on a classical computer requires resources that grow exponentially with the number of particles being simulated, since fully representing a general quantum many-body state requires exponentially many classical numbers (ampli- tudes) – quickly becoming intractable classically for even modestly-sized molecules of real chemical interest. He proposed that a computer built from quantum components could naturally represent and evolve such quantum states without this exponential blowup, since the simulating system is itself inherently quantum. This is considered espe- cially promising as a near-to-medium-term application (compared to, say, cryptographically-relevant Shor’s algo- rithm) because useful quantum chemistry and materials science simulations may require substantially fewer qubits and shallower circuits than breaking RSA encryption does – making it a leading candidate for where quantum com- puters might first deliver genuine practical value.

Q5.2 What is Hamiltonian simulation, and what is Trotterization (the Trotter-Suzuki decompo- sition) used for within it?

Hamiltonian simulation is the task of implementing the time-evolution operator e−iHt for a given quantum system’s Hamiltonian H (describing its energy and dynamics) as an actual quantum circuit. The diﬀiculty is that a realistic Hamiltonian is typically a sum of many individual terms (e.g. different pairwise interactions between particles) that generally don’t commute with each other, so e−i(H1+H2)t cannot simply be implemented as e−iH1t · e−iH2t directly – Trotterization approximates the full evolution by breaking the total time t into many small steps and, within each tiny step, applying each individual term’s (much easier to implement) evolution one after another in sequence; as the step size shrinks, this approximation converges to the true, full evolution, with the approximation error controllable by using smaller time steps (at the cost of needing more total circuit steps/gates).

Q5.3 What is the Variational Quantum Eigensolver (VQE), and why was it specifically designed to be more resilient to noise than a full, fault-tolerant phase-estimation-based approach to the same problem?

VQE estimates a Hamiltonian’s ground-state energy (a central, recurring quantity of interest across quantum chem- istry and materials science) using a hybrid quantum-classical loop: a relatively shallow, parameterized quantum circuit (”ansatz”) prepares a trial quantum state, the quantum computer measures the corresponding energy expecta- tion value for the current parameters, and a classical optimizer then adjusts those parameters to iteratively minimize the measured energy, repeating until convergence. This design was deliberately chosen over the theoretically more direct approach of using full quantum phase estimation to extract the ground-state energy, because VQE’s shallow circuits require substantially fewer sequential gate operations before decoherence corrupts the result – making it far more tolerant of the imperfect, noisy qubits available on today’s real (”NISQ,” Noisy Intermediate-Scale Quantum) hardware, at the cost of weaker theoretical guarantees on solution quality and a classical optimization loop that can itself get stuck or converge slowly.

Source page 12

Quantum Algorithms Deck 5

Q5.4 What is the ”ansatz” in a variational quantum algorithm like VQE, and why does choosing a good one represent a central, often problem-specific design challenge?

The ansatz is the specific, parameterized quantum circuit structure used to prepare candidate trial states, whose ad- justable parameters (typically rotation angles) the classical optimizer tunes during the algorithm’s iterative loop. Choosing a good ansatz involves a genuine trade-off with no universally correct answer: an ansatz that’s too sim- ple/shallow may not be expressive enough to represent the true ground state at all, no matter how its parameters are tuned (a fundamental limitation, not merely an optimization diﬀiculty) – while an ansatz that’s too complex/deep, though potentially more expressive, requires more gates (worsening noise/decoherence problems on real hardware) and introduces a much larger, harder-to-navigate parameter landscape for the classical optimizer, increasing the risk of getting stuck in poor local minima or encountering ”barren plateaus” (regions where the optimization gradient vanishes, stalling progress entirely) – making ansatz design a highly active, largely empirical and problem-specific area of ongoing research rather than a solved, one-size-fits-all component.

Source page 13

Quantum Algorithms Deck 6 Variational & NISQ-Era Algorithms Variational & NISQ-Era Algorithms

Q6.1 What does ”NISQ” (Noisy Intermediate-Scale Quantum) mean, and how does this era’s hardware reality shape the specific style of algorithm researchers currently favor?

NISQ, a term coined by John Preskill in 2018, describes the current and near-term era of quantum hardware: devices with a meaningful but still modest number of qubits (tens to a few thousand), which lack full quantum error correction and therefore accumulate errors/decoherence fairly quickly, limiting the practical circuit depth (number of sequential gate operations) that can be run before the result becomes too noisy to be useful. This hardware reality has di- rectly shaped algorithm research toward hybrid quantum-classical, variational approaches (like VQE and QAOA) specifically because they use comparatively shallow quantum circuits combined with classical optimization, rather than the deep, long circuits that algorithms like Shor’s (in its full, fault-tolerant form) fundamentally require – an explicit adaptation of algorithmic strategy to match what today’s imperfect, error-prone, pre-fault-tolerant hardware can actually still execute usefully.

Q6.2 What is the Quantum Approximate Optimization Algorithm (QAOA), and what class of real-world problems is it designed to address?

QAOA is a variational algorithm (structurally similar to VQE) specifically designed for tackling combinatorial op- timization problems – tasks like Max-Cut (partitioning a graph’s nodes into two groups to maximize the number of edges crossing between them), scheduling, or portfolio optimization, which are often classically NP-hard to solve exactly. It works by alternating between applying a ”problem” unitary (encoding the specific optimization problem’s cost function into phase rotations) and a ”mixer” unitary (which explores/mixes between different candidate solu- tions), for a number of alternating rounds p – with a classical optimizer tuning the parameters of both unitaries across rounds to maximize the probability of measuring a high-quality (low-cost, or near-optimal) solution. Like VQE, it’s specifically designed to be runnable using shallow, near-term-hardware-compatible circuits rather than requiring full fault tolerance.

Q6.3 What is ”quantum machine learning” (QML), and what is meant by the concept of a ”quan- tum kernel” for classification tasks?

Quantum machine learning explores using quantum circuits as components within (or entirely replacing parts of) classical machine learning pipelines, hoping to exploit quantum effects for some computational or expressivity ad- vantage. One prominent approach maps classical data points into an exponentially large quantum feature space (via a specific ”feature map” quantum circuit encoding the data into qubit states), then computes a quantum kernel – essentially a measure of similarity (overlap) between two data points’ corresponding quantum states, computed via a quantum circuit – which can then be fed into an otherwise entirely classical kernel-based algorithm (like a support vector machine) in place of a classical kernel function. The hope is that certain quantum feature maps might create similarity structures in this quantum feature space that are computationally hard to reproduce or even approximate classically, potentially giving a genuine advantage for specific, carefully chosen classification tasks – though rigor- ously establishing genuine, practically useful quantum advantage for real-world (rather than artificially constructed) machine learning datasets remains an actively contested, unresolved area of ongoing research.

Source page 14

Quantum Algorithms Deck 6

Q6.4 What is a ”barren plateau” in variational quantum algorithm training, and why is it consid- ered one of the most serious practical obstacles to scaling up VQE/QAOA-style algorithms?

A barren plateau is a region of a variational circuit’s parameter landscape where the gradient (the signal a classi- cal optimizer relies on to know which direction to adjust parameters) becomes exponentially small as the number of qubits grows – for suﬀiciently large, suﬀiciently ”generic” (expressive) parameterized circuits, this vanishing- gradient problem can become so severe that the classical optimizer essentially has no usable signal to follow at all, and training effectively stalls regardless of how it’s initialized or which optimizer is used. This is considered a seri- ous obstacle specifically because it appears to worsen as problem/qubit-count size increases – precisely the regime where quantum advantage would need to actually manifest for these algorithms to be practically useful – suggesting that naively scaling up today’s variational algorithms to larger qubit counts may not straightforwardly work without new techniques (specialized ansatz designs, layer-wise training strategies, or problem-specific structural constraints) specifically developed to avoid or mitigate barren plateaus.

Source page 15

Quantum Algorithms Deck 7 Quantum Complexity Theory Quantum Complexity Theory

Q7.1 What is the complexity class BQP (Bounded-error Quantum Polynomial time), and how does it relate to the classical complexity classes P and NP?

BQP is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability bounded below some fixed threshold (e.g. at most 1/3) on every run. It’s known that P ⊆BQP (anything a classical computer can eﬀiciently solve, a quantum computer can too, simply by simulating the classical algorithm) – but whether BQP actually contains problems outside P that provide a genuine, exploitable computational advantage is exactly what algorithms like Shor’s (which is known to be in BQP, and is strongly believed not to be eﬀiciently solvable classically, i.e., not known to be in P) aim to demonstrate. The relationship between BQP and NP is notably not one of containment in either direction, as far as is currently proven – BQP is neither known to contain all of NP, nor is NP known to contain all of BQP; famously, Grover’s algorithm’s quadratic (not exponential) speedup for NP-style unstructured search problems suggests quantum computers likely do not eﬀiciently solve all of NP (i.e., BQP is not believed to contain all of NP), a subtly important and often-misunderstood point in popular descriptions of quantum computing’s power.

Q7.2 What is ”quantum supremacy” (also called quantum advantage), and what specific claim did Google’s 2019 Sycamore experiment make, versus what it did not claim?

Quantum supremacy refers to a quantum computer performing some well-defined computational task meaningfully faster than any currently feasible classical computer/algorithm could – the task itself does not need to be practi- cally useful; it only needs to be a genuine, verifiable demonstration that quantum hardware can outperform the best available classical approach at something. Google’s 2019 Sycamore experiment specifically claimed its 53-qubit processor performed a particular, deliberately-constructed random circuit sampling task (sampling from the output distribution of a specific, designed-to-be-classically-hard random quantum circuit) in about 200 seconds, versus an estimated (and later disputed/revised) classical supercomputer runtime of thousands of years. It explicitly did not claim this random-sampling task itself was useful for any practical application – it was intentionally chosen specif- ically because it’s believed to be hard for classical computers, not because sampling random circuit outputs solves any real-world problem.

Q7.3 Why was Google’s original quantum supremacy claim later disputed/narrowed by subse- quent classical algorithm improvements, and what does this reveal about how ”quantum advantage” claims should generally be interpreted?

Following the 2019 announcement, researchers (including IBM) developed improved classical simulation techniques and demonstrated they could perform the same specific random-circuit-sampling task on a powerful classical super- computer in a dramatically shorter time than Google’s original ”thousands of years” classical estimate suggested – substantially narrowing (though not necessarily eliminating) the claimed advantage. This episode illustrates an important, general lesson about interpreting quantum advantage claims: any specific claim is only ever a statement relative to the best classical algorithms and hardware known at the time of the claim – it is not, and cannot be, a permanent, unconditional proof that no future classical algorithmic breakthrough could ever match or exceed the demonstrated quantum performance for that same specific task. This is precisely why the community has increasingly shifted terminology from the more absolute-sounding ”quantum supremacy” toward the more measured, explicitly comparative ”quantum advantage” or ”quantum utility,” reflecting genuine ongoing uncertainty and the expectation that claims will continue to be actively contested and refined by classical algorithmic progress.

Source page 16

Quantum Algorithms Deck 7

Q7.4 What is the difference between a provable, mathematically rigorous quantum speedup (like Grover’s or Shor’s) and an empirically observed but not fully rigorously proven quantum advantage (such as claims made for certain variational/NISQ algorithms)?

Algorithms like Shor’s and Grover’s come with rigorous mathematical proofs establishing exactly how many oper- ations they require and, in Grover’s case, a matching proof that no classical (or even alternative quantum) algorithm could do better for that specific problem class – these are airtight, provable results independent of any particular hard- ware or specific problem instance. Many claims of advantage for variational/NISQ-era algorithms (VQE, QAOA) and quantum machine learning approaches, by contrast, are typically empirical – based on running specific problem instances on specific hardware and observing better performance than a specific classical baseline attempted, without an accompanying rigorous, general mathematical proof that no classical algorithm could ever match that performance for the broader problem class. This distinction matters enormously for correctly interpreting the current state of the field: rigorously proven speedups represent settled, durable mathematical facts, while many currently-claimed near- term ”quantum advantages” remain genuinely open questions still subject to revision by future classical algorithmic improvements, exactly as happened with the original quantum supremacy claim.

Source page 17

Quantum Algorithms Deck 8 Error Correction & Fault Tolerance Error Correction & Fault Tolerance

Q8.1 Why is quantum error correction fundamentally harder than classical error correction, given that both must deal with unwanted noise/bit-flips?

Classical error correction can simply copy a bit multiple times (e.g. store 000 to represent 0) and use majority voting to correct a flipped bit – this straightforward strategy is exactly forbidden for quantum information by the no-cloning theorem, since an unknown qubit state cannot be copied. Additionally, quantum information is vulnerable to a continuous, richer variety of possible errors beyond simple bit-flips – phase-flip errors (which have no classical bit analogue at all) and, in principle, arbitrary small continuous rotations away from the intended state – and, crucially, directly measuring a qubit to check for an error (the way you might read a classical bit to check it) would itself collapse the very superposition the algorithm depends on, destroying the quantum information you’re trying to protect. Quantum error correction must therefore detect and correct errors without ever directly learning the protected state’s actual quantum information itself – a fundamentally more constrained and subtle problem than classical error correction.

Q8.2 What is a ”logical qubit,” and roughly why does correcting for both bit-flip and phase-flip errors require encoding it across multiple physical qubits?

A logical qubit is a single, protected, reliable unit of quantum information encoded redundantly across many physical qubits, engineered so that errors on individual physical qubits can be detected and corrected without destroying the encoded logical information. Because quantum errors include both bit-flip and phase-flip types (and these are, in a precise technical sense, complementary/non-commuting error types), a code must be structured to protect against both simultaneously – the simplest schemes (like Shor’s original 9-qubit code) achieve this by essentially nesting a bit-flip-correcting code and a phase-flip-correcting code together, while more modern, hardware-eﬀicient codes (like the surface code) achieve similar dual protection through a different, more geometrically local structure of many physical qubits arranged in a 2D grid – but in all cases, correcting for the full range of possible quantum errors necessarily requires a meaningfully larger physical-to-logical qubit overhead than classical error correction typically needs.

Q8.3 What is the ”surface code,” and why has it become the leading candidate error-correction scheme for most current large-scale superconducting-qubit quantum computing efforts?

The surface code arranges physical qubits in a two-dimensional grid, with alternating qubits used to store quantum information and to perform repeated, local ”stabilizer” measurements that detect (without directly revealing) the presence and type of nearby errors, using only nearest-neighbor interactions between physically adjacent qubits on the grid. It has become the leading candidate primarily because of this locality – it doesn’t require any qubit to interact directly with another qubit far away on the chip, which matches extremely well with the physical constraints of real superconducting-qubit hardware, where distant physical qubits are especially diﬀicult to couple together reliably – combined with a relatively high error-rate threshold (roughly around 1%, meaning individual physical qubit/gate error rates below this threshold can, in principle, be suppressed arbitrarily by using a large enough code), a threshold that is realistically achievable, if only just barely, with current and near-term hardware fidelities.

Q8.4 What is the ”error correction threshold theorem,” and why is it considered one of the most important theoretical results underpinning the long-term feasibility of large-scale, fault-

What is the ”error correction threshold theorem,” and why is it considered one of the most important theoretical results underpinning the long-term feasibility of large-scale, fault-

Source page 18

Quantum Algorithms Deck 8 tolerant quantum computing? The threshold theorem proves that, provided the physical error rate per gate/qubit is below some specific threshold value, it is possible to perform an arbitrarily long and large quantum computation with an arbitrarily low overall logical error rate, by using a suﬀiciently large quantum error-correcting code and correspondingly increasing the physical- to-logical qubit redundancy – crucially, without this improvement in reliability ever ”running out” as the computation grows longer, so long as physical errors stay below that threshold. This result is foundational because it establishes, as a matter of rigorous theory rather than optimistic speculation, that large-scale fault-tolerant quantum computing is not fundamentally blocked by any inherent physical limit that gets worse and worse the larger a computation grows – it transforms the entire challenge of building a useful, large-scale quantum computer into what is fundamentally an engineering problem (reliably achieving and maintaining physical error rates below the relevant threshold, then scaling up the number of physical qubits), rather than a problem requiring any further, currently-unknown theoretical breakthrough. End of deck.