If computers that you build are quantum
then spies everywhere will all want ‘em.
Our codes will all fail
and they’ll read our email,
till we get crypto that’s quantum, and daunt ‘em
- Jennifer and Peter Shor

This first subunit involves a brief introduction to QIS: quantum information science. An introduction to the big ideas of quantum information and quantum computing serves to motivate the upcoming topics. Some discussion of the "hype" vs realities of QIS might be in order here. A little background in classical computers may be relevant (note that some are discussed in the "Parts of a computer" section below)

Classical computers store, process, and manipulate bits (characterized abstractly as 0 or 1). Current optimal algorithms for factoring large numbers take time that grows exponentially with the size of the number to be factored, and current commercial encryption takes advantage of that fact. If one were to have functioning quantum computers that could store and manipulate quantum bits (i.e., superpositions of 0 and 1 - which we will discuss shortly), there exists an algorithm (Shor's) that could "decrypt" current common protocols exponentially faster. This has generated excitement and hype, and there are major efforts in industry and academia to construct such machines and develop new algorithms. A key aspect of quantum computing is the concept of "basis size" - for a 4-bit quantum computer, a given stored qubit can be a superposition of up to $2^4 = 16$ basis states. In some sense, this represents exponentially more information in a single qubit than the 4 bits a classical computer stores. 

This is a (brief) introduction to qubits (including Dirac notation) and superposition. For students with a with a physics background, this is intended to make the quick shift from more general quantum observables to 0's and 1's. 

Classical computers work with bits, denoted by states 0 or 1. The physical implementation of those bits is rather arbitrary (typically low and high voltage on a wire), but for many practical computing purposes also irrelevant. The same will be true for quantum computers, but now the qubit can be in any superposition state $a\ket{0} + b\ket{1}$. 

Classical computing requires gates: operators that act on a bit (one or more) and output a resulting bit. The "Not" gate is the simplest single-bit gate: inputing a 0 yields a 1 and vice versa. This can also be thought of as a logic operation (interpret 0 = "false" and 1 = "true") The "And" gate acts on 2 inputs and returns a single output, the logical "And" operation.

Quantum gates similarly take input states, act on them, and produce output states. The final stage of a set of quantum operations will ultimately be a measurement, but the sequential operations should not make any measurements (indeed, avoiding such collapse of the quantum superposition state is a major engineering challenge at the moment). Schematically, the process can be thought of schematically like this:

Much current physics and engineering research is devoted to studying how to physical implement qubits - examples include spin-1/2 systems where 0 and 1 represent "up" and "down" spin in the Z direction, and certain gates could involve applied magnetic fields (for instance), but the states could also be photon polarization, energy levels of trapped atoms,  current in Josephson junctions, or many more. For discussing gates and algorithms, just as with classical bits, this physical implementation is not essential. 

A quantum gate is an operation performed on qubits.  Mathematically, gates are associated with unitary and linear operators. Linear means e.g. $Z(a\ket{0} + b\ket{1}) = aZ\ket{0} + bZ\ket{1}$. Thus, one way to define them is by their operation on computational basis states.

• $X$-gates: $X\ket{0} = \ket{1}, \ \ X\ket{1}=\ket{0}$. 
  (The $X$-gate is a 'bit flip' or NOT gate: taking $\ket{0}$ to $\ket{1}$, and vice versa. )
• $Z$-gates: $Z\ket{0} = \ket{0}, \ \ Z\ket{1}=-\ket{1}$. 
  The $Z$-gate  is thus sometimes called a "phase gate" (flipping the phase of $\ket{1}$ states.)  
• $Y$-gates: $Y\ket{0} = -i \ket{1}, \ \ Y\ket{1}=i\ket{0}$. 
  The $Y$-gate is thus a combination of the previous two ($Y = iZX$).
• Identity ($I$): $I\ket{0} = \ket{0}, \ \ I\ket{1}=\ket{1}$.
  The identity operator $I$ does not alter input states in any way. 
• Hadamard gates: 
  $H \ket{0} = \frac{1}{\sqrt{2}} ( \ket{0} + \ket{1}) \;\; \text{ and } H\ket{1} = \frac{1}{\sqrt{2}} ( \ket{0} - \ket{1})$.
  The Hadamard is a common and useful gate in quantum computing algorithms -  it converts pure computational states into superposition states.

Note that $ XX = YY = ZZ = H H = I$, and that order matters, e.g. $X$ does not commute with $Z$. 

A natural follow-up is to ask the same question for $H\ket{0}$. These questions provide elementary practice and serve as conversation starters. $H$ plays a huge role in algorithms: often the first step is to start with a bunch of $\ket{0}$ states, then act $H$ on each to get a collection of superposition states.

Circuit diagrams use lines to indicate individual qubits and boxes to indicate quantum gates.  They are read from left to right.  The following diagram depicts the equation: $\ket{\psi}_{out} = X Z \ket{\psi_{out}}$. 

Note how the equation looks "backwards" compared to the circuit, but it is clear in both that the $Z$ gate acts first.  We can also depict a measurement by using a symbol of a "meter" as shown below (note that different textbooks often have different conventions for a measurement symbol).

When we add additional qubits, they are shown as additional lines where the top line is understood to be the first qubit.  The circuit diagram below shows the output for the first qubit is $ZH\ket{0}$ and the output of the second qubit is $X\ket{1}$.

When moving to N-qubit systems, the dimensionality of your basis grows as $2^N$. Here we briefly introduce students to the ideas of combining two single particle states into a larger-dimensional 2-qubit state, and how to represent this in Dirac (or matrix) notation, using the language of tensor products.  

There is only so much that can be done with a single qubit.  To add a second qubit, we use the tensor product $\otimes$.  If the first qubit is in the state $\ket{0}$ and the second qubit is in the state $\ket{1}$, then the two-qubit state can be written as $\ket{0} \otimes \ket{1}$.  There are several shorthand ways to write this.  Below are all equivalent formulations:

$ \ket{0} \otimes \ket{1} = \ket{0} \ket{1} = \ket{01}$

For brevity, the last one is most commonly used unless it is important to emphasize the states of the individual qubits, in which case the $\otimes$ symbol will be used. 

When dealing with 2-particle systems,  2-qubit operations can (sometimes) be described as a tensor product of operators (e.g., $\hat{A}\otimes\hat{B}$), and can (always) be represented by a 4x4 matrix in the 4-d two-qubit Hilbert space.   

For example, in the circuit below, the first set of gates can be written as a tensor product: $H \otimes Z$, but based on the information we have, the second gate $U$ cannot be broken down into a separate gate on each qubit.

Mathematically, the circuit is represented as:

$ U(H\otimes Z) (\ket{\psi_A} \otimes \ket{\psi_B}) = U ( H\ket{\psi_A} \otimes Z\ket{\psi_B})$

Two (or more) particle quantum systems can exhibit interesting correlations (entanglement) stronger than any classical system. 

A state is entangled when it cannot be written as a single tensor product of two single-qubit states.  

For example, consider the state $\tfrac{1}{\sqrt{2}}(\ket{00} + \ket{01})$. This state is NOT entangled, because we can 'factor' it into $\ket{0} \otimes \tfrac{1}{\sqrt{2}}(\ket{0} + \ket{1})$.  In this case the first qubit is in the state $\ket{0}$ and the second state is in the state $\tfrac{1}{\sqrt{2}}(\ket{0} + \ket{1})$.  

In contract, we can look at the entangled state $\tfrac{1}{\sqrt{2}}(\ket{00} + \ket{11})$.  There is no way to write a ket for the first or second qubit on their own.  The state must be written together. 

Note: It is possible to describe the first qubit using a reduced density operator.  The state of the first qubit would be the completely mixed state $\rho_1 = \frac{1}{2}\mqty( 1 & 0 \\ 0 & 1)$.  

Second note: Entanglement has some interesting properties and consequences. We won't get into them in this module, but more information can be found in module "Entanglement and EPR".

In order to have a quantum computer, we need gates that act not only on one qubit, but gates that work on multiple qubits.  More specifically, we need gates that will "entangle" two qubits.  The most common gate of this type is called the CNOT, or controlled-NOT gate.  It does exactly as the name suggests: performs a NOT gate controlled by another qubit.  The following is the circuit diagram for a CNOT gate:

The solid black dot on the top 'wire' indicates that this is the control qubit. The gate on the second qubit will be performed only if the control qubit is a 1. (This has interesting effects for superposition states, as we see in the clicker questions below!) 

We can define how the CNOT gate acts on the four 2-qubit computational basis states:

$$ CNOT\ket{00} = \ket{00} \;\;\;\; CNOT\ket{01} = \ket{01}$$

$$ CNOT\ket{10} = \ket{11} \;\;\;\; CNOT\ket{11} = \ket{10}$$

We can use the CNOT to entangle two independent qubits as in the circuit in the clicker question example below.

The one-time pad is a perfectly secure way to encrypt information.  In this protocol, both parties must share a secret key.  The one-time pad security relies on the fact that this key is truly secret (no one else has access to it) and that it is only used a single time (hence the name ``one-time''). The secret key must be at least as long as the message (no portion of the key should be repeated).

If Alice wishes to send a message to Bob, Alice will take the message and add the secret key to obtain the cyphertext (the encoded message). In the case of a binary message and a binary key, this would be addition mod 2.  

$ \text{message} \oplus \text{key} = \text{cyphertext} $

In mod 2, Bob will just need to do $\text{cyphertext} \oplus \text{ key} = \text{message}$ to decode the cyphertext.

We will often do examples using the english alphabet, in which the addition will be modulo 26.  In this case, to decode the cyphertext you will need to ${\it subtract}$ the key (mod 26) to obtain the message. 

In all QKD protocols, it is an important assumption that an eavesdropper cannot copy (or clone) an unknown quantum state. The proof (by contradiction) is relatively straightforward:

Assume you have a 'cloning machine'.  Such a machine would take an unknown state $\ket{\psi}$ and a blank state (let's call it $\ket{b}$) and turn it into two copies of $\ket{\psi}$.  Mathematically, we write it as:  $U_{clone} (\ket{\psi} \otimes \ket{b}) = \ket{\psi} \otimes \ket{\psi} $

Since we want to be able to clone an arbitrary state, the cloning machine should also work if we input the state $\ket{\phi}$:  $U_{clone} (\ket{\phi} \otimes \ket{b}) = \ket{\phi} \otimes \ket{\phi} $

We want to take the inner product of the two equations: 

$$ [ ( \bra{\psi} \otimes \ket{b} ) U_{clone}^\dagger ] [U_{clone} ( \ket{\psi} \otimes \ket{b} ) ] = [ \bra{\phi} \otimes \bra{\phi} ] [ \ket{\psi} \otimes \ket{\psi} ]  \label{cloneeqn}$$

• $U_{clone}^\dagger U_{clone} = 1$ since $U$ is unitary
• Make sure to take the inner product of qubit 1 (from eqn 1) with qubit 1 (from eqn 2) and then for qubit 2 (from eqn 1) with qubit 2 (from eqn 2)

Then we have that:

$ \ip{\phi}{\psi} \ip{b}{b} = \ip{\phi}{\psi} \ip{\phi}{\psi} $

$ \ip{\phi}{\psi} = \ip{\phi}{\psi}^2$

This is only true if $\ip{\phi}{\psi}$ is equal to 1 or 0.  Meaning the cloning machine will only work for states that are identical or orthogonal.  In other words, you can build a cloning machine, but it will only clone a set of basis states, not an arbitrary superposition of those basis states.

This is one of the more common QKD protocols and is perfect for use in intro quantum mechanics classes as it only requires knowledge of two-level superposition states and the results of measurements.  

In our example, we will use spin-1/2 particles, and we will discuss measurements of spin in the $x$ and $z$ directions.  

Players:
     Alice - Wants to share a secret key with Bob.  She sends qubits to Bob, randomizing what she ends. 
     Bob - Wants to share a secret key with Alice.  Bob receives the qubits sent by Alice and will measure them in a randomly chosen basis.
     Eve - An eavesdropper who wants to gain information about the secret key without being detected.  She will intercept the qubits that Alice sends to Bob and make measurements before sending the qubit on to Bob.

The Protocol: The following steps can be recorded in the handout (available for download below).

1. Alice sends qubits to Bob in either the X or the Z basis.  She randomly sends one of
   $ \ket{\psi_{0z}}=\ket{0} \;\;\quad \quad \ket{\psi_{0x}}= \ket{+} = \frac{1}{\sqrt{2}}(\ket{0} + \ket{1}) $
   $ \ket{\psi_{1z}}=\ket{1} \;\;\quad \quad \ket{\psi_{1x}}= \ket{-} = \frac{1}{\sqrt{2}}(\ket{0} - \ket{1}) $
   Alice records the basis she sent (X or Z) and whether she sent the (0 or 1) for each basis.  The sequence of 0s and 1s will turn into the secret key.
2. Bob receives the qubits and makes a measurement.  He randomly chooses to measure in either the Z or the X basis and records the results (0 or 1) and the basis he chose (X or Z).
3. Alice and Bob reveal the basis they sent or measured.  They do this publically.  They will throw away all elements of their key (the 0s and 1s) where their basis choice did not match.
4. Test for an eavesdropper: Once Alice and Bob have the remaining key, it should match perfectly.  The only reason their keys might differ is if there was an eavesdropper messing things up or if there was some decoherence in their qubit channel.  They select a portion of their key to compare publically (they will then need to throw away these elements of the key as they are no longer secret).  If that portion of their keys is identical, they can feel confident that the rest of their key also matches.  If their keys are not identical, they do not have confidence in the rest of their key and will abandon the protocol and start again.  

In reality, anything can happen to the qubit as it travels from Alice to Bob. We are going to assume the worst: that a very powerful and quantum-savvy enemy has intercepted the qubit and knows enough of the protocol to make the best measurements they can before sending the qubit to Bob.

Here is the best that an eavesdropper can do:

• Measure the intercepted qubit in either the X or Z basis.  Record everything.
• Send the resulting qubit to Bob.

You can follow along in the handout to see the repercussions of this interception.  In short:

• Eve will randomly pick the "right" basis to measure in 50% of the time.  When she does this, the state she sends to Bob will be unchanged from what Alice sent.  In these instances, she is undetectable.
• The other 50% of the time, Eve will select the "wrong" basis (the basis that is opposite to what Alice sent). In these instances, by chance, Eve will get the same key value as Alice 50% of the time and get an opposing value 50% of the time.
• Altogether, Eve has a 25% chance of messing up each qubit that gets sent to Bob.

If Alice and Bob did not test for the presence of an eavesdropper, even with an error rate of 25%, Eve would certainly gain valuable information if Alice and Bob tried to use their "secret" key to encode a message.