An algorithm is an outline of logical steps that will solve a specific problem. A protocol is a series of ground rules for any sort of communication involving multiple parties. Quantum protocols and algorithms make use of the two most characteristic features of quantum mechanics, entanglement and superposition, to establish communication and solve problems much more efficiently than classical computers ever could.
Firstly, we need to know how to classify entanglement. Let’s consider the following two states.
$$ \begin{align*}\ket{\Psi^-}&=\frac {1}{\sqrt 2}(\ket {01}-\ket {10})\\ \ket \psi &= \frac{3}{2\sqrt2} \ket {00} + \frac{3}{2\sqrt2}\ket {01} +\frac{\sqrt3}{4} \ket {10} +\frac{1}{4} \ket {11} \end{align*} $$
The first state is one of the Bell states, which we know is entangled. We can check whether the second state is separable (unentangled) using the following property.
$$ \begin{align*}\ket q_1\otimes\ket q_2&=c_0\hat c_0\ket0_1\ket0_2+c_0\hat c_1\ket0_1\ket1_2+c_1\hat c_0\ket1_1\ket0_2+c_1\hat c_1\ket1_1\ket1_2\\ &=\blue{c_0\hat c_0}\ket{00}+\red{c_0\hat c_1}\ket{01}+\red{c_1\hat c_0}\ket{10}+\blue{c_1\hat c_1}\ket{11}\\\\
\blue{c_0\hat c_0}(\blue{c_1\hat c_1})&=\red{c_0\hat c_1}(\red{c_1\hat c_0})=c_0c_1\hat c_0\hat c_1 \end{align*} $$
$$ \begin{align*}\ket \psi &= \frac{3}{2\sqrt2} \ket {00} + \frac{3}{2\sqrt2}\ket {01} +\frac{\sqrt3}{4} \ket {10} +\frac{1}{4} \ket {11} \\\frac{3}{2\sqrt2}\left(\frac{1}{4}\right)&\neq\frac{3}{2\sqrt2}\left(\frac{\sqrt3}{4}\right)\end{align*} $$
Therefore, we know that the second state is, in fact, also entangled. However, there is a major difference between the two. For example, suppose we measured the left qubit as $\ket 0$. The resulting states are
$$ \begin{align*}\ket{\Psi^-}&=\ket {01}\\ \ket \psi &= \frac{1}{\sqrt2} (\ket {00} +\ket {01}) \end{align*} $$
In the case of $\ket {\Psi^-}$, we know that the second qubit must now be in the state $\ket 1$. But in the case of $\ket \psi$, we know merely that the second qubit will be either in state $\ket 0$ or $\ket 1$ with a fifty-fifty probability. We would call the first original state maximally entangled and the second partially entangled.
Definition:
When one qubit in a maximally entangled state is measured, the outcome uniquely determines the state of the second qubit. All Bell states represent maximum entanglement.
When one qubit in a partially entangled state is measured, the outcome determines a superposition in which the second qubit now is.
The first quantum protocol we will look at is super-dense coding, with which we can communicate bits of classical information using a smaller number of qubits.
Let’s suppose that the sender, Alice, is choosing between four options and wants to convey her decision to the receiver, Bob. For example, Bob is asking Alice what her favorite ice cream flavor is. Previously, they both agreed that $00$ means chocolate, $01$ means vanilla, $10$ means strawberry, and $11$ means pistachio. Classically, Alice would need two bits to communicate one of the four options $00, 01, 10, 11$. But by using quantum mechanics we can do better.
<aside> 💡 Holevo’s theorem tells us that n number of qubits can store only n bits of information. Therefore, Alice will need two qubits for communicating her decision. However, super-dense coding allows her to do so by sending only one qubit to Bob.
</aside>
The protocol goes as follows, Alice and Bob each have one qubit from the maximally entangled Bell state $\ket {\Phi^+}={1}/{\sqrt 2}(\ket {00}+\ket {11})$.
If Alice wants to answer $00$, she does nothing to her qubit and simply sends it over to Bob. Bob, who now has both qubits, then does the Bell measurement, which consists of CNOT, followed by Hadamard on Alice’s qubit and a measurement along the z-axis.
$$ \ket {\Phi^+}=\frac{1}{\sqrt 2}(\ket {00}+\ket {11})\stackrel{CNOT}{\longrightarrow}\frac{1}{\sqrt 2}(\ket {00}+\ket {10})=\ket+\ket 0\stackrel{H\otimes I}{\longrightarrow}\ket 0\ket 0 $$
Where the left qubit belongs to Alice and the right one to Bob.
If Alice wants to answer $01$, she first applies the X gate on her qubit and then sends it to Bob, who again does the Bell measurement.
$$ \ket {\Phi^+}=\frac{1}{\sqrt 2}(\ket {00}+\ket {11})\stackrel{X\otimes I}{\longrightarrow}\ket {\Psi^+}=\frac{1}{\sqrt 2}(\ket {10}+\ket {01})=\frac{1}{\sqrt 2}(\ket {01}+\ket {10})\stackrel{CNOT}{\longrightarrow}\frac{1}{\sqrt 2}(\ket {01}+\ket {11})=\ket+\ket 1\stackrel{H\otimes I}{\longrightarrow}\ket 0\ket 1 $$
If Alice wants to answer $10$, she applies the Z gate to her qubit and then sends it to Bob, who does the Bell measurement.
$$ \ket {\Phi^+}=\frac{1}{\sqrt 2}(\ket {00}+\ket {11})\stackrel{Z\otimes I}{\longrightarrow}\ket {\Phi^-}=\frac{1}{\sqrt 2}(\ket {00}-\ket {11})\stackrel{CNOT}{\longrightarrow}\frac{1}{\sqrt 2}(\ket {00}-\ket {10})=\ket-\ket 0\stackrel{H\otimes I}{\longrightarrow}\ket 1\ket 0 $$
And finally, if Alice wants to answer $11$, she acts on her qubit with the X gate followed by the Z gate and sends it to Bob, who does the Bell measurement.
$$ \ket {\Phi^+}=\frac{1}{\sqrt 2}(\ket {00}+\ket {11})\stackrel{X\otimes I}{\longrightarrow}\frac{1}{\sqrt 2}(\ket {10}+\ket {01})=\frac{1}{\sqrt 2}(\ket {01}+\ket {10})\stackrel{Z\otimes I}{\longrightarrow}\ket {\Psi^-}=\frac{1}{\sqrt 2}(\ket {01}-\ket {10})\stackrel{CNOT}{\longrightarrow}\frac{1}{\sqrt 2}(\ket {01}-\ket {11})=\ket-\ket 1\stackrel{H\otimes I}{\longrightarrow}\ket 1\ket 1 $$