Lectures On Quantum Computing
Lectures on Quantum ComputingDan C. Marinescu and Gabriela M. MarinescuComputer Science DepartmentUniversity of Central FloridaEmail: [dcm,magda]@cs.ucf.eduOctober 13, 20031
Contents1 Preface82 Introduction2.1 Computing and the Laws of Physics . . . . . . . . . . .2.2 Quantum Information . . . . . . . . . . . . . . . . . .2.3 Quantum Computers . . . . . . . . . . . . . . . . . . .2.4 The Wave and the Corpuscular Nature of Light . . . .2.5 Deterministic versus Probabilistic Photon Behavior . .2.6 State Description, Superposition, and Uncertainty . . .2.7 Measurements in Multiple Bases . . . . . . . . . . . . .2.8 Measurements of Superposition States . . . . . . . . .2.9 An Augmented Probabilistic Model. The Superposition2.10 A Photon Coincidence Experiment . . . . . . . . . . .2.11 A Three Beam Splitter Experiment . . . . . . . . . . .2.12 BB84, the Emergence of Quantum Cryptography . . .2.13 A Qubit of History . . . . . . . . . . . . . . . . . . . .2.14 Summary and Further Readings . . . . . . . . . . . . .2.15 Exercises and Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Probability Rule. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3 Quantum Mechanics, a Mathematical Model of the Physical World3.1 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.2 n-Dimensional Real Euclidean Vector Space . . . . . . . . . . . . . . . . .3.3 Linear Operators and Matrices . . . . . . . . . . . . . . . . . . . . . . . . .3.4 Hermitian Operators in a Complex n-Dimensional Euclidean Vector Space3.5 n-Dimensional Hilbert Spaces. Dirac’s Notations . . . . . . . . . . . . . . .3.6 The Inner Product in an n-Dimensional Hilbert Space . . . . . . . . . . . .3.7 Tensor and Outer Products . . . . . . . . . . . . . . . . . . . . . . . . . .3.8 Quantum States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.9 Quantum Observables. Quantum Operators . . . . . . . . . . . . . . . . .3.10 Spectral Decomposition of a Quantum Operator . . . . . . . . . . . . . .3.11 The Measurement of Observables . . . . . . . . . . . . . . . . . . . . . . .3.12 More about Measurements. The Density Operator . . . . . . . . . . . . . .3.13 Young’s Double-Slit Experiments . . . . . . . . . . . . . . . . . . . . . . .3.14 Stern - Gerlach Type Experiments . . . . . . . . . . . . . . . . . . . . . . .3.15 The Spin as an Intrinsic Property . . . . . . . . . . . . . . . . . . . . . . .3.16 Schrödinger’s Wave Equation . . . . . . . . . . . . . . . . . . . . . . . . .3.17 Heisenberg’s Uncertainty Principle . . . . . . . . . . . . . . . . . . . . . .3.18 A Brief History of Quantum Ideas . . . . . . . . . . . . . . . . . . . . . . .3.19 Summary and Further Readings . . . . . . . . . . . . . . . . . . . . . . . .3.20 Exercises and Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4 Qubits and Their Physical Realization4.1 One Qubit, a Very Small Bit . . . . . . . . . . .4.2 The Bloch Sphere Representation of One Qubit4.3 Rotation Operations on the Bloch Sphere . . . .4.4 The Measurement of a Qubit . . . . . . . . . . 6162646871737579828385868991.94949798102
4.54.64.74.84.94.104.114.124.134.144.15Pure and Impure States of a Qubit . . . . . . . . . . . . .Two Qubits. Entanglement. . . . . . . . . . . . . . . . . .The Fragility of Quantum Information. Schrödinger’s Cat .Qubits, from Hilbert Spaces to Physical Implementation .Qubits as Spin 12 Particles . . . . . . . . . . . . . . . . .The Measurement of the Spin . . . . . . . . . . . . . . . .The Qubit as a Polarized Photon . . . . . . . . . . . . . .Entanglement . . . . . . . . . . . . . . . . . . . . . . . . .The Exchange of Information Using Entangled Particles . .Summary and Further Readings . . . . . . . . . . . . . . .Exercises and Problems . . . . . . . . . . . . . . . . . . . .1051061081091121141181221231251275 Quantum Gates and Quantum Circuits5.1 Classical Logic Gates and Circuits . . . . . . . . . . . . .5.2 One Qubit Gates . . . . . . . . . . . . . . . . . . . . . .5.3 The Hadamard Gate, Beam splitters and Interferometers5.4 Two Qubit Gates. The CNOT Gate . . . . . . . . . . . . .5.5 Can we Build Quantum Copy Machines? . . . . . . . . .5.6 Three Qubit Gates. The Fredkin Gate . . . . . . . . . .5.7 The Toffoli Gate . . . . . . . . . . . . . . . . . . . . . .5.8 Quantum Circuits . . . . . . . . . . . . . . . . . . . . . .5.9 The No Cloning Theorem . . . . . . . . . . . . . . . . .5.10 Qubit Swapping and Full Adder Circuits . . . . . . . . .5.11 Unitary Operations on a Single Qubit. Rotation Matrices5.12 Single Qubit Controlled Operations . . . . . . . . . . . .5.13 Multiple Qubit Controlled Operations . . . . . . . . . . .5.14 A Quantum Circuit for the Walsh-Hadamard Transform5.15 Mathematical Models of a Quantum Computer . . . . .5.16 Errors, Uniformity Conditions, and Time Complexity . .5.17 Summary and Further Readings . . . . . . . . . . . . . .5.18 Exercises and Problems . . . . . . . . . . . . . . . . . . 651661686 Quantum Algorithms6.1 Introduction to Quantum Algorithms . . .6.2 Quantum Turing Machines . . . . . . . . .6.3 Quantum Parallelism . . . . . . . . . . . .6.4 Deutsch’s Algorithm . . . . . . . . . . . .6.5 Quantum Fourier Transform . . . . . . . .6.6 Simon’s Algorithm for Phase Estimation .6.7 Order Finding . . . . . . . . . . . . . . . .6.8 Quantum Algorithms for Integer Factoring6.9 The Hidden Subgroup Problem . . . . . .6.10 Quantum Search Algorithms . . . . . . . .6.11 Quantum Simulation . . . . . . . . . . . .6.12 Summary and Further Readings . . . . . .6.13 Exercises and Problems . . . . . . . . . . .1711711721731751791871901901901901901901903.
7 Reversible Computations7.1 Turing Machines, Reversibility, and Entropy . . . . . . . . . . .7.2 Thermodynamic Entropy . . . . . . . . . . . . . . . . . . . . . .7.3 Maxwell Demon . . . . . . . . . . . . . . . . . . . . . . . . . . .7.4 Energy Consumption. Landauer Principle . . . . . . . . . . . .7.5 Low Power Computing. Adiabatic Switching . . . . . . . . . . .7.6 Bennett Information Driven Engine . . . . . . . . . . . . . . . .7.7 Logically Reversible Turing Machines and Physical Reversibility7.8 Summary and Further Readings . . . . . . . . . . . . . . . . . .7.9 Exercises and Problems . . . . . . . . . . . . . . . . . . . . . . .1911911931951961981991992012018 The “Entanglement” of Computing and Communication with Quantum Mechanics2028.1 Uncertainty and Locality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2028.2 Possible Explanations of the EPR Paradox . . . . . . . . . . . . . . . . . . . . 2048.3 The Bell Inequality. Local Realism . . . . . . . . . . . . . . . . . . . . . . . . 2048.4 EPR Pairs and Bell States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2078.5 Quantum Teleportation with Maximally Entangled Particles . . . . . . . . . . 2098.6 Anti-Correlation and Teleportation . . . . . . . . . . . . . . . . . . . . . . . . 2178.7 Dense Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2198.8 Quantum Key Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2238.9 Summary and Further Readings . . . . . . . . . . . . . . . . . . . . . . . . . . 2278.10 Exercises and Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2279 Appendix I: Modular Arithmetic9.1 Elementary Number Theory Concepts . .9.2 Euclid’s Algorithm for Integers . . . . .9.3 Euclid’s Algorithm for Polynomials . . .9.4 The Chinese Remainder Theorem and its9.5 Computer Arithmetic for Large Integers9.6 Summary and Further Readings . . . . .9.7 Exercises and Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Applications. . . . . . . . . . . . . . . . . . . . . .10 Appendix II: Welsh-Hadamard Transform10.1 Hadamard Matrices . . . . . . . . . . . . .10.2 The Fast Hadamard Transform . . . . . .10.3 Further Readings . . . . . . . . . . . . . .10.4 Exercises and Problems . . . . . . . . . . .11 514
Notationsch kBGRCZnGF (q) i 1α0 , α1 , . . .α0 , α1 , . . . αj eiαCnH2Hn ψ , φ ψ ψ φ ψ φ The speed of light in vacuum: c 3 1010 cm s 1 .Planck’s constant: h 6.6262 10 34 J s.h 1.054 10 34 J s.Reduced Planck’s constant: 2πBoltzman’s constant: kB 1.131 10 23 J K 1 .The universal gravitational constant: G 6.672 10 8 cm3 g 1 s 2 .The field of real numbers.The field of complex numbers.The finite field of integers modulo n with n a prime number.The Galois field with q elements with q pn ,with p a prime number and n an integer.The finite field GF (pn ) has characteristic p.Imaginary square root of unity.Complex numbers. αj Real(αj ) i Imaginary(αj )Complex conjugates. αj Real(αj ) i Imaginary(αj )The modulusof the complex number αj . αj [Real(αj )]2 [Imaginary(αj )]2Euler’s formula: eiα cos(α) isin(α).n- dimensional vector space over the field of complex numbers.Two-dimensional Hilbert space.n-dimensional Hilbert space.ket vectornotation);e.g., ψ , φ column vectors in C3 (Dirac’sβ0α0 α1β1 φ ψ α2β2bra vector (Dirac’s notation); the dual of ψ , i.e., ψ † . The row vector ψ is the transpose of the complex conjugate of ψ . α0If ψ α1 then ψ ψ † ( ψ )T (α0 , α1 , α2 ).α2The scalar (inner) product of ψ and φ ; it is a complex number.β0 T ψ φ ψ φ (α0 , α1 , α2 ) β1 α0 β0 α1 β1 α2 β2 .β2The tensor product of ψ and φ ; it is a vector. α0 β0 α0 β1 α0 β2 α1 β0 α0β0 αβ ψ φ ψ φ α1 β1 11 α1 β2 α2β2 α2 β0 α2 β1 α2 β25
ψ φ The outer product of ψ or a matrix. and φ ; it is a linear operator α0α0 β0 α0 β1 α0 β2 ψ φ ψ ( φ )T α1 (β0 , β1 , β2 ) α1 β0 α1 β1 α1 β2 α2α2 β0 α2 β1 α2 β2 ψ The norm of vector ψ . ψ ψ ψ α0 2 α1 2 α2 2 .ALinear operator or matrix.Partial derivative of operator A. A/ aitr(A)The trace of matrix A; the sum of its diagonal elements.det(A) A The determinant of matrix A.Minor obtained by eliminating row i and column j from A.MijATranspose of matrix Amn ; row i, 1 i m of Amn becomes column i of ATmn .ATComplex conjugate of matrix Amn ;A aij a ij , 1 i m, 1 j n.Hermitian conjugate, or dual of A. A† (A )T .A†ρDensity matrix.0 if (i j)Kronecker’s delta function. δij δij1 if (i j) A formulation of Heisenberg’s uncertainty principle; x px 2 x and px are indeterminacies in particle position andmomentum along direction x, respectively.i dtd Ψ HΨ Schrödinger equation.HHamiltonian operator.hDe Broglie’s equation. p is the momentum of a particle andp λλ is the wavelength of the wave associated with it.S kB ln(W ) The thermodynamic entropy S. kB is the Boltzman’s constant.W is the probability of a given state.u vSum modulo 2 (Exclusive OR). Given binary n-tuples u (u0 , u1 , . . . un 1 ) andv (v0 , v1 , . . . vn 1 ) then u v (u0 v0 , u1 v1 , . . . un 1 vn 1 )orif ui 1 and vi 0.ui ui 1 if ui 0 and vi 1,aLargest integer smaller than or equal to the real number a.gcd(m, n)The greatest common divisor of integers m and n. The largest integerdividing both m and n.lcd(m, n)The least common multiple of integers m and n. A The cardinality of the set A. The number of elements of A.The set of non-zero elements of a field F , {F {0}}.F ord(α)The order of the element α F , with F a finite field.The multiplicative inverse of integer a modulo n. a · a 1 1 (mod n).a 1 (mod n)Zp [x]Polynomials in x with coefficients from the finite field Zp .[g(x)]The equivalence class containing the polynomial g(x).(a0 , a1 , a2 , a3 ) Vector representing the polynomial g(x) a0 a1 x a2 x2 a3 x3 .Vector space of k tuples over the field F .Vk (F )[n, M ]-codeBlock code with M codewords each of length n.(n, k)-codeLinear code with k information symbols and blocks of length n.(n, k, d)-code Linear code with k information symbols, blocks of length n, and distance d.Orthogonal element of code C.C 6
{n, k, d1 , d2 }σ0 , σ1 , σ2 , σ3H, S, TGCN OTGT of f oliWjXpX (x)pX,Y (x, y)pX Y (x y)FX (x)E [X]V ar[X]H(X)H(X, Y )Quantum code where n qubits are used to store or transmit k bitsof information and allow correction of up to (d1 1)/2 amplitude errorsand simultaneously up to (d2 1)/2 phase errors.Pauli matrices.1 00 1σ1 σx X σ0 I 0 11 00 i1 0σ2 σy Y σ3 σz Z i 00 1The Hadamard (H), phase (S) and π/8 (T) matrices for one qubit gates101 11 0S T H 121 10 i0 eiπ/4The matrix ofCNOT, a two qubit gate. the controlled-NOT, 1 0 0 0 0 1 0 0 GCN OT 0 0 0 1 0 0 1 0The matrix ofgate. the Toffoli gate, a three qubit 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 GT of f oli 00001000 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0The Welsh-Hadamard transform of j qubits.Wj 1 H Wj .Wj is defined recursively as: W1 HDiscrete or continuous random variable.The probability density function of the random variable X.The joint probability density function of random variables X and Y .The conditional probability density function of X conditioned by Y .The cumulative distribution function of the random variable X.xFX (x) P rob(X x) pX (t)dt continuous case.The expected value of the random variable X.ni 1 xi pX (xi ) discrete caseE[X] continuous case.XpX (x)dxThe variance of the random variable X.n2 discrete casei 1 (xi E[X]) pX (xi )V ar[X] 2(x E[X]) pX (x)dx continuous case. The Shannon entropy of random variable X. ni 1 pX (xi )log2 pX (xi ) discrete caseH(X) continuous case. pX (x)log2 pX (x)dxThe joint entropy of X and Y . xi yj pX,Y (xi , yj ) log2 pX,Y (xi , yj ).H(X, Y ) X Y pX,Y (x, y) log2 pX,Y (x, y).7
1PrefaceA tremendous progress has been made in the area of quantum computing and quantuminformation theory during the past decade. Thousands of research papers, a few solid referencebooks, and many popular-science books have been published in recent years in this area. Thegrowing interest in quantum computing and quantum information theory is motivated by theincredible impact this discipline could have on how we store, process, and transmit data andknowledge in this information age.Computer and communication systems using quantum effects have remarkable properties.Quantum computers enable efficient simulation of the most complex physical systems we canenvision. Quantum algorithms allow efficient factoring of large integers with applications tocryptography. Quantum search algorithms speedup considerably the process of identifyingpatterns in apparently random data. We can guarantee the security of our quantum communication systems because eavesdropping on a quantum communication channel can always bedetected.It is true that we are years, possibly decades away from actually building a quantumcomputer requiring little if any power at all, filling up the space of a grain of sand, andcomputing at speeds that are unattainable today even by covering tens of acres of floor spacewith clusters made from tens of thousands of the fastest processors built with current stateof the art solid state technology. All we have at the time of this writing is a 7 (seven) qubitquantum computer able to compute the prime factors of a small integer, 15. Building aquantum computer faces tremendous technological and theoretical challenges. At the sametime, we witness a faster rate of progress in quantum information theory where applicationsof quantum cryptography seem ready for commercialization. Recently, a successful quantumkey distribution experiment over a distance of some 100 km has been announced.It is very difficult to predict how much time will elapse from the moment of a greatdiscovery until it materializes into a device that profoundly changes our lives. The firstatomic bomb was exploded in 1945, less than 10 years after the discovery of the nuclearfission by Lise Meitner and Otto Hahn [74]. The first microprocessor was built in late 1970s,some 30 years after the discovery of the transistor on December 23, 1947 by William Shockley,John Bardeen, and Walter Brattain. Francis Harry Compton Crick and James Dewey Watsondiscovered the double helix structure of the genetic material in 1957 and the full impact oftheir discovery will continue to reverberate for years to come.We believe that the time to spread the knowledge about quantum computing and quantum information outside the circle of quantum computing researchers and students majoringin physics is ripe. Students and professionals interested in information sciences should getacquainted with a very different way of thinking than the one used to construct today’s algorithms. This certainly posses tremendous challenges, since, for many years, computer sciencestudents have been led to believe that they can get by with some knowledge of discrete mathematics and little if any understanding of physics at all1 . But times are changing; in somesense we are going back to the age when a strong connection between physics and computersexisted.The present volume, “Lectures on Quantum Computing”, is devoted to quantum com1This seems to be a perennial problem. When James II, the king of Great Britain, insisted that a Benedictine monk be given a degree without taking any examinations or swearing the required oaths, Isaac Newton,who was the Lucasian professor at Trinity College at Cambridge, wrote to the Vice-Chancellor “Be courageous and steady to the Laws and you cannot fail.” The Vice-Chancellor took Newton’s advice and. wasdismissed from his post.8
puting. The first chapter introduces the reader to the quantum world by way of severalexperiments. The second chapter provides the most basic concepts of quantum mechanicsand of the supporting mathematical apparatus. The third chapter introduces the qubit andhints at simple physical realizations of a qubit. The next chapter is devoted to quantum gatesand quantum circuits. The fifth chapter presents quantum algorithms. The sixth chapteris devoted to reversible computations. The last chapter introduces the reader to quantumteleportation, quantum key distribution, and dense coding. The text is intended to be selfcontained; concepts, definitions, and theorems from linear algebra, necessary to develop themathematical apparatus of quantum mechanics are introduced in Chapter 2. Appendix 1presents modular arithmetic necessary for understanding the factoring algorithms. Appendix2 is devoted to the Welsh-Hadamard transform.We treat a quantum computer as a mathematical abstraction. Yet, we discuss in somedepth the fundamental properties of a quantum system necessary to understand the subtletiesof counterintuitive quantum phenomena such as entanglement.“Lectures on Quantum Computing” is intended as a textbook for a one semester firstcourse in quantum computing. The time table we suggest for covering the material is: twoweeks for Chapter 1, two weeks for Chapter 2 two weeks for Chapter 3, three weeks forChapter 4, three weeks for Chapter 5 and Appendices 1 and 2, one week for Chapter 6, andtwo weeks for Chapter 7. Any graduate or undergraduate student with a solid background inlinear algebra and calculus should be able to do well in the class.A second volume, “Lectures on Quantum Information Theory”, is devoted to quantuminformation theory. The volume starts with a deeper discussion of the postulates of quantummechanics, necessary to understand the rather difficult subject of quantum measurements andthe Bell inequality. Then we cover classical quantum information theory and classical errorcorrecting and error detecting codes. The next chapters expose the reader to the quantuminformation theory concepts and to quantum error correcting codes. We devote a chapter toquantum cryptography and conclude the book with a chapter on the physical realization ofquantum computing and communication systems. An appendix provides a summary of concepts, definitions, and theorems related to algebraic structures and to finite fields in particular,necessary to understand coding theory.A fair number of well-written “popular science” books devoted to qualitative explanationof quantum physics and quantum computing are available. The term “popular” simply meansthat such books have a larger audience than traditional scientific books, yet, probably, thoseacquainted with such books form a relatively small segment of the “populus”. As sciencemakes new discoveries at a fairly rapid pace, the gap between those who are acquainted tosome degree with the scientific knowledge and those who are oblivious to science becomeslarger and larger. This fact should be a cause of great concern for all of us.The two volumes on quantum computing and quantum information theory combine aqualitative presentation with a more rigorous, quantitative analysis. Whenever possible weattempt to avoid the sometimes difficult mathematical apparatus, the trademark of quantummechanics. In his marvellous book “A Brief History of Time” [61], Stephen Hawking, theastrophysicist who is now the Lucasian professor, shares with his readers the warning he gotfrom his editor: “expect the sales to be cut in half for every equation in your book”. Thereare k 102 equations in this series of lectures and 2100 1, 00010 is a very large number.Peter Shor has made several constructive suggestions and signaled some of the problems inan early version of the manuscript. P.K. Aravind, Dan Burghelea, and Boris Zel’dovich havegone with a fine tooth comb over a more evolved version of the first volume. We are greatly9
indebted to the four of them. Robert E. Lynch from the Mathematics and the ComputerScience Departments at Purdue University has reviewed an early version of the manuscriptand made a number of recommendations. Of course, the authors are responsible for all theremaining errors. Tom Robbins, our editor from Prentice Hall, communicated with us hisvision and helped shape the book.10
2IntroductionTwo of the greatest scientific discoveries of the twentieth century, quantum mechanics and thegeneral theory of relativity, target physical phenomena which we rarely, if ever, experience inour daily lives. After all, no human being has ever travelled at a speed approaching the speedof light, nor are we often in the position to observe quantum effects on earth.Quantum is a Latin word meaning some quantity. In physics it is used with the samemeaning as the word discrete in mathematics, i.e., some quantity or variable that can takeonly sharply defined values as opposed to a continuously varying quantity. The conceptscontinuum and continuous are known from geometry and calculus. For example, on a segmentof a line there are infinitely many points, the segment consists of a continuum of points. Thismeans that we can cut the segment in half, and then cut each half in half, and continue theprocess indefinitely.It is extremely difficult to accept the non-determinism governing the quantum world. Evensome of the greatest minds of our time, including Albert Einstein, had doubts about suchunsettling ideas. Even more troubling for most of us is the concept of non-locality, the factthat two quantum objects even when separated by a distance possibly measured in light years,could influence one another, and that the change of state of one determines an instantaneouschange of state of the other.Most laws governing the physical phenomena studied by quantum physics are counterintuitive and can only be presented with the aid of a rather sophisticated mathematicalapparatus. We have to free our thinking from sensory information and step into a verydifferent world. For example, we believe that we can measure the position first and then thevelocity (thus the momentum) of an object, or we can measure the velocity first and then theposition, and expect exactly the same results in both experiments. This is true for a car, anairplane, a rocket, or a bullet in flight, but it is false for quantum particles such as electrons, orfor photons. Measuring the position of a quantum particle makes it impossible to determineits velocity with an arbitrary high level of accuracy. The reverse is also true, if we measurefirst the velocity it is impossible to determine the position of the particle with an arbitraryhigh level of accuracy. The explanation, very simple for the layperson with some knowledgeof linear algebra, has its roots in a rather trivial property of the matrix multiplication: theproduct of matrices is non-commutative2 . Measuring a property (the velocity or the position)of a quantum particle corresponds to a mathematical operation, namely, applying the operatorassociated with that property (observable) to the vector describing the state of the system.A linear operator has a matrix associated with it, and the non-commutativity of the productof two matrices implies that the order of the measurements is important.It is clear, as we shall see shortly, that the laws of physics and the laws of quantum mechanics in particular, limit our ability to process information increasingly faster and cheaperusing present day solid state technologies. The question addressed by the new discipline ofquantum information processing is if the strange world of quantum phenomena can be harnessed and eventually be put to “good use”. It turns out that communication and computersystems using quantum effects have remarkable properties. A quantum communication channel transmits information using quantum effects, e.g., when the information is encoded intothe spin of an electron, or in the polarization of a photon. Eavesdropping on a quantumcommunication channel can always be detected. Quantum computing enables efficient simulation of the most complex physical systems that we can envision. Quantum algorithms have2If A and B are matrices then their product is non-commutative, AB BA.11
been discovered that allow efficient factoring of large integers. This particular problem is ofimmense practical interest because efficient factoring algorithms would allow us to decryptwith ease communication encrypted with today’s state of the art encryption techniques. Parallel search quantum algorithms are equally promising for data mining and other importantapplications.In this chapter we first discuss the laws of physics that limit our ability to build fastercomputers using current technologies. Then, we discuss several experiments that provide someinsight regarding quantum effects and discuss a practical application of quantum informationtheory. To conclude the chapter we outline the milestones leading to the new discipline ofquantum computing.2.1Computing and the Laws of PhysicsComputers are systems subject to the laws of physics. One of these laws, the finite speedof light, limits the potential reliability of future computing systems. The components ofa computer exchange information among themselves, e.g., the processor reads and writesinformation from/to memory, data is transferred from the internal registers to the Arithmeticand Logic Unit (ALU), and so on. Transmission of information is associated with a transportof energy from the source to the destination, but no physical phenomena may propagate witha speed larger than the speed of light. It takes one nanosecond, 10 9 seconds, for the lightto travel a distance of 30 cm in vacuum and about 20 cm in a metallic conductor. Therefore,the speed of a computer is limited by the size of its components. It is inevitable that inour quest to increase the speed, at some point the components of a computer will approachatomic dimensions 3 . When this happens, switching, the change of the state of a component,will be governed by Heisenberg’s uncertainty principle 4 . It follows that we may not beable to determine the state of that component with absolute certainty and the results of acomputation, though carried out by a very fast computer, will be unreliable.The technology enabling us to build smaller and faster computing engines encountersother physical limitations as well. We are limited in our ability to increase the density andthe speed of a computing engine. Indeed, the heat produced by a super dense computingengine is proportional to the number of elementary computing circuits, thus, to the volumeof the engine. To prevent the destruction of the engine we have to remove the heat through asurface surrounding the device, see Figure 1(b). Let us assume that we pack the logic gatesas densely as possible, say in a sphere of radius r. The heat dissipated is then proportionalto the number of gates, thus to the volume of the sphere, V (4/3)πr3 .
University of Central Florida Email: [dcm,magda]@cs.ucf.edu October 13, 2003 1. Contents 1Preface 8 2 Introduction 11 . A tremendous progress has been made in the area of quantum computing and quantum growing interest in quantum computing and quantum information theory is motivated by the, Quantum and.
1. Quantum bits In quantum computing, a qubit or quantum bit is the basic unit of quantum information—the quantum version of the classical binary bit physically realized with a two-state device. A qubit is a two-state (or two-level) quantum-mechanical system, one of the simplest quantum systems displaying the peculiarity of quantum mechanics.
Quantum computing is a subfield of quantum information science— including quantum networking, quantum sensing, and quantum simulation—which harnesses the ability to generate and use quantum bits, or qubits. Quantum computers have the potential to solve certain problems much more quickly t
Topics History of Computing What are classical computers made of? Moore's Law (Is it ending?) High Performance computing Quantum Computing Quantum Computers Quantum Advantage The Qubit (Information in superposition) Information storage Different kinds of quantum computers Superconducting vs Ion Traps Annealing vs Universal/Gate quantum computers
Quantum computing with photons: introduction to the circuit model, the one-way quantum computer, and the fundamental principles of photonic experiments . quantum computing are presented and the quantum circuit model as well as measurement-based models of quantum computing are introduced. Furthermore, it is shown how these concepts can
Keywords—machine learning, quantum computing, deep learning, quantum machine intelligence I. INTRODUCTION There is currently considerable interest in quantum computing. In the U.S. in January 2019, the National Quantum Initiative Act authorized 1.2 billion investment over the next 5-10 years (Rep Smith, 2019). A quantum computing race is ongoing
According to the quantum model, an electron can be given a name with the use of quantum numbers. Four types of quantum numbers are used in this; Principle quantum number, n Angular momentum quantum number, I Magnetic quantum number, m l Spin quantum number, m s The principle quantum
Quantum effects - superposition, interference, and entanglement NISQ - Noisy Intermediate-Scale Quantum technology, often refers in the context of modern very noisy quantum computers QASM - Quantum Assembly used for programming quantum computers Quantum supremacy - demonstration of that a programmable quantum
AutoCAD Architecture) is now included with AutoCAD as a specialized toolset. It is built specifically to create and modify software-based design and documentation productivity for architects. Purpose-built architectural design tools help eliminate errors and provide accurate information to the user, allowing more time for architectural design. This study details the productivity gains that .
