High Performance Programming for Soft Computing

1515

Quantum ComputingQuantum Computing

Oscar Montiel

ABSTRACT

We present concise information of the main topics that are needed to

understand QC. In the introduction the great potential of this fi eld,

in special for soft computing, is presented. We depart from classical

computing explaining the limitations of classical Turing machines

with the aim to introduce the Quantum Turing Machine to simulate

Quantum algorithms; we use digital logic to introduce the necessary

concepts about the circuit model and reversible computing, with the

purpose of extending these concepts to quantum gates and algorithms.

Brief overviews of the mathematics used in QC and the basic principles

of quantum mechanics also are included. Basic concepts such as the

Bloch sphere, quantum bits, registers, gates, circuits and measurement

are explained.

15.1 Introduction

In the twenty-fi rst century, many signifi cant developments in science

and engineering have been achieved through interdisciplinary research.

Quantum computing (QC) is about computing with quantum systems,

called quantum computers. A quantum computer is a computational

device that makes use of the quantum mechanics (QM) phenomena such

as entanglement, superposition and interference to perform operations

on data. Quantum computers are different from classical binary digital

Instituto Politécnico Nacional, CITEDI, Tijuana, México.

E-mail: [e-mail]

Quantum ComputingQuantum Computing 307

computers since they work with quantum bits. The theoretical model is

the quantum turing machine (QTM) which is a normal turing machine

(TM) with quantum parallelism. Richard Feynman introduced this fi eld

for the fi rst time in the 80’s (Feynman 1982) since he observed that certain

quantum-mechanical effects cannot be simulated in an effi cient way using

a classical computer. Such observation let to speculate that using quantum

effects may become more effi cient computing. The interest grew up in 1994

when Peter Shor published the paper entitled “Algorithms for Quantum

Computation : Discrete Logarithms and Factoring” (Shor 1994) where

he described polynomial time quantum algorithms for fi nding discrete

logarithms and factoring integers.

Quantum computing is a computational model that may provide

exponential advantages over classical computational models such as

probabilistic and deterministic turing machines (Arora and Barak 2010). It

combines QM, information theory and aspects of computer sciences; QC

differs from classical computing based on traditional logic in many respects,

for example, instead of operating on bits and Boolean logic, QC is based

on quantum logic and operates on qubits. The idea is to exploit quantum

effects to compute in an effi cient and faster way than using conventional

computers. QC uses a specifi c implementation to gain a computation

advantage over conventional computers. Although the fi eld is relatively

new, it promises a dramatic computing speed increase using properties

such as superposition and entanglement; it is expected to obtain, in some

cases, an exponential amount of parallelism.

There are several recent works focussing on the application of QC in the

soft computing area, for example: In (Visintin et al. 2012) there is a proposal

to associate the states of a quantum register with membership functions

of fuzzy subsets, and the rules in the fuzzyfi cation process, are performed

using unitary quantum transformations; also it is presented a proposal of

t-norms and t-conorms based on unitary and controlled quantum gates.

With respect to the use of QC with neural networks, in (Nayak et al. 2011)

it is presented the basic concepts of quantum neural computing as well as a

mathematical model of a quantum neuron to discuss the training algorithm.

It is discussed that Quantum Neural Network is a new paradigm based on

the combination of classical neural networks and quantum computation,

and it is presented an introductory representation of quantum artifi cial

neural network modeled on the basis of double-slit experiment. In (Finch

2012) the author proposes two algorithms for training neural nets on a

quantum computer , through a simulation it is shown that they can be

used to train neural nets much faster than using the same methods on a

classical computer. In the robotics fi eld we can fi nd other applications of

quantum computing like an improved hierarchical Q-learning algorithm

in conjunction with quantum parallelization computation for a mobile-