REPORT ON QUANTUM COMPUTER

CLICK HERE TO DOWNLOAD REPORT ON QUANTUM COMPUTER

QUANTUM COMPUTER   Report Transcript

INTRODUCTION- Combining physics, mathematics and computer science, quantum computing has developed in the past two decades from a visionary idea to one of the most fascinating areas of quantum mechanics. The recent excitement in this lively and speculative domain of research was triggered by Peter Shor (1994) who showed how a quantum algorithm could exponentially "speed-up" classical computation and factor large numbers into primes much more rapidly (at least in terms of the number of computational steps involved) than any known classical algorithm. Shor's algorithm was soon followed by several other algorithms that aimed to solve combinatorial and algebraic problems, and in the last few years theoretical study of quantum systems serving as computational devices has achieved tremendous progress.

Common belief has it that the implementation of Shor's algorithm on a large scale quantum computer would have devastating consequences for current cryptography protocols which rely on the premiss that all known classical worst-case algorithms for factoring take time exponential in the length of their input (see, e.g., Preskill 2005). Consequently, experimentalists around the world are engaged in tremendous attempts to tackle the technological difficulties that await the realization of such a large scale quantum computer. But regardless whether these technological problems can be overcome (Unruh 1995, Ekert and Jozsa 1996, Haroche and Raimond 1996), it is noteworthy that no proof exists yet for the general superiority of quantum computers over their classical counterparts. A classical computer has a memory made up of bits, where each bit represents either a one or a zero. A quantum computer maintains a sequence of qubits. A single qubit can represent a one, a zero, or, crucially, any quantum superposition of these; moreover, a pair of qubits can be in any quantum superposition of 4 states, and three qubits in any superposition of 8. The history of computer technology has involved a sequence of changes from one type of physical realisation to another --- from gears to relays to valves to transistors to integrated circuits and so on. Today’s advanced lithographic techniques can create chips with features only a fraction of micron wide. Soon they will yield even smaller parts and inevitably reach a point where logic gates are so small that they are made out of only a handful of atoms. On the atomic scale matter obeys the rules of quantum mechanics, which are quite different from the classical rules that determine the properties of conventional logic gates. So if computers are to become smaller in the future, new, quantum technology must replace or supplement what we have now.

The point is, however, that quantum technology can offer much more than cramming more and more bits to silicon and multiplying the clock--speed of microprocessors. It can support entirely new kind of computation with qualitatively new algorithms based on quantum principles! WHAT IS QUANTUM IN QUANTUM COMPUTER? One of the embarrassments of quantum computing is the fact that, so far, only one algorithm has been discovered, namely Shor's, for which a quantum computer is significantly faster than any known classical one. It is almost certain that one of the reasons for this scarcity of quantum algorithms is related to the lack of our understanding of what makes a quantum computer quantum (see also Preskill 1998 and Shor 2004). As an ultimate answer to this question one would like to have something similar to Bell's (1964) famous theorem, i.e., a succinct crispy statement of the fundamental difference between quantum and classical systems,

encapsulated in the non-commutative character of observables. Quantum computers, unfortunately, do not seem to allow such simple characterization. Observables—in the quantum circuit model there are only two, the preparation of the initial state and the observation of the final state, in the same basis, and of the same variable, at the end of the computation—are not as important here as in Bell's case since any measurement commutes with itself. The non-commutativity in quantum computing lies much deeper, and it is still unclear how to cash it into useful currency. Quantum computing skeptics (Levin 2003) happily capitalize on this puzzle: If no one knows why quantum computers are superior to classical ones, how can we be sure that they are, indeed, superior? The elusive character of the physical resource responsible for the quantum "speed-up" can be nicely demonstrated with the following example. Consider a solution of a decision problem, say satisfiability, with a quantum algorithm based on the circuit model. What we are given here as input is a proposition in the propositional calculus and we have to decide whether it has a satisfying truth assignment. As Pitowsky (2002) shows, the quantum algorithm appears to solve this problem by testing all 2n assignments "at once", yet this quantum ‘miracle’ helps us very little since any measurement performed on the output state collapses it,

and if there is one possible truth assignment that solves this decision problem, the probability of retrieving it is 2-n, just as in the case of a classical probabilistic Turing machine which guesses the solution and then checks it. Pitowsky's conclusion is that in order to enhance computation with quantum mechanics we must construct ‘clever’ superpositions that increase the probability of successfully retrieving the result far more than that of a pure guess. Shor's algorithm and the class of algorithms that evaluate a global property of a function (this class is known as the hidden subgroup class of algorithms) are (so far) a unique example of both a construction of such ‘clever’ superposition and a retrieval of the solution in polynomial time. The quantum adiabatic algorithm may give us similar results, contingent upon the existence of an energy gap that decreases polynomially with the input. WHAT IS QUIBIT? From a physical point of view a bit is a physical system which can be prepared in one of the two different states representing two logical values --- no or yes, false or true, or simply 0 or 1. Quantum bits, called qubits, are implemented using quantum mechanical two state systems; these are not confined to their two basic states but can also exist in superpositions: effectively this means that the qubit is both in state 0 and state 1. The Bloch Sphere QUANTUM GATE- Classical computational gates are Boolean logic gates that perform manipulations of the information stored in the bits. In quantum computing these gates are represented by matrices, and can be visualized as rotations of the quantum state on the Bloch sphere. This visualization represents the fact that quantum gates are unitary operators, i.e., they preserve the norm of the quantum state (if U is a matrix describing a single qubit gate, then U†U=I, where U† is the adjoint of U, obtained by transposing and then complex-conjugating U). As in the case of classical computing, where there exists a universal gate (the combinations of which can be used to compute any computable function), namely, the NAND gate which results from performing an AND gate and then a NOT gate, in quantum computing it was shown (Barenco et al., 1995) that any multiple qubit logic gate may be composed from a quantum CNOT gate (which operates on a multiple qubit by flipping or preserving the target bit given the state of the control bit,

an operation analogous to the classical XOR, i.e., the exclusive OR gate) and single qubit gates. One feature of quantum gates that distinguishes them from classical gates is that they are reversible: the inverse of a unitary matrix is also a unitary matrix, and thus a quantum gate can always be inverted by another quantum gate. The CNOT Gate Unitary gates manipulate the information stored in the quantum register, and in this sense ordinary (unitary) quantum evolution can be regarded as computation (DiVicenzo 1995 showed how a small set of single-qubit gates and a two-qubit gate is universal, in the sense that a circuit combined from this set can approximate to arbitrary accuracy any unitary transformation of n qubits). In order to read the result of this computation, however, the quantum register must be measured.

The measurement gate is a non-unitary gate that "collapses" the quantum superposition in the register onto one of its terms with the corresponding probability. Usually this measurement is done in the computational basis, but since quantum mechanics allows one to express an arbitrary state as a linear combination of basis states, provided that the states are orthonormal (a condition that ensures normalization) one can in principle measure the register in any arbitrary orthonormal basis. This, however, doesn't mean that measurements in different bases are efficiently equivalent. Indeed, one of the difficulties in constructing efficient quantum algorithms stems exactly from the fact that measurement collapses the state, and some measurements are much more complicated than others. How quantum computer compute? Once the register is prepared in a superposition of different numbers one can perform operations on all of them. Quantum computer processor Thus quantum computers can perform many different calculations in parallel: a system with n qubits can perform 2n calculations at once! This has impact on the execution time and memory required in the process of computation and determines the efficiency of algorithms. How Powerful are Quantum Computer? For an algorithm to be efficient, the time it takes to execute the algorithm must increase no faster than a polynomial function of the size of the input. Think about the input size as the total number of bits needed to specify the input to the problem—for example, the number of bits needed to encode the number we want to factorize.

If the best algorithm we know for a particular problem has the execution time (viewed as a function of the size of the input) bounded by a polynomial then we say that the problem belongs to class P. Computational complexity Problems outside class P are known as hard problems. Thus we say, for example, that multiplication is in P whereas factorization is not in P. “Hard? in this case does not mean “impossible to solve? or “non-computable.? It means that the physical resources needed to factor a large number scale up such that for all practical purposes, it can be regarded as intractable. However some of quantum algorithms can turn hard mathematical problems into easy ones --

- factoring being the most striking example so far. The difficulty of factorisation underpins the security of what are currently the most trusted methods of public key encryption, in particular of the RSA (Rivest, Shamir and Adelman) system, which is often used to protect electronic bank accounts. Once a quantum factorisation engine (a special-purpose quantum computer for factorising large numbers) is built, all such cryptographic systems will become insecure. Potential use of quantum factoring for code-breaking purposes has raised the obvious suggestion of building a quantum computer. How to build a Quantum Computer? In principle we know how to build a quantum computer; we start with simple quantum logic gates and connect them up into quantum networks. A quantum logic gate, like a classical gate, is a very simple computing device that performs one elementary quantum operation, usually on two qubits, in a given time. Of course, quantum logic gates differ from their classical counterparts in that they can create and perform operations on quantum superpositions. Quantum networks Realizations The quantum computer might be the theoretician's dream, but as far as experimentalists are concerned, its realization is a nightmare. The problem is that while some prototypes of the simplest elements needed to build a quantum computer have already been implemented in the laboratory, it is still an open question how to combine these elements into scalable systems. Shor's algorithm may break the RSA code, but it will remain an anecdote if the largest number that it can factor is 15. In the circuit-based model the problem is to achieve a scalable quantum system that at the same time will allow one to (1) robustly represent quantum information, (2)

perform a universal family of unitary transformation, (3) prepare a fiducial initial state, and (4) measure the output result. Alternative paradigms may trade some of these requirements with others, but the gist will remain the same, i.e., one would have to achieve control of one's quantum system in such a way that the system will remain "quantum" albeit macroscopic or even mesoscopic in its dimensions. Several ingenious solutions to the first two requirements above were devised, including quantum error correction codes (Shor 1995) and fault tolerant computation (Shor and DiVicenzo 1996, Aharonov and Ben-Or 1997) that dramatically reduce the spread of errors during a ‘noisy’ quantum computation. The problem, however, lies in the last two requirements. If one hopes to solve intractable problems efficiently with a scalable quantum computer, then the preparation of the input state and the measurement of the output state must be performed in such a way that will not increase the complexity of the computation. In other words, if the construction of the theoretical operator that measures a quantum state which encodes a solution to an NP-complete problem requires an exponential time, or even solving yet another NP-complete problem, then one has gained nothing by representing this solution in a quantum state. Why is it difficult to make a Quantum Computer? As the number of quantum gates in a network increases, we quickly run into some serious practical problems. The more interacting qubits are involved, the harder it tends to be to engineer the interaction that would display the quantum properties. The more components there are, the more likely it is that quantum information will spread outside the quantum computer and be lost into the environment, thus spoiling the computation. This process is called decoherence. Thus our task is to engineer sub-microscopic systems in which qubits affect each other but not the environment. APPLICATION- As our technology rushes forward, several factors work together to push us toward the quantum computing world,

and push out the classical silicon-based chips. These factors are: scaling in size, energy consumption, economics of building leading edge computers, and new applications that are available with quantum computers that cannot be executed with classical computers. At the current rate of chip miniaturization, energy efficiency, and economics, the classical computer of the year 2020 (if it could happen at all), would contain a CPU running at 40 GHz (or 40,000 MHz), with 160 Gb (160,000 MB) RAM, and run on 40 watts of power. Scaling -Our computing world is surrounded by breath-taking innovations, and many of them involve more powerful and smaller chips.

Chip capacity has doubled every 18 months, according to Moore’s Law, but the chip size remains constant. The number of transistors on a single chip is rising exponentially also. Keyes extrapolates that if miniaturization continues at the current rate, a bit will be represented by a single atom by the year 2020. This trend inevitably leads us into the micoworld of quantum effects, where classical rules no longer apply. Energy -The speed of chips is also rising exponentially. Faster, more densely-packed, and closer transistors cause thermodynamic problems. Advances in energy efficiency are required to keep the chips from melting during use. Fortunately, energy efficiencies are increasing, and the thermodynamic problems are being resolved. These energy advances are also pushing the physics of chips into the quantum realm. Quantum computers are reversible, therefore there is theoretically no net energy consumption. Quantum reversibility means that quantum computers drive themselves forward in infinitesimal (reversible) steps, much the same way that molecules of perfume would diffuse from a perfume bottle. Quantum computer programs are not "run", but are said to "evolve," as they process the program’s inputs to outputs. Incidentally, reversibility also means that the inputs of a quantum computer can be implied from the outputs; the program can be run backwards to get the inputs.) The argument for energy inevitability is a "carrot-and-stick" argument: the energy inefficiencies drive us away from classical computers, and the appeal for energy-free (or at least, much reduced energy consumption) computing drives us toward quantum computers. Economics -Besides the energy factors at the micro level of computing, there are large-scale economic factors pushing us to a more energy-efficient means of computing: 5% of the entire national power production is consumed by computing machinery.

With "fossil fuels continuing to dwindle, fission power in disfavor with the public, and fusion power still many decades away, the drain computers impose on our power supply could become significant." The cost to build a semiconductor plant doubles every three years. By extrapolating that trend to the year 2020, a semiconductor plant will cost $1 trillion to build, which is 5% of the U.S. GNP. Based on Motorola’s sales figures, a similar company would need $10 trillion in annual sales to support that kind of construction. Japan, in its bid for software and hardware global dominance, has allocated huge funds for quantum computer research. ***, VP of Hewlett-Packard, reported that 70% of all quantum computer research is being done by the Japanese. They have included quantum computers as an integrated step of their global acquisition strategy. FUTURE PROSPECTS- Encryption Technology The speed of quantum computers also jeopardize the encryption schemes that rely on impracticably-long times to decrypt by brute force methods. Encryption schemes that may take millions of years to guess and check are now vulnerable to quantum computers that may reach a solution within one year. Many governments, included ours, use such encryption schemes for national security. They are very interested in any technology that puts that at risk. As a result, the Office of Naval Research, the CIA, and DARPA, are sinking huge funds into quantum computer research. DARPA is funding $5 million for a Quantum Information and Computing Institute, and the CIA is funding an unknown amount for factoring of large integers, a fundamental part of encryption technology. Ultra-secure and Super-dense Communications It is possible to transmit information without a signal path by using a newly-discovered quantum principles, quantum teleportation. There is no way to intercept the path and extract information. Ultra-secure communication is also possible by super-dense information coding, which is a new technology in its own right. Quantum bits can be used to allow more information to be communicated per bit than the same number of classical bits. Improved Error Correction and Error Detection Through similar processes that support ultra-secure and super-dense communications, the existing bit streams can be made more robust and secure by improvements in error correction and detection. Recovering informational from a noisy transmission path will also be a lucrative and useful practice. Molecular Simulations Richard Feynman showed in 1982 that classical computers cannot simulate quantum effects without slowing down exponentially;

a quantum computer can simulate physical processes of quantum effects in real time. Molecular simulations of chemical interactions will allow chemists and pharmacists to learn more about how their products interaction with each other, and with biological processes such as how a drug may interact with a person’s metabolism or disease. Pharmaceutical research offers a big market to such applications. True Randomness Classical computers do not have the ability to generate true random numbers.

The random number generators on today’s computers are pseudo-random generators—there is always a cycle or a trend, however subtle. Pseudo-random generators cannot simulate natural random processes accurately for some applications, and can not reproduce certain random effects. Quantum computers can generate true randomness, thus give more veracity to programs that need true randomness in their processing. Randomness plays a significant part of applications with a heavy reliance on statistical approaches, for simulations, for code making, randomized algorithms for problems solving, and for stock market predictions, to name a few. With the global forces of computer competition, encryption technology for national security, new applications, and the thermodynamics of computer systems changing as they are, there is a rush toward the new quantum technology to produce the first viable quantum computer. The world is moving toward a place that no classical computer has gone before, nor can go.