Today on the arXiv a paper appeared, written by Lara Tatli and me. The paper is on solving Diophantine equations on a quantum computer using Grover's algorithm.
The project started last summer when Lara (an undergraduate physics student at Durham) got in touch to ask if she could do a summer project with me. I had an idea to use a quantum search algorithm to find roots of equations in a more efficient way than a classical algorithm might, and I suggested to her we could start looking at that. My initial idea was very vague but I thought perhaps we could encode floating point numbers in an interesting way search for values of x which solve f(x)=0 for some hopefully interesting functions. This "root finding" is a common basic tool of numerical analysis and many problems can be formualted this way.
When looking at how to encode the numbers on a quantum computer, it became clear that starting from the simplest case - where the numbers are just straight binary representations of integers - would be the easiest place to start, but still interesting enough. Equations where the numbers can only take on integer values are called Diophantine equations after Diophantus of Alexandria who studied them in the 3rd century. The standard definition of Diophantine equations has them acting in at least two variables, and a simple example is finding all the Pythagorean Triples - the set of right-angled triangles with integer sides. The basic example there is {3,4,5} since these integers satisfy Pythagoras' theorem 32+42=52. There are an infinite number of solutions of the equation x2+y2=z2 where x,y,z are all positive integers. Fermat's Last theorem famously states that there are no solutions of xn+yn=zn where x, y, and z are positive integers and n is an integer greater than 2.
Anyway - our ambition is, at this stage, at the level of a simpler Diophantine equation, and we just looked at x+y=5, arbitrarily chosen. Here, there are lots of solutions if you allow x and y to be negative integers, while if you restrict to x,y>=0 then there are solutions (x,y)=(0,5), (1,4), (2,3), (3,2), (4,1), (5,0). This is what we were hoping to find.
Grover's algorithm works by constructing a quantum phase oracle that can take a linear superposition of encodings of all possible (x,y) pairs within some range of values of x and y (we encoded each with 3 bits, so from 0 to 7) and change the phase of the quantum amplitude for each component of the linear superposition that represents a valid solution. Then a neat trick uses quantum interference to amplify those states which had been marked out, while reducing the amplitude of the others. In general several cycles of this marking and amplification can be needed to pick out the answers, but - crucially - fewer cycles than a non-quantum search. It's a very standard quantum algorithm, first worked out by Grover in the 90s. Applying it to simple Diophantine equations like we have done doesn't seem to be something that people have done before, though I dare say now our paper is up on arXiv, someone will come along and point out that it has been implemented already. It's a pretty simple thing, but has the potential to be worked up in to a more powerful solver of more interesting equations.
Here's the final plot from the paper where we show the quantum state of the quantum comptuer after two iterations of Grover's algorithm, where we see that there are four quantum states picked out which we have labelled with the encoding of the x and y values. If you split the 6-bit binary strings into two 3-bit strings for the values of x and y, you'll see they add up to 5.
.png)
