Transcript Quantum Computing - Computing and Information Sciences

Quantum Computing
David Dvorak
CIS 492
Quantum Computing Overview
• What is it?
• How does it work?
– The basics
– Clarifying with examples
• Factoring
• Quantum Cryptography
• Why should we care?
– Societal implications
– Bugs to work out
– How will it affect the future?
• References
One analogy…
“A quantum computer is to a regular computer,
what a laser is to a lightbulb.”
--Seth Lloyd, MIT
What is Quantum Computing?
• Currently, computer chips are filled with gates
only fractions of a micron wide
• Gates will move to the atomic level
• At an atomic level matter obeys different rules
– Quantum Mechanics
– Allows completely new algorithms
– Better than cramming more gates on a chip
• Theoretical beginnings in the 80s, experiments in
the 90s
The Basics of Quantum
Computing
• An atom, not an electron, is the physical bit
– An electron is 0 or 1
– Quantum mechanics: at atom is 0, 1, or both
– “coherent superposition”
• The bit in quantum mechanics is a qubit
• What’s the difference?
– n bits can store one of 2n numbers at any time
– n qubits can store all 2n numbers at once
The advantage of qubits
• Adding qubits increases storage exponentially
• Can do operations on all superpositions…like
parallel computation
– One math operation on 2n numbers encoded with
n bits requires 2n steps or 2n parallel processors
– The same operation on 2n numbers encoded by n
qubits takes 1 step
• This makes complex problems much easier
Example: Factoring
• Factoring takes longer as digits increase
• Increasing CPU speed only increases
calculation linearly, need exponentially
• Factoring 1000 digit number classically
would take longer than estimated life of
universe
• Quantum computers do this in minutes
Other uses of Quantum
Computing
• Modeling large complex systems
– the brain
– the universe
•
•
•
•
Can describe an atom with a few bits
Takes 100 bits to describe atoms interacting
2100 or 10100 bits, 1090 particles in whole universe
Few 100 qubits easily solves this problem
– physics or chemistry
Cryptography
RSA cryptography relies on the
difficulty of factoring large numbers
to be secure…
Quantum Cryptography
• To break RSA a hacker would need a large scale
quantum computer (10,000 qubits)
• Quantum computing offers new possibilities for
secure communication
– “entanglement”
– two quantum bits correlated stronger than possible in
regular physics
– teleportation
– two entangled objects can only be known by their
“owners”…privacy implications
Quantum Cryptography
• Entangled atoms are like keys
• Cannot be known to anyone else by laws of
quantum physics
– Has transmitted securely over 1km
– Bank of England wants to use it locally
• However, transmissions easily interrupted
– Denial of service
– However, eavesdroppers are easily detected
– Can intercept and retransmit, but it will be know
Societal implications
• Has increased thinking, quantum computing
opens a world of possibilities
• Common language between the sciences:
math, physics, chemistry, computers…
• Thinking of complex problems to solve
• Secure communication
• Biggest advance yet…changes the way we
think of the universe, ie, Schroedinger’s cat
Kinks to work out
• Must reduce decoherence
– Computation spreads beyond local components, effects
other qubits
– Qubits must only interact with themselves, not their
environment
• Must control quantum phenomenon
• Make quantum computers scalable
– Current quantum computers have 10 or so qubits
– 1000s of qubits would be ideal
The future of quantum computing
• In 100 years quantum computers will be
boring
– Maybe not in all households, but common
– Molecular computers in households?
• Developing better cryptography
• Think up more problems to solve…won’t be
able to solve them quite yet
References
• www.qubit.org (Barneco and Ekert)
– www.qubit.org/library/intros/comp/comp.html
– www.qubit.org/library/intros/crypt.html
• www.pbs.org (Lloyd, Divincenzo, and Whaley)
– www.pbs.org/kcet/closertotruth/transcripts/308_quantu
mcomputers.pdf
– www.pbs.org/kcet/closertotruth/explore/learn_08.html
The End
Questions?