Conjugation by the Hadamard gate sends to . Therefore its Bloch vector action is
It is a rotation through about : differs by a global phase from the corresponding spin rotation.
The S gate and T gate differ by global phases from -axis rotations:
Indeed , which sends to .
The six Pauli eigenstates have Bloch vectors , , :
Classical convex combinations of density operators produce the corresponding convex combinations of their Bloch vectors. Their convex hull is the stabilizer octahedron:
The six vertices are pure Pauli states; the faces and interior represent their mixtures. To verify the reverse inclusion, give the vertex in the sign of each coordinate weight and use the leftover weight at the origin, itself the equal mixture of either opposite pair.
Figure 1. . The red diameter shows all mixtures of and . The six Pauli vertices generate the blue octahedron. The gold point is the T-gate resource state: it lies on the Bloch sphere but outside this octahedron. Details.
The Pauli multiplication identity gives . Its eigenvalues are therefore , and those of the density matrix are
Hermiticity and trace one are automatic; positive semidefiniteness holds exactly for . Thus physical qubit states form the Bloch ball, with pure states on the Bloch sphere and mixed states inside.
For the mixture of the two standard-basis states,
These form the entire -axis diameter, shown in the left panel of the diagram in part b. Generate the state by selecting with classical probability and with probability , then discarding the classical selection record. A coherent superposition is generally a different state: the forgotten classical record removes off-diagonal coherence.
The input is the Bell state , where . Acting on the first qubit reverses the signs of all three terms containing its Pauli matrices, so in computational basis order the output is
Its eigenvalues are : in particular, its expectation value in is . It therefore fails to be positive semidefinite, although its trace remains one. This single entangled state proves that the universal NOT gate is positive but not completely positive, so it cannot be a deterministic physical quantum channel on an arbitrary input.
The universal NOT gate is the isotropic qubit map with factor . It sends
For , the output has the same two nonnegative eigenvalues as the input, exchanged, and still has trace one. Thus it maps every single-qubit density matrix to a density matrix. Its linear extension to all operators is , not for arbitrary unnormalized . Positivity on one qubit does not establish complete positivity when an ancilla is present.
Conjugation by one Pauli matrix fixes that same matrix and reverses the other two. For example, , , and . Applying this to each component of the Bloch vector gives
Hence the quantum depolarizing channel is
The Kraus operators and establish complete positivity for . At every state becomes maximally mixed. For the factor is negative: it reverses the vector as well as reducing its length. Its most negative value is , consistent with the complete-positivity range of the isotropic qubit map.
For any column vector and positive semidefinite input , the Kraus representation gives
Thus the output is positive semidefinite. The cyclic property of the trace and completeness of the Kraus operators give
More strongly, tensoring with an arbitrary ancilla replaces by , so the same argument proves complete positivity rather than only positivity on single-system density matrices.
If has Kraus operators , the composition of quantum channels has
This is again a trace-preserving Kraus representation. The composition of completely positive maps is completely positive even without the trace-preserving assumption; in the general case, the product Kraus operators still establish complete positivity.
The Pauli matrices are Hermitian matrices with zero trace, so a real Bloch vector makes Hermitian and gives . Their Pauli multiplication identity implies . Consequently the two eigenvalues of are , including the zero-vector case, and
A density matrix must also be positive semidefinite. The displayed eigenvalues are nonnegative exactly when . Thus real coordinates alone are insufficient: the allowed vectors fill the Bloch ball. Its boundary consists of pure states, with eigenvalues one and zero; its center is the maximally mixed state .
Normalize the second qubit as . Since a Pauli X gate changes to , the Boolean quantum oracle acts as
This quantum phase kickback leaves the second qubit uncorrelated with the first. Put : for a constant function and for a balanced Boolean function. Apart from the irrelevant global phase , the first qubit and environment reach
The population-preserving interaction commutes with the quantum oracle on this answer-register input, so its placement before or after the oracle, between the two Hadamard gates, gives the same result. Substitute into b:
The printed Deutsch algorithm uses the rule zero means constant function; one means balanced Boolean function. With that rule, the Deutsch algorithm with pure dephasing succeeds for either class with
For real nonnegative environment overlap this is , ranging from certainty at to random guessing at . For general complex overlap, a coherent shift can invert the printed answer: for example makes the printed rule always wrong. If the overlap is known but the printed quantum measurement is retained, choose the better labeling of its outcomes; this gives
There is a further improvement if a known can be compensated by the phase gate before the final Hadamard gate. It removes the coherent shift without reversing any actual quantum decoherence, and yields
This is optimal when only the first qubit is accessible, with equal prior probabilities for the two classes. Before the final Hadamard gate, their reduced density matrices are
The difference has eigenvalues , giving trace distance . The Holevo–Helstrom theorem therefore bounds the success probability by , exactly attained by the compensated procedure. A known phase shift and loss of coherence have different effects: at the two density matrices coincide and no measurement on the available qubit can reveal the answer.
Write . The Cauchy-Schwarz inequality gives because the two environment states are normalized. Immediately after the interaction, the joint quantum state is
Applying the last Hadamard gate gives
Since the environment is unobserved, the Born rule uses the squared norm of the environment-valued coefficient of :
Thus the Hadamard interference with environment overlap formula is
The plus sign follows from the explicitly chosen phase gate and the order of the inner product. Equivalently, before the last Hadamard gate the partial trace over the environment gives
The complex environment overlap in qubit dephasing both reduces the quantum coherence by and adds a relative quantum phase . Orthogonal environment states have and give for every . If , the quantum interference fringe has full contrast and is only shifted; the qubit has not become mixed. For , is immaterial.
Moving the interaction to between the first Hadamard gate and the phase gate gives
the identical joint quantum state. Therefore the expression is unchanged. This is the commutation of computational-basis dephasing and phase gates; it uses the specified population-preserving interaction with the same environment states, rather than an arbitrary model of quantum decoherence.
Use the conventional phase gate in computational basis order . The single-qubit Hadamard gate and the successive quantum states are
The final Hadamard gate recombines the two components, giving
The leading factor in the last expression is a global phase. The Born rule therefore yields
At the output is certainly zero, whereas at it is certainly one. The phase gate changes no intermediate outcome probabilities; the final Hadamard gate converts a relative quantum phase into an observable quantum interference fringe.
With no access to the discarded qubit, the two preparations are exactly the reduced density matrices in c, with equal prior probabilities. Their difference is
Since , its eigenvalues are . The trace norm and trace distance are consequently
The Holevo–Helstrom theorem gives the optimum
To establish attainability, rather than only an upper bound, measure the Hermitian operator
where are Pauli matrices. Since , report first qubit for the positive outcome; second qubit for the negative outcome. The corresponding orthogonal projections are . Their success probability is
which reaches the bound. Identical eigenvalues of the two density matrices do not make them indistinguishable: their eigenvectors differ, and this quantum measurement detects that difference.
For a Hermitian matrix , the spectral theorem gives , with real eigenvalues and a unitary matrix . Hence
The square root here is the unique positive square root of an operator. Taking the trace, which is unchanged by unitary similarity, proves
For a density matrix, all eigenvalues are nonnegative and sum to one. Its trace norm is therefore
The absolute values cannot be omitted for a general Hermitian matrix, since positive and negative eigenvalues can cancel in its trace but never in its trace norm.
Let be the coefficient of . The partial trace contracts the repeated index of the discarded qubit:
For the first qubit, each diagonal entry is and the upper off-diagonal entry is . For the second qubit, the diagonal entries are and , while the upper off-diagonal entry is . Thus the two reduced density matrices, each in computational basis order , are
Both have eigenvalues and trace one, so both are mixed states even though the joint quantum state is pure. Their different eigenvectors are visible in the useful rewrite
Absorbing the minus sign into one local basis vector makes this a Schmidt decomposition with nonnegative coefficients. It also checks both partial traces and exhibits the entanglement responsible for the mixed local descriptions.
Expand the given pure state in the ordered computational basis :
The coefficients have squared magnitudes , summing to one. The density matrix is the outer product , not the diagonal matrix of these four probabilities: its off-diagonal entries retain quantum coherence. Therefore
The outer product is a Hermitian matrix and is positive semidefinite: . Its trace is one, and , as required for a pure state.
For any normalized vector , the Born rule assigns the probability to the corresponding rank-one orthogonal projection. This must be nonnegative for every , which is exactly positive semidefiniteness. For any complete orthonormal basis , the outcome probabilities must sum to one:
Thus a Hermitian matrix represents a physical density matrix only if
These conditions are also sufficient in finite dimension. The spectral theorem writes with and , describing a quantum state ensemble of pure states with valid mixing probabilities. A Hermitian matrix alone could have negative eigenvalues, hence negative measurement probabilities.
Each run of Simon's algorithm uses one oracle call and returns one uniform sample from . Collect samples as rows of a matrix and solve over the two-element field using Gaussian elimination. Once the rows have matrix rank , the kernel is , so the promised nonzero vector is uniquely determined. Dependent samples, including , must be allowed for; exactly runs need not suffice.
For a rough quantitative estimate, put . When the existing samples span an -dimensional vector subspace of , the next sample increases the matrix rank with probability . The random spanning of a binary vector space estimate gives
Alternatively, samples fail to span with probability less than : failure means some nonzero linear functional on the -dimensional space vanishes on every sample, and a union bound gives . Consequently
The Gaussian elimination requires only a polynomial amount of classical work, for example bit operations for samples. The degenerate case needs no calls because the promise already specifies .
Classically, distinct inputs with equal function values reveal . Uniformly sampling distinct inputs finds such a function collision after roughly calls, by the birthday square-root scale. For sampled inputs, the expected number of colliding pairs is . The usual randomized classical query complexity of Simon's problem is therefore exponential in , on the scale
A straightforward exhaustive classical search instead uses calls. The square-root collision estimate is the sharper classical comparison; the quantum advantage concerns access to the promised quantum oracle, rather than an explicit table of all function values.
Apply the Hadamard transform to the conditional quantum state from c. Since modulo two, its output is
If , the two probability amplitudes cancel by destructive quantum interference. If , they add, giving
Thus every observed string obeys . This Simon Fourier sampling is uniform on the -dimensional vector subspace over the two-element field. Indeed, the nonzero linear functional has a kernel of dimension by the rank-nullity theorem. The distribution does not depend on , so measuring or discarding the second quantum register gives the same statistics for the first.
An observed value must lie in the image of . Choose either preimage . The two-to-one function promise and imply that its preimages are exactly and . A computational-basis measurement of the second quantum register projects the joint quantum state onto the unnormalized vector
By the Born rule, . Dividing by its square root gives the conditional first-register pure state
Choosing the other preimage merely interchanges the two summands. The result is a Simon coset state, retaining quantum coherence between the two inputs that share the measured function value. Outcomes outside the image have probability zero and hence no conditional state to normalize.
Write for bitwise exclusive or. Both quantum registers begin in . After the first Hadamard transform their joint quantum state is
The quantum oracle maps each component to . By linearity, the required quantum state is therefore
The different first-register computational-basis states are orthogonal, so there are orthogonal joint components of squared probability amplitude , even though some second-register values coincide. Thus the displayed quantum state is normalized.

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