Chapter 1 Quantum Computing Basics and Concepts

1 Chapter 1 Quantum Computing Basics IntroductionThis book is for researchers and students of computational intelligence as well as forengineers interested in designing Quantum algorithms in the circuit content of this book is presented as a set of design methods of Quantum circuitswith the focus on evolutionary algorithm; however some heuristic algborithms aswell as a wide range of application of Quantum circuits are general idea behind this book is to represent every computational problemas a Quantum circuit and then to use some classical synthesisapproach to designthe circuit. The goal of such approach is to describe and illustrate the use of clas-sical design methods and their extension into Quantum logicsynthesis. The reasonof using the circuit representation is that in classical logic synthesis various algo-rithms exist for the design of both combinatorial and sequential circuits and thusdesigning Quantum algorithms in the circuit representation provides a good basisfor comparison.

2 Moreover the circuit representation is onethat is the most explicit;at the same time it provides a good visual representation as well as it also allows adirect formalization and generalization of principles of both Quantum computationand circuit know that Quantum Computation relies on Quantum mechanics which is amathematical model that describes the evolution of physical realization of computa-tion and hence the computer itself. Several philosophically different but physicallyequivalent formulations have been found for Quantum mechanics [Sty02]. In thisbook , we follow Schr odinger [Sch26] which describes the physical state of a quan-12 Chapter 1. Quantum Computing Basics AND CONCEPTStum system by a temporally evolving vector| iin a complete complex inner productspace H called a Hilbert space.

3 The time evolution under the influence of a singleterm of the Hamiltonian is a single physical operation and inthis book we will be de-signing and optimizing circuits at the level of such operations (pulses). (Hamiltonianis a physical state of a system which is observable corresponding to the total energyof the system. Hence it is bounded for finite dimensional spaces and in the case ofinfinite dimensional spaces, it is always unbounded and not defined everywhere).The interesting fact about this book is the unified approach;in this book weuse solely circuit representation (either direct such as wires and functions or moresophisticated representation such as a Reed-Muller form) to design logic circuuits,sequential machines or robot controllers for motion or machine learning.

4 The tar-get of all these circuits is to provide examples of application of Quantum circuitsand hopefully also show theri superiority over the classical circuits of the this book is devoted to the computational aspects ofdesigning quan-tum computers, Quantum algorithms and Quantum computational intelligence, onemay ask Why Quantum computers are of interest and why are they more powerfulthan standard computers when used to solve problems in computational intelli-gence? This is question is the main motivation for this introductory Chapter wherethe Quantum Computing is explained starting from its hisotrical context and endingin a description of Quantum circuits and some of their Why Quantum Computing ? Quantum Mechanics (QM) describes the behavior and properties of elementaryparticles (EP) such as electrons or photons on the atomic andsubatomic in the first half of the 20th century mainly by Schr odinger [Sch26],Bohr [Boh08], Heisenberg [Cas] and Dirac [Dir95], it was only in the late 70 s thatquantum information processing systems has been proposed [Pop75,Ing76,Man80].

5 Even later, in the 80 s of the last century it was Feynman who proposed the firstphysical realization of a Quantum Computer [Fey85]. In parallel to Feynman, Be-nioff [Ben82] also was one of the first researchers to formulate the principles ofquantum Computing and Deutsch proposed the first Quantum Algorithm [Deu85].The reason that these Concepts are becoming of interest to computer engineeringcommunity is mainly due to the Moore s law [Moo65]; that is: the number of transis-tors in a chip doubles every 18 months and the size of gates is constantly problems such as heat dissipation and information loss are becomingvery important for current and future technologies. Improving the scale of transis-tors ultimately leads to a technology working on the level ofelementary WHY Quantum Computing ?

6 3(EP) such as a single electron or photon. Since Moore s paperthe progress led tothe current 35 nm ( 10 10m) circuit technology which considering the size of anatom (approximately 10 10m) is relatively close to the atomic size. Consequentlythe exploration of QM and its related Quantum Computing becomes very impor-tant to the development of logic design of future devices andin consequence to thedevelopment of Quantum algorithms, Quantum CAD and quantumlogic synthesisand architecture methodologies and theories. Because of their superior performanceand specific problem-related attributes, Quantum computers will be predominantlyused in computational intelligence and robotics, and similarly to classical computersthey will ultimately enter every area of technology and day-to-day the fact of being based on paradoxical principles, QM has found applicationsin almost all fields of scientific research and technology.

7 Yet the most importanttheoretical and in the future also practical innovations were done in the field ofQuantum Computing , Quantum information, and Quantum circuits design [BBC+95,SD96].Although only theoretical Concepts of implementation of complete Quantum com-puter architectures have been proposed [BBC+95,Fey85,Ben82,Deu85] the contin-uous progresses in technology will allow the construction of Quantum Comput-ers in close future, perhaps in the interval of 10 to 50 progressin implementation and architectures proove that this area is just at its beginingand is gorwing. For instance the implementation of small Quantum logic opera-tions with trapped atoms or ions [BBC+95, NC00, CZ95, DKK03, PW02] are theindication that this time-frame of close future can be potentially reduced to onlya few years before the first fully Quantum computer is constructed.

8 The largestup to date implementation of Quantum computer is the adiabatic computer byDWAVE [AOR+02, AS04, vdPIG+06, ALT08, HJL+10]. Although up to now it isstill an open issue whether the DWAVE computer is a proper Quantum computeror not [], it provides consideerable speed up over classicalcomputer in the SATimplementation and int the Random Number Generation []. In parallel to theadiabatic Quantum computer, architectures for full Quantum computers have beenproposed [MOC02, SO02, MC]. In these proposals the Quantum computations isimplemented over a set of flying-photons that represents thedegree of freedom ofinteractions between qubits. Such architectures however have not been implementedas of Chapter presents the basic Concepts of Quantum Computing as well as the tran-sition from Quantum physics to Quantum Computing .

9 We also introduce quantumcomputing models, necessary to understand our Concepts of Quantum logic, quan-tum Computing and synthesis of Quantum logic circuits. The Section introducessome mathematical Concepts and theories required for the understanding of quan-tum Computing . Section second section presents a historical overview of the4 Chapter 1. Quantum Computing Basics AND Concepts Quantum mechanical theory and Section presents the transition from quantummechanics to Quantum logic circuits and Quantum Mathematical Preliminaries to Quantum Com-putingAccording to [Dir84] each physical system is associated with a separate Hilbertspace H. An H space is an inner product vector space where the unit-vectors are thepossible states of the system. An inner product for a vector space is defined by thefollowing formula:( )hx,yi=Xkx kykwhere x and y are two vectors defined on H andx denotes a complex conjugateof x.

10 For Quantum computation it is important to introduce the orthonormal basison H, in particular considering the12-spin Quantum system that is described by twoorthonormal basis states. An orthonormal set of vectors M inH is such that everyelement of M is a unit vector (vector of length one) and any twodistinct elementsare Orthonormal basis setAn orthonormal basis set can be defined such as:{(1,0,0)T,(0,1,0)T,(0,0,1)T}. Inthis space, a linear operator A represented by a matrix A transforms an input vectorvto an output vectorwsuch asw= Bra-Ket notationOne of the notations used in Quantum Computing is the bra-ketnotation introducedby Dirac [Dir84]. Is it used to represent the operators and vectors; each expressionhas two parts, a bra and a ket. Each vector in the H space is a ket| iand itsconjugate transpose is brah |.