View
216
Download
0
Category
Preview:
Citation preview
Vorlesung Quantum Computing SS ‘08 1
Quantum ComputingPhysik der Quanten-Informationsverarbeitung
C. Meyer, C.M. Schneider
Vorlesung SS ‘08
Vorlesung Quantum Computing SS ‘08 2
Heise-online: 14.02.2007 12:49 << Vorige | Nächste >>
Erster Quantenprozessor der Welt vorgestellt Das kanadische Start-up D-Wave Systems hat in Kalifornien einen Quantenprozessor mit 16 Qubits vorgestellt. Die Qubits werden von je einer kreisförmigen supraleitenden Stromschleife aus dem Metall Niob dargestellt. Die Betriebstemperatur des Prozessors beträgt 5 Millikelvin, 0,005 Grad über dem absoluten Nullpunkt. "Unser Durchbruch in der Quantentechnologie ist ein wichtiger Fortschritt bei der Lösung wirtschaftlicher und wissenschaftlicher Probleme, die bislang nur schwer in den Griff zu bekommen waren", erklärte D-Wave-Systems CEO Herb Martin.
in the media
Vorlesung Quantum Computing SS ‘08 3
plan…
1. introduction
2. quantum mechanical background
3. basic operations/superposition/entanglement
4. quantum computing with ion traps
5. Deutsch-Josza algorithm and its implementation
6. NMR quantum computing
7. Shor algorithm and its implementation (15 = 5x3)
8. magnetic resonance QC in solid state
9. quantum dots for quantum computing
10. first experiments
11. superconducting qubits
12. quantum error correction
13. invitation to Research Centre Jülich
Vorlesung Quantum Computing SS ‘08 4
technology of computation
• 2-state (binary) logic: “0” and “1”• state is defined by a switch: “open” & “closed”• logic operations: array of switches (gates)• mechanical switches (Zuse Z1)• electromechanical relays (Zuse Z3)
Rebuilt 1960 by K. ZuseDeutsches Museum München
Built
Techniques
Frequency
Speed
Format
Weight
Tasks
“Processor”: 600 relaysMemory: 1400 relays
Multiplication
22-bit digits floating point
Technical calculations,chess
Vorlesung Quantum Computing SS ‘08 5
ENIAC
• Electronic Numerical Integrator And Computer• 17468 vacuum tubes• weight 20 t, power consumption 150 kW
1946
Vorlesung Quantum Computing SS ‘08 6
Moore’s law
Vorlesung Quantum Computing SS ‘08 7
birth of microelectronics
• 1947 invention of transistor• 1958 invention of integrated circuit (TI)• 1971 first microprocessor (4004)
Vorlesung Quantum Computing SS ‘08 8
microprocessors
4-bit 8-bit 32-bit 64-bit
Intel 40041971
Intel 80801974 2000
20051985
16-bit
increase power of microprocessors bybus bit width and clock frequency
Vorlesung Quantum Computing SS ‘08 9
microprocessor designhttp://www.offis.de/
Embedded Hardware- / Software-SystemsDr. Jens Appell
Vorlesung Quantum Computing SS ‘08 10
breaking the barrier?
min
imu
m s
ize
of
ch
ip c
om
po
ne
nts
(n
m)
source:
quantum effects in silicon
technology barrier silicon
year
pro
tein
s,
ma
cro
-mo
lec
ule
s
siz
e o
f v
iru
se
s a
nd
DN
Asemiconductor industry
exponential extrapolation
Vorlesung Quantum Computing SS ‘08 11
computational power
we want to increase our capability of solving problems
speed accuracy complexity
increase what is a complex problem?
Is there a subset of {−2,−3,15,14,7,−10} which adds up to 0?
Easy: verify that sum{-2,-3,15,-10} = 0
Difficult: identify this subset
Similar problem: find prime factors of 1601
Vorlesung Quantum Computing SS ‘08 12
fundamental approach
Question: Is there a general method or process by which one could decide whether a mathematical proposition could be proved?
Answer: No!
On computable numbers, with an application to the Entscheidungsproblem Proceedings of the London Mathematical Society, Series 2, Vol.42 (1936 - 37) pages 230 to 265online available: http://web.comlab.ox.ac.uk/oucl/research/areas/ieg/e-library/sources/tp2-ie.pdf
“Turing Machine”
what is a computer and what kind of problems can it solve?
Vorlesung Quantum Computing SS ‘08 13
Turing machine
head
• Consists of a stripe and a head
ə 0 0 0 1 1 1 0 0 0 0 0
• Stripe consists of symbols “0”, “1”, “blank”, “ə”
b,f
• Head can be in states, e.g. „b“ and „f“• Symbols determine the action of the head:
- Writing/Erasing of symbol- Direction of reading- change of state
Vorlesung Quantum Computing SS ‘08 14
boolean algebra and logic gates
classical (irreversible) computing
gateinout
1-bit logic gates: identity
x NOT x
0 11 0
x Id
0 01 1
NOT
x NOT x
Vorlesung Quantum Computing SS ‘08 15
boolean algebra and logic gates
2-bit logic gates:
y x OR y
0
1
0
1
0
0
1
1
x
0
1
1
1
y x AND y
0
1
0
1
0
0
1
1
x
0
0
0
1
x
yx OR y
x
yx AND y
Vorlesung Quantum Computing SS ‘08 16
Turing Machine
0 1 ə
b R,b R,f P1,L,b R,b
f E,R,f R,f L,b
ə 0 0 0 1 1 1 0 0 0 0 0
head
b
head
b
head
b
head
f
head
f
head
b
head
f
head
f
head
f
head
b
1
head
f
head
b
1
head
b
1
head
b
head
b
head
f
table of states
what happens, depends on the states of the head
ə 0 0 0 1 1 1 0 0 0 0 0
head
f
head
f
head
f
head
b
head
f
56 + 7 = 63
Vorlesung Quantum Computing SS ‘08 17
complexity classes
• Deterministic Turing Machine (DTM) models all classical computers therefore called “universal”
• Probabilistic Turing Machine (PTM): actions are carried out with certain probability
P: problems that can be solved with a DTM in polynomial time
ZPP: problems that can be solved with a PTM with zero probability of error in polynomial time.
NP: problems that can be solved with a NDTM in polynomial time.
• Non-Deterministic Turing Machine (NDTM): multiple computation paths (“computation tree”)
Vorlesung Quantum Computing SS ‘08 18
traveling salesman problem
the traveling salesman problem is NP-complete
What is the shortest route betweena given number of cities?
scales exponentially with number of cities for a DTM
Can a physical implementation be found that provides a better solution?
Experiment
Vorlesung Quantum Computing SS ‘08 19
physical system designed for problem
soap bubbles can (theoretically) be used to solve some optimization problems in NP-complete
soap bubbles ≠ NDTMquantum computer ≠ NDTM
[Feynman1982] “ ....certain quantum mechanical effects cannot be simulated efficiently on a classical computer. This observation led to speculation that perhaps computation in general could be done more efficiently if it made use of these quantum effects.”
R. P. Feynman, Int. J. Theor. Phys. 21, 467(1982); Found. Phys. 16, 507(1986)
Vorlesung Quantum Computing SS ‘08 20
Quantum Turing Machine
• Read, write, and shift operations are accomplished by quantum interactions
• Tape and head exist each in a quantum state• symbols “0” or “1” are replaced by qubits, which can hold a
quantum superposition of |0 and |1
The quantum Turing machine can encode many inputs to a problem simultaneously, and then it can perform calculations on all the inputs at the same time. This is called quantum parallelism.
David Deutsch, Proceedings of the Royal Society of London A 400 (1985), 97
Vorlesung Quantum Computing SS ‘08 21
quantum bits
conventional bit
on <=> 3.2 - 5.5 V <=> 1
off <=> -0.5 - 0.8 V <=> 0
quantum mechanical bit (qubit)
| 0 <=> <=>
| 1 <=> <=>
10(
(
01(
(
a1| 0 + a2| 1 = a1
a2( )
superposition:
Vorlesung Quantum Computing SS ‘08 22
quantum parallelism
a1 F |00>+
a2 F |01>+
a3 F |10>+
a4 F |11>
}{a1 |00>
+a2 |01>
+a3 |10>
+a4 |11>
}{input
b1 |00>+
b2 |01>+
b3 |10>+
b4 |11>
}{=
output
F
Vorlesung Quantum Computing SS ‘08 23
quantum computing
calculationpreparation read-outtime
classical bit
1 ON 3.2 – 5.5 V
0 OFF -0.5 – 0.8 V
exponentially faster for Fourier transformation (Shor algorithm)
quantum-bit (qubit)
0 1
a10 + a21 =a1a2
H H-1U |A|
time
decoherence
Vorlesung Quantum Computing SS ‘08 24
important algorithms
database search N data sets
e.g. find no. in phonebook (60 million data sets)
30 millionsteps
7746steps
89 steps1019 steps
taskalgorithm classicalcomputer
quantumcomputer
prime factor decomposition
e.g. 128 bit decoding
Vorlesung Quantum Computing SS ‘08 25
trapped ions
C. Monroe, D.Wineland, et al. Nature 2000
R. Blatt group (Innsbruck) '97 - '00
C. Monroe group, Michigan ‘06
Vorlesung Quantum Computing SS ‘08 26
spin resonance
7 mm
Vorlesung Quantum Computing SS ‘08 27
quantum dots
J. R. Petta et al., Science 2005
F. Koppens et al., Nature 2006
Vorlesung Quantum Computing SS ‘08 28
superconductor electronics
Y. Nakamura et al., Nature 1999
I. Chiorescu et al., Science 2003
Vorlesung Quantum Computing SS ‘08 29
implementations
atoms or ions in trapselectronic states of atoms/ionsvibrational modes
spintronicelectron spins in quantum dotsexchange interaction
superconductor electronicsCooper pairs or fluxJosephson coupling
spin resonance (NMR, ESR)spins in molecules or solid state matrixhyperfine, exchange, or magnetic dipolar interaction
(CH)5 Fe (CO)2
F
C C
C C
F
F
F
F
Vorlesung Quantum Computing SS ‘08 30
from classic to quantum
we live in Hilbert Space Hthe state of our world is |
Recommended