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 2015 iii Paper 67 3 d Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Use an -qubit state as the witness. Uniformly choose a term and perform the two-outcome positive operator-valued measure . Regard the second outcome as an energy flag. For witness , its probability isThis is an efficient local-energy measurement verification: a unitary operator on the relevant qubits and one ancilla qubit can implement the measurement using the isometryThe local dimension is constant; the term matrices and the measurement can be approximated to inverse-polynomial accuracy. Uniform choice of and the classical threshold comparison also have polynomial overhead.
SetIn the nontrivial case , is inverse-polynomial. Cases outside this energy range are decided directly from .
Ask for witness registers, measure an independently sampled local term on each, and accept if the mean number of energy flags is at most . An honest product ground state on a YES instance has flag probability at most . The Hoeffding inequality gives failure at most . For completeness, the required Bernoulli concentration estimate follows by bounding the centered log moment-generating function : and is a tilted Bernoulli variance, at most . Hence ; exponential Markov's inequality optimized at yields , and the lower-tail version follows in the same way.
Soundness must also cover entangled witness registers. The averaged flag effect is . All its eigenvalues are at least on a NO instance. The repeated verifier's acceptance effect is a polynomial in the commuting tensor-factor operators and . In their product eigenbasis its eigenvalues are lower-tail probabilities of independent Bernoulli variables whose parameters are each at least . Their lower tail is bounded by the identical-parameter tail at , using the same uniform-variable coupling as in QMA parallel repetition with entangled witnesses. Therefore its operator norm is at most , which bounds acceptance for any entangled witness.
Choosinggives completeness at least and soundness at most . A slightly larger constant absorbs implementation errors; for example, approximate each flag effect in norm to at most , retain a gap at least , and increase by a constant factor. The total witness length and circuit size are polynomial. Thus
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 67 3 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
The local Hamiltonian problem is a promise problem specified by a sum on qubits, where is polynomial in , each Hermitian term acts on at most a fixed number of qubits, and the terms and two thresholds are described with polynomially many bits. The promise gap satisfies . In a convenient normalization, . The task is to distinguishThere is no required answer when the minimum energy lies between the thresholds. A formulation with Hermitian terms of polynomially bounded norm is equivalent: shift each term by a known scalar lower bound and rescale all terms by a polynomial bound to obtain positive semidefinite terms of norm at most one, while shifting and rescaling in parallel. The promise gap remains inverse-polynomial.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 67 3 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Interpret the high-success formulation as completeness at least and soundness at most , where for a growing polynomial . This is the standard error-reduction claim. Literally placing around a success probability approaching one supplies no useful lower bound; it is the failure probability that must be inverse-polynomially small.
Let be the quantum verifier acceptance operator acting on one witness register:Acceptance on is . On a NO instance, ; on a YES instance, an honest witness has acceptance at least .
Ask for witness registers, with odd, run independently on each register with fresh ancillas, and accept a strict majority. The QMA parallel repetition with entangled witnesses acceptance operator isDiagonalize . In the tensor-product eigenbasis, an eigenvalue of is the majority probability for independent Bernoulli random variables with parameters equal to the selected eigenvalues of . On a NO instance every parameter is at most . Coupling these variables using independent uniform random numbers shows that their upper majority tail is bounded by the tail with every parameter . This bounds the operator norm and therefore covers every supplied witness, including a witness entangled across the registers. No independence assumption about a dishonest witness is being made.
For a valid Chernoff bound, if is a sum of independent Bernoulli variables of parameter at most , Markov's inequality applied to yieldsAn honest product witness on a YES instance gives independent trials with rejection probability at most , so its failure probability has the same bound. The printed concentration bound is not valid as stated: for five trials at parameter , the upper-majority probability is . The valid bound above suffices for a rigorous proof.
Choose the next odd integer above . ThenThe witness length and circuit size increase by only ; the majority calculation has polynomial overhead. Conversely, inverse-polynomial failure probability is at most for all sufficiently large input lengths. Finitely many smaller lengths can be handled by hard-wired verifiers, giving the usual constants. Hence the two definitions give the same class QMA. The same QMA error reduction argument also yields exponentially small failure with polynomially many copies.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 67 3 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
A promise problem belongs to QMA if there are polynomials and a uniform family of quantum circuits of size at most , taking a -qubit witness and clean ancillas, with one output qubit interpreted as acceptance, such thatNo condition is imposed outside the promise. The witness may be an arbitrary density operator, and the verifier is efficient but need not know how to prepare an honest witness. Pure witnesses suffice for completeness because the acceptance probability is linear in the witness. QMA is quantum verification with polynomially many witness qubits and a constant completeness-soundness gap.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 67 2 c Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Part (a) shows that is invariant throughout the interpolation. As the Hamiltonians are Hermitian, is invariant as well: evolution starting in has no leakage into other sectors. The quantum adiabatic theorem may therefore be applied using the restricted spectral gap, even if other sectors of the full Hamiltonian have different low-energy levels.
Combining (b)(iv) with the supplied bound for gives for a constant . The matrix has diagonal entries and off-diagonal entries . Its Gershgorin discs all lie in , so . Thus the runtime criterion for adiabatic preparation of a computational history state is satisfied bywith a sufficiently large constant.
Starting from the supplied initial ground state , the resulting state obeysHere the trace norm follows the question's convention; the conventional trace distance is half this norm. The Hamiltonian has explicitly specified terms, each acting on at most five qubits, so its description and the runtime are polynomial in circuit size. If is polynomially bounded, the whole preparation has polynomial cost. The initial computational input is assumed to have been prepared, as in the premise of the quantum adiabatic theorem.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 67 2 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-20
Define the orthonormal history basiswhere . Orthogonality follows from the distinct unary quantum clock strings, regardless of overlaps between the computational states.
The initialization term acts diagonally:Each propagation term only couples the two clock strings adjacent to its step. The gate and its adjoint giveand for . The same calculation covers the two endpoint terms.
Thus both Hamiltonians preserve , and in the history basis their restrictions areThis history-subspace propagation Hamiltonian is a path graph Laplacian with a factor . The specified two-clock endpoint formulas assume ; a shorter circuit can first be padded with identity gates.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 67 1 a Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Let and be its complement, with Hilbert-space dimension . Use Haar twirling conditional expectation to defineThis is an operator supported on . The normalization is essential: the partial trace alone would not fix an operator already supported on .
Subtract the integrand from and use the operator norm triangle inequality. Since and every unitary operator has norm one, the assumed Lieb-Robinson bound, applied to a unitary supported on the entire complement, givesThe factor was bounded by ; there is no sum over sites and hence no volume-dependent prefactor.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 66 5 iii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Choose an orthonormal basis of the joint -dimensional Hilbert space whose first vector is the given purification of a density operator . Apply rank-one dephasing to in this basis, and denote the resulting diagonal probabilities by . Their first entry isThe preceding entropy increase under nonselective projective measurement and entropy bound with one prescribed probability yieldTherefore the quantum Fano inequality isThe quantity is the entanglement fidelity of on ; it is already a squared overlap, so it is , rather than , that enters the binary entropy. The argument is an instance of the entropy bound from overlap with a pure state in dimension . At the output is the original pure state and its Von Neumann entropy is zero. For the system is trivial and the same zero-entropy conclusion holds without evaluating .
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 66 5 ii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Put . The rank-one dephasing is . If , positivity givesso . The kernel of is exactly the span of these zero-probability basis vectors and is therefore contained in the kernel of . Taking orthogonal complements proves support inclusion under rank-one dephasing:Here the support of a positive operator is the orthogonal complement of its kernel.
On that support, is diagonal in the measurement basis, givingConsequently the relative-entropy identity for rank-one dephasing isKlein's inequality gives , since both density operators have trace one. For singular , first restrict to where is positive definite, replace by , and let . The support inclusion ensures that the limit is finite. ThusThis proves entropy increase under nonselective projective measurement using Klein's inequality. Equality holds exactly when , so the original density operator was already diagonal in the chosen basis.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 66 5 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
For , normalize the remaining probabilities by , . Directly splitting the Shannon entropy sum givesHere is the binary entropy. The Shannon entropy of a distribution on points is at most . For example, nonnegativity of its Kullback-Leibler divergence from the uniform distribution gives . Thus the entropy bound with one prescribed probability isFor , equality holds precisely when the remaining probabilities are all . For , the distribution is deterministic and both sides are zero. The displayed formula is for ; a one-point alphabet simply has zero Shannon entropy.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 66 4 iii Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-06
Use the Shannon second coding theorem in its channel capacity form . The finite-alphabet erasure channel erases independently of the input. On an unerased output Bob knows exactly; on the erasure output his posterior distribution is still . Its classical conditional entropy is thereforeEquivalently, and , so the binary entropy terms cancel in the mutual information.
For an alphabet of size , Shannon entropy is at most , with equality for the uniform distribution. Maximizing the displayed mutual information proves the capacity of a finite-alphabet erasure channel:This includes , which transmits the whole symbol, and , which transmits no information.
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





