# Long Questions Use this for longer written practice and oral-exam style review. The answer blocks stay plain so you can hide them while testing yourself or move them into another study system. ## Foundations And Formalism - Question 1. Explain the difference between amplitudes and probabilities, and why interference makes quantum algorithms possible. ``` Probabilities are nonnegative real numbers that add directly when alternatives are mutually exclusive. Quantum amplitudes are complex numbers that combine before measurement. The Born rule converts amplitudes into probabilities only after the relevant amplitudes have been added and squared in magnitude. This is why interference is central to quantum computation. A quantum algorithm does not merely explore many branches and then read all of them. It arranges phases and unitary transformations so that amplitudes for wrong answers cancel while amplitudes for useful answers reinforce. The computational advantage comes from controlling this interference pattern, not from extracting an exponential amount of classical information from the statevector. ``` - Question 2. Derive why global phase is unobservable but relative phase can matter. ``` Let |psi> be a normalized state and let e^{i theta}|psi> be the same state multiplied by a global phase. For any measurement effect or projector M, the probability is <psi| e^{-i theta} M e^{i theta} |psi> = <psi|M|psi>. The global phase cancels from every measurable probability, so it is not physical. Relative phase is different. For example, (|0>+|1>)/sqrt(2) and (|0>-|1>)/sqrt(2) have the same computational-basis probabilities, but applying a Hadamard maps them to |0> and |1> respectively. Relative phase affects later interference, so it can become observable after a basis change. ``` - Question 3. Explain why a quantum gate must be unitary in the closed-system model. ``` Closed-system quantum evolution must preserve normalization and inner products. If two states are evolved by U, then probabilities remain well-defined only if ||U|psi>|| = |||psi>|| for every |psi>. This is equivalent to U dagger U = I in finite dimension, so U is unitary. Unitarity also implies reversibility. This is why circuit descriptions of quantum algorithms often need to compute, copy classical reversible information into work registers, and then uncompute garbage. If unwanted workspace remains entangled with the answer register, the final interference step can fail. ``` - Question 4. Explain the difference between superposition and mixture using density matrices. ``` A superposition is a pure quantum state such as |+> = (|0>+|1>)/sqrt(2). Its density matrix is |+><+| = (1/2) [[1, 1], [1, 1]]. A 50-50 mixture of |0> and |1> is rho = (1/2)|0><0| + (1/2)|1><1| = (1/2) [[1, 0], [0, 1]]. Both states give the same probabilities in the computational basis, but they are physically different. The pure superposition has off-diagonal coherence terms. Those terms can produce interference after a basis change. The mixture has no such coherence, so a later Hadamard does not turn it into a deterministic outcome. ``` - Question 5. Compute the reduced state of one qubit of a Bell pair and explain the result. ``` Start with |Phi+> = (|00> + |11>) / sqrt(2). The density matrix is rho_AB = (1/2)(|00><00| + |00><11| + |11><00| + |11><11|). Trace out Bob. The terms |00><00| and |11><11| survive as |0><0| and |1><1| on Alice's system. The cross terms vanish because Bob's labels are orthogonal: <1|0> = 0 and <0|1> = 0. Therefore rho_A = (1/2)|0><0| + (1/2)|1><1| = I/2. The global Bell state is pure, but either qubit alone is maximally mixed. This mixedness is not merely classical ignorance about preparation; it comes from looking at one subsystem of a larger entangled state. ``` - Question 6. Give the pure two-qubit separability test and apply it to a Bell state. ``` For |psi> = a|00> + b|01> + c|10> + d|11>, reshape the amplitudes into the coefficient matrix M = [[a, b], [c, d]]. The state is separable if and only if M has rank 1. For a 2 by 2 matrix, this is equivalent to ad - bc = 0. For the Bell state (|00>+|11>)/sqrt(2), we have a = d = 1/sqrt(2) and b = c = 0. Then ad - bc = 1/2, which is nonzero. Therefore the Bell state is entangled. ``` - Question 7. Explain the Schmidt decomposition and why it is useful for entanglement. ``` Any pure bipartite state can be written as |psi> = sum_i sqrt(lambda_i) |alpha_i>|beta_i>, where the lambda_i are nonnegative and sum to one, and the local basis vectors are orthonormal. The number of nonzero lambda_i values is the Schmidt rank. This form is useful because it makes pure-state entanglement transparent. A pure bipartite state is separable if and only if its Schmidt rank is 1. The same lambda_i values are also the nonzero eigenvalues of the reduced density matrices. Therefore the Schmidt decomposition directly gives both a separability test and the ingredients for entanglement entropy. ``` - Question 8. Explain when entropy is and is not a clean entanglement measure. ``` For a pure bipartite state |psi>_AB, the entanglement entropy is the Von Neumann entropy of either reduced state: S(rho_A) = -Tr(rho_A log_2 rho_A), where rho_A = Tr_B(|psi><psi|). In this pure-state setting, any mixedness of rho_A comes from entanglement with B, so the entropy cleanly measures bipartite entanglement. For mixed bipartite states, the same shortcut fails. A subsystem or joint state can have entropy because of classical randomness, noise, or entanglement with an external environment. For example, the separable mixture (1/2)|00><00| + (1/2)|11><11| has local entropy, but it is not entangled between the two named qubits. Entropy is therefore a clean entanglement measure only in the pure bipartite setting without additional caveats. ``` ## Protocols, Bell Tests, And Cryptography - Question 9. Prove the no-cloning theorem for arbitrary unknown states. ``` Assume a universal cloning unitary U exists. Then for arbitrary |psi>, U(|psi>|0>) = |psi>|psi>. For two states |psi> and |phi>, this implies U(|psi>|0>) = |psi>|psi> U(|phi>|0>) = |phi>|phi>. Because U is unitary, it preserves inner products. The inner product before cloning is <psi|phi>. The inner product after cloning is <psi|phi>^2. So universal cloning would require <psi|phi> = <psi|phi>^2 for all pairs of states. This is true only when the overlap is 0 or 1. Arbitrary quantum states can have intermediate overlap, so no universal perfect cloner exists. ``` - Question 10. Explain quantum teleportation as a resource transformation. ``` Quantum teleportation transfers an unknown quantum state from Alice to Bob using one shared Bell pair and two classical bits. Alice performs a Bell-basis measurement on the unknown state and her half of the Bell pair. This produces two classical bits. She sends those bits to Bob. Bob applies the corresponding Pauli correction to his half of the Bell pair and recovers the original unknown state. The protocol does not copy the state. Alice's measurement destroys the original local copy, and Bob's corrected qubit becomes the output. Teleportation is therefore a resource transformation: shared entanglement plus classical communication can transmit an unknown quantum state without sending the physical qubit that originally carried it. ``` - Question 11. Explain superdense coding and why it does not violate information bounds. ``` Superdense coding lets Alice send two classical bits to Bob by transmitting one qubit, provided Alice and Bob already share a Bell pair. Alice encodes her two-bit message by applying one of four Pauli operations to her half of the Bell pair. She sends that qubit to Bob. Bob now has both halves and performs a Bell-basis measurement to recover the two classical bits. This does not violate information bounds because the protocol consumes prior shared entanglement. The transmitted qubit is not acting alone; the communication resource is one sent qubit plus one shared Bell pair. Without the entangled pair, one qubit cannot simply transmit two arbitrary classical bits in this way. ``` - Question 12. Derive the classical CHSH bound and compare it to the quantum value. ``` In the CHSH game, Alice receives x, Bob receives y, and they output a and b. They win when a xor b = x and y. A deterministic classical strategy fixes Alice's answers for x=0,1 and Bob's answers for y=0,1 in advance. The four input pairs require three parity constraints with a xor b = 0 and one parity constraint with a xor b = 1. Multiplying or xoring all four constraints creates a contradiction, so no deterministic local strategy can satisfy all four inputs. The best deterministic strategy wins three out of four cases, so the classical winning probability is at most 3/4. Shared randomness only randomizes among deterministic strategies, so it cannot exceed 3/4. The quantum strategy using a Bell pair and appropriate measurement bases wins with probability cos^2(pi/8) approximately 0.854. This violates the classical local hidden-variable bound, but it does not enable signalling because each party's local marginal distribution remains independent of the other party's input. ``` - Question 13. Explain how Bell violation can be used for certified randomness. ``` Ordinary random-looking data could come from a classical pseudorandom generator, a noisy device, or a predetermined table. Bell-based randomness certification uses a stronger idea: if separated devices violate a Bell inequality under the required assumptions, then their outputs cannot be fully explained by predetermined local hidden variables. The certification is not magic. It depends on assumptions about device separation, input choice, statistical confidence, and the physical model. But the key point is operational: the observed nonlocal correlation bounds how predictable the outputs could have been to a local hidden-variable adversary. This gives a route to randomness evidence based on correlation structure rather than trust in the internal device design. ``` ## Algorithms, Query Complexity, And Complexity Theory - Question 14. Explain the oracle model and why query complexity is useful in quantum algorithms. ``` In the oracle model, part of the input is accessed through a black-box function. Query complexity counts how many times an algorithm must call that oracle to solve the problem. This isolates access to the problem instance from other computational work. The model is useful in quantum algorithms because quantum queries can be made in superposition. Algorithms such as Deutsch-Jozsa, Bernstein-Vazirani, Simon, and Grover expose how coherent access to an oracle can change the number of required queries. At the same time, query complexity prevents cheating: one must not hide the entire difficulty of the problem inside an unrealistically powerful oracle. ``` - Question 15. Explain Deutsch-Jozsa and what kind of speedup it demonstrates. ``` Deutsch-Jozsa considers a Boolean function promised to be either constant or balanced. Classically, deterministic algorithms may need many oracle queries in the worst case to distinguish these possibilities. The quantum algorithm prepares a uniform superposition, queries the oracle in phase, and then applies Hadamards so the global structure of the function interferes into the all-zero outcome or away from it. The algorithm demonstrates a query-complexity separation under a promise. It is not a general-purpose claim that every decision problem becomes easy. Its value is pedagogical and structural: it shows how one coherent query can reveal a global property of a black-box function. ``` - Question 16. Explain Bernstein-Vazirani and why it is cleaner than Deutsch-Jozsa. ``` Bernstein-Vazirani gives oracle access to a function f_s(x)=s dot x mod 2 for an unknown hidden string s. The quantum algorithm prepares a uniform superposition, uses phase kickback to write (-1)^{s dot x} into the amplitudes, and then applies Hadamards. The final state is |s>, so measuring reveals the entire hidden string in one oracle query. It is cleaner than Deutsch-Jozsa because the output is not only a promised classification. The algorithm recovers a concrete hidden object. It also makes phase kickback very explicit, which is why it is a good bridge from basic interference to more advanced hidden-structure algorithms. ``` - Question 17. Explain Simon's algorithm and its relationship to Shor's algorithm. ``` Simon receives oracle access to a function with the promise that f(x)=f(y) exactly when x xor y is either 0 or a hidden string s. The quantum algorithm samples strings z satisfying z dot s = 0 over GF(2). Repeating the procedure gives linear equations, and classical Gaussian elimination recovers s. The relationship to Shor is conceptual. Simon finds hidden xor-period structure, while Shor finds periodic structure in modular arithmetic. In both cases, the quantum part samples information about a hidden structure, and the classical part performs post-processing to recover the object of interest. ``` - Question 18. Given oracle access to a list of $N$ points in the plane, describe a quantum algorithm that decides whether any three points are collinear in time $O(N^{3/2})$. The oracle may be queried in superposition. Explain why the algorithm succeeds with probability greater than $1/2$, and justify the claimed running time. ``` A quantum algorithm for Collinearity is to use Grover search over all triples of points. Let the input be N points p_1, …, p_N. We are given black-box access to the points, and the black-box can be queried in superposition. There are C(N,3) = O(N^3) possible triples of points. For each triple (i,j,k), define an oracle: f(i,j,k) = 1 if p_i, p_j, p_k are collinear
f(i,j,k) = 0 otherwise To compute f(i,j,k), query the black-box for the three points: p_i = (x_i,y_i)
p_j = (x_j,y_j)
p_k = (x_k,y_k) Then check whether x_i(y_j - y_k) + x_j(y_k - y_i) + x_k(y_i - y_j) = 0 If this equality holds, then the three points are collinear. The quantum algorithm is: 1. Create a uniform superposition over all triples (i,j,k), where i < j < k. 2. Use the oracle f to mark exactly those triples whose three points are collinear. 3. Run Grover search on this space of triples. 4. Measure the final state to get a candidate triple. 5. Verify the triple by querying the three points and checking the collinearity condition. The search space has size M = C(N,3) = O(N^3) Grover search uses O(sqrt(M)) oracle calls, so the running time is O(sqrt(N^3)) = O(N^(3/2)) Each oracle call only needs a constant number of black-box queries, since it only checks three points. Therefore, the whole algorithm runs in O(N^(3/2)) time. If a collinear triple exists, Grover search finds one with constant probability greater than 1/2. If the number of solutions is unknown, we can use the standard Grover search variant for an unknown number of marked items. So the algorithm succeeds with constant probability strictly greater than 1/2. ``` - Question 19. Explain Grover's algorithm and why it is optimal in the black-box model. ``` Grover's algorithm searches an unstructured space of N candidates with a marking oracle. It starts in a uniform superposition, applies a phase oracle that marks solutions, and then applies a diffusion operation that amplifies marked amplitudes. Repeating this process about O(sqrt(N/M)) times when there are M marked items gives a constant probability of measuring a solution. The important limitation is that this speedup is quadratic, not exponential. BBBV-style lower bounds show that unstructured black-box search requires Omega(sqrt(N)) quantum queries. Therefore Grover is essentially optimal for the black-box search setting. It is powerful, but it does not turn arbitrary brute-force search into an efficient solution. ``` - Question 20. Explain the role of the Quantum Fourier Transform in Shor's algorithm. ``` Shor's algorithm reduces factoring to order finding. The quantum part prepares a superposition over exponents, computes modular exponentiation, and uses the Quantum Fourier Transform to convert periodic structure into peaks in the frequency domain. Measurement gives data from which the period can be recovered using classical continued fractions or related post-processing. The QFT is not just a faster classical Fourier transform. It is a unitary basis change applied to quantum amplitudes. Its role is to make periodicity visible in samples without reading out the whole exponentially large state. ``` - Question 21. Explain why Shor's algorithm does not prove that NP-complete problems are easy for quantum computers. ``` Shor's algorithm gives a polynomial-time quantum algorithm for factoring and discrete logarithms. These problems have special algebraic structure, and the algorithm exploits period finding. NP-complete problems are not known to reduce to this same structure in a way that gives efficient quantum algorithms. Also, factoring is not known to be NP-complete. The existence of Shor's algorithm shows that some problems believed hard for classical computers are easy for quantum computers, but it does not imply BQP contains NP-complete problems. Grover's algorithm and black-box lower bounds are a warning against overgeneralizing quantum speedups. ``` - Question 22. Explain BQP and the role of bounded error. ``` BQP is the class of decision problems solvable by a uniform family of polynomial-size quantum circuits with bounded error. Typically, the algorithm must accept yes-instances with probability at least 2/3 and accept no-instances with probability at most 1/3, or equivalent constants separated from 1/2. The exact constants are not essential because success probability can usually be amplified by repetition. Bounded error is important because quantum algorithms are probabilistic after measurement. BQP captures efficient quantum computation with reliable enough output, not deterministic certainty from a single run. ``` ## Hamiltonians, Noise, And Error Correction - Question 23. Explain how Hamiltonians generate time evolution and why this matters for a circuit-focused course. ``` For a closed quantum system with Hamiltonian H, time evolution is |psi(t)> = exp(-iHt)|psi(0)> in units where hbar=1. The operator exp(-iHt) is unitary when H is Hermitian. This matters even in a circuit-focused course because real quantum hardware evolves under physical Hamiltonians. Circuits are a control abstraction, while Hamiltonians describe continuous dynamics, energy spectra, adiabatic algorithms, simulation problems, and many noise models. Understanding both languages lets you connect algorithms to devices. ``` - Question 24. Explain the adiabatic algorithm and the role of the spectral gap. ``` The adiabatic algorithm starts with a Hamiltonian whose ground state is easy to prepare and slowly changes it into a problem Hamiltonian whose ground state encodes the answer. If the change is slow enough and the system remains near the ground state, measuring at the end reveals the solution. The spectral gap is the energy difference between the ground state and the nearest excited state during the interpolation. Small gaps make it harder to remain adiabatic because the system is more likely to transition out of the ground state. Runtime therefore depends strongly on the minimum gap along the path. This is why adiabatic algorithms are not automatically efficient merely because the final Hamiltonian encodes a problem. ``` - Question 25. Explain quantum noise using density matrices and channels. ``` Quantum noise is naturally described by density matrices and quantum channels. A channel maps an input density matrix rho to an output density matrix. Many physical channels can be written in Kraus form: E(rho) = sum_k E_k rho E_k dagger, with the trace-preserving condition sum_k E_k dagger E_k = I. This formalism includes decoherence, depolarization, amplitude damping, phase damping, and other open-system effects. It is more general than unitary evolution because the system may be interacting with an environment that is not explicitly tracked. ``` - Question 26. Explain why quantum error correction is possible despite measurement and no-cloning. ``` Quantum error correction does not copy an unknown quantum state. Instead, it encodes one logical state into a larger entangled subspace. The code is designed so that common physical errors move the state into distinguishable error subspaces. Syndrome measurements identify which error subspace the state moved into without measuring the protected logical amplitudes. The recovery operation then maps the corrupted state back into the code space. Measurement is not forbidden; direct measurement of the logical information is forbidden. Syndrome measurement is useful precisely because it asks what error happened rather than what the encoded alpha and beta are. ``` - Question 27. Derive the syndrome table for the three-qubit bit-flip code. ``` Encode alpha|0> + beta|1> as alpha|000> + beta|111>. Use the stabilizer checks Z1Z2 and Z2Z3. A bit flip changes the parity checks adjacent to the flipped position. No error gives syndrome (+1,+1), so do nothing. X1 gives syndrome (-1,+1), so correct qubit 1. X2 gives syndrome (-1,-1), so correct qubit 2. X3 gives syndrome (+1,-1), so correct qubit 3. The syndrome tells us the error location for a single X error. It does not reveal alpha or beta, so the logical superposition remains protected. ``` - Question 28. Explain the stabilizer formalism using the Bell state and the three-qubit code. ``` A stabilizer is an operator S such that S|psi> = |psi>. The Bell state (|00>+|11>)/sqrt(2) is stabilized by XX and ZZ. These operators compactly describe the fact that the two qubits agree in both the X and Z bases. For the three-qubit bit-flip code, the code space is stabilized by ZZI and IZZ. These stabilizers check whether neighboring qubits have the same Z-basis parity. A single X error flips one or both syndrome signs, allowing the error location to be inferred. The stabilizer formalism is powerful because many important states and codes can be described by generators rather than by listing exponentially many amplitudes. ``` - Question 29. Explain the Gottesman-Knill theorem and its limitation. ``` The Gottesman-Knill theorem says that circuits made only from stabilizer-state preparations, Clifford gates, Pauli measurements, and classical feedforward can be simulated efficiently on a classical computer. Clifford gates map Pauli operators to Pauli operators, so the stabilizer description remains compact throughout the computation. The limitation is just as important as the theorem. Stabilizer circuits are quantum, but they are not universal for quantum computation. Universal quantum computing requires resources outside the stabilizer-only Clifford fragment, such as non-Clifford gates. Therefore Gottesman-Knill explains an efficient simulation boundary; it does not make all quantum computation classically easy. ``` - Question 30. Explain what the threshold theorem contributes to the debate about whether quantum computing is too analog and fragile. ``` The threshold theorem says, roughly, that if physical error rates are below a certain threshold and the noise assumptions are controlled, then fault-tolerant constructions can make arbitrarily long quantum computations reliable with manageable overhead. This directly addresses the objection that quantum amplitudes are analog quantities and therefore small errors must inevitably accumulate until computation becomes impossible. The answer is not that hardware is easy or noise is irrelevant. The answer is that error correction and fault tolerance can discretize the relevant error information through syndrome extraction and prevent small physical errors from directly becoming logical failure, provided the physical noise is below threshold. ```