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 2014 iii Paper 63 2 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
QMA is the class of promise problems for which a uniform polynomial-size quantum circuit checks a polynomial-size quantum witness. A YES instance has some quantum witness accepted with probability at least ; on a NO instance every quantum witness is accepted with probability at most . The verifier initializes its own ancilla qubits to zero. Mixed quantum witnesses do not improve the maximum because acceptance is linear in their density operator.
For a verifier and quantum witness embedding , define the witness acceptance operatorThe Rayleigh quotient gives . Every entry of can be recomputed by the polynomial-storage path summation of part (b); no full quantum witness matrix needs to be stored.
Let the quantum witness have qubits, so its dimension is . For this positive operator, trace-power witness optimization usesThis is the useful exponentiated form of the supplied logarithmic inequality. Positivity is required; such a logarithmic statement is not true for an arbitrary operator. No logarithms or roots need to be calculated.
Choose . On a NO instance,since . On a YES instance, . Thus comparison of with one distinguishes the cases using only multiplication and a final comparison.
Evaluate the trace byThere are active quantum witness indices, each requiring bits. Accumulate one product at a time and recompute its matrix entries as required. Together with the verifier path workspace, this uses polynomially many real registers. The potentially enormous time and the numerical precision are unrestricted in . Therefore , without solving an exponentially large eigenvalue problem by storing its matrix.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 63 2 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
The class uses polynomial-register real-arithmetic computation: its storage restriction counts real registers, without limiting their precision or the running time. Use the usual decision-model interpretation that computed real values may be compared with fixed thresholds, and that the fixed universal gate set's real constants are available. Without a way to test values, arithmetic instructions alone would not specify the intended decision model.
Let a BQP quantum circuit use qubits and gates. A matrix element can be evaluated by depth-first quantum circuit path summation:Enumerate the intermediate -bit strings recursively. Store the current strings and loop positions, a partial product, and the partial sum at each depth. There are at most active levels, using registers or bits of loop information, not an exponentially long state vector. Each fixed-locality gate matrix element is computed from its few affected bits. Represent a complex number by two real registers; complex multiplication and addition require only real addition, subtraction and multiplication.
Recompute this amplitude separately for every final string whose output bit is one, accumulating the Born rule probabilityThe outer enumeration needs only another bits and a real accumulator. Arbitrarily large running time is allowed, so repeated recomputation is harmless. Compare with to distinguish the promised BQP cases. This proves using polynomial storage.
The printed probability hint omits the squares of the amplitude moduli. Summing their absolute values alone is not the Born rule and can exceed one. The corrected sum above is necessary for the containment proof. The argument is about the stated real-register model, rather than a claim that exponential-precision numbers are free in an ordinary bit-cost model.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 63 2 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
BQP consists of promise problems decided by a uniform family of polynomial-size quantum circuits. On input , with polynomially many zero-initialized ancilla qubits, a designated output measurement accepts with probability at least on YES inputs and at most on NO inputs. Uniformity means a classical polynomial-time procedure produces the quantum circuit description from the input length, or equivalently produces the verifier quantum circuit with supplied as input.
For BQP error reduction, run independent copies with freshly initialized registers. If the completeness and soundness thresholds are any constants , accept when the fraction of accepting trials exceeds . A Hoeffding inequality bounds either error by , with repetitions. The threshold need not be a simple majority when both and lie on the same side of .
Choosing sufficiently large gives the usual thresholds, or any other fixed separated thresholds. Even an inverse-polynomial gap can be amplified using polynomially many repetitions. Classical threshold evaluation can be incorporated into the uniform computation. Thus fixed separated acceptance probabilities define the same BQP class. This argument concerns unrestricted BQP quantum circuits and does not assume such amplification is available for restricted stoquastic circuits.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 63 1 d Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For a normalized computational history state, the output projector sees only its final clock component. With the quantum circuit's acceptance probability,This proves the hint, including for a computational basis quantum witness. Moreover is a stoquastic Hamiltonian term, so adding it with positive coefficient preserves stoquasticity.
There are two substantive problems with the stated promise. First, for any basis quantum witness the initialized state has nonnegative amplitudes, and every permutation matrix preserves them. Write the output as , with both vectors entrywise nonnegative. ThenThe stoquastic acceptance floor rules out the printed one-third soundness condition. There are no NO instances of that literal promise. Second, the ground space includes histories of arbitrary quantum witnesses. It is the maximum over those quantum witnesses, not the maximum over basis quantum witnesses, that determines the lowest output energy. Even the identity quantum circuit accepts each basis input with probability , but accepts a quantum witness with probability one. Thus a basis-witness soundness bound would not control this Hamiltonian, even if its numerical threshold were repaired.
The requested nontrivial hardness statement therefore needs the standard quantum-witness StoqMA promise, with and inverse-polynomial gap . The intended reduction can be completed precisely under that corrected promise. Define the quantum witness embedding and the witness acceptance operatorIt is a positive contraction, and . The minimum expectation of on the history ground space is . This is also consistent with a nonnegative optimal StoqMA quantum witness: is entrywise nonnegative, so replacing amplitudes by their absolute values cannot decrease its quadratic form.
A uniform ground-space perturbation bound is needed because the gap shrinks with quantum circuit length. Put , and choose a positive inverse-polynomial coefficientFor the history ground projector and any unit vector with , the operator norm bound givesThe last inequality completes the square in and uses . Testing a ground space minimizing vector gives the upper bound . Since , we obtainYES instances of the corrected promise have energy at most ; NO instances have energy at leastThe separation is at least , an inverse polynomial. The quantum circuit and all these Hamiltonian terms have polynomial-size descriptions. This proves StoqMA hardness for the local Hamiltonian problem variant that permits the nonlocal clock, under the corrected quantum witness and acceptance promise.
The printed perturbation formula also has where a general perturbation belongs. Its unspecified cannot be treated as uniform in a closing gap. Likewise a circuit-length-independent constant cannot in general satisfy the stated small-perturbation requirement for an arbitrary long quantum circuit. The explicit bound above avoids both issues; it does not claim the defective literal promise defines standard StoqMA.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 63 1 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Use the unitary change of basis from part (b). It reduces the Feynman-Kitaev Hamiltonian to , whereThe positive eigenvalues of are positive integers, since its commuting ancilla projectors act on different qubits. The positive spectral gap of is . Thus both positive spectra are bounded below by , for .
Let , and split the work space into and . The common ground space is . A unit vector in orthogonal to has the form , where . Its orthogonal projection onto simply removes its time-zero component, so the projected norm is . Consequently the smallest angle between two subspaces, after removing their common intersection, satisfiesThe Kitaev geometrical lemma now givesHere supplies the penultimate step. HenceIf there are no input constraints, and the propagation gap is already , which is stronger.
The printed geometric-lemma notation needs a correction: the maximum overlap defines , not , and is taken over normalized vectors in the two kernels, with the common ground space removed. The ground space restriction is essential when many quantum witnesses are allowed.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 63 1 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For an arbitrary vector , the preceding positive quadratic forms show that zero energy requiresThus all its clock components are generated by one correctly initialized input. Ifthen consists of , with unrestricted quantum witness . Normalization gives the computational history stateConversely, every such computational history state annihilates every propagation term and the input term, hence has zero energy. These states are exactly the ground space, not merely examples of its vectors. In particular, histories of computational basis quantum witnesses span the ground space; their coherent superpositions are also zero-energy states.
Another way to see the propagation constraint is to conjugate by . Then , whereThe spectrum of a path propagation Hamiltonian has a unique uniform clock zero mode. This is the path with vertices. The upper summation index in the printed auxiliary formula must be , rather than , to agree with its stated dimension and spectrum; using would introduce an extra vertex.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 63 1 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Write the quantum circuit as , and let , . Use a nonlocal quantum clock with orthonormal states . Let the work space include the quantum witness and the ancilla qubits. The input penalty of a history Hamiltonian is built fromIt annihilates precisely the correctly initialized ancilla qubits, leaving the quantum witness unrestricted. The Feynman-Kitaev Hamiltonian without output penalty isEach propagation summand is positive: on vectors with adjacent clock components , its quadratic form is . The input penalty of a history Hamiltonian is also a positive semidefinite operator, so .
To verify that this is a stoquastic Hamiltonian, use the work computational basis and the clock basis. Every is a permutation matrix, so the propagation off-diagonal entries are nonpositive. The zero-ancilla projectors are diagonal, while also has nonpositive off-diagonal entries. No positive off-diagonal entry is introduced by summing these terms. Thus is positive semidefinite and stoquastic, with no output penalty.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 61 4 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Use the operator norm induced by the usual vector norm, and assume the input quantum state is normalized. Since and the Hadamard gate is unitary, the J-gate phase-error operator norm isWrite the exact and implemented quantum circuits as ordered products and . The quantum circuit gate-error telescoping bound follows fromEvery surrounding factor is unitary, including gates tensored with identities on other qubits, so the triangle inequality and the submultiplicativity of the operator norm giveThe exact Controlled-Z gates contribute zero to that sum. ThusThe endpoint is sufficient because each implemented angle error is strictly smaller than . If , the circuits are identical and any positive works. The bound controls the stated vector distance with actual gate phases retained, so no adjustment of the global phase of one output is needed.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 61 3 iii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
The binary phase is . ThereforeOn the phase register, apply the tensor product of phase gatesIts action on is multiplication by . Thus the positive-phase fractional power of a unitary operator is implemented by uncomputation after coherent phase estimation:HenceThe inverse phase-estimation circuit uses controlled powers of built from the supplied inverse oracle, with all other quantum gates reversed. No phase-register measurement is made, so arbitrary superpositions are preserved and the ancilla qubits return to zero. The straightforward implementation uses controlled-unitary queries plus the Fourier and phase circuitry; the arbitrary phase gates are accepted exactly as stipulated.
The branch convention matters. This construction uses the phase representative specified here, corresponding to argument in . It implements that explicitly defined root, even for . The usual complex principal branch with argument in would choose a different root on some eigenvalues. No substitution of that alternative branch is implicit.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 61 3 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Since is a unitary operator, its eigenstates form an orthonormal basis. Expand , with eigenphases . By linearity, the unmeasured quantum phase estimation output isThis is generally an entangled state, not a phase label attached to an unchanged pure system state. The distinct eigenvalues give distinct phase labels, so a computational basis measurement yields with Born rule probability and leaves in the system register. Before measurement, all relative phases remain coherent; that is essential for the following spectral transformation. If phases were degenerate, a measured label would instead select the corresponding eigenspace component.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 61 3 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Let and use an -qubit phase register. Begin with and apply to the phase register, creating . Controlled powers implementFor phase qubit , counted from the most significant bit, the controlled power is . It can be built from calls to the supplied controlled- gate. By quantum phase kickback, the phase-register state isApply the inverse quantum Fourier transform to obtain the exact quantum phase estimation mappingA computational basis measurement of the first register determines with certainty, hence and the eigenvalue . Exactness follows from the promised dyadic phase; no approximation or continued-fraction reconstruction is needed.
With only controlled- available as a query, the repeated-power construction uses oracle calls. The other Fourier-transform circuitry has polynomial size in in the ideal phase-gate model. The cost of exact phase estimation on a dyadic spectrum is therefore not polynomial in in this primitive-query model unless powered queries have additional implementations. The task does not require such a polynomial bound.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 61 2 iv Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Write , and . The easy starting state is uniform over all -bit labels, so its good fraction is , not . For distinct primes one has . If both primes are odd, and , giving . If one prime is two, the other is an odd prime ; since has bits, , and .
The uniform coprime state for a semiprime can now be prepared by one exact Grover rotation. SetPrepareUse the good subspace spanned by with and . Its squared overlap with is exactly . The Euclidean algorithm supplies a reversible computation of the membership predicate, including the range check; condition a sign flip on membership and the extra qubit being one, then uncompute the workspace. This implements .
The starting-state reflection uses the inverse of its known preparation and a reflection on the all-zero state. Applying once invokes exact amplitude amplification at , and givesThe extra qubit factors off, and the arithmetic workspace is returned to zero. Although the stated range includes , that label is not coprime to itself, so the predicate is equivalent and avoids admitting labels outside the intended range.
The supplied determine in polynomial time; no factoring procedure is needed. Binary arithmetic, range comparison, the reversible greatest common divisor, the two starting-state reflections and the controlled sign flip all have polynomial-size circuits. Thus the construction takes polynomial time in in the ideal model allowing the specified one-qubit state preparation. Exactness uses the rotation with known amplitudes ; with a fixed finite approximate gate library one obtains arbitrary accuracy with precision overhead, rather than an automatic promise of exact state preparation. In the ideal model the preparation succeeds with certainty, without rejection sampling. If desired, the extra can be reset by a Pauli X gate.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 61 2 iii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Prepare the two data qubits in and a phase ancilla qubit in . A single Boolean quantum oracle query flips only the marked amplitude. Its success fraction is , so in amplitude amplification. The fixed diffusion reflection gives after one iteration.
Directly, after the query the marked amplitude is and the other three are . Their mean is . The diffusion reflection replaces each amplitude by , yielding one at the marked input and zero elsewhere. ThusHere is understood with its target ancilla qubit, and acts only on the data. It is independent of : , with the central diagonal gate implementable using two Pauli Z gates and one Controlled-Z gate. Measuring the data in the computational basis therefore finds the unique marked string with certainty after one oracle query.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 61 2 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Let be the orthogonal projection onto the good vector subspace , and let the normalized input be . Set with , and defineAssuming coherent access to the two reflections, the amplitude amplification theorem states thatpreserves the plane spanned by and acts as a rotation, givingHence the good-outcome probability is . When is known, choose the nearest nonnegative integer to . The resulting angle is within of , so the good probability is at least . For small this is close to one and requires iterations. Exact success occurs when . Known also allows exact amplitude amplification by ancilla qubit dilution or selective phase adjustment when ordinary integer iterations would overshoot.
If has a known coherent preparation, its reflection is implemented with , and a zero-state phase flip. A coherent membership test supplies the reflection about . Merely possessing an unknown copy of does not automatically supply its reflection. For the state is already good; for this two-reflection construction cannot generate a good component. These cases delimit the theorem's algorithmic assumptions.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 61 2 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Assume is normalized and the Hilbert space has dimension . The rank-one orthogonal projection satisfies and .
For , has eigenvalue zero on the orthogonal complement of , so it cannot be a unitary operator. The complementary orthogonal projection kills and is not unitary in any positive dimension. In contrast, the Householder reflectionis Hermitian and obeys . Its eigenvalues are along and on the orthogonal complement.
For , only is unitary. In the exceptional one-dimensional case, is also unitary; its complement remains zero.
Past exam of the mathematics course of the University of Cambridge 2014 iii Paper 61 1 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Use the positive-sign quantum Fourier transformOrthogonality of the finite-group characters makes a unitary operator. Here is the least positive period. The injectivity within one period implies : write , . Periodicity gives , and injectivity forces . Put .
Start with two available computational basis states . Apply to the first register and query the modular-addition quantum oracle:Measure the second register. For some , the first register becomes the normalized coset stateThe quantum Fourier transform of a periodic coset state isIndeed, the inner geometric sum vanishes unless the Fourier label is a multiple of . Measuring that label gives for a uniformly random . Compute, by the Euclidean algorithm,Thus exact period recovery from a Fourier sample succeeds whenever is coprime to , andHere is the Euler totient function. The classical number-theory input is the totient lower bound from the Mertens product: for sufficiently large , for an absolute , with the finitely many small cases handled separately. For recovery is certain; for its probability is . The useful asymptotic probability statement is a lower bound, hence notation; it can be much larger for particular periods, for example a prime period.
There is one oracle query, two Fourier transforms and two measurements. The final greatest common divisor and division use polynomial time in . This meets the specified primitive-operation model without assuming that an arbitrary- Fourier gate is free in another gate model. If a constant success probability is wanted, repeat independently times and return the least common multiple of the candidates: each candidate divides , and one successful sample makes that least common multiple exactly .
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





