Topics (384k) Articles (398k) Users (410) Discussions (242) Comments (383) Files (13k) New article
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 324 4 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For first-order two-local Hamiltonian simulation, regard each term as a Hermitian operator, as is standard for a local-Hamiltonian decomposition. The Lie-Trotter product formula for bounded operators statesin operator norm; the reversed factor ordering is just as valid as the displayed one. Take and use the circuitEach factor is a unitary operator on at most two qubits and hence is one allowed two-qubit gate, with a spectator identity for a one-qubit term. The factors in the rightmost part of each written product act first. Merely quoting the limit would not establish the requested rate, so we give a quantitative error bound.
For two Hermitian operators and , differentiatinggives . The commutator identity obtained by differentiating implies . Since the surrounding factors are unitary, integration yields the first-order unitary product-formula error boundSplitting the terms successively and using the triangle inequality therefore gives the one-step estimatefor . Here submultiplicativity of the operator norm gives . The ordering chosen for the products changes the sign of local commutators, not this norm bound. Applying part (i) to the steps givesChoose . For the error is strictly below ; is exact already with . The quantum circuit contains two-qubit gates. A sufficient gate count isThus the worst-case polynomial degree in this first-order bound is six. Terms with disjoint supports commute and may improve the count in particular decompositions, but the stated assumptions alone suffice for this bound, without a further sparsity or bounded-degree condition. The requested gate model allows arbitrary two-qubit unitaries, so no additional compilation error is incurred here.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 324 4 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
The spectral norm is the induced Euclidean operator norm:It is the largest singular value. From the definition, multiplying on either side by a unitary operator leaves the norm unchanged: right multiplication permutes the unit sphere of possible inputs, and left multiplication preserves output lengths. In particular every unitary operator has norm one.
For unitary product telescoping, replace the factors one at a time. With empty products interpreted as the identity,All cross terms cancel. By the triangle inequality and unitary invariance of the spectral norm,This bound is independent of the dimension and does not assume that any of the factors commute.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 324 3 iv Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Use GHZ preparation with Hadamard and controlled-Z gates for . Apply a Hadamard gate to the first qubit, then a controlled-NOT gate from that qubit to each of the other qubits. Every controlled-NOT can be written in the allowed gate set asIndeed conjugating the target by makes the controlled phase into a controlled . The rightmost gate acts first. Consequently the Clifford circuit uses allowed gates and givesFor every chosen qubit , tracing out the other qubits yields . Equivalently, across that qubit versus the rest, the displayed state is a Schmidt decomposition with two nonzero coefficients . It is therefore entangled across every such bipartition.
Entanglement does not prevent the polynomial single-output simulation from part (iii). The simulation follows the measured observable rather than claiming that the intermediate states remain product states. When , there is no remaining subsystem and the requested entanglement is impossible; the construction and claim require .
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 324 3 iii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Write . Instead of storing the output vector, use Heisenberg propagation of a Pauli observable through a Clifford circuit:Initialize the compact Pauli group representation at and conjugate successively by , in that order, using . This giveswith local-update work and storage. The resulting Pauli operator is Hermitian, so we can express it as , where and each is or . Any factors in the representation from part (i) are converted using , with their phases absorbed into .
The product state input now makes the expectation factorize:Each factor is a two-by-two matrix calculation. More explicitly, for , the three nontrivial expectations are , , and for , respectively.
Thus this single-output process has a strong classical simulation in polynomial time, even when the individual input states are not stabilizer states. As usual, the given state identities must provide efficiently computable amplitudes. With finite-precision inputs, each factor can be evaluated to error and its approximation clipped to to obtain the final expectation to error at most , because all factors lie in . The required extra precision is only bits. Exact evaluation applies when the input descriptions support exact arithmetic. This avoids silently assigning a finite exact-computation cost to arbitrary unspecified real numbers.
Once the probabilities are known, a classical randomized computation can reproduce this measured bit. The argument concerns the specified one-qubit output; it does not assert that every joint measurement distribution for arbitrary product inputs can be simulated by this same single-observable calculation.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 324 3 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
The computational-basis projectors on the first qubit areThe Pauli Z gate acts as on the first subspace and on the second, so . By the Born rule, . Therefore the expectation determines the output probabilities:The normalization supplies ; no product-state assumption is needed for this identity.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 324 3 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Store a tensor-product element of the Pauli group asThe phases of the original single-qubit factors can all be accumulated into . This binary phase representation of a Pauli string uses bits. It retains phases, which must not be dropped when computing probabilities later.
For the conjugation convention in the question, direct multiplication of the two-by-two matrices givesandThese backward Pauli updates for Hadamard and phase gates use , not . On the affected line , the updates areAll phases are reduced modulo four and the updates use the old bits.
For a Controlled-Z gate on lines , its diagonal action givesFor the controlled-Z update in the binary phase representation, conjugation respects products, so these determine the rule for every Pauli operator on those lines. In the chosen ordered convention it isThe phase arises when a newly introduced is moved past . For instance becomes , so this sign matters.
The untouched factors are unchanged. Each Clifford operation therefore needs only a fixed number of local bit updates; reconstructing the requested full list takes time. Put the final phase into the first factor, which is permitted because the single-qubit Pauli group includes all multiples by . The classical cost is polynomial, despite the exponentially large matrix of the operation on the full state space.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 324 2 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Follow the printed examples by counting positive squares, so zero is not marked. For , the marked output set isA one-to-one map from the finite set to itself is a permutation, so exactly inputs have outputs in . In the uniform quantum superposition , the initial good probability is therefore . For permutation-preimage quantum search, this known marked density under a permutation is .
Define the efficiently computable predicate to be one if and only if is a positive square. The assumed Boolean quantum oracle for , acting on and a ancilla, implements its diagonal sign operation . Compute the modular-addition quantum oracle into a zero output register, apply this sign operation, and uncompute:This implements for , with the work registers clean. Only forward calls to were promised, but its inverse costs one such call: if on the second register, thenIndeed the output addition is changed into subtraction. Thus each marked reflection costs exactly two queries to ; all other operations used here are independent of the unknown .
Use the amplitude amplification theorem with , whose reflection is allowed by the assumptions. With , choose nearest to . Here for every , so a trial succeeds with probability at least . AlsoMeasure and use one additional query to evaluate and check . On failure, restart with fresh registers. Four independent trials have failure probability at most , so the required confidence and query bound areThis is an upper bound on quantum query complexity, not a claim that arbitrary reflections or every classical gate have constant cost. Including zero as a square would change to without changing the asymptotic bound. With the printed positive-square interpretation, has no valid output and no algorithm can satisfy the success requirement; the intended asymptotic task necessarily has .
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 324 2 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Prepare an ancillary qubit inIt can be prepared from by an operation followed by a Hadamard gate, independently of . One call to the Boolean quantum oracle then gives quantum phase kickback:The data state receives a minus sign precisely on the basis vectors spanning , while the ancilla remains unchanged and unentangled. One oracle call realizes the reflection. By linearity it is the marked-state phase oraclewith one oracle call. The ancillary preparation and its optional inverse use only fixed operations, so no additional knowledge of is needed.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 324 2 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Take to be normalized and let be the orthogonal projection onto the good subspace. The two reflection operators areThe first fixes the hyperplane orthogonal to and negates its normal direction. The second fixes and negates . Both are Hermitian operators and unitary operators, since their defining projectors square to themselves. For a non-normalized nonzero vector, divide by .
Put , with , and define normalized orthogonal good and bad vectorsThen . The amplitude amplification theorem states that the iterate satisfies, for every nonnegative integer ,To prove it, the span of is invariant under both reflection operators. In that ordered orthonormal basis,Multiplying the second matrix into advances the angle by . Induction proves the formula, and projecting onto gives . The minus sign in is just a global phase choice, but it makes the displayed state formula exact.
If is known, choose nearest to , with . The final angle is within of , so . For , this is at least after iterations, and is close to one when is small. For , measuring the initial state already has success above . Repeated independent attempts with a success test give any fixed desired success probability. This is the quadratic improvement of amplitude amplification over repeated sampling, which takes attempts. At there is no good component to amplify, and at the initial state is already entirely good; these endpoint cases do not require the undefined normalized component vectors.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 324 1 iii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Here the true multiplicative order is four, and it divides every power-of-two Fourier-register size , including the choice from part (ii). A second-register measurement produces one of the four periodic cosetsIts quantum Fourier transform has nonzero amplitudes only at , and each has squared modulus . The inverse transform only changes phases or permutes these four labels. Hence the measured ratios are equally likely.
For or , continued-fraction recovery in quantum order finding returns denominator four. Part (i) then gives factors three and five. For , the reduced denominator is two. Although two is not a period, the candidate-denominator gcd post-processing in part (ii) still gives a factor:The zero outcome produces no useful even candidate and the run fails. For the factor-extraction procedure specified above, three of the four outcomes succeed:There is an important convention behind this answer. A version that rejects a candidate unless before attempting any gcd rejects , since . Under that validated-period convention only the two odd-numerator phases succeed, givingThus the probability of recovering the true multiplicative order is , whereas the probability of finding a factor with direct gcd post-processing is . The printed question does not specify this classical post-processing detail; stating it avoids identifying these two different events.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 324 1 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Let . In the Shor algorithm, first use classical arithmetic to deal with even and perfect powers, and to reject prime inputs. Perfect-power recognition and primality testing have polynomial-time classical algorithms. Factoring a perfect power , with , already gives a nontrivial factor . We may therefore consider an odd composite with at least two distinct prime factors.
Choose uniformly from and compute its greatest common divisor with using the Euclidean algorithm. A proper nontrivial divisor ends the computation. Otherwise is a unit, and the remaining task is quantum order finding. SetPrepare a uniform quantum superposition in a -qubit register and use quantum modular exponentiation in a second register to obtainRepeated squaring and reversible modular multiplication implement this step with polynomially many quantum gates in . Apply the inverse quantum Fourier transform to the first register and perform a quantum measurement in the computational basis, obtaining . Measuring the second register first, and Fourier-transforming the resulting periodic coset, gives the same distribution of .
Here is a quantitative quantum Fourier sampling bound for order finding. If , multiplication by cycles its orbit states. The Fourier eigenstates of that cycle have eigenvalues , and the initial state has squared overlap with each, for . ThereforeConditioned on a particular eigenphase , its nearest integer outcome obeys and has probability at least . Indeed the absolute amplitude is , where . For , the numerator is at least and the denominator at most ; the limiting value at is one.
If , the fraction is reduced, and givesUse continued-fraction recovery in quantum order finding. The relevant approximation theorem says that reduced fractions satisfying are continued fraction convergents of . For an input rational of digits, their candidates can be enumerated classically in time, and their denominators are at most the reduced input denominator. This is the supplied continued-fraction result; discard candidate denominators exceeding . A zero measurement is treated as a failed order-finding sample.
For each remaining even candidate denominator , compute by repeated squaring, and try and . Return only a divisor with ; otherwise repeat the quantum sample or choose another . This candidate-denominator gcd post-processing cannot return an incorrect factor, since its output is checked directly. When the recovered denominator is the true even multiplicative order and the square root of one is nontrivial, part (i) guarantees success. Checking before trying the gcds is also a valid, more restrictive convention; the single-run distinction matters in part (iii).
Two further standard quantitative facts explain why repetitions remain efficient. First, for a uniformly chosen unit modulo an odd integer with at least two distinct prime divisors, the probability of a useful unit in Shor factorization is at least : its true multiplicative order is even and . To see the source of this bound, the Chinese remainder theorem for unit groups makes the prime-power components independent. Each odd-prime-power unit group is cyclic. If its 2-primary order is , the probability of the largest possible value of is , and the probability of any specified smaller value is at most . Failure requires all components to have the same : either all zero, making odd, or all the same positive value, making the halfway power in every component. Conditioning on one component, the chance another component matches it is at most , so total failure is at most .
Second, the fraction of phase numerators coprime to is , where is the Euler totient function. The elementary totient-ratio lower bound suffices: if the distinct prime divisors are , then and . The totient product formula therefore givesThus for a good , the probability of sampling a coprime phase numerator with the required accuracy is at least . This is inverse-polynomial in the input length, so polynomially many repetitions achieve any fixed success probability. The quantum Fourier transform uses elementary rotations and Hadamard gates in the ideal gate description, and the other quantum and classical stages are polynomial in .
The reduction is therefore polynomial in the bit length:A small denominator need not itself be the true multiplicative order; verification of the final factor is essential, and no guarantee is claimed for every individual sample.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 324 1 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For coprime integers , the multiplicative order is the smallest positive exponentIt exists because multiplication by is an element of the finite group of units modulo an integer. For the example, the successive residues areNone of the first three is one, so the order is four.
The factor extraction from an even modular order uses the factorization . If the multiplicative order is even, put . Minimality of the multiplicative order excludes ; we also require . Thus is a nontrivial square root of one. Neither nor is divisible by all of . If either were coprime to , its inverse modulo , applied to , would make the other divisible by , a contradiction. Hence the greatest common divisorsare proper nontrivial factors. For odd , and have no common prime divisor of , so these two divisors are complementary. If the initial is not coprime to , a proper already supplies a factor without quantum order finding.
For and , and , which is neither nor . The factors areThe necessary conditions for this order-based reduction are a unit , even true multiplicative order, and .
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 323 5 3 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For the distribution and POVM from part 2, apply the data-processing inequality for quantum relative entropy to the measurement channel. The quantum mutual information is the quantum relative entropy from the joint density operator to the product of its marginals, so for ,The last step uses for the binary entropy and . If , rearrangement and then the supremum over give the one-shot classical-quantum coding converse:For , the sole POVM effect is , forcing , and the bound is trivial. For , division by is undefined: the undivided inequality remains valid and gives no size restriction. The displayed coding bound is therefore understood for , or with a vacuous right-hand side at .
An alternative uses the original decoder directly. Let be the uniform message and its measured estimate. For , Fano's inequality bounds the conditional entropy by . The Holevo bound givesThus the same coding bound follows by bounding the classical mutual information obtainable from the POVM.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 323 5 2 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Choose uniform on and zero outside it, so the marginal density operator of is . Define the binary test for quantum decoding success byEach is a positive contraction. The computational basis blocks of are these effects on and zero elsewhere. Thus , making a POVM on the whole space, including labels outside .
On the correlated classical-quantum state, its acceptance probability isOn the product of the marginal density operators,since . The two requested probabilities are therefore and . In the notation for binary output density operators, the measurement channel sends the joint input to and the product input to ; their parameters describe outcome one, not outcome zero.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 323 5 1 Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Use logarithms to base two, so Von Neumann entropy and quantum relative entropy are measured in bits. For density operators ,The quantum relative entropy formula applies when the support of a positive operator is contained in that of ; otherwise . Use in the Von Neumann entropy formula.
The binary density operator is diagonal with eigenvalues . Its Von Neumann entropy is the binary entropy:The two diagonal density operators commute, so their quantum relative entropy isA term with zero numerator has value zero; a positive numerator and zero denominator give . In particular, , whereas or gives .
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 323 4 iii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Write . Normalization says , and the Schmidt rank equals the matrix rank of . Its nonzero singular values are therefore with .
The overlap with the maximally entangled state is . The trace norm estimate of Q3(i), with test linear operator , followed by the Cauchy-Schwarz inequality, givesFor two pure states, the unsquared quantum fidelity is the absolute value of their overlap. Hence the maximally entangled overlap bound from Schmidt rank isThe bound is attained by . Thus uniform Schmidt coefficients on aligned basis pairs give the greatest possible overlap for that Schmidt rank.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 323 4 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
The coefficient matrix in the computational basis isFor a bipartite pure state, the partial traces give and . Therefore the requested reduced density matrices areThe columns of are orthogonal. Their norms are and , so normalizing them gives the orthonormal setWith and , a Schmidt decomposition isExpanding this expression reproduces the minus sign in the coefficient. The two reduced density matrices both have eigenvalues and , consistent with these Schmidt coefficients.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 323 4 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For any normalized pure state on finite-dimensional Hilbert spaces , the Schmidt decomposition givesThe and form orthonormal sets in their respective spaces. The positive numbers are the Schmidt coefficients, and is the Schmidt rank. Taking a partial trace gives the reduced density matricesThus the nonzero eigenvalues of the two reduced density matrices agree.
One construction is a singular value decomposition of the coefficient matrix in . If , the columns of give , the complex conjugates of the columns of give , and the singular values give . This also explains why the Schmidt coefficients are real and nonnegative.
Pinned article: Introduction to the OurBigBook Project
Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
Intro to OurBigBook
. Source. We have two killer features:
- topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculusArticles of different users are sorted by upvote within each article page. This feature is a bit like:
- a Wikipedia where each user can have their own version of each article
- a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.Figure 1. Screenshot of the "Derivative" topic page. View it live at: ourbigbook.com/go/topic/derivativeVideo 2. OurBigBook Web topics demo. Source. - local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
- to OurBigBook.com to get awesome multi-user features like topics and likes
- as HTML files to a static website, which you can host yourself for free on many external providers like GitHub Pages, and remain in full control
Figure 2. You can publish local OurBigBook lightweight markup files to either OurBigBook.com or as a static website.Figure 3. Visual Studio Code extension installation.Figure 5. . You can also edit articles on the Web editor without installing anything locally. Video 3. Edit locally and publish demo. Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension. - Infinitely deep tables of contents:
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact





