Quantum Computation and Image Processing: New Trends in Artificial Intelligence

1 Introduction

In 1985 Deutsch [Deutsch, 1985] developed a theoretical ma­ chine named Universal Quantum Turing Machine (UQTM), that is, a machine based on quantum theory capable of per­ forming computations, and showed that such machine was a generalization of a universal Turing machine. It is also shown in [Deutsch, 1985] that a quantum computer (QC), that is, a physical system capable of performing computations accord­ ing to the rules of quantum mechanics, can perform certain tasks faster than its classical counterpart. Deutsch and Jozsa [Deutsch and Jozsa, 1992] and Shor [Shor, 1994] showed concrete problems where such speed-up is possible.

Among QC properties, we find:

1. Superposition of states. The basic component of a QC is a qubit, that is, a physical entity (such as an electron or a photon) that can be mathematically represented as a vector in a 2D Hilbert space 1{ 2 . The general form of a qubit is

where a, tJ are complex numbers constrained by lal 2 + 1.61 2 = 1 and {lx), IY)} is an arbitrary basis of H 2 [Nielsen and Chuang, 2000]. Thus, 11/1) is a superpo­ sition of states lx) and ly), and therefore 11/1) can be prepared in an infinite number of ways by varying the values of a and tJ. See figure 1.a. In contrast, classi­ cal computers measure bit values using only one basis, { 0,1} and the only two possible states are those that cor­ respond to the measurement outcomes, 0 or 1.

1. Entanglement. Entanglement is a special correlation among quantum systems that has no paragon in classi­ cal systems. Entanglement is seen to be at the heart of QIP unique properties, and an example of it is its role in Quantum Teleportation [Nielsen and Chuang, 2000].

The previous properties may have deep implications in sev­ eral fields of Computer Science, in particular in Artificial In­ telligence (AI) both on theoretical (e.g. faster algorithms and secure tranmissions) and technological spheres (current tech­ nology is now being built taking into account quantum effects due to component size).

The purpose of this poster is to propose an initial step to­ wards the integration of QIP techniques in image processing and, as a future work, in related fields as Computer Vision and Pattern Recognition.

2 Storing an image in a qubit array

2.1 Visual Information Storage in a Multi Particle Quantum System

Let Q = {lq1)1, lq2) 2, ... , lqn)n} be a set of qubits. Our goal is to store visual information in Q. In order to take advantage of 1{ 2 properties, allowed quantum states used to store visual information in a qubit lqi) are M = {IO), ll), I+), 1-)}.

Schematics of an apparatus capable of detecting electromagnetic frequencies and pro­ ducing a set of quantum states as output. I 'I/>} being an overall state of that set of qubits

We define a machine B that divides the whole frequency range of the visible spectra into a partition F1 , F2 , ... , FM and assigns a qubit array (that is, a set of spatially ordered qubit states) Qi to each partition subset Fi (see figure 2). Note that B must act as a bijective function between frequency par­ tition subsets F; and sets of qubit states Q.,, i.e. it is not al­ lowed to have the same qubit state distribution for two differ­ ent frequency subsets. So, for each pixel from a given image, B produces a particular qubit array from the set { Q;}.

Let us suppose that machine B produces only qubit states IO) and 11). Thus, the number of colors that can be repre­ sented in an array of n qubits is 2n, just like in the classical case (for gray scale or primary color values, for instance) but, if we include qubit states I+) and 1-), then the number of different colors that can be stored is 2 2 n.

However, quantum mechanics has a constraint: reading (that is, measuring) non-orthogonal states (as I 0) , 11) , I+) and 1- ) are) is a probabilistic process. Thus, if only one ba­ sis is used to measure all states in M, information retrieval will not be accurate. In addition, the postulates of quantum mechanics state that the post-measurement quantum state is, in general, different from the pre-measurement quantum state (they are equal if and only if the pre-measurement quantum state is equal to one of the orthogonal vectors of the measure­ ment basis).

In order to perform accurate measurements, we now introduce per each pixel, a set of control qubits C = {IPI)1, IP2)2, ... , IPn)n}. IO) and 11) are the only allowed quantum states for elements in C. The purpose of this new element is to use qubit !Pi) to know which basis has to be used to perform a measurement on lqi) (a generalization of this scheme is to allow the quantum programmer to choose only one storing basis for each pixel). So, by measuring qubit IP;) in the canonical basis, it is possible to perform accurate measurements. Formally speaking, the observable used to measure control qubits IP;) is A1 = a1IO) (OI + f3II1) (11. The observables used to measure qubits lqi) are, in the case the outcome in measuring A1 was a1 then A2 = a2IO) (OI + fJ2 11) (11, while in the case the outcome was /31, then we mea-, I I sure A2 = a2 1 I+) (+I+ fJ2 1-) (-1.

2.2 Quantum secrecy vs Eavesdropping

It is relevant to point out the fact that having no a priori knowledge of which measurement basis has to be used to read information in qubits lq;) introduces two very convenient properties: secrecy and eavesdropping detection. Indeed, if an eavesdropper tries to read the information in lq;) without reading IP;), two main advantages with no counterpart in clas­ sical computers are found: a) the eavesdropper has an only 50% chance of reading accurate information (if he/she fail s to choose the right measurement basis, he/she will get only a random outcome), and b) the post-measurement state of a measurement performed with a wrong basis allows us to de­ tect eavesdropping [Bouwmeester et a!., 2001]. This means that in order to provide secure transmission of information, it is sufficient to send only control qubits IP;) via secure cryp­ tographic scheme.

3 Future Work

Next steps include the use of entanglement for gray level and color image segmentation. The basic idea is to entangle qubits with similar colors and to develop quantum algorithms for image segmentation.

Acknowledgments

S.E. Venegas-Andraca gratefully acknowledges the receipt of a CONACyT scholarship from the Mexican National Council of Science and Technology.

The authors want to thank N. Paunkovic for his very stim­ ulating and wise comments about this work.