### Transcription of 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. 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).

3 (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. 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?

4 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].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].

5 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** ?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.

6 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. 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.

7 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. 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.

8 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** . 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.

9 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. 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].

10 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 |. The application of bra to ket results in the bra-ketnotationh|i. In the bra-ket notation, the inner product is represented byh m| ni=1,forn=m. By inverting the order and performing the ket-bra multipolicationthe outer product is obtained; it is given by| mih n|.The information in **Quantum** computation is represented by a qubit that in theDirac notation can be written in the form of a characteristicequation. For instancea qubit with two possible orthonormal states|0iand|1iis described by eq. MATHEMATICAL PRELIMINARIES TO **Quantum** COMPUTING5deeper meaning of this equation will be explained in of this **Chapter** .( )| i= |0i+ | Heisenberg NotationIn general, to describe basis states of a **Quantum** System, theDirac notation ispreferred to the vector based Heisenberg notation.