Phase 'Kick-back' Algorithms

Consider some black-box that encodes some function \(f\) that is implemented as a controlled\(-U_f\)  gate acting on the state space \(\mathcal{H}_A\otimes\mathcal{H}_B\) consisting of two registers \(A\) and \(B\) of qubits. Generally, when a controlled\(-U_f\) gate is applied it is thought of as only affecting the target register \(B\) leaving the control register \(A\) unchanged. Therefore, the action of the \(c-U_f\) gate is of the form
\[c-U_f: \left|x\right>\left|\phi\right>\mapsto \left|x\right>\left|\phi'\right>,\]
For some state \(\left|\phi'\right>\in\mathcal{H}_B\). Suppose some state \(\left|\psi\right>\in\mathcal{H}_B\) is chosen to satisfy
\[c-U_f(\left|x\right>\left|\psi\right>)= v_x\left|x\right>\left|\psi\right>,\]
where  \(v_x\) is some complex number that could depends on \(x\). In this case, the state \(\left|x\right>\left|\psi\right>\) is called an eigenstate of the operator \(c-U_f\),  and \(v_x\) is called the eigenvalue of the eigenstate. Moreover, the state \(\left|\psi\right>\) may also satisfy
\[c-U_f(\left|y\right>\left|\psi\right>)= v_y\left|y\right>\left|\psi\right>,\]
for some other state \(\left|y\right>\in\mathcal{H}_B\) and eigenvalue \(v_y\).

 This situation is more interesting when the control register is in some superposition of states such as \(\alpha\left|x\right>+\beta\left|y\right>\in\mathcal{H}_A\). Then
\[\begin{array}{r l}
c-U_f\big((\alpha\left|x\right>+\beta\left|y\right>)\left|\psi\right>\big) & =c-U_f(\alpha\left|x\right>\left|\psi\right>)+c-U_f(\beta\left|y\right>\left|\psi\right>) \\
 &= v_x\alpha\left|x\right>\left|\psi\right>+v_y\beta\left|y\right>\left|\psi\right> \\
 &=\big(v_x\alpha\left|x\right>+v_y\beta\left|y\right>\big)\left|\psi\right>,
\end{array}\]
and depending on the eigenvalues the state in the control register may contain a relative phase factor between the states \(\left|x\right>\) and \(\left|y\right>\). In this context, by associating the eigenvalue to the state in the control register, the action of the controlled\(-U_f\) gate can effectively be thought of as changing the state in the control register instead of the target register. Then by performing a measurement on the states, the existence of this phase factor may contain relevant information about the function \(f\) encoded in the black box.
 
   This technique of preparing the input in an eigenstate of a controlled\(-U\) gate, and then associating the eigenvalue to the control register is referred to as phase kick-back. A whole class of quantum algorithms exploits this technique in order to learn some property of a function \(f\) encoded in a black-box with fewer queries than would be needed in the classical case. 

Quantum Teleportation

Suppose Alice has a qubit in an arbitrary state \(\left|\psi\right>=\alpha\left|0\right>+\beta\left|1\right>\), and Bob wants to have an identical qubit \(\left|\psi\right>\) too.  If Alice knew enough information about the state \(\left|\psi\right>\) to either completely specify the numbers \(\alpha\) and \(\beta\), then these can be communicated to Bob. This would be worthwhile if Bob knew a unitary operator \(U\) such that, say,  \(U\left|0\right>=\left|\psi\right>\) that allows Bob to prepare the state. If the exact state \(\left|\psi\right>\) is unknown to Alice, then the situation is complicated because there is no amount of measurements Alice could make to the state \(\left|\psi\right>\) that provide sufficient information to uniquely determine the state \(\left|\psi\right>\) since any measurement made to \(\left|\psi\right>\) would only return some computational basis state. If Alice is willing to give up her qubit there is the option of physically sending the qubit to Bob if Bob is spatially displaced. This method entails a safe means of sending \(\left|\psi\right>\) through some quantum channel without any error, which may be rather difficult in practice. If the means of communicating quantum mechanically does not exist than the only alternative Alice and Bob have is to rely on classical means of communication. Fortunately, communicating classical bits is fairly easy to do in practice.

The quantum teleportation protocol allows two parties to send a qubit in an unknown state \(\left|\psi\right>\) without actually physically relocating the original qubit, and only having to communicating two classical bits of information. The protocol relies on the essential ability of the two parties involved to share an entangled Bell state between them.

Suppose Alice possesses an unknown state \(\left|\psi\right>=\alpha\left|0\right>+\beta\left|1\right>\) and shares an entangled pair of qubits in the Bell state \[\left|\beta_{00}\right>=\frac{1}{\sqrt2}(\left|00\right>+\left|11\right>)\] with Bob. In the quantum teleportation protocol, Alice first performs a Bell measurement on her two qubits of the register. This will yield information of some basis state \(\left|\beta_{ab}\right>\), or equivalently some state \(\left|ab\right>\) in the computational basis. Using the information from what state Alice observes, Alice communicates  two classical bits \(ab\) to Bob who then performs the operation \(Z^aX^b\) on his qubit based off the values of the bits \(ab\)  to turn it into the desired state \(\left|\psi\right>\).

(A circuit for quantum teleportation.  The top two wires represent Alice's register, which begin with  some qubit in an unknown state \(\left|\psi\right>\), and one qubit of a Bell state \(\left|\beta_{00}\right>\) shared with Bob's register represented by the bottom wire. Alice first performs a Bell measurement obtaining a state  \(\left|ab\right>\), and then communicates two classical bits \(ab\) to Bob who performs the operation \(X^bZ^a\) that transforms his qubit to the state \(\left|\psi\right>\).)

In the circuit for the quantum teleportation protocol the top two wires represent Alice's register and the bottom wire represents Bob's register. Note that the operations and measurement that Alice performs constitutes a Bell measurement. At the start of the protocol the state representing the whole system is
\[\left|\psi_0\right>=\left|\psi\right>\left|\beta_{00}\right>=\frac{1}{\sqrt2}(\alpha\left|0\right>+\beta\left|1\right>)(\left|00\right>+\left|11\right>),\]or when expanded
\[\left|\psi_0\right>=\frac{1}{\sqrt2}(\alpha\left|000\right>+\alpha\left|011\right>+\beta\left|100\right>+\beta\left|111\right>),\]
Since the first two qubits in the register represent Alice's system and the third qubit represents Bob's register the states are grouped with kets accordingly in order to make this more explicit in the notation as follows
\[\left|\psi_0\right>=\frac{1}{\sqrt2}(\alpha\left|00\right>\left|0\right>+\alpha\left|01\right>\left|1\right>+\beta\left|10\right>\left|0\right>+\beta\left|11\right>\left|1\right>).\]
Then the state after the controlled-NOT operation where the first qubit serves as the control and the second qubit as the target is
\[\left|\psi_1\right>=\frac{1}{\sqrt2}(\alpha\left|00\right>\left|0\right>+\alpha\left|01\right>\left|1\right>+\beta\left|11\right>\left|0\right>+\beta\left|10\right>\left|1\right>),\]
and after the Hadamard gate is applied to the first qubit the state becomes
\[\left|\psi_2\right>=\frac{1}{2}(\alpha(\left|00\right>+\left|10\right>)\left|0\right>+\alpha(\left|01\right>+\left|11\right>)\left|1\right>+\beta(\left|01\right>-\left|11\right>)\left|0\right>+\beta(\left|00\right>-\left|10\right>)\left|1\right>),\]
which can be regrouped as
\[\left|\psi_2\right>=\frac{1}{2}(\left|00\right>(\alpha\left|0\right>+\beta\left|1\right>)+\left|01\right>(\alpha\left|1\right>+\beta\left|0\right>)+\left|10\right>(\alpha\left|0\right>-\beta\left|1\right>)+\left|11\right>(\alpha\left|1\right>-\beta\left|0\right>)).\]
Examining Bob's register and noticing that
\[\begin{array}{l l}
\alpha\left|0\right>+\beta\left|1\right> = \left|\psi\right>, \\
\alpha\left|1\right>+\beta\left|0\right> = X\left|\psi\right>, \\
\alpha\left|0\right>-\beta\left|1\right> = Z\left|\psi\right>, \\
\alpha\left|1\right>-\beta\left|0\right> = XZ\left|\psi\right>, \\
\end{array}\]
allows the state before measurement to be expressed as
\[\left|\psi_2\right>=\frac{1}{2}(\left|00\right>\left|\psi\right>+\left|01\right>X\left|\psi\right>+\left|10\right>Z\left|\psi\right>+\left|11\right>XZ\left|\psi\right>),\]
or more concisely as
\[\left|\psi_2\right>=\frac{1}{2}\displaystyle\sum\limits_{i,j\in\{0,1\}}\left|ij\right>X^jZ^i\left|\psi\right>.\]
This is an entangled state! Therefore, when Alice measures the first two qubits where some basis state \(\left|ab\right>\) will be observed with equal probability,  Bob's qubit will be left in the state \(X^bZ^a\left|\psi\right>\). When Alice communicates the two bits \(ab\) that result as the outcome of the measurement, Bob can perform the  inverse operation \(Z^aX^b\) on the state \(X^bZ^a\left|\psi\right>\) turning the qubit in his register to the desired state \(Z^aX^bX^bZ^a\left|\psi\right>=\left|\psi\right>\) thereby completing the protocol.

The state of the joint system at the end of the protocol is \(\left|\psi_3\right>=\left|ab\right>\left|\psi\right>\), which leaves Bob's register in the state \(\left|\psi\right>\). Its important to note that as a consequence of this protocol Alice no longer possess the state \(\left|\psi\right>\). The original register that did contain \(\left|\psi\right>\) has turned into the state \(\left|a\right>\) after the measurement was performed. If this were not the case, and the joint system did happen to contain two copies of \(\left|\psi\right>\), then the proposed protocol would in fact contradict the no-cloning theorem. Moreover, it may seem that this teleportation protocol is in violation of the theory of special relativity, which prohibits information to be exchanged faster than the speed of light. In this regard, the protocol is actually void of contradiction because the state \(\left|\psi\right>\) is not effectively transmitted to Bob until after he receives the information of the two bits \(ab\) from Alice. Since these bits are communicated classically, they are indeed constrained from traveling faster than the speed of light avoiding any violation of the principles of special relativity.

The quantum teleportation protocol is another prime example of how entanglement can be used as a resource. In this sense, it can be said that a shared entangled pair and  the exchange of two bits of classical information is equatable to the exchange of one quantum bit of information.

Superdense Coding

Suppose we have two parties, Alice and Bob, and Alice would like to communicate some information to Bob. More specifically, Alice would like to communicate the values of two classical bits \(a\) and \(b\) to Bob. Quite trivially, Alice can do so by simply sending these two bits of information to Bob, but this requires Alice to send two bits to completely specify both. That is, communicating only a single bit is not sufficient information to determine the state of the second bit---at least classically.  Superdense coding is a quantum algorithm or protocol that allows Alice to send two bits of classical information to Bob by only sending a single quantum bit. This is accomplished by exploiting the entanglement that exists in the Bell state \(\left|\beta_{00}\right>=\frac{1}{\sqrt2}(\left|00\right>+\left|11\right>)\).

In the superdense coding scenario, Alice and Bob share the entangled Bell state \[\left|\beta_{00}\right>=\frac{1}{\sqrt2}(\left|00\right>+\left|11\right>),\] where Alice posses the first qubit in the register and Bob the second. Depending on which of the four possible combinations of two bits \(ab\in\{00,01,10,11\}\) Alice would like to communicate, Alice performs the operation \(Z^aX^b\) to her qubit of the Bell state and sends her qubit to Bob who then performs a Bell measurement on both of the qubits to get the state \(\left|ab\right>\) encoding the two classical bits Alice originally wanted to communicate. The circuit diagram describing this procedure is presented in the figure below, where the top wire of the circuit represents Alice's qubit and the bottom wire represents Bob's. Before the Bell measurement is performed, it is assumed that Alice has somehow provided Bob with her qubit so that Bob can jointly measure both qubits.


(A circuit for superdense coding. To communicate two classical bits \(ab\) to Bob, Alice applies the operation \(X^bZ^a\) to her qubit (represented by the top wire of the circuit) of the shared bell state \(\left|\beta_{00}\right>\), and then allows Bob to perform a joint Bell measurement on both qubits to yield the state \(\left|ab\right>\) encoding the two classical bits \(ab\).)

To observe why the superdense coding circuit accomplishes what its intended to note that applying \(Z^aX^b\) to \(\left|\beta_{00}\right>\), for the different choices of \(ab\in\{00,01,10,11\}\), transforms \(\left|\beta_{00}\right>\) to the other Bell states.
To see this, let \(Z^aX^b\left|\beta_{00}\right>=\left|\psi_1\right>\), then
\[\left|\psi_1\right>=\frac{1}{\sqrt2}(\overline b\left|00\right>+b\left|01\right>+(-1)^ab\left|10\right>+(-1)^a\overline b\left|11\right>)=\left|\beta_{ab}\right>,\]
where \(\overline b=(b+1)mod2\). Thus, by applying a Bell measurement to the state \(\left|\psi_1\right>=\left|\beta_{ab}\right>\), the state \(\left|ab\right>\) will be observed with certainty.

Superdense coding shows that it is possible to send two bits of classical information by sending only a single qubit. However, this can only be done provided that the qubit being sent is in an entangled state with another qubit. It is also implicit here that one party has the ability to successfully send a qubit to another receiving party. This is an example that shows how entanglement can be used a resource to accomplish something that would otherwise be impossible in the classical realm.

Quantum Entanglement

Although Bell states are systems of two qubits, neither of them can be expressed as the tensor product of any two states in \(\mathcal{H}^2\). That is, for each Bell state \(\left| \beta_{ij}\right>
\neq\left|\psi\right>\otimes \left|\phi\right>\) for any states \(\left|\psi\right>, \left|\phi\right>\in\mathcal{H}^2\). This has the implication of certain correlations that exist when measurements of the individual qubits are made on a Bell state. For instance, consider \[\left|\beta_{00}\right>=\frac{1}{\sqrt2}(\left|00\right>+\left|11\right>),\] and suppose the first qubit in the register is measured. This measurement will yield either \(\left|0\right> \) or \(\left|1\right>\) each with probability \(\frac{1}{2}\). A subsequent measurement on the second qubit in the register would then give a definite state \(\left|0\right>\) or \(\left|1\right>\) with probability \(1\) depending on the state of the first qubit being either \(\left|0\right> \) or \(\left|1\right>\), respectively. However, if it was the second qubit that was observed first, then either \(\left|0\right> \) or \(\left|1\right>\) would be observed with equal probability and the state of the first qubit would be correlated with the second in the same way.

The kind of correlations present in Bell states, where the measurement outcomes of subsystems of a larger composite system are inherently correlated is a property of entangled systems. A state \(\left|\psi\right>\in \mathcal{H}_A\otimes \mathcal{H}_B\) of some composite system is entangled if \(\left|\psi\right>\neq\left|\phi_A\right>\otimes\left|\phi_B\right>\) for any states \(\left|\phi_A\right>\in \mathcal{H}_A\) and \(\left|\phi_B\right>\in\mathcal{H}_B\). Otherwise, if it is possible to express a state \(\left|\psi\right>\in \mathcal{H}_A\otimes \mathcal{H}_B\) as a tensor product of two states \(\left|\psi\right>=\left|\phi_A\right>\otimes\left|\phi_B\right>\), then the state \(\left|\psi\right>\) is called a separable state. The existence of entangled states is a unique feature of quantum mechanics, and such states are exploited in various quantum algorithms and protocols.

Measurements in the Bell Basis

The state of a quantum system is generally represented in terms of the classical states that would result after the system is measured. These classical states have the property that they are  classically distinguishable from one another. The computational basis conventionally serves to index these classical states. The postulates of quantum mechanics allows non-classical states to be defined, and these states can be used to construct an arbitrary basis to describe the states in the system. Therefore, there ought to be a way to make measurements in an arbitrary basis. Abstractly speaking, this can always be performed. In practice however, these basis states must be related to the computational basis states in order to make better physical sense of the measurements.

 In the previous section an explicit circuit was constructed that output the Bell states given the computational basis states as input. This circuit can be thought of as performing the unitary operation \(U=(H\otimes I)(c-X)\). Then the inverse operation of \(U\) given by \(U^\dagger=(c-X)^\dagger(H\otimes I)^\dagger\) is the operation that takes as input some Bell state \(\left| \beta_{ij}\right>\) and outputs the corresponding classical basis state \(\left|ij\right>\). Therefore, in order to perform a measurement in the Bell basis it suffices to apply \(U^\dagger\) to some Bell state \(\left| \beta_{ij}\right>\), measure the system, and use information obtained from the observed state \(\left|ij\right>\) to infer \(\left| \beta_{ij}\right>\). This procedure can be generalized to make measurements in an arbitrary basis provided with a circuit that can implement the transformation of the classical basis to the desired one.

 In the figure below, a circuit for performing a measurement in the Bell basis is given along with the Bell measurement circuit to be interpreted as an equivalent circuit. Notice that this circuit before the measurements are performed is precisely the circuit that results from reversing the circuit for the construction of Bell sates. To construct the actual inverse of an arbitrary circuit not containing any measurements, simply reverse the order of the gates and replace each with its conjugate transpose. In the case of the circuit for measuring in the Bell basis, since \(H^\dagger=H\) and \(c-X^\dagger=c-X\), the circuit also happens to be the same circuit that results from merely reversing the order of the gates.

(A circuit for measuring in the Bell basis. This circuit takes some Bell state \(\left|\beta_{ij}\right>\) as input and applies a controlled\(-NOT\) gate \(c-X\) followed and a Hadamard gate \(H\) followed by a measurement to each each register to yield the corresponding computational basis state \(\left|ij\right>\). Shown below is the Bell measurement gate, which will be used as a shorthand symbol that represents the circuit shown above.)