1. Summary

• Definition (from Jack Hidary’s book): A quantum computer is a device that leverages specific properties described by quantum mechanics to perform computation.
• A quantum computer is not a parallel computer.
• Any quantum computation is described by a series of matrix multiplications.
• Not any matrix is permitted. The matrix has to be reversible plus there are other constraints as well imposed by laws of quantum physics.
• So the whole computation or circuit as it is called – just like we have a Boolean circuit in classical computing – can be reduced to a matrix operation known as the unitary matrix of the circuit denoted by U.
• The input to the circuit is a familiar bit string of n bits and output is also a n bit string. E.g., with n=4, example input: 0101 and example output: 1100.
• However, the output of a quantum circuit is not deterministic. A quantum circuit can put the bits into superposition and entanglement with the result that the output bit string is described by a joint probability distribution function ||Ψ||2. So there will be a ||Ψ0000||2 that gives the joint distribution of the output bits when input is 0000 and a different ||Ψ0001||2 that gives the joint distribution of output bits when input is 0001. Keeping the input fixed at 0000 if we make repeated measurements, we will get different outputs (e.g., in one measurement it can be 0011, in another measurement it can be 1010) whose frequency of occurrence will obey ||Ψ0000||2. Take a pause and let this sink in. Now we can see if we have nbits, there are total 2n possible outputs and so ||Ψ||2 for a given input is a real-valued vector of length 2n. And if we consider all the inputs, we get a matrix of order 2n × 2n. This matrix is nothing but ||𝑈||2. The ij entry in this matrix ||𝑈||2𝑖𝑗 is the probability that when the circuit is given input j, the output will be i.
• We can see from above that it becomes exponentially difficult to simluate the outcome of a quantum computer using a classical computer. That fact in itself provides a somewhat contrived use-case where quantum computers would outperform classical computers and is at the heart of Google’s Quantum Supremacy achievement.
• Given an input, if the joint probability distribution of output bits can be factored out into a multiplication of individual probabilities i.e., if ||Ψ||2=Π𝑖||𝜓𝑖||2 or taking an example of n=4 bits, if following holds ||Ψ||2=||𝜓𝑎||2⋅||𝜓𝑏||2⋅||𝜓𝑐||2⋅||𝜓𝑑||2. Stated in English we are saying that if the probability we will get an output of abcd – where each of a, b etc. is a 0 or 1 – is equal to the probability that the 0 bit is equal to d which we denote by ||𝜓𝑑||2 and further this number ||𝜓𝑑||2 doesn’t depend on what the other bits are, multiplied by the probability that the 1st bit is equal to c given by ||𝜓𝑐||2 and so on, then this corresponds to the case when there is no entanglement. So the definition of entanglement is a joint pdf that cannot be factored out. If there is no entanglement then we only need to store 2𝑛 numbers for the individual probabilities (0 or 1) of the n output bits to calculate ||Ψ||2 for a given input. But this case does not make for any interesting applications.
• Superposition is the process that puts a classical bit (a classical bit is a definite 0 or 1) into a quantum state when it is no longer a 0 or 1 but is simultaneously both with some probability. We call this a qubit. What does it mean physically? The spin of an electron is a good candidate for a qubit. Whenever we measure the spin, it is either up or down but before measurement it can be in a superposition of both up and down states. A classical bit is put in a superposition state by application of a Hadamard gate. The application of a Hadamard followed by a controlled not CNOT puts two bits into entanglement. We can see why. The CNOT gate takes two bits as input – one is a control bit and the other is a target bit. The CNOT gate will flip the target bit depending on whether the control bit is set. And the control bit itself is neither 0 or 1. Its in a superposition of the two states. That entangles the two bits as their fate is entertwined now.
• Superposition and entanglement are the essence of quantum physics.

2. An example: putting it all together

Install the Cirq library by following the steps at https://github.com/quantumlib/Cirq/blob/master/docs/install.md#installing-on-docker

docker pull quantumlib/cirq

Check it works

docker run -it quantumlib/cirq

 python -c "import cirq; print(cirq.google.Foxtail)"

 # should print:

 # (0, 0)───(0, 1)───(0, 2)───(0, 3)───(0, 4)───(0, 5)───(0, 6)───(0, 7)───(0, 8)───(0, 9)───(0, 10)

# │ │ │ │ │ │ │ │ │ │ │

 # │ │ │ │ │ │ │ │ │ │ │

 # (1, 0)───(1, 1)───(1, 2)───(1, 3)───(1, 4)───(1, 5)───(1, 6)───(1, 7)───(1, 8)───(1, 9)───(1, 10)

Run the image

docker run -it quantumlib/cirq

Create a random circuit of 4×4 qubits arranged in a grid. The code is from the book Quantum Computing by Jack Hidary. It uses the cirq.experiments.generate_supremacy_circuit_google_v2_grid method which is no longer available in latest version of cirq but is there in the version of cirq in the Docker image (as of this writing):

root@eb880b341bec:/examples# python Python 3.6.7 (default, Oct 22 2018, 11:32:17) [GCC 8.2.0] on linux Type "help", "copyright", "credits" or "license" for more information.

>>> import cirq

 >>> nrows=4

 >>> ncols=4

>>> depth=5

>>> supremacy_circuit=cirq.experiments.generate_supremacy_circuit_google_v2_grid(nrows, ncols, depth, seed=123)

 >>> print(supremacy_circuit)

 ┌──────┐ (0, 0): ───H───@───X^0.5─────────T───────@────────X^0.5───H─── │ │ (0, 1): ───H───@───X^0.5─────────@───────┼X^0.5───T───────H─── │ │ (0, 2): ───H───T─────────────────@───────┼@───────@───────H─── ││ │ (0, 3): ───H───T─────────────────────────┼┼───────@───────H─── ││ (1, 0): ───H───T───@─────────────Y^0.5───@┼───────@───────H─── │ │ │ (1, 1): ───H───T───┼──────────────────────┼───────@───────H─── │ │ (1, 2): ───H───@───┼────@────────X^0.5────@───────X^0.5───H─── │ │ │ (1, 3): ───H───@───┼────┼X^0.5───T────────────────────────H─── │ │ (2, 0): ───H───@───@────┼────────Y^0.5───T────────────────H─── │ │ (2, 1): ───H───@───X^0.5┼────────@───────@────────X^0.5───H─── │ │ │ (2, 2): ───H───T────────@────────@───────┼X^0.5───@───────H─── │ │ (2, 3): ───H───T─────────────────────────┼@───────@───────H─── ││ (3, 0): ───H───T─────────────────────────┼┼───────@───────H─── ││ │ (3, 1): ───H───T─────────────────────────@┼───────@───────H─── │ (3, 2): ───H───@───Y^0.5─────────T────────┼───────────────H─── │ │ (3, 3): ───H───@───X^0.5─────────T────────@───────X^0.5───H─── └──────┘

Increasing the depth of the circuit will expand it in the horizontal direction (i.e., more to the right) and insert more quantum gates. Let’s calculate the unitary of this circuit:

>>> U = cirq.unitary(supremacy_circuit)

 Killed

Oops! well, we have 16 qubits, meaning we are trying to calculate a matrix of 216 x 216 complex numbers. This will take total

>>> import math

>>> a=math.pow(2,16)

 >>> a*a*2*4 34359738368.0

bytes (this is 34GB in case you missed it) assuming each real number is stored as 4 byte float. So we can see its very difficult for classical computers to simulate what we will get from a quantum computer.

Let’s reduce the circuit to 3×3 qubits and try again

>>> import cirq

 >>> nrows=3

>>> ncols=3

 >>> depth=5

>>> supremacy_circuit=cirq.experiments.generate_supremacy_circuit_google_v2_grid(nrows, ncols, depth, seed=123)

 >>> print(supremacy_circuit)

 (0, 0): ───H───@───X^0.5────T───────@────────────X^0.5───H─── │ │ (0, 1): ───H───@───X^0.5────@───────┼────Y^0.5───T───────H─── │ │ (0, 2): ───H───T────────────@───────┼────@───────X^0.5───H─── │ │ (1, 0): ───H───T───@────────X^0.5───@────┼───────@───────H─── │ │ │ (1, 1): ───H───T───┼─────────────────────┼───────@───────H─── │ │ (1, 2): ───H───T───┼────@───Y^0.5────────@───────X^0.5───H─── │ │ (2, 0): ───H───@───@────┼───X^0.5───T────────────────────H─── │ │ (2, 1): ───H───@───X^0.5┼───@───────X^0.5────────T───────H─── │ │ (2, 2): ───H───T────────@───@───────Y^0.5────────T───────H───

Ready to calculate unitary? Try it:

>>> U=cirq.unitary(supremacy_circuit)

 >>> import numpy

 >>> numpy.shape(U) (512, 512)

Let’s see Ψ0 – the wave function when input to the circuit is 000000000 (remember we have 3×3 or 9 qubits). Its a complex valued vector. The first 3 elements are shown:

>>> psi_0 = U[:,0]

 >>> psi_0[0:3]

 array([-0.00457646-0.02209709j, -0.03772209-0.00457646j,
-0.05334709-0.03314563j])

Measuring the circuit will collapse the wave function to a definite state and the probabilities of getting 000000000, 000000001, 000000010, 000000011 and so on in the output will be given by the square of the modulus (also known asamplitude) of the complex numbers. We can calculate it like this

>>> prob = numpy.square(numpy.abs(psi_0))

Verify

>>> numpy.sum(prob)

 1.0000000000000018

Let’s take a random entry in the matrix U

>>> U[45,33]

 (-0.06897208691207966+0.03772208691207965j)

What does this entry mean? It means that if this circuit is fed an input of

>>> "{0:09b}".format(33)

 '000100001'

the output will be

>>> "{0:09b}".format(45)

 '000101101'

with a probability

>>> numpy.square(numpy.abs(U[45,33]))

 0.006180104614009962

Google’s quantum supremacy experiment generated a random circuit of 𝑛×𝑛 qubits. They then keep the input fixed at 000⋅⋅⋅000 and sample the output of the circuit many times. The results from sampling the output are used to create a pdf which is then verified against the expected pdf calculated using a classical computer. This tells them that the quantum circuit is behaving correctly. They slowly increase n until they reach a point (n=52) where calculation of expected pdf using a classical computer becomes infeasible – the moment of quantum supremacy.

One can see that one natural application of quantum computers will be to generate truly random numbers. This corresponds to a wave function where each ||𝜓𝑖||2=𝑐𝑜𝑛𝑠𝑡𝑎𝑛𝑡 corresponding to a uniform pdf.

There are two challenges in quantum computing: One is that keeping the qubits entangled and superimposed becomes very difficult as the number of bits and the depth of the circuit increases. This is the hardware challenge and this is what Google accomplished with their recent results on quantum supremacy. The other is finding problems that can be expressed as quantum computations – where quantum computing can outperform classical computing. This is the software challenge. The famous example is Shor’s factorization algorithm which can be used to break RSA cryptography that forms the backbone of secure communications between computers today, but it will take sometime for it to become practical since the number of qubits it requires is outside what today’s quantum computers can provide.