The Cook-Levin theorem states that the Boolean satisfiability problem is NP-complete under polynomial-time many-one reductions. Membership in NP follows by guessing an assignment and evaluating the formula in time polynomial in its description length.
For hardness, let have a deterministic polynomial-time verifier , with a polynomial witness-length bound. Use a fixed polynomial certificate length: a short certificate is encoded by its length followed by padded data, and the verifier checks this encoding. Pad the computation to exactly steps, with accepting and rejecting states absorbing. Enlarge polynomially if necessary to cover input/witness initialization. A standard polynomial slowdown permits a single-tape Turing machine, so it suffices to handle that model.
Encode a tape cell by a fixed number of bits recording its alphabet symbol and either no head or the head's finite control state. Starting with one head, a cell's next label depends only on its own label and the two neighboring labels: a head can change the symbol where it sits and can enter only a neighbor. Each such finite local function has a constant-size Boolean circuit. The initial row fixes , blanks and the starting head, leaving only the witness bits as Boolean circuit inputs. There are relevant cells with blank margins beyond every possible head position, and updates. Repeating these local Boolean circuits produces a Boolean circuit of size , with an output detecting an accepting head in the final row. The construction is computable in polynomial time. Induction on rows shows that every assignment to produces exactly the verifier's valid computation; invalid local encodings can be assigned arbitrary Boolean circuit behavior because they never arise from the valid initial row.
Convert this Boolean circuit to conjunctive normal form using a Tseitin transformation. Introduce one variable for each wire, and encode each gate output by:
Gate relationClauses imposing equivalence
Unit clauses fix constant sources and assert the final output. Each input assignment has exactly one extension to its gate values, so the resulting formula is satisfiable precisely when some witness makes accept. It has clauses of bounded length and is produced in polynomial time. Thus
This proof also gives hardness for clauses of at most three literals, without needing a separate satisfiability assumption.
This is the Deutsch-Jozsa test with an arbitrary uniform-state unitary, and does not require to be a power of two. Choose a known unitary operator such that . Prepare the target qubit in . One Boolean-oracle call gives quantum phase kickback:
Apply to the index register. The amplitude on is
It equals or for the two constant strings, and equals zero for a balanced string. Consequently a single query decides the promised problem exactly: measure the index register and report constant for outcome zero, balanced for any other outcome. This is the Deutsch-Jozsa algorithm with the available exact state-preparation operation.
Under the usual reversible-circuit interpretation, there is a genuine obstruction to uniform probability lowering by a unitary in the printed premise. The universal assertion cannot hold for arbitrary : it fails already at the search density .
An explicit counterexample uses , one good basis state , and . The six pure states
all have good probability . Their equally weighted density operator is , a maximally mixed state. Every unitary operator leaves this mixture unchanged, so its average output good probability remains . The printed assertion would instead make all six output probabilities , a contradiction. More generally, averaging states uniformly over good and bad basis vectors and two opposite phases gives , proving the same obstruction at the actual search density .
The intended conditional construction needs only a supplied reversible preparation that lowers the success probability of the particular starting state, not of every state. Here is the complete argument under that weaker resource assumption. Count and as supplied, query-free operations, as required for the claimed input-oracle bound. Let and choose
If equality holds, use the original preparation. Otherwise use the stipulated preparation on to obtain with good probability . Its reflection operator is implementable by
The good and bad components may be nonuniform, but amplitude amplification applies to this same two-dimensional decomposition. After iterations of , its good probability is
Thus the stated exact-query conclusion follows from accessible preparation of one known-overlap state and its inverse. If the supplied preparation uses oracle queries, those costs cannot be omitted.
A physically realizable known-state success dilution for exact amplitude amplification is available in the standard enlarged marking-oracle model. Append a flag in , where , and call a joint state good only when and the flag is one. This prepared state's success probability is exactly . Reflect about this known product preparation and mark the joint good subspace; ordinary iterations then succeed with certainty. A supplied controlled phase oracle gives one marking query per iteration, or a Boolean bit oracle computes , applies the joint phase and uncomputes in two queries. Measuring the data therefore returns a good with certainty in queries. This changes the state space and marking test, and does not assert the impossible universal -qubit circuit. Controlled access is an additional resource in a bare phase-oracle model, so it is made explicit rather than silently assumed.
The amplitude amplification theorem concerns a known preparation quantum circuit and a good-subspace projector . Write , with . Let and . Then
The reflection operators preserve the two-dimensional good-bad plane and rotate it by , so iterations amplify a small known success probability to a constant close to one. Each iteration uses one good-subspace phase test and one use each of , together with a known reflection. Amplitude amplification provides a quadratic improvement in the number of repetitions of a successful preparation. The query cost of the preparation and its inverse must be included when they themselves use the input oracle. Exact amplitude amplification uses additional known-overlap preparation or phase matching to avoid integer-iteration overshoot.
A good item must exist, so assume ; if , the requested search is impossible, while makes every output good. Put and . Normalize the good and bad components of the uniform superposition state as
The Boolean phase oracle negates and fixes . The Grover diffusion operator is . Its implementation is independent of : conjugate the reflection about by Hadamard gates. One Grover search algorithm iteration is
Hence, by the Grover rotation angle formula,
Choose the nonnegative integer nearest to . Its final angle differs from by at most , so a computational-basis measurement succeeds with probability at least . The allowed small-density regime includes , giving the requested bound. Each iteration uses one Boolean phase oracle query, and .
For , and one iteration reaches exactly. Thus one query gives a good outcome with certainty:
This is exact Grover search on four entries applied to a marked fraction of one quarter, not only to a four-element register.
Use the quantum Fourier transform convention , where . Reindexing the shifted sum gives
Thus the cyclic shift operator has these eigenvectors, with eigenvalues . This is cyclic shift diagonalization by the quantum Fourier transform, and it implies with .
For , the binary encoding is , with the more significant qubit. The required diagonal phase is
so . The allowed-gate circuit is therefore
In execution order, apply the inverse QFT, then the two phase gates, then the forward QFT. There is no extra global phase. Reversing the Fourier sign convention would conjugate both phase gate parameters.
The PDF's small superscript is essential: . Interpret as the least positive period, the multiplicative order of modulo . If one permitted an unspecified nonminimal period, the answer would not be identifiable; for example, gives the same constant function with period one or period eight. Under the promised periodic modular-exponential interpretation, , so is a unit. Thus
In particular, different residue classes modulo have different function values, which is necessary for the usual quantum period finding coset argument.
Prepare by applying the quantum Fourier transform to the first register. Use repeated squaring to precompute , then multiply the value register by that known number controlled on bit of . These controlled modular multiplications are reversible because is a unit; their inverses use the modular inverses of the same constants. This produces with a polynomial number of the assumed arithmetic operations. Known work registers can be uncomputed.
Measure the value register. Since , its fiber is exactly one coset, and the first register becomes
The quantum Fourier transform of a periodic coset state is supported uniformly on the outcomes , . Indeed the inner geometric series is zero unless , and each allowed amplitude has modulus .
Take two independent Fourier samples and return
This is two-sample exact period recovery. The Chinese remainder theorem makes divisibility of independent uniform residues independent across the different prime divisors of . For each such prime , both and are divisible by with probability . Therefore
The number-theoretic facts used here are the Chinese remainder theorem, the Euler product for the Riemann zeta function at two, and . The candidate can also be certified by : it divides the least period, so this equality holds exactly when it is the full period. Each preparation, reversible evaluation, QFT, measurement and greatest common divisor calculation has the assumed or standard polynomial time cost in . Two runs suffice for the desired constant success probability. Quantum period finding recovers the least period with probability at least in polynomial time.
With every bath spin up, the two conditional bath states in the Zurek spin-bath model differ only by global phases. The decoherence factor is
There is no quantum decoherence, even for a very large bath. The device evolves as the pure state , while the bath stays in its original product eigenstate up to phase. Since no device information is imprinted in distinguishable bath states, the conditional environment overlap has unit modulus. The phase rotation must not be mistaken for decay of off-diagonal magnitude.
Let . In the Zurek spin-bath model, , so unitary time evolution with is . The bath Hamiltonian terms commute, and device states have eigenvalues . Hence
where the two normalized conditional bath states are
Take each bath factor normalized, , and . This entails no restriction: if only the product is initially normalized, divide each nonzero factor by its norm; the product of these norms is one.
Taking the partial trace over the bath gives the reduced density matrix
The orientation of this conditional environment overlap fixes the sign of the phase in the upper-right entry. Factorizing the overlap yields the decoherence factor
The populations are conserved because . Only phase coherence can be reduced. In particular,
Quantum decoherence here results from distinguishable conditional bath states, although the complete system remains in a pure state under unitary time evolution.

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