Lecture notes on Quantum Computing

how quantum computing works and how quantum computing will change the world. quantum computing lecture notes pdf free download
Dr.DavidWllker Profile Pic
Dr.DavidWllker,United States,Professional
Published Date:11-07-2017
Your Website URL(Optional)
i QUANTUM COMPUTING Jozef Gruska QUANTUM WORLD CLASSICAL WORLD Quantum computation is Classical computation is deterministic probabilistic, sequential highly (exponentially) parallel working with real probabilities working with complex one of the outcomes of quantum superposition amplitudes M is randomly picked up - all other results unitary E of computation are irreversibly lost A E. S quantum T. computation U (evolution) R E Only at this point do indeterminacy and probabilities M come in E N T quantum measurement has the effect of ‘‘magnifying’’ quantum events from quantum to classical level .. described by Schrodinger equation using entanglement as a computational resourceChapter 1 FUNDAMENTALS INTRODUCTION The power of quantum computing is based on several phenomena and laws of the quantum world that are fundamentally different from those one encounters in classical computing: complex probability amplitudes, quantum interference, quantum parallelism, quantum en- tanglement and the unitarity of quantum evolution. In order to understand these features, and to make a use of them for the design of quantum algorithms, networks and processors, onehastounderstandseveralbasicprincipleswhich quantummechanicsisbasedon, aswell as the basics of Hilbert space formalism that represents the mathematical framework used in quantum mechanics. The chapter starts with an analysis of the current interest in quantum computing. It then discussesthe mainintellectual barriersthat hadtobe overcometo makea visionof the quantumcomputeranimportantchallengetocurrentscienceandtechnology. Thebasicand specific features of quantum computing are first introduced by a comparison of randomized computing and quantum computing. An introduction to quantum phenomena is done in three stages. First, several classical and similar quantum experiments are analysed. This is followed by Hilbert space basics and by a presentation of the elementary principles of quantum mechanics and the elements of classical reversible computing. LEARNING OBJECTIVES The aim of the chapter is to learn 1. the main reasons why to be interested in quantum computing; 2. the prehistory of quantum computing; 3. the specific properties of quantum computing in comparison with randomized com- puting; 4. the basic experiments and principles of quantum physics; 5. the basics of Hilbert space theory; 6. the elements of classical reversible computing. 12 CHAPTER 1. FUNDAMENTALS You have nothing to do but mention the quantum theory, and people will take your voice for the voice of science, and believe anything. Bernard Shaw (1938) Quantum computing is a big andgrowingchallenge,for both science and technology. Computations based on quantum world phenomena, processes and lawsofferradicallynew andverypowerfulpossibilitiesandleadto differentconstraintsthan computationsbasedonthelawsofclassicalphysics. Moreover,quantumcomputingseemsto havethepotentialtodeepenourunderstandingofNatureaswellastoprovidemorepowerful information processing and communication tools. At the same time the main theoretical concepts and principles of quantum mechanics that are needed to grasp the basic ideas, models and theoretical methods of quantum computing, are simple, elegant and powerful. This chapter is devoted to them. Introduction of the basic concepts in this chapter will be detailed and oriented mainly to those having no, or close to no, knowledge of quantum physics and quantum information processing. 1.1 Why Quantum Computing Do not become attached to things you like, do not maintain aversion to things you dis- like. Sorrow, fear and bondage come from one’s likes and dislikes. Buddha Quantumcomputingiswithoutdoubtoneofthehottesttopicsatthecurrentfrontiersof computing, orevenofthe wholescience. It soundsveryattractiveandlooksverypromising. There are several natural basic questions to ask before we start to explore the concepts and principles as well as the mystery and potentials of quantum computing. 1. Why to consider quantum computing at all? The development of classical computers is still making enormous progressand no end of that seems to be in sight. More- over, the design of quantum computers seems to be very questionable and almost surely enormously expensive. All this is true. However, there are at least four very good reasons1.1. WHY QUANTUM COMPUTING 3 for exploring quantum computing as much as possible. • Quantum computing is achallenge. A very fundamental and very natural challenge. Indeed,accordingtoourcurrentknowledge,ourphysicalworldisfundamentallyquan- tum mechanical. All computers are physical devices and all real computations are physical processes. It is therefore a fundamental challenge, and actually our duty, to explore the potentials, laws and limitations of quantum mechanics to perform infor- mation processing and communication. All classical computers and models of computers, see Gruska (1997), are based on classicalphysics(evenifthisisrarelymentionedexplicitly), andthereforetheyarenot fully adequate. There is nothing wrong with them, but they do not seem to explore fully the potential of the physical world for information processing. They are good and powerful, but they should not be seen as reflecting our full view of information 1 processing systems. Moreover, theoretical results obtained so far provide evidence that quantum compu- tation represents the first real challenge to the modern, efficiency oriented, version of the Church-Turing thesis: Any reasonable model of computation can be efficiently simulated by proba- bilistic Turing machines. • Quantumcomputingseemstobeamustandactuallyourdestiny. Asminiaturization of computing devices continues, we are rapidly approaching the microscopic level, where the laws of the quantum world dominate. By Keyes (1988), an extrapolation of theprogressinminiaturizationshowsthataround2020computingshouldbeperformed atthe atomiclevel. At that time, if the developmentkeepscontinuing ashitherto, one electronshouldbeenoughtostoreonebit,andtheenergydissipationof1kT ln2should 2,3 be sufficient to process one bit. Thus, not only scientific curiosity and challenges, but also technological progress requires that the resources and potentials of quantum 4 computing be fully explored. • Quantum computing is a potential. There are already results convincingly demon- strating that for some important practical problems quantum computers are theoret- ically exponentially more powerful than classical computers. Such results, as Shor’s factorization algorithm, can be seen as apt killers for quantum computing and have enormously increased activity in this area. In addition, the laws of quantum world, 1 At this point it should be made clear that quantum computers do not represent a challenge to the basic Church–Turing thesis concerning computability. They cannot compute what could not be computed by classical computers. Their main advantage is that they can solve some important computational tasks much more efficiently than classical computers. 2 In such a case it will be necessary to include in the design and description of computers quantum theory and such quantum phenomena as superposition and entanglement, to obtain correct predictions about computer behaviour. However, the clear necessity to go deeper into the quantum level for improving performanceofcomputersdoesnotimmediatelyimplythat thewaypursuedunderthecurrentinterpretation of the term “quantum computing” is the only one, or even the best one. 3 The single electron transistor is already under development, see page 313. 4 Atthesametimeoneshouldnotethatwhilequantumphysicshasbeenalreadyforalongtimeessentialto theunderstanding oftheoperationsoftransistorsandother keyelements ofmoderncomputers, computation remained to be a classical process. In addition, at the first sight there are good reasons for computing and quantum physics to be very far apart because determinism and certainty required from computations seem to be in strong contrast with uncertainty principle and probabilistic nature of quantum mechanics.4 CHAPTER 1. FUNDAMENTALS harvestedthroughquantumcryptography,canoffer,inviewofourcurrentknowledge, unconditional security of communication, unachievable by classical means. • Finally, the development of quantum computing is a drive and gives new impetus to explore in more detail and from new points of view concepts, potentials, laws and limitations of the quantum world and to improve our knowledge of the natural world. The study of information processing laws, limitations and potentials is nowadays in generala powerful methodologyto extend our knowledge,andthis seemsto be partic- ularly true for quantum mechanics. Information is being identified as one of the basic and powerful concepts of physics and quantum entanglement is an important commu- nication resource. Several profound insights into the natural world have already been 5 obtained on this basis. Remark 1.1.1 The above ideas are so new and important, that they deserve an additional analysis. Historically, the fundamental principles of physics first concerned the problems of matter—what things are made of and how they move. Later, the problems of energy started to be reflected in the leading principles of physics—how energy is created, expressed and transformed. As the next stage an alternative seems to be to look to information processing for a new source of fundamental principles and basic laws. For example, concerning the par- ticles, the questions of the movement of particles may be superseded by how particles can be utilized for information processing. Finally, let us observe some similarities between energy and information. Both of them have many representations, but basic principles, and also equations, hold independently of the form in which energy or information is presented. The increasing importance of information processing principles for current science has been first, correctly, reflected in the views and understanding (due to Landauer, 1991), that “information is physical” and in the corresponding changes of emphases on the essence and ways to deal with information processing problems. However, it could be the case that this is only the first step and perhaps even more fundamental changes in the principles of physics 6 could be obtained from the view that “physics is informational”. These new views of the role of information in quantum physics also bring new potentials, challenges and questions for quantum physics. Is the well known “weirdness” of the quantum world due to the fact that physical reality is governed by even more basic laws of the infor- mation processing world? Is quantum theory a theory of the physical or of the information world? Can the study of quantum information help to deal with the most basic problems quantum theory has? As an example of a change of research aims in physics under the influence of computer science research paradigms, consider quantum evolution. Traditionally, quantum physics 5 For example, manifestations of quantum nonlocality that go beyond entanglement (see Bennett et al. 1998),theuseofquantumprinciplesforsecuretransmissionofclassicalinformation(quantumcryptography), the use of quantum entanglement for reliable transmission of quantum states over a distance (quantum teleportation), the possibilityof preserving quantum coherence in the presence of irreversiblenoise processes (quantum error correction and fault tolerant computation). In addition, by Steane (1997), one has to realize that historically much of fundamental physics has been concerned with discovering fundamental particles of Nature and the equations which describe their motions and interactions. It now appears that a different program may be equally important. Namely, to discover the ways Nature allows, and prevents, information to be expressed and manipulated, rather than particles to move. 6 A lot of research is stillneeded to determine the position and real role information plays in physics. The extreme views go even so far that information is a physical quantity, similar as energy in thermodynamics (Horodecki, 1991, and Landauer, 1991, 1995), or even that information is deeper than reality—a substance that is more fundamental than matter and energy.1.1. WHY QUANTUM COMPUTING 5 has been concerned with the study or design of particular quantum systems and the study of various related fundamental problems. In addition to these problems quantum computing brought up new general and fundamental questions. Namely, what are the best, from well defined quantitative point of views, quantum evolutions to solve particular algorithmic or communication tasks. Or a problem of the maximum quantum computation power achievable in a quantum system of a certain dimension and disturbance level (Steane, 1998b), and of the way to reach such a maximum. New fundamental questions in quantum mechanics are raised also in connection with the following problem: how secure are, or can be, quantum cryptographic protocols? For example, the question how much information can be extracted from a quantum system for a given amount of expected disturbances? These questions are of fundamental importance far beyond quantum cryptography. To answer these questions, new theoretical insights and also new experiments seem to be needed. In addition, an awareness has been emerging also in the foundations of computing that fundamental questionsregardingcomputabilityand computationalcomplexityarein adeep 7 sense questions about physical processes. If they are studied on a mathematical level then the underlying models have to reflect fully the properties of our physical world. This in particular implies that computational complexity theory has to be, in its most fundamental 8 form, based on models of quantum computers. 2. Can quantum computers do what classical ones cannot? The answer de- pends on the point of view. It can be YES. Indeed, the simplest example is generation of random numbers. Quantum algorithms can generate truly random numbers. Deterministic algorithms can generate only pseudo-random numbers. Other examples come from the sim- ulation of quantum phenomena. On the other hand, the answer can be also NO. A classical computer can produce truly random numbers when attached to a proper physical source. 3. Where lie the differences between the classical and quantum information processing? Some of the differences have already been mentioned. Let us now discuss some others. Classical information can be read, transcribed (into any medium), duplicated at will, transmittedandbroadcasted. Quantuminformation,ontheotherhand,cannotbeingeneral read or duplicated without being disturbed, but it can be “teleported” (as discussed in Section 6.4). In classical randomized computing, a computer always selects one of the possible com- putation paths, accordingto a sourceof randomness,and “what-could-happen-but-did-not” 7 An understanding has emerged that each specific computation is performed by a physical system evolv- ing in time and, consequently, that one of the basic problems of computing, namely “what is efficiently computable?” is deeply related to one of the basic problems of physics, namely “which dynamical systems are physically realizable?” 8 The following citations reflect a dissatisfaction with the fact that the development of complexity theory ignored one of its most fundamental tasks. The fact that this had been so is in one way explainable but, in another way, hardly forgivable. A. Ekert (1995): Computers are physical objects and computations are physical processes. The theory of computation is not a branch of pure mathematics. Fundamental questions regarding computability and computational complexity are questions about physical processes that reveal to us properties of abstract entities such as numbers or ideas. Those questions belong to physics rather than mathematics. J.Beckman et al(1996): The theory of computation would be bootless if the computations that it describes could not be carried out using physically realizable devices. Hence it is really a task of physics to charac- terize what is computable, and to classify the efficiency of computations. The physical world is quantum mechanical. Therefore, the foundations of the theory of computation must be quantum mechanical as well. The classical theory of computation should be viewed as an important special case of a more general theory.6 CHAPTER 1. FUNDAMENTALS has no influence whatsoever on the outcome of the computation. On the other hand, in quantum computing, exponentially many computational paths can be taken simultaneously in a single piece of hardware and in a special quantum way and “what-could-happen-but- did-not” can really matter. Acquiring information about a quantum system can inevitably disturbs the state of the system. The tradeoff between acquiringquantum information and creating a disturbance of the system is due to quantum randomness. The outcome of a quantum measurement has a random element and because of that we are unable always faithfully infer the (initial) state of the system from the measurement outcome. Perhaps the main difference between classical and quantum information processing lies inthe factthatquantuminformationcanbe encodedin mutualcorrelationsbetweenremote partsofphysicalsystemsandquantuminformationprocessingcanmakeessentialuseofthis phenomena—calledentanglement—not available for classical information processing. Anotherbigdifferencebetweentheclassicalandquantumworldsthatstronglyinfluences quantum information processingstems fromthe fact that the relationship between a system anditssubsystemsisdifferentinthequantumworldthanintheclassicalworld. Forexample, the states of a quantum system composed of quantum subsystems cannot be in general decomposed into states of these subsystems. 4. Can quantum computers solve some practically important problems much more efficiently? Yes. For example, integer factorization can be done in polynomial time on quantum computers what seems to be impossible on classical computers. Searching in unordered database can be done provably with less queries on quantum computer. 5. Where does the power of quantum computing come from? On one side, quantum computation offers enormous parallelism. The size of the computational state space is exponential in the physical size of the system and the energy available. A quantum bit can be in any of a potentially infinite number of states and quantum systems can be simultaneously in superposition of exponentially many of the basis states. A linear number of operations can create an exponentially large superposition of states and, in parallel, an exponentially large number of operations can be performed in one step. Secondly, it is the branching and quantum interference that create parallel computation andconstructive/destructivesuperpositionsofstatesandcanamplifyordestroytheimpacts of some computations. Due to this fact, we can, in spite of the peculiarities of quantum measurements, utilize quantum parallelism. Thirdly, it is mainly the existence of so-called “entangled states” that makes quantum computing more powerful than classical and allows even very distant parts of systems to be strongly tied. This creates a base for developing and exploring quantum teleportation and other phenomena that are outside of the realm of the classical world. After all this excitement let us start to deal with more prosaic and “harder ”questions. 6. Where are the drawbacks and bottlenecks of quantum computing? There are, unfortunately, quite a few. Let us mention here only two of them. • Quantum computing can provide enormous parallelism. However, there are also enor- mous problems with harnessing the power of its parallelism. According to the basic principles of quantum mechanics, a (projection) measurement process can get out of (large) quantum superposition only one classical result, randomly chosen, and the remaining quantum information can be irreversibly destroyed.1.2. PREHISTORY OF QUANTUM COMPUTING 7 • An interaction of a quantum system with its environment can lead to the the so- calleddecoherenceeffects andcangreatlyinfluence, orevencompletelydestroy,subtle quantum interference mechanisms. This appears to make long reliable quantum com- putations practically impossible. 7. How feasible are (powerful) quantum computers and really important quantuminformationprocessingapplications? Itistooearlytogiveadefiniteanswer. On one side, there is a strong scientific belief, based on long term experiences of science, that something very important will come out of the research in quantum computing. Ontheotherhand,onehastoadmitthatmanyofthecurrentexcitingresultsconcerning quantum computing should be seen as Gedanken experiments. Namely, one works with systems (experiments) that perhaps do not exist, or cannot be performed in the real world, or only with enormous difficulty, but do not contradict any known law within a (certain) 9 consistent theory of quantum mechanics. Such considerations, systems and results are usually taken as being in principle acceptable. In addition, in the recent years quite impressive progress has been made on the experi- mental level and ways have been found to deal with many problems that seemed to prevent the utilization of the powerof quantum computing. Especially experimental quantum cryp- tography has made formidable progress to show that long distance optical fiber, open-air and even earth-satellites quantum key generation seems to be feasible. Finally, it seems quite safe to assume that either quantum computing will meet its expectations or something new and important will be learned and our knowledge of Nature will be enhanced. 8. Are not current computers quantum? No, in spite of the fact that current com- puters use elements, for example semiconductors, whose functioning cannot be explained without quantum mechanics. Current computers are in some very restricted sense quantum mechanical because everything can be seen as being quantum mechanical. In spite of that, current computers are not considered as fully quantum mechanical. The main difference between a classical and a quantum computer is on the information storage and processing level. Inclassicalcomputersinformationisrecordedinmacroscopictwo-levelsystems,called bits, representing two bit values. In quantum computers information is recorded and pro- cessed at microscopic level using two-level quantum systems, called quantum bits, that can be in any quantum superposition of quantum states corresponding to two classical bits. 9. Can quantum computers eventually replace classical ones? Nobody knows, but this does not seem to be so, at least not in the near future. Both classicaland quantum computers have their strongand weak points, and it seems currently that they can support, but not replace, each other. 1.2 Prehistory of Quantum Computing The past is but the beginning of a be- ginning, and all that is and has been is but the twilight of the dawn. Herbert Georg Wells (1866-1940) 9 The term “Gedanken experiment” is used in several meanings. Sometimes it is required that the corre- sponding systems or experiments are in principle possible. Sometimes it is sufficient that no physical law is known that would not allow such an experiment.8 CHAPTER 1. FUNDAMENTALS Since 1945we havebeen witnessing a rapid growthof the rawperformance of computers with respect to their speed and memory size. An important step in this development was the invention of transistors, which already use some quantum effects in their operation. However, it is clear that if such an increase in performance of computers continues, then 16 14 after 50 years, our chips will have to contain 10 gates and operate at a 10 Hz clock rate 30 10 (thus delivering 10 logic operations per second) . It seems that the only way to achieve that is to learn to build computers directly out of the laws of quantum physics. In order to come up seriously with the idea of quantum information processing, and to develop it so far and so fast, it has been necessary to overcome several intellectual barriers. The most basic one concerned an important feature of quantum physics—reversibility 11 (see Section 1.7). None of the known models of universal computers was reversible. This 12 barrier was overcome first by Bennett (1973), who showed the existence of universal re- versible Turing machines, and then by Toffoli (1980, 1981) and Fredkin and Toffoli (1982), 13 who showed the existence of universal classical reversible gates. The secondintellectual barrierwasovercomebyBenioff (1980,1982,1982a)whoshowed that quantum mechanical computational processes can be at least as powerful as classical computational processes. He did that by showing how a quantum system can simulate actions of the classical reversible Turing machines. However, his “quantum computer” was not fully quantum yet and could not outperform classical ones. The overcoming of these basic intellectual barriers had significant and broad conse- quences. Relations between physics and computation started to be investigated on a more general and deeper level. This has also been due to the fact that reversibility results im- 14 plied the theoretical possibility of zero-energycomputations. A Workshop on Physicsand Computation started to be organized and in his keynote speech at the first of these work- 15 shops, in 1981, R. Feynman (1982) asked an important question: Can (quantum) physics be (efficiently) simulated by (classical) computers? At the same time he showed good rea- sons to believe that the answer is negative. Namely, that it appears to be impossible to 10 Duetothesefacts,theconcernwasvoicedquiteawhileagoonthepossiblenegativeeffectsthatquantum phenomena could induce in the “classical” operations of computers. For example, what fundamental limits could Heisenberg’s uncertainty principle impose on memory chips whose bits are stored in single electron states? Thisapproach was later superseded, as we shall see, by more optimistic, more constructive and more ambitious aims to harness the power of quantum mechanics to perform computations. 11 Reversibility is actually not an exclusive phenomenon of the quantum world. Reversibility also occurs in the classical physics. It is only the physics of large systems (classical but also quantum) that is not reversible. The fact is that classical computationally reversible systems suggested by Bennett and others, as discussed later, were not practically realizable. This brought up the idea of considering quantum reversible information processing systems. 12 For earlier references see Section 9.5 in Appendix. 13 Bennett (1988) traces the need to think seriously about the thermodynamics of mental processes (and computation was thought of this way in the nineteenth century), back to the famous paradox of “Maxwell’s demon” from1871, which seemed to violate the second law of thermodynamics, see Appendix, Section 9.1.5. 14 Actually, the original motivation for studying the reversibility of computation came from the interest in determining the ultimate thermodynamic costs of elementary information processing operations, especially because heat removal has always been a major engineering concern in the design of classical computers, limiting the density with which active components could be packed. In the beginnings of the modern computer era there was a folklore belief, going back to a von Neumann’s lecture in 1949 (see Burks, 1966), that at least kT ln2 of energy is needed per bit operation. Attempts to prove this misleading folklore belief led Landauer to the discovery of reversible computing. 15 Richard P. Feynman (1918-1988), an American physicist. His main scientific contributions were in quantum electrodynamics and in the study of interactions of elementary particles. He gave a mathematical description of helium. Feynman received the 1965 Nobel prize for physics for his contributions to quantum electrodynamics. He has also been known for his extraordinary capabilities to explain physical phenomena and his lectures and textbooks represent an additional important contributions to modern physics.1.2. PREHISTORY OF QUANTUM COMPUTING 9 simulate a general quantum physical system on a probabilistic Turing machine without an 16 exponential slowdown . Moreover, he speculated that one could deal with the problem by allowing computers to run according to the laws of quantum mechanics. In other words, thatquantumcomputerscouldbeexponentiallymorepowerfulthanclassicalonesandcould be a first reasonable model of computation that does not obey the modern Church–Turing 17 thesis. The third intellectual barrier that had to be overcome was a lack of a proper model for a universal quantum computing device capable of simulating effectively any other quan- tum computer. The first step to overcome this barrier was done by Deutsch (1985) who elaborated Feynman’s ideas and developed a (theoretically) physically realisable model of quantum computers, a quantum physical analogue of a probabilistic Turing machine, which makes full use of the quantum superposition principle, and on any given input produces a random sample from a probability distribution. Deutsch conjectured that it might be more efficient than a classical Turing machine for certain computations. He also showed the existence of a universalquantum Turing machine (that could consequently simulate any physicalprocessandexperiment)andalsoamodelofquantumnetworks—aquantumanalog of classical sequential logical circuits. However, his model of the universal Turing machine had the drawback that the simulation of other quantum Turing machines (QTM), could 18 be exponential. This problem was then overcome by Bernstein and Vazirani (1993) and Yao (1993). They showed the existence of universal quantum Turing machines capable of simulating other quantum Turing machines in polynomial time. (For a full proof see Bern- stein andVazirani(1997).) The paperof BernsteinandVazirani(1993)laid the foundations of quantum complexity theory. In addition, Yao (1993) showed that QTM and quantum circuits compute in polynomial time the same class of functions. This result implies that the concept of quantum computation in polynomial time is robust enough and independent of the machine models. Inparallelwiththedevelopmentofthebasicmodelsofquantumcomputinganeffortwas put into overcomingthe fourth intellectual barrier. Can quantum computing be really more powerful than classical computing? Are there some good reasons to assume that quantum computingcouldbringanessential(exponential)speed-upofcomputationsforatleastsome importantinformationprocessingproblems? Thiswasaveryimportantissuebecauseitwas clear that any design of a quantum computer would require overcoming a number of large scientificandengineeringbarriersandthereforeitwasneededtoknowwhethertheproposed model of quantum computer offers, at least theoretically, any substantial benefit over the classical computers. Inspiteofthefactthatthisproblemhasnotyetbeencompletelyresolvedthereisalready strong evidence that this is so. It was first shown by Deutsch and Jozsa (1992), that there are problems unknown to be in P that could be solved in polynomial time on quantum computers, and therefore belongtotheclassQEPofproblemssolvablewithcertaintyinpolynomialtimeonquantum computers. By recasting the original Deutsch–Jozsa problem, in the framework of so-called 16 Actually, thisisnowadays intuitivelypretty obvious becauseninteracting 2-state quantum systems may n have up to 2 basis states. 17 R. Freivalds called my attention to the fact that Yu. Manin already in 1980 in his book “Computable and uncomputable” pointed out explicitly the potential advantages of quantum computing (exponential number of basis states to work with simultaneously) and emphasized a need to design a theory of quantum automata that would be abstract enough and would have a proper balance between mathematical principles and fundamental principles of quantum mechanics without specification of some physical realizations. 18 Deutsch centered his attention on the computability and not on complexity issues.10 CHAPTER 1. FUNDAMENTALS “promise problems”, Berthiaume and Brassard (1992, 1992a, 1992b, 1994) proved the first separation results in the relativized quantum complexity theory. For example, they showed A A that there is an oracle A such that QEP 6⊂ ZPP —they proved the existence of an oracle for which there are computational problems that QTM can solve in polynomial time with certainty, but eachprobabilisticTuring machine to solvethese problems with certainty needs exponential time for some inputs. These results were first improved by Bernstein and Vazirani (1993) and later by Simon (1994). He proved the following result that was at that time the strongest argument in favor of the superiority of quantum computers over classical ones. Theorem 1.2.1 There exists an oracle relative to which there is a problem solvable in poly- nomial time (with bounded error probability) on a quantum computer, but any probabilistic Turing machine with bounded error probability solving this problem (using the oracle) will n/2 require exponential time (at least 2 steps) on infinitely many inputs (of length n). Results of Bernstein and Vazirani (1993) and Simon (1994)provide formal evidence that, in 19 the relativized setting, QTM are more powerful than PTM. However, all these problems were quite artificial. Very important and much needed steps along these lines have been the results of Shor (1994, 1997) who, building on the works of the above mentioned authors, especially on Simon’s method, showed how to factor integers, and how to compute discrete logarithms in polynomial time on potential quantum computers—two problems of crucial importance for public-key cryptography. Duetotheseresultsquantumcomputing, thattillthenusedtobeconsideredasacurios- ityforfewvisionaries,startedtobeofbroaderscientific, andnotonlyscientific,interest. An intensive search started to discover physical principles and processes that could eventually make quantum computation practical. Moreover, several groups of experimental physicists around the world have begun projects to explore experimentally the basic principles of quantum computing. Thenextquestiontoaddresswaswhetheronecanbuildapracticallysuccessfulquantum computer. Could quantum computingbe broughtfrom avisionarystagetoan experimental stage (and later to an engineering stage)? This question is still to be answered. An intensive effort to deal with quantum computer design problems has brought some remarkable success, but also revealed new problems. On one hand success came in an unexpected area. Quantum cryptography—in which 20 one tries to exploit quantum phenomena to transmit quantum information in such a way that undetectable eavesdropping is impossible, has already reached an experimental stage. There has also been success in the effort to find sufficiently simple reversible quantum gates that could be used to build potential quantum computers. The classicaluniversal reversible gates have three inputs and outputs. Sleator and Weinfurter (1995), Barenco (1995) and DiVincenzo(1995)haveshownuniversaltwobitquantumgates. Thishasbeenanimportant result because the problem to control interaction of three particles seems to be much more complexthanforthecaseoftwoparticles. Inaddition,Barenco(1995)andLloyd(1995)have shown that almost any quantum two-bit gate is universal. These results greatly simplified the search for physical implementations of quantum computational networks. On the other hand, it has also turned out that the first models of quantum computers were oversimplified and that for quantum computing to come to an experimental or even 19 However, itisnecessary tomake clearthat the question whether quantum computers allowone toobtain essentially more computational power has not yet been completely satisfactorily answered. 20 Heisenberg’s uncertainty principle—see Section PREHISTORY OF QUANTUM COMPUTING 11 engineering stage many fundamental problems still need to be solved. The necessity of examining impacts of inaccuracies, emissions and coupling with the environment of any realistic device on the capability of quantum computing to meet their promises has long been emphasized by Landauer (1994). Especially problems decoherence causes made many to believe that it is in principle impossible to design reliably enough functioning quantum 21 computer. The situation started to look almost hopeless. A breakthrough came after overcoming anotherintellectualbarrier: itwasrealisedthatthesituationisnotasbadasitlooksandthat physicsdoesnotneedtorelyonitselfonlyinthesearchforhowtoovercomeproblemsofthe imperfections of operations, emission and of the decoherence. Mathematics and informatics seem to be able to help significantly. The first important and encouraging result was due to Bernstein and Vazirani (1993). They showed that quite weak precision requirements are sufficient for quantum computing—only logarithmic precision for inputs and gates is needed. Discovery of error-correcting codes by Shor (1995), and soon by many others, allowed one to cope with decoherence and operational imperfections during transmission and storage of quantum information. (In behind there was a key discovery that quantum noise/errors, in principle continuous, can be viewed and dealt with as being discrete.) The discovery of quantum fault-tolerant computations by Shor (1996) allowed one to cope with 22 decoherenceandimprecisionsduringprocessingofquantuminformation. Thediscoveryof “concatenatedcodes”(KnillandLaflamme,1996)and“quantumrepeaters”(Briegel,1998), allows one to cope with the problem of storage and transmission of quantum information for a long time and long distance with desirable reliability. Quantum cryptography has also contributed to an awareness that quantum computing is full of pitfalls, not fully understood yet. In 1993, Brassard, Cr´epeau, Jozsa and Langlois surprised the community by the claim (proof) that a quantum bit commitment protocol provably unbreakable by both parties is possible. It took three years to find out, by Lo and Chau (1997, 1997a) and Mayers (1998), that proposed protocols are, in principle, insecure. Another intellectual barrier was overcome by contributions of Cirac and Zoller (1995). They showed, at least on the laboratory level, that in the search for technology to build quantum processors and computers one does not need to wait till some “unobtainium” is available, but that one can start with the existing technologieswith which there are already richexperimentalexperiences. (Ofcourse,thisisnotthewholestory. Onealsohastorealize that even if it might be possible to build small quantum computers, scaling up to machines largeenoughtomakereallyimportantcomputationscouldpresentfundamentaldifficulties.) 21 Pessimism that technology cannot be made reliable enough to realize useful computations is not a new phenomenon intheshorthistoryofmoderncomputers. Forexample,intheautobiography ofK.Zuse(1984), there is a story about sceptical reactions to his talk in 1938 in which he anticipated -based on discussions with Schreyer-that about 2000 tubes would be needed to build an electronic computer. (At that time the biggest electronic devices were broadcasting stations with few hundreds of valves.) Similarly, the idea that ENIACwithits16000tubescouldworkforasufficientlylongtimewasforthattimeanenginneringphantasy that would hardly get through a granting agency of “peace time”. 22 Actually Landauer’s constant challenge of “visionaries” to show a really workable path to the future has been of immense significance for making correct research agenda in quantum computing. Quantum computing is an excellent example of the rapid progress in science and technology that can be achieved by optimists and visionaries if they closely cooperate with, and listen to, sceptics and pessimists directing constructively the effort of visionaries and optimists on the key problems to attack.12 CHAPTER 1. FUNDAMENTALS 1.3 From Randomized to Quantum Computation 23 A comparison of probabilistic Turing machines (PTM), with quantum Turing machines (QTM) will allow us to see, in an easy and transparent way similarities and differences between these two basic models of classical and quantum computing. In this way we can also demonstrate the advantages and problems quantum computing has. There are good reasons to start our introduction to quantum computing by compar- ing probabilistic and quantum Turing machines. Probabilistic Turing machines represent nowadays the most important model of classical computing. Polynomial time computation on probabilistic Turing machines stands for a formal equivalent of “feasibility” in classical computing. In addition, similarly to classical Turing machines, quantum Turing machines were historically the first really fully quantum and powerful model of quantum computing. 1.3.1 Probabilistic Turing machines Formally, a (one-tape)probabilistic Turing machine, on a finite setQ of states and the finite alphabet Σ, is given by a transition function δ : Σ×Q×Σ×Q×←,↓,→−→0,1 24 assigningtoeachpossibletransitionaprobabilityinsuchawaythatforeachconfiguration c andallitssuccessor-configurationsc ,...,c ,thefollowinglocalprobabilitycondition 0 1 k is satisfied: Ifp , 1≤i≤k, is the probability, assigned byδ, of the transition fromc toc , i 0 i then (see Figure 1.1a): k X p =1. i i=1 This condition is often written in the following form: if (σ ,q )∈ Σ×Q, then 1 1 X δ(σ ,q ,σ,q,d) =1. 1 1 (σ,q,d)∈Σ×Q×←,↓,→ On the base of the transition function δ of a PTMM we can assign probabilities to all edges, to all nodes and also to all configurationsof each level of any configuration tree ofT. ′ Theprobabilityassignedtoanedgec→c ofsuchatreeisgivendirectlybyδ andrepresents ′ the probability that computation goes, in one step, from c to c . From that we can assign a probability to each node N of any configuration tree, see Figure 1.2a, as the product of all probabilities assigned to the edges on the path from the root to N. (The probability assigned to the root is defined to be 1.) The probability assigned to an arbitrary nodeN is therefore the probability that a computation starting at the root reaches the node N. Itmayhappenthatatacertainlevelofaconfigurationtreethereareseveraloccurrences (1) (m) c ,...,c of the same configuration c, see Figure 1.3a. In such a case, if p is the i 23 Alan M.Turing (1912-1954) an English mathematician. He wrote fundamental papers on computability and artificial intelligence and invented a computation model bearing his name. During the Second World War Turing participated in the cryptanalysis project ULTRA in Bletchley Park and in the design of the first powerful electronic computer Colossus. After the war he supervised the design and building of ACE, a large electronic digital computer at the National Physical Laboratory. 24 A configuration is a full description of the global state of a PTM. It can be seen as having the form w qw , wherew w is the current content of the tape, q is the current state and the current position of the 1 2 1 2 head of the PTM is on the cell with the first symbol of w . 21.3. FROM RANDOMIZED TO QUANTUM COMPUTATION 13 c c 0 0 p p p p α α α α 1 2 k-1 k 1 2 k-1 k c c c c c c c c 1 2 1 2 k-1 k k k-1 2 2 2 2 p + p + .... + p + p = 1 α + α +.....+ α + α = 1 2 k 1 k-1 2 k-1 k 1 (a) PTM (b) QTM Figure 1.1: Local probability conditions (i) probability assigned to the occurrencec of the configurationc, then the total probability that the configurationc occurs at that level of the configuration tree is given by the sum m X p . i i=1 Now, if c ,...,c are all distinct configurations occurring at a certain level of the con- 1 k figuration tree, andp ,...,p are their global probabilities of occurrence at that level, then 1 k the following global probability condition has to be satisfied: k X p =1. i i=1 1 1 1 2 2 2 2 0.5 0.5 2 2 2 2 0.5 0.5 2 2 2 2 2 2 0.5 2 2 2 2 2 2 0.5 0.5 c d d c a b b c 0.25 0.25 0.25 0.25 0.5 0.5 0.5 -0.5 0.5 0.5 0.5 0.5 (a) PTM (b) QTM (c) invalid computation Figure 1.2: Configuration trees with probabilities and the probability amplitudes14 CHAPTER 1. FUNDAMENTALS (2) (1) (2) (m) (1) (m) c c c c c c p p p α α α m 1 2 1 2 m (a) PTM (b) QTM Figure 1.3: Multiple occurrences of the same configuration Exercise 1.3.1 Show that if a PTM satisfies the local probability condition, then it also satisfies the global probability condition. The local probability condition can also be seen as assigning to each configuration a “linear superposition” of successor configurations F(c)=p c +p c +...+p c , 1 1 2 2 k k P k with p = 1, where F is some kind of “global transition function” of T and p is the i i i=1 25 probability of having c as the next configuration of c. Let us now consider any superpo- i P P k k sition p c of configurations with p = 1. If we replace, in such a superposition, i i i i=1 i=1 any particular configurationc by the superposition of its successorconfigurations, as above, and make corresponding multiplications by constants and corresponding additions, we get again a superposition of configurations with coefficients summing up to 1. All this implies that the transition function δ of a PTMM actually determines a so- called transition matrix M , rows and columns of which are labeled by configurations M ofM (and therefore the matrix can be infinite) and M (i,j) is the probability that the M configurationc is the successor configuration ofc . Such a transition matrix clearly has all i j entries nonnegative and the sum of its entries in each column is 1. In this case, if we multiply M with a column vector of the same dimension and only M nonnegative elements, the sum of which is 1, we get again a column vector with only non- negative elements the sum of which is 1. We can therefore seeM as a mapping that maps M any superposition of configurations satisfying the global probability condition to another superposition of configurations satisfying again the global probability condition. The time evolution of a probabilistic Turing machineM can therefore also be described by a sequence of probability distributions, representedby superpositions, which begins with 25 This assignment of linear superpositions to PTM has no real meaning for PTM but helps us to make a better analogy with QTM.1.3. FROM RANDOMIZED TO QUANTUM COMPUTATION 15 thesuperpositioncontainingonlytheinitialconfiguration,andsuchthattheithdistribution providesthelikelihoodofeachpossibleconfigurationafterthe(i−1)ststepoftheevolutionof M. Eachnextsuperposition(probabilitydistribution)canbeobtainedfromthepreviousone by multiplying with the matrixM . The matrixM can thereforebe seen as representing M M the evolution of the PTMM. In each particular computation of a PTM only one path is taken from the whole set of paths of the configurationtree, in accordancewith the assigned probabilities. To simulate a PTM we need therefore to keep track of only a constant amount of information. We could also imagine a PTMM as being put into a box with a glass top through which we could watch (not influence) the particular steps taken byM, one after another. At the end of the computation we could see the result obtained. A PTM computation can therefore be observed and the act of their observation has no effect on its further computation. (Why should it have?) Concerningtheoutcomes,aPTMcanbeseenasdefiningarandomsample,aprobability distribution on the final configurations for each initial configuration. InordertostudythecomputationalpowerofPTMweneedtoimposesomerestrictionon the probabilities allowed. Otherwise one could hide hard-to-compute numbers or properties into them. It is well known that in order to study computational complexity problems of 1 ,1. randomized computing, it is sufficient to allow only probabilities from the set0, 2 After this lengthy review of probabilistic Turing machines and their behaviour we are in a better position to discuss quantum Turing machines and their behaviour. 1.3.2 Quantum Turing machines Formally, a (one-tape) quantum Turing machine, with a finite set Q of states and the finite alphabet Σ, is given by a transition function δ :Σ×Q×Σ×Q×←,↓,→−→C 0,1 assigning a so-called amplitude (or probability amplitude)—a complex number, the absolute value of which is in the interval 0,1—to each transition in such a way that for 26 each configuration c and all its successor configurations c ,...,c the following local 0 1 k probability condition is satisfied: if α is the amplitude assigned to the transition from i c to the configurationc , then (see Figure 1.1b) 0 i k X 2 α =1 i i=1 2 and thereforeα canbe seen (and will be seen)asa probabilityof transitionfromc toc . i 0 i However, as discussed later, this is not the only condition a transition function of a QTM has to satisfy. The transition function of a QTM can be used to assign amplitudes (not probabilities) also to all edges, nodes and all configurations of the same level of a configuration tree. The amplitude assigned to an edge is given directly by δ. The amplitude assigned to a node is the product of the amplitudes assigned to all edges on the path from the root to that node, assuming again that the amplitude 1 is assigned to the root (see Figure 1.2b). As for the case of PTM, let us assume that at a particular level of the configuration (1) (2) (m) tree there are several occurrences, say c ,c ,...,c , of the same configuration c. (See 26 The concept of configuration is defined in a similar way as for PTM.16 CHAPTER 1. FUNDAMENTALS (i) Figure 1.3b). Let nowα be the amplitude of the configurationc at that level. In such a i case the total amplitude of c at that level is defined to be m X β = α. i i=1 SofarallthatlooksquitesimilartothecaseofPTM.Theonlydifferencebeingthatinthe case of PTM we have worked with probabilities and now we are working with (probability) amplitudes. An essential difference between PTM and QTM concerning their computations comes now. If c ,c ,...,c are all mutually different configurations at a certain level of 1 2 k the configuration tree, then their total amplitudes β ,...,β have to satisfy the following 1 k global probability condition k X 2 β =1, i i=1 2 andβ is said to be the probability of the occurrence of the configurationc at that level i i of computation. It is not true that if a QTM satisfies all local probabilityconditions, then it also satisfies all global probability conditions. A counter example is shown in Figure 1.2c. Whatdoesallthisactuallyimply? Asweshallseesoon,thewayprobabilitiesareassigned toconfigurationsatparticularlevelsofcomputationsrepresentsanenormousdifferencewith respect to the case of PTM. Indeed, one of the important consequences is the existence of constructive and destructive interferences. Exercise 1.3.2 If α, β are complex numbers, then 2 2 2 α+β =α +β +2αβcosθ, whereθ is the angle which the vectorsα andβ subtend at the origin of the complex plane. 2 Analyse the value ofα+β for cases: (a) α=β; (b) α=−β; (c) α=iβ. Itmayhappen, thatfortheamplitudesα ,...,α ofalloccurrencesofaconfigurationat 1 k P P k k 2 2 a level of the configurationtree the following inequality holds: α α and i i i=1 i=1 in suchcaseswespeakaboutpositiveinterference oraboutconstructive interference. For example, the configurationd in the configuration tree in Figure 1.2b has at the last 1 1 level two occurrences, each with the amplitude , and therefore with the probability . 2 4 1 However, the total probability that this configuration occurs at that level is actually ( + 2 1 1 1 2 ) =1, and therefore not 2× but 4× , twice as much than it would seem. 2 4 4 P P k 2 2 It may also happen that α α . In such a case we speak aboutnegative i i i=1 interference or destructive interference. For example, the configurationc in the configuration tree in Figure 1.2b has two occur- 1 1 rences, one with the amplitude , second with the amplitude− . Their sum is therefore 0. 2 2 Thisimplies, inspite ofthe fact thattherearetwopathsleadingtothe configurationc, that the probability that c occurs at that level is 0 The total probabilityof the occurrenceof a configurationata step of computation is the probability that an observer will get that configuration as the result of the computation at that level (if an observation is performed). If such a probability is 0, there is no way to get the results, in spite of the fact there are computational paths leading to them Why is that1.3. FROM RANDOMIZED TO QUANTUM COMPUTATION 17 so? This is surely puzzling. But this is the way quantum world is. Such are the rules that say how much and which information one can get from the quantum world to the classical world by an “observation” or a “measurement”—one of the most puzzling phenomenon of quantum physics, to be discussed in moredetail in the Sections 1.4.3,1.5.3and 1.6.2 aswell as in Appendix, Section 9.1.4. From the fact that we can have positive and negative interferences, one of the basic tricks of quantum computing follows. One has to program quantum computers in such a way that correct and desirable answers, due to positive interference, have large probability, and incorrect, or not desirable answers, due to destructive inference, have very small, or zero, probability. What does this all imply? Is there some other condition, more transparent than the global probability condition a quantum Turing machine has to satisfy? Yes, there is. In the same way as for PTM, to each QTMM we can associate a matrix M of M configuration transitions such thatM (i,j) is the amplitude of having the configurationc M i as the successor configuration of the configurationc . Entries ofM are therefore complex j M numbersandthelocalprobabilityconditionimpliesthatEuclideannormofitscolumnvector is 1. For a QTMM it has to hold that the matrixM is unitary, i.e., ∗ ∗ M M =M M =I, M M M M ∗ whereM istheconjugatetransposeofM , i.e. thetranspositionofM andconjugation M M M of its elements, andI is the unit matrix.       0 1 0 −i 1 0 σ = σ = σ = x y z 1 0 i 0 0 −1 (a) (b) (c)   1 1 √ √ 1 1−i 1+i 2 2 1 1 √ √ − 1+i 1−i 2 2 2 (d) (e)     iα i(α−θ) icosθ sinθ e cosθ −ie sinθ i(α+θ) iα sinθ icosθ −ie sinθ e cosθ (f) (g) Figure 1.4: Examples of unitary matrices of degree 218 CHAPTER 1. FUNDAMENTALS Exercise 1.3.3 (a) Show that if A and B are unitary matrices of the same dimension,   A 0 thenthe matrix is also unitary: (b) Show that ifAandB are unitarymatrices 0 B of the same dimension, then so is the matrix A·B. 2 2 2 Exercise 1.3.4 Show the following properties of Pauli matrices: (a) σ =σ =σ =I; x y z (b) σ σ =iσ , where (k,l,m) is a cyclic permutation of (x,y,z); (c) all Pauli matrices k l m have eigenvalues 1 and−1. Therequirementof unitarityis farfromobvious. Examplesofunitarymatricesofdegree 27 28 two, including Pauli matrices , are shown in Figure 1.4 . A general form of the unitary matrix of degree two can be found on page 64. It can be shown that if the transition matrix of a QTM is unitary, then all global probability conditions are satisfied. Another important consequence of unitarity is that eachQTM is reversible(and the same is true for eachquantum evolution). This means that from a given superposition of configurations in a step of a computation we can uniquely deduce the superposition of configurations in the previous step. Exercise 1.3.5 (a) Verify the unitarity of the matrices shown in Figure 1.4; (b) show 2 2 the unitarity of any n×n matrix A with Ai,j = if i =6 j and Ai,i =−1+ , for n n any 1≤i≤n. Exercise 1.3.6 Show that: (a) the determinant of any unitary matrix is±1; (b) all unitarymatrices ofadegreen form agroup, with respecttomultiplication, usuallydenoted U(n); (c) all unitary matrices of degree n and with determinant equal to 1 also form a ∗ group, usually denotedSU(n); (d) all eigenvalues of unitarymatrices have absolute value 1. Another essential difference between a PTM and a QTM could be seen when we would try “to observe” the evolution of a QTM and to find out the results of its computations. In the case of a PTM, at each particular computation a single path through the config- uration tree has to be chosen, and we could watch (though not influence) the path being taken. Theresultwouldbeobtainedwiththeprobabilityattachedtothefinalconfiguration. On the other hand, a QTM always follows all paths of the configuration tree simultane- ously Sincethenumberofnodesatthelevelsofaconfigurationtreecangrowexponentially, this means that a QTM can, simultaneously, take an exponentially large number of paths and can be, at particular steps of computation, in a superposition of exponentially many configurations (with respect to the number of computational steps), at the same time In addition, the computational evolution of a QTM, and of any quantum computation, is fully determined by its unitary matrix and it is deterministic. 27 Wolfgang Pauli (1900–1958), an American physicist of Austrian origin, with positions in Hamburg, Zu¨rich and Princeton. He received the 1945 Nobel prize for his exclusion principle (formulated in 1924), according towhichnotwo electronsinanatom maybeinthe samequantum state. In1930 Pauliderivedthe existence of the neutrino, before it was experimentally observed. He also made fundamental contributions in quantum electrodynamic, quantum field theory and paramagnetism. 28 Matrices σ ,σ and σ are called Pauli matrices and they play an important role in the theory of x y z 1 spin- electrons. They were introduced by W. Pauli in 1927 to describe angular momentum and magnetic 2 momentum of electrons.1.4. HILBERT SPACE BASICS 19 Moreover,thereis noway“towatch”the computationsofaQTM.We could“put itinto a box and let it run” but we cannot watch it, or open the box before computation is done— at least not without serious consequences. This would be an observation (a measurement) and, accordingto the laws of quantum mechanics, it could immediately lead to a disruption of the computation and could result in a loss of (quantum) information At the end of the computation we can try to observe (measure) the result. However we can not get in general the whole resulting superposition of configurations. Only one of them, randomly chosen, with the probability determined by the corresponding global amplitude. In addition, once such information is obtained, all other results of the computation (all other configurations) are irreversibly lost. Finally, it is only at this point, in general, in a measurement, or an observation, where probabilities and indeterminancy enter quantum computation. A QTM can therefore get in linear time an exponential number of results, but unfortu- nately we cannot read them all out. (Disappointing, but this is the way it is. In spite of that, QTM can be more efficient than classical ones.) This seems to imply that we actually cannot get more with a QTM than with a proba- bilistic Turing machine that would provide us, randomly, with one result Fortunately, this is not true. There are sometimes clever ways to make a QTM use its enormous parallelism to get to the single needed result, with a high probability, which seems not to be obtainable efficiently without this quantum parallelism. This is, however, not a simple task, what will be demonstrated in Section 3.2. Both PTM and QTM produce their results with certain probabilities. Therefore they actually define probability distributions on possible outputs. In order to study the computational power of a QTM we also need to make some re- striction on the probability amplitudes allowed. Otherwise one could hide hard-to-compute numbers or properties into them. It has been shown, as discussed in Chapter 5, that in ordertostudythe computationalcomplexityproblemsofquantumcomputing itissufficient 4 3 3 4 to allow only amplitudes from the set−1,− ,− ,0, , ,1. 5 5 5 5 Remark 1.3.7 Figure1.5summarizes,veryinformally,themainfeaturesofclassicalversus quantumcomputations. AsweshallseeinSection1.6,quantumcomputation,asdetermined byquantumevolutiononly,isadeterministicprocess,contradictingwidespreadnaivebeliefs, and probabilities appears only when “creatures” of the classical world try “to observe” the outcomes of quantum processes. On the other hand, modern complexity theory considers probabilistic computations as the main mode of efficient computing. It is one of the profound problems in science to determine what classical and quantum worlds actually are and where a borderline between them is—if there is any. Interesting enough, even some of the founders of quantum mechanics have been very careful about it. Forexample,Bohravoidedtoreferringexplicitlytotwotypesofworlds. Heonlyemphasized a need to use two different languages to talk about quantum and classical phenomena. 1.4 Hilbert Space Basics The whole science is nothing more than a reformulation of everyday thinking. Albert Einstein: Physics and reality (1936)

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.