Final Report for the GK "Materials and Concepts of Quantum Information Processing"

Ralf Stadelhofer
GK-Scholarship Holder: 01.11.2001 - 31.10.2004
e-mail: ralf.stadelhofer@udo.edu
University of Dortmund
Department of Computer Science

Date: November 18, 2004

The concept of computational power provides a fundamental new language for studying the relationship between classical and quantum physics. Unfortunately the development of quantum algorithms (QA) is a very cumbersome task due to the counterintuitive character of quantum physics. The approach we use in our work to develop QAs is the usage of an automatic algorithm design technique called Genetic Programming (GP). The usage of GP in evolving quantum algorithms was pioneered by [4,10]. In GP one evolves algorithms by imitating nature in the evolution of species. In our work this imitation proceeds as follows:

• Each individual of a population is a QA which itself is described by an unitary operation. As any unitary operation can be decomposed into a sequence of one- and two-qubit gates (elementary quantum gates) one can represent a quantum algorithm by such a sequence. Thus each individual (QA) of a population is a sequence of elementary quantum gates.
• To detect how well an individual of a population in the GP system solves a problem, one can simulate the corresponding quantum algorithm on a classical computer. The measurement probabilities thus obtained are used to calculate a fitness value that indicates the ability of the quantum algorithm to solve the posed problem.
• Dependent on this fitness value, new individuals are created by mutations and crossover.
• Promising individuals are produced by repeating this procedure of fitness calculations, mutations and crossovers, several times.

The fitness calculation of a QA cannot be done efficiently on a classical computer because quantum gates are represented by unitary matrices whose dimension grows exponentially with the number of qubits. As a whole population of up to 5000 QAs has to be evaluated in each generation (up to 5000 generations) one is limited to a small number of qubits ($\sim 10$) to keep the time, such a simulation takes, in reasonable limits. This limitation forced us to: a) introduce a new kind of oracle gates, and b) to restrict the class of problems to decision problems:

a)

An oracle gate O is used to encode the value $x_{i}\in \{0,1,...,l\}$ with $l\in\mathbb{N}$ that is returned by a black-box $X=(x_{0}, x_{1},...,x_{N-1})$ on input $i\in\{0,1,...,N-1\}$, into the quantum system. Usually this is done using two quantum registers, one carrying the index $i\in\mathbb{N}$ of the black-box element to be queried and another to store the output $x_{i}$ of such a query:

$${\bf {O}}\vert\underline{i}\rangle\vert\underline{b}\rangle = \ve... ...e; \quad i\in\{0,1,...,N-1\};\quad b,x_{i}\in\{0,1,...,l\};\quad l\in\mathbb{N}$$ (1)

Here and in what follows we use $\underline{i}$, $\underline{b}$ and $\underline{x_{i}}$ to denote the binary decomposition of the integers $i$, $b$ and $x_{i}$, respectively. $\underline{b}\oplus\underline{x_{i}}$ denotes the bitwise XOR operation between the bit strings $\underline{b}$ and $\underline{x_{i}}$. This scheme is a straightforward way to ensure that the oracle gate is unitary. Unfortunately one needs an extra output register of $m>\log_{2}{(l)}$ qubits which increases the time necessary to simulate the quantum algorithm on a classical computer exponential in $m$. Therefore it is reasonable, as proposed by [6], to test oracle gates that encode the black-box entries $x_{i}$ into phase shifts of the query register $\vert\underline{i}\rangle$:

$${\bf {O}}\vert\underline{i}\rangle=\left(e^{2\pi\imath/l}\right)^{x_{i}}\vert\underline{i}\rangle$$ (2)

Sometimes it is helpful to use a hybrid approach that encodes the value $x_{i}$ partly into a phase shift of the query register and partly into an output register:

$${\bf {O}}\vert\underline{i}\rangle\vert\underline{b}\rangle=\left... ...ert\underline{i}\rangle\vert\underline{b}\oplus\underline{x_{i}}^{(xor)}\rangle$$ (3)

Here we used a decomposition of the integer $x_{i}$ into the integer $x_{i}^{(phase)}\in\{0,1,...,\xi-1\}$ and into the binary string $\underline{x_{i}}^{(xor)}$. Consider for example the integer $x_{i}\in\{0,1,2,3\}$ which is to be encoded into a quantum state that only has one output qubit. As $x_{i}$ can be encoded unambiguously into two bits one has to encode one of these two bits into the output register and the other by a phase shift. For $x_{i}=3$ one gets: ${\bf {O}}\vert i\rangle\vert 0\rangle=-\vert i\rangle\vert 1\rangle$. All the oracle gates presented here are valid quantum operations and can be easily implemented in an experiment.

b)

In a decision problem one wants to know if a black-box has a certain property (as periodicity) or not. The restriction on decision problems is due to the fact that otherwise we would need an extra readout register to store the numerical result of a computation. Also this restriction makes it possible to introduce a GP-system that can find the most convenient measurement procedure by its own. Such a measurement procedure can reduce the necessity of extra qubits needed for post computations that allow an encoding of the answer into a single output qubit.

Using the guidelines mentioned above we were able to develop the following scalable and formerly unknown QAs:

1)

Quantum algorithms solving the parity problem on single issue and ensemble quantum computers:
The determination of the parity of a string of $N$ binary digits is a well known problem in classical as well as in quantum information processing, which can be formulated as a black-box problem. It has been established that quantum algorithms require at least $N/2$ oracle calls [1,2]. In [9] we present an algorithm, developed using GP, that reaches this lower bound and is also optimal in terms of additional gate operations required. There we also discuss its application to pure and mixed states. Since it can be applied directly to thermal states, it does not suffer from signal loss associated with pseudo-pure state preparation. We also show that for ensemble quantum computers the number of oracle calls can be further reduced by a factor $2^k$, provided the signal to noise ratio is sufficiently high. This additional speedup is linked to (classical) parallelism of the ensemble quantum computer. In [9] we also demonstrate the experimental realizations of the parity algorithms on a liquid-state NMR quantum computer.

2)

An exact and scalable quantum algorithm solving a special case of the hidden subgroup problem:
Simon's problem [5] was the first one that showed an exponential gap in the number of oracle queries needed by a quantum algorithm and those needed by any classical probabilistic algorithm. Simon's problem can be stated as a hidden subgroup problem and the algorithm solving it is a probabilistic one. Therefore it is suggestive to explore the conditions under which related problems can be solved by an exact algorithm.

With the help of our GP system it was possible to develop a formerly unknown exact and scalable quantum algorithm that solves the following special case of the hidden subgroup problem:

One is given the finite abelian group $G=\{0,1\}^{n}$ of the size $\vert G\vert=N=2^{n}$. The group multiplication operation is the bitwise XOR operation ($\oplus$). Additionally one is given a black-box $X=(x_{0},x_{1},\dots,x_{N-1})$ with $x_{i}\in\{0,1,2,3\}$ and $\underline{i}\in G$. One is promised that either condition A or condition B holds:

(A)

There exists a nontrivial subgroup $H\subset G$ with $\vert H\vert=\vert G\vert/2$ and an element $g\in G$ such that:

$$\forall i\not= j\;\;$$with$$\;\; \underline{i},\underline{j}\in G:\;\; x_{i}=x_{j} \Leftrightarrow \underline{i},\underline{j}\in g\oplus H$$

(B)

There exists only the subgroup $H=G$ such that

$$\forall i\not= j\;\;$$with$$\;\; \underline{i},\underline{j}\in G:\;\; x_{i}=x_{j} \Leftrightarrow \underline{i},\underline{j}\in g\oplus H$$

Decide which one of the conditions A or B holds.

Here we demanded the group $G$ to be $\{0,1\}^{n}$ with the bitwise XOR operation as group multiplication. If one drops these two restrictions the above problem is the general hidden subgroup problem. Also we used the notation $g\oplus H$ to denote the coset of $H$: If the group $G$ has the subgroup $H\subset G$ then to each $g\in G$ one can define a set $g\oplus H=\{g\oplus h\,:\; h\in H\}$ which is also called a coset of $H$.

Our quantum algorithm solves this problem with two oracle calls, only. The upper part of figure 1 shows this algorithm on three qubits, the lower part shows this algorithm on four qubits. Because $x_{i}\in\{0,1,2,3\}$ one can decompose $x_{i}$ into two binary values $x^{(phase)}_{i}$ and $x^{(xor)}_{i}$. Using this property our oracle gate ${\bf {O}}$ is defined analogous to Eq. (3) by

$${\bf {O}}\;\vert\underline{i}\rangle\vert b\rangle = (-1)^{x^{(phase)}_{i}}\vert \underline{i}\rangle\vert b\oplus x^{(xor)}_{i}\rangle \;\;$$with$$\;\; b,x^{(phase)}_{i}, x^{(xor)}_{i} \in \{0,1\} \;\;$$and$$\;\; \underline{i}\in\{0,1\}^{n} .$$

Measurement of the final state returns the state $\vert 0 ... 0\rangle$ if $K=G$, otherwise one does not measure $\vert 0 ... 0\rangle$.

An exact classical algorithm that solves this problem needs at most $n+1$ black-box queries (here: $\vert G\vert=2^{n}$) where $n$ denotes the number of query qubits. A probabilistic classical algorithm can solve this problem using $k>1$ queries with an error probability of $2^{-k+1}$ (for $\vert G\vert\gg 1$).

Figure: Quantum algorithms on three and four qubits as found by our GP system. The lowest qubit is an ancillary qubit and corresponds to the binary variable b in the definition of ${\bf{O}}$: ${\bf{O}}\;\vert\underline{i} \rangle\vert b \rangle = (-1)^{x^{(phase)}_{i}}\vert \underline{i} \rangle\vert b\oplus x^{(xor)}_{i}\rangle$. The upper $n$ query qubits are used to encode $\underline{i}\in G$. H denotes the Hadamard gate and $\sigma _{y}$ denotes a Pauli matrix.

Despite the algorithms presented above we were also able to develop a quantum algorithm that solves a special case of the Deutsch-Jozsa problem [8]. But, as we noticed, this algorithm was already discovered in [7], therefore we didn't present this algorithm here.

Up to this work, as far as we know, all quantum algorithms found with the help of GP were either already known quantum algorithms [4], unknown but not scalable quantum algorithms [11] or scalable quantum algorithms that do not show any quantum speedup [4]. Using GP we were able to evolve scalable, formerly unknown better-than-classical quantum algorithms, which indicates that automated programming techniques provide a useful and not yet fully explored tool in the quest for new quantum algorithms.