Home >  Quantum Computing Osama Awwad Department of Computer Science Western Michigan University Overview Introduction Data

Quantum Computing Osama Awwad Department of Computer Science Western Michigan University Overview Introduction Data


 
 

Quantum Computing 

Osama Awwad

Department of Computer Science

Western Michigan University 
 


 
 

Overview 

  •  Introduction
  • Data Representation
  • Computational Complexity
  • Implementation Technologies
  • Quantum Computer Languages

 


 
 

Introduction to quantum mechanics  

  • Quantum mechanics is a fundamental branch of theoretical physics with wide applications in experimental physics that replaces classical mechanics and classical electromagnetism at the atomic and subatomic levels.

 


 
 

Introduction to quantum mechanics 

  • Quantum mechanics is a more fundamental theory than Newtonian mechanics and classical electromagnetism
  • It provides accurate and precise descriptions for many phenomena that these "classical" theories simply cannot explain on the atomic and subatomic level
 
 

What is a quantum computer? 

  •   A quantum computer is a machine that performs calculations based on the laws of quantum mechanics, which is the behavior of particles at the sub-atomic level.
 
 
  • Moore��s Law: We hit the quantum level 2010~2020.
 

Why bother with quantum computation?


 
 

Computer technology is making devices smaller and smaller�� 

��reaching a point where classical physics is no longer a suitable model for the laws of physics.


 
 

Physics and Computation 

  • Information is stored in a physical medium, and manipulated by physical processes.
 
  • The laws of physics dictate the capabilities of any information processing device.
 
  • Designs of  ��classical�� computers are implicitly based in the classical framework for physics
 
  • Classical physics is known to be wrong or incomplete�� and has been replaced by a more powerful framework:  quantum mechanics.
 
 

The design of devices on such a small scale will require engineers to control quantum mechanical effects. 

Allowing computers to take advantage of quantum mechanical behaviour allows us to do more than cram increasingly many microscopic components onto a silicon chip�� 

�� it gives us a whole new framework in which information can be processed in fundamentally new ways. 

The nineteenth century was known as the machine age, the twentieth century will go down in history as the information age. I believe the twenty-first century will be the quantum age. Paul Davies, Professor Natural Philosophy – Australian Centre for Astrobiology


 
 
 

��No, you��re not going to be able to understand it. . . . You see, my physics students don��t understand it either. That is because I don��t understand it. Nobody does. ... The theory of quantum electrodynamics describes Nature as absurd from the point of view of common sense. And it agrees  fully with an experiment. So I hope that you can accept Nature as She is -- absurd. 

Richard Feynman 

Nobody understands quantum mechanics


 
 

��consider a setup involving a photon source,  
            a half-silvered mirror (beamsplitter),  
              and a pair of photon detectors. 

photon source 

beamsplitter 

detectors 

A simple experiment in optics


 
 

50% 

50% 

Simplest explanation:  beam-splitter acts as a classical coin-flip, randomly sending each photon one way or the other. 

Now consider what happens when we fire a single photon into the device��


 
 

 
    
�� consider a modification of the experiment�� 

100% 

The simplest explanation is wrong! 

The simplest explanation for the modified setup would still predict a 50-50 distribution�� 

full mirror 

The ��weirdness�� of quantum mechanics��


 
 

Classical probabilities�� 

Consider a computation tree for a simple two-step (classical) probabilistic algorithm, which makes a coin-flip at each step, and whose output is 0 or 1: 





The probability of the computation following a given path is obtained by multiplying the probabilities along all branches of that path�� in the example the probability the computation follows the red path is 

The probability of the computation giving the answer 0 is obtained by adding the probabilities of all paths resulting in 0: 

 


 
 

|0 

|1 

|0 

|1 

��vs quantum probabilities �� 

In quantum physics, we have probability amplitudes, which can have complex phase factors associated with them. 

The probability amplitude associated with a path in the computation tree is obtained by multiplying the probability amplitudes on that path.  In the example, the red path has amplitude 1/2, and the green path has amplitude –1/2. 

The probability amplitude for getting the answer |0 is obtained by adding the probability amplitudes�� notice that the phase factors can lead to cancellations!  The probability of obtaining |0 is obtained by squaring the total probability amplitude.  In the example the probability of getting |0 is


 
 

 
    
�� consider a modification of the experiment�� 

The simplest explanation for the modified setup would still predict a 50-50 distribution�� 

full mirror 

Explanation of experiment 

100%


 
 

Representation of Data 

  • Quantum computers, which have not been built yet, would be based on the strange principles of quantum mechanics, in which the smallest particles of light and matter can be in different places at the same time.
  • In a quantum computer, one "qubit" - quantum bit - could be both 0 and 1 at the same time. So with three qubits of data, a quantum computer could store all eight combinations of 0 and 1 simultaneously. That means a three-qubit quantum computer could calculate eight times faster than a three-bit digital computer.
  • Typical personal computers today calculate 64 bits of data at a time. A quantum computer with 64 qubits would be 2 to the 64th power faster, or about 18 billion billion times faster. (Note: billion billion is correct.)  
 
 

A bit of data is represented by a single atom that is in one of two states denoted by |0> and |1>.  A single bit of this form is known as a qubit

 


 
 

Representation of Data  - Qubits 

A physical implementation of a qubit could use the two energy levels of an atom.  An excited state representing |1> and a ground state representing |0>.   

Excited State 

Ground State 

Nucleus 

Light pulse of frequency for time interval t 

Electron 

State |0> 

State |1>


 
 

Representation of Data - Superposition 

A single qubit can be forced into a superposition of the two states denoted by the addition of the state vectors: 

|> =   |0> +   |1> 

Where    and    are complex numbers and |  |   +  |   |   = 1  

1 

2 

1 

2 

1 

2 

2 

2 

A qubit in superposition is in both of the states |1> and |0 at the same time


 
 

Representation of Data - Superposition 

Light pulse of frequency for time interval t/2 

State |0> 

State |0> + |1> 

  • Consider a 3 bit qubit register.  An equally weighted superposition of all possible states would be denoted by:

|> =     |000> +    |001> + . . . +     |111> 

1 

��8 

1 

��8 

1 

��8


 
 

Data Retrieval 

  • In general, an n qubit register can represent the numbers 0 through 2^n-1 simultaneously.

Sound too good to be true?��It is!

  • If we attempt to retrieve the values represented within a superposition, the superposition randomly collapses to represent just one of the original values.
 
 

In our equation:  |> = 1  |0> + 2  |1> ,   represents the probability of the superposition collapsing to |0>.  The ��s are called probability amplitudes.  In a balanced superposition,  = 1/��2n   where n is the number of qubits. 




n


 
 

Relationships among data - Entanglement 

  • Entanglement is the ability of quantum systems to exhibit correlations between states within a superposition.
  • Imagine two qubits, each in the state |0> + |1> (a superposition of the 0 and 1.)  We can entangle the two qubits such that the measurement of one qubit is always correlated to the measurement of the other qubit.

 


 
 

Measuring multi-qubit systems 

If we measure both bits of 
 
 

we get  with probability  
 


 
 

Measurement 
 

  • ||2, for amplitudes of all states matching an output bit-pattern, gives the probability that it will be read.
  • Example:

  0.316|00› + 0.447|01› + 0.548|10› + 0.632|11› 

    • The probability to read the rightmost bit as 0 is |0.316|2   +  |0.548|2  =  0.4
  • Measurement during a computation changes the state of the system but can be used in some cases to increase efficiency (measure and halt or continue).

 


 
 

Quantum mechanics and information 

How does this affect communication complexity? 

How does this affect information security? 

How does this affect computational complexity? 

Any physical medium capable of representing 0 and 1 is in principle capable of storing any linear combination


 
 

A ��Probabilistic Turing Machine�� (PTM) is an abstract model of the modern (classical) computer. 

Strong Church-Turing Thesis:

A PTM can efficiently simulate any realistic model of computing. 

Widespread belief in the Strong Church-Turing thesis has been one of the underpinnings of theoretical computer science. 

The Classical Computing Model


 
 

What do we mean by ��efficient��? 

The complexity of an algorithm measures how much of some resource (e.g. time, space, energy) the algorithm uses as a function of the input size. 

e.g. the best known algorithms for factoring an n bit number uses time in 

(number field sieve algorithm)


 
 

Factoring is believed to be hard on a Turing machine (or any equivalent model), but how do we know that there isn��t some novel architecture on which it is easy?


 
 

The Strong Church Turing thesis tells us that all reasonable models can be efficiently simulated by a PTM, which implies that if it��s hard for a PTM it must be hard for any other reasonable computer. 

i.e. we believe computational problems, like factoring, have an intrinsic difficulty, independent of how hard we try to find an efficient algorithm.


 
 

In the early 1980s, Richard Feynman observed that it seems implausible for a PTM to efficiently simulate quantum mechanical systems�� 

��quantum computers  are  
    quantum mechanical systems�� 

�� so quantum computing is a model which seems to violate the Strong Church-Turing thesis!


 
 

Are quantum computers realistic? 

Are quantum computers realistic? 

The answer seems to be YES!   

If the quantum computers are a reasonable model of computation, and classical devices cannot efficiently simulate them, then the Strong Church-Turing thesis needs to be modified to state: 

 A quantum computer can efficiently simulate any realistic model of computation.


 
 

Applications 

  •  Efficient simulations of quantum systems
  • Phase estimation; improved time-frequency and other measurement standards (e.g. GPS)
  • Factoring and Discrete Logarithms
  • Hidden subgroup problems
  • Amplitude amplification
  • and much more��
 
 

Quantum Algorithms 

a,b  G     ,       ak = b      ,   find k 

Integer Factorization (basis of RSA cryptography): 
 

Discrete logarithms (basis of DH crypto, including ECC): 

Given N=pq, find p and q.


 
 

Computational Complexity Comparison 

Elliptic Curve Discrete Logarithms 

Factoring 

Quantum 

Classical 

(in terms of number of group multiplications for n-bit inputs)


 
 

The following cryptosystems are insecure against such quantum attacks: 

Which cryptosystems are threatened by Quantum Computers?? 

  • RSA (factoring)
  • Rabin (factoring)
  • ElGamal (discrete log, including ECC – see Proos and Zalka)
  • Buchmann-Williams (principal ideal distance problem)
  • and others�� (see MMath thesis, Michael Brown, IQC)
 

Information security protocols must be studied in the context of quantum information processing. 

http://arxiv.org/abs/quant-ph/0301141 

We need to worry NOW about information that needs to remain private for long periods of time.

It takes a long time to change an infrastructure.


 
 

Quantum Information Security 

  • Quantum key establishment (available now/soon)
  • Quantum random number generation (available now/soon)
  • Quantum money  (require stable quantum memory)
  • Quantum digital signatures (requires quantum computer)
  • Quantum secret sharing (requires quantum computer)
  • Multi-party quantum computations 
  • and more��
 

We can exploit the eavesdropper detection that is intrinsic to quantum systems in order to derive new ��unconditionally secure�� information security protocols. The security depends only on the laws of physics, and not on computational assumptions.


 
 

Quantum computing in computational complexity theory  

  • The class of problems that can be efficiently solved by quantum computers is called BQP, for "bounded error, quantum, polynomial time".
  • Quantum computers only run randomized algorithms, so BQP on quantum computers is the counterpart of BPP on classical computers
  • In complexity theory, BPP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of at most 1/3 for all instances. The abbreviation BPP refers to Bounded-error, Probabilistic, Polynomial time.
 

 


 
 

Quantum computing in computational complexity theory 

  • BQP is suspected to be disjoint from NP-complete and a strict superset of P, but that is not known.
  • Both integer factorization and discrete log are in BQP. Both of these problems are NP problems suspected to be outside BPP, and hence outside P
  • Both are suspected to not be NP-complete
  • There is a common misconception that quantum computers can solve NP-complete problems in polynomial time (generally suspected to be false )
 
 

Quantum computing in computational complexity theory


 
 

Implementation requirements 

  • Qubit implementation itself
  • Control of unitary evolution
  • Initial state preparation (qubits)
  • Measurement of the final state(s)
 
 

Implementation  

  • Ion Traps
  • Nuclear magnetic resonance (NMR)
  • Optical photon computer
  • Solid-state

 


 
 

Optical photon computer 
 

  • One method of this type uses the interaction between an atom and photon in a resonator, and another uses optical devices such as a beam splitter, mirror, etc. 
 
 

NMR 

  • NMR uses the spin of an atomic nucleus to represent a qubit.
  • Chemical bonds between spins are manipulated by a magnetic field to simulate gates.
  • Spins are prepared by magnetising, and induced voltages are used for measurement. Currently it is thought that
  • NMR will not scale to more than about twenty qubits.
  • In 2006, the researchers reached a 12-coherence state and decoded it using liquid state nuclear magnetic resonance quantum information processors.
 
 

Ion Traps 

  • This method uses two electron orbits of an ion (charged atom) trapped within an electromagnetic field in a vacuum to form a qubit (ion trap method).
 
 

Solid-state device 
 

   There are two well-known qubits of this type.

  1. A qubit achieved by a superconducting circuit using a Josephson junction that creates a weak bond between two superconductors.
  2. A qubit achieved by a semiconductor quantum dot, which is a structure from 10 to several hundred nanometers in size for confining an electron.

 


 
 

Quantum Computer Languages 
 

    Even though no quantum computer has been built that hasn��t stopped the proliferation of papers on various aspects of the subject. Many such papers have been written defining language specifications. 

  • QCL - (Bernhard �� Omer) C like syntax and very complete. http://tph.tuwien.ac.at/»oemer/qcl.html .
  • qGCL - (Paolo Zuliani and others)

    http://web.comlab.ox.ac.uk/oucl/work/paolo.zuliani/

  • Quantum C - (Stephen Blaha) Currently just a specification,
 

 


 
 

References 

  • ��A survey of quantum computing and automata��. E. de Doncker and L. Cucos, In Fourth World Multiconference on Systemics, Cybernetics, and Informatics (SCI'00), (2000).
  • ��The Temple of Quantum Computing��, Riley T. Perry.2004
  • ��Quantum Computation:A Computer Science Perspective��, Anders K.H. Bengtsson. 2005
  • http://en.wikipedia.org/wiki/Quantum_computing
  • http://www.nec.co.jp/rd/Eng/innovative/E3/top.html
  • http://www.sciencedaily.com/

 


 
 

Q & A 

Thank You


Set Home | Add to Favorites

All Rights Reserved Powered by Free Document Search and Download

Copyright © 2011
This site does not host pdf,doc,ppt,xls,rtf,txt files all document are the property of their respective owners. complaint#nuokui.com
TOP