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 is
This is an efficient local-energy measurement verification: a unitary operator on the relevant qubits and one ancilla qubit can implement the measurement using the isometry
The 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.
Set
In 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.
Choosing
gives 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
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 distinguish
There 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.
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 is
Diagonalize . 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 yields
An 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 . Then
The 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.
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 that
No 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.
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 by
with a sufficiently large constant.
Starting from the supplied initial ground state , the resulting state obeys
Here 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.
Define the orthonormal history basis
where . 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 give
and for . The same calculation covers the two endpoint terms.
Thus both Hamiltonians preserve , and in the history basis their restrictions are
This 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.
Let and be its complement, with Hilbert-space dimension . Use Haar twirling conditional expectation to define
This 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, gives
The factor was bounded by ; there is no sum over sites and hence no volume-dependent prefactor.
Choose
For , , and therefore
Thus is the desired Lieb-Robinson localization by Haar twirling. The displayed choice assumes the usual positive constants ; if the interaction bound has , the error is identically zero and any positive works. For negative times the same argument uses .
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 is
The preceding entropy increase under nonselective projective measurement and entropy bound with one prescribed probability yield
Therefore the quantum Fano inequality is
The 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 .
Put . The rank-one dephasing is . If , positivity gives
so . 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, giving
Consequently the relative-entropy identity for rank-one dephasing is
Klein'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. Thus
This 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.
For , normalize the remaining probabilities by , . Directly splitting the Shannon entropy sum gives
Here 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 is
For , 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.
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 therefore
Equivalently, 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!
We have two killer features:
  1. 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-calculus
    Articles 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/derivative
  2. 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.
    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.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
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