Skip to main content

Quantum Class 6, Thurs 2020-09-17

Source

2 Useful books

A student recommended these two books to the class.

  1. Quantum Computing: An Applied Approach by Jack Hidary

  2. Quantum Computation and Quantum Information by Nielsen and Chuang

The first book is more relevant to the class because it has more hands on examples. The second book is good for more theoretical information on the topic, but is still really interesting.

3 More on No Cloning

I made some supplementary material on cloning (copying), which works in the classical world but not in the quantum world.

Classically, you can easily clone a bit. Consider a 2-bit system, $x, y$. Represent the state with a 4-vector

$s=\begin{vmatrix} a_0\\a_1\\a_2\\a_3\end{vmatrix}$

where exactly one $a_i=1$ and the other three are 0. E.g., if $a_3=1$ then $x=y=1$.

Here's a 2-input, 2-output circuit that clones the first bit.

$x'=x\\y'=x$

Its truth table is

x y | x'y'
0 0 | 0 0
0 1 | 0 0
1 0 | 1 1
1 1 | 1 1

The matrix M is:

1 1 0 0
0 0 0 0
0 0 0 0
0 0 1 1

That is, the final state is $s' = \sum_j M_{ij} b_j$

However, M is singular. So this is not a legal quantum circuit. Let's try again.

The better way is the 3-input Toffoli gate in Figure 5.66 on page 156. The function is

$x'=x \\ y'=y \\ z'= z \oplus xy$

The truth table is

x y z | x'y'z'
0 0 0 | 0 0 0
0 0 1 | 0 0 1
0 1 0 | 0 1 0
0 1 1 | 0 1 1
1 0 0 | 1 0 0
1 0 1 | 1 0 1
1 1 0 | 1 1 1
1 1 1 | 1 1 0

The matrix is Eqn 5.62 on page 155.:

1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 0

Let x=1, z=0. Then:

x'= 1
y'= y
z'= y

and we've cloned y in the classical case.

This matrix is nonsingular and so is legal in a quantum circuit.

Try $y= \frac{1}{\sqrt{2}} | 0> + \frac{1}{\sqrt{2}} | 1>$. Using x=1, z=0, the input will be

$\frac{ | 1, 0, 0> + | 1, 1, 0>}{\sqrt{2}}$

and the state is

$(0, 0, 0, 0, \frac{1}{\sqrt{2}} , 0, \frac{1}{\sqrt{2}} , 0)^T$

Multiplying that by the matrix gives

$\frac{ | 1, 0, 0> + | 1, 1, 1>}{\sqrt{2}}$

Instead of cloning y into z, this entangled y and z.

This isn't new; we already know how to engangle two qbits.

Engangling isn't the same as cloning. The point of cloning is that we could operate on the two bits separately. If they're engangled, operating on one affects the other.

4 Chapter 6, Algorithms of Quantum Computing for Computer Scientists

Today's big new stuff.

As usual, I'm typing the important points into this blog, together with my observations and opinions.

The algorithms are all searching for an answer. (An alternative is algorithms that compute something, like inverting a matrix.)

For these examples, the quantum algorithm is quite different from the classical algorithm, and is asymptotically faster.

Current research is deciding what algorithms can be made faster.

p 172: Any function can be made invertible by adding a control bit.

4.1 Deutsch

  1. We have a black box F(x) -> x'.

  2. We're told that F is either balanced or constant.

  3. How to determine which?

  4. We can input any x and see the result.

  5. Classically: eval F(0) and F(1).

  6. That took two evals and some comparisons.

  7. All that matters is the number of evals. We assume that they're slower than everything else.

  8. Quantumly (quantumicly?) we can determine which type F is with only one eval plus some extra matrices.

4.2 Deutsch - Jozsa

Now $F: \{0,1\}^n \to \{0,1\}$.

We're told that it's either constant or balanced. It's not neither.

Which is it?

Classically, we need n/2+1 evals of F.

Quantumly, we need only 1.

4.3 Simon's periodicity

Blackbox $F: \{0,1\}^n \to \{0,1\}^n$

For some unknown $c$, $F(x\oplus c) = F(x)$.

Determine $c$.