1. A recipe for solving a computational problem is called an algorithm. In order to compare the speed of classical and quantum algorithms, we need a way of counting computational steps for classical and quantum algorithms that is fair to compare.
2. How many steps an algorithm needs depends on whether it receives an easy or hard instance of the problem. Typically we are interested in algorithms that work the best on average. Another issue is that for the algorithms that we do know, we don't usually know if they are the best that we can do (you can sometimes prove a classical algorithm is optimal by using lower-bound arguments). So here we are really comparing quantum methods with best as-of-yet classical methods. Put differently, it maybe the case (though many believe it unlikely) that classical and quantum computers have the same computational power; we just have not found the best classical algorithms that match the performance of quantum ones.
Here I will describe a problem for which quantum computers have a distinct advantage over classical ones. It is an example of what is called a black-box problem in computer science.
To explain what a black-box problem is like, consider a game where you have to guess what animal I am thinking about. To help you guess, you are allowed to ask me yes-no questions. In this analogy, the game is like a computational problem and the animal represents the answer to this problem. Your questions correspond to inputs of a function and I serve as a black box that computes this function for you. The number of times you ask me a question is the number of queries made to the black box, which counts as the number of steps in a computation.
Black-box problems seem rather artificial since we are given access to functions that are computed "magically in one step" but they are convenient theoretical constructs that allow us to compare the performance of classical and quantum algorithms. Here we will consider a problem formulated by Daniel Simon in 1994, which resembles a quite natural real-world problem.
In Simon's problem, you are given access to a black box which computes a function f whose input and output is n bits. There is a promise that whenever $f(x) = f(y)$ for some pair of inputs $x$ and $y$, then either $x = y$ or $x \oplus y$ = p (recall that the XOR of $x$ and $y$ or $x \oplus y$ means we take each corresponding bit and add them, but with $1+1=0$, e.g., $0101 \oplus 1100 = 1001$.) Here $p$ is called the period of $f$. The goal is to find $p$.
Intuitively this is a very hard problem classically since you would need to find two different inputs $x$ and $y$ for which $f(x) = f(y)$, but there is nothing we know about $f$ that will help us find such a pair more easily than just randomly picking $x$ and $y$.
From what is called the birthday attack, if a function has $m$ possible values that are equally likely, then we can expect to find two inputs $x$ and $y$ such that $f(x) =f(y)$ if we evaluate $f$ for random inputs about $1.25\sqrt{m}$ times. This means that any classical algorithm for solving Simon's problem for an $n$-bit function, which has $2^{n}$ possible output values,
will require checking around $\sqrt{2^{n}}$ inputs.
It is not too difficult to show how to solve the problem quantumly for an arbitrary function on n bits but to be more explicit in our calculations, we consider the example of a function $f$ on 3 bits where $f(x) = f(y)$ for $x \oplus y = 001 = p$. For completeness, let us suppose that $f(000) = 101, f(010) = 111, (f100) = 011$, and $f(110) = 010$. Actually it does not matter what the values for $f$ we get for these inputs; only the period $p$ matters for the algorithm.
 |
An efficient quantum algorithm for solving Simon's problem. The top 3 qubits form the input register and the bottom 3 form the output register. The box labeled f is a quantum black box for the 3-qubit function. The box with a metered scale denotes a measurement of a qubit in the $\{|0\rangle , |1\rangle \}$-basis.
|
The figure above shows the circuit for Simon's algorithm on our 3-bit function $f$. Recall that the Hadmard gate is the qubit unitary gate which takes $|0 \rangle$ to $|+\rangle = ( |0\rangle + |1\rangle) / \sqrt{2}$ and $|1\rangle$ to $|-\rangle = ( |0\rangle - |1\rangle) / \sqrt{2}$. Notice also that a quantum black box works by having separate registers for the input (say its value is $x$) and output qubits (pre-assigned to some value $v$) and the black box acts on both registers simultaneously before returning the input $x$ and final output $v \oplus f(x)$, i.e., it takes
$|x\rangle |v\rangle$ to $|x\rangle |v \oplus f(x)\rangle$
To see how the quantum state evolves from left to right in the quantum circuit, we will write the qubits for the input and output registers separately. The initial state is
$|000 \rangle |000 \rangle$.
After applying Hadamard gates to the input qubits, we get
$|+++\rangle |000\rangle $.
After querying the quantum black box,
$[ |00+\rangle |101 \rangle + |01+ \rangle |111\rangle + |10+ \rangle |011\rangle + |11+\rangle |010\rangle ]/2$,
where the output values follow from how we defined $f$ in the above.
After the second application of Hadamard gates on the input qubits, we have
$[ |++0\rangle |101\rangle + |+-0 \rangle|111\rangle + |-+0\rangle |011\rangle + |--0\rangle |010\rangle ]/2$.
After measuring the output qubits in the $\{|0\rangle , |1\rangle \}$-basis,
$|++0 \rangle |101 \rangle$ or $|+-0 \rangle|111\rangle$ or $|-+0\rangle|011\rangle$ or $|--0\rangle|010\rangle$,
each with probability 25%.
After measuring the input qubits in the $\{|0\rangle , |1\rangle \}$-basis, we get
$|000\rangle$ or $|010\rangle$ or |$100\rangle$ or $|110\rangle$
from the input qubits, each with probability 25%.
This means that if we run the algorithm a few times, it returns 3 bits such that the first 2 bits could be anything but the third bit is always 0. More precisely, if the algorithm returns the value z then we always get some z such that
$z \cdot p = 0$,
that is, the product of each bit of $z$ with each bit of the period $b$ is 0.
This gives us a simple way of finding $f$: run the algorithm a few times until we get enough $z$ values to solve for all the bits of the period $p$.
We showed the calculation for a particular function $f$ but the algorithm works in a similar fashion for any arbitrary function $f$ on bits with period $p$:
(i) apply Hadamard gates to the input qubits
(ii) query the quantum black box using all the qubits
(iii) apply Hadamard gates to the output qubits
(iv) measure the input qubits in the $\{|0\rangle , |1\rangle \}$-basis.
The input register qubits yields a bit-string value whose bit-wise product with the period is 0 for all corresponding pairs of bits.
We get random values for $z$ so there is no fixed number of times we need to repeat the circuit to get $p$. However, it can be shown that if $f$ is a function on $n$ bits, then the probability we can solve for $p$ exactly after $n$ repetitions of the circuit is bigger than 25%. This means we can almost always find the period just by always repeating the circuit $4n$ times for any function on $n$ bits.
Therefore comparing the best classical algorithm, which would need $\sqrt{2^{n}}$ queries to a black box for the $n$-bit function $f$, and this quantum algorithm, which requires a small multiple of $n$, we see a big computational speed-up.
For comparison, the classical and quantum algorithms require about the same number of steps for $n=10$ but for $n = 20$, we have $1.25\sqrt{2^{20}} = 1280$, so the classical algorithm needs more than 60 times the number of quantum queries.
We have seen a quantum speed-up but it works for an artificial problem so how significant is it really in real-world terms? Well, it turns out that the problem of prime number factorization, which is believed to be a hard problem for classical computers to solve, can be solved if one can find the period of a function for integers. This is a slightly more complicated problem that one involving bit-strings but it can be solved by a quantum circuit with a structure similar to Simon's algorithm. We know this as Shor's algorithm.
Many of today's practical crypto-systems are secure if we are correct in assuming that certain computational problems are hard even for the fastest PCs. But Shor's algorithm has shown us that some hard problems might not be so hard at all, given the right quantum technology.
References:
Dave Bacon, Simon's Algorithm (2006).
John Watrous, Simon's algorithm (2006).
No comments:
Post a Comment