English

not defined

no text concepts found

Introduction to Quantum Computation Andris Ambainis University of Latvia What is quantum computation? New model of computing based on quantum mechanics. Quantum circuits, quantum Turing machines More powerful than conventional models. Quantum algorithms Factoring: given N=pq, find p and q. 1/3) O(n Best algorithm 2 , n -number of digits. Many cryptosystems based on hardness of factoring. O(n2) time quantum algorithm [Shor, 1994] Similar quantum algorithm solves discrete log. Quantum algorithms 0 1 0 ... 0 x1 x2 x3 xn Find if there exists i for which xi=1. Queries: input i, output xi. Classically, n queries. Quantum, O(n) queries [Grover, 1996]. Speeds up exhaustive search. Quantum cryptography Key distribution: two parties want to create a secret shared key by using a channel that can be eavesdropped. Classically: secure if discrete log hard. Quantum: secure if quantum mechanics valid [Bennett, Brassard, 1984]. No extra assumptions needed. Quantum communication Dense coding: 1 quantum bit can encode 2 classical bits. Teleportation: quantum states can be transmitted by sending classical information. Quantum protocols that send exponentially less bits than classical. Experiments ~10 different ideas how to implement QC. NMR, ion traps, optical, semiconductor, etc. 7 quantum bit QC [Knill et.al., 2000]. QKD has been implemented. Outline Today: basic notions, quantum key distribution. Tomorrow: quantum algorithms, factoring. Friday: current research in quantum cryptography, coin flipping. Model Quantum states Unitary transformations Measurements Quantum bit |1> |0> 2-dimensional vector of length 1. Basis states |0>, |1>. Arbitrary state: |0>+|1>, , complex, ||2+ ||2=1. Physical quantum bits Nuclear spin = orientation of atom’s nucleus in magnetic field. = |0>, = |1>. Photons in a cavity. No photon = |0>, one photon = |1> Physical quantum bits (2) Energy states of an atom |0> ground state |1> excited state Polarization of photon Many others. General quantum states k-dimensional quantum system. Basis |1>, |2>, …, |k>. General state 1|1>+2|2>+…+k|k>, |1|^2+…+ |k|^2=1 2k dimensional system can be constructed as a tensor product of k quantum bits. Unitary transformations Linear transformations that preserve vector norm. In 2 dimensions, linear transformations that preserve unit circle (rotations and reflections). Examples Bit flip | 0 | 1 | 1 | 0 Hamamard transform 1 | 0 2 | 0 1 | 1 |0 2 1 2 1 2 |1 |1 Linearity Bit flip |0>|1> |1>|0> By linearity, |0>+|1> |1>+|0> Sufficient to specify U|0>, U|1>. Examples |1> 1 2 1 |0 2 |1 |0> 1 2 |0 1 2 |1 Measurements Measuring |0>+|1> in basis |0>, |1> gives: 0 with probability | |2, 1 with probability | |2. Measurement changes the state: it becomes |0> or |1>. Repeating measurement gives the same outcome. Measurements |0> Probability 1/2 1 2 |0 1 |1> Probability 1/2 2 |1 General measurements Let |0>, | 1> be two orthogonal one-qubit states. Then, |> = 0|0> + 1|1>. Measuring | > gives | i> with probability |i|2. This is equivalent to mapping |0>, | 1> to |0>, |1> and then measuring. Measurements 1 2 1 2 |0 1 2 |1 Probability 1 |0 1 2 |1 Measurements |1> 1 1 2 |0 1 |1 2 Probability 1/2 2 |0 Probability 1/2 1 2 |1 Measurements Measuring 1|1>+2|2>+…+k|k> in the basis |1>, |2>, …, |k> gives |i> with probability |i|2. Any orthogonal basis can be used. Partial measurements Example: two quantum bits, measure first. 1 1 1 2 00 2 2 | 00 2 10 Result 1 Result 0 1 01 1 2 | 01 | 10 Classical vs. Quantum Classical bits: can be measured completely, are not changed by measurement, can be copied, can be erased. Quantum bits: can be measured partially, are changed by measurement, cannot be copied, cannot be erased. Copying One nuclear spin Two spins ? Impossible! Related to impossiblity of measuring a state perfectly. No-cloning theorem Imagine we could copy quantum states. | 0 | 0 | 0 | 1 | 1 | 1 Then, by linearity 1 2 |0 1 2 | 1 1 2 | 0 | 0 1 2 | 1 | 1 Not the same as two copies of |0>+|1>. Key distribution Alice and Bob want to create a shared secret key by communicating over an insecure channel. Needed for symmetric encryption (onetime pad, DES etc.). Key distribution Can be done classically. Needs hardness assumptions. Impossible classically if adversary has unlimited computational power. Quantum protocols can be secure against any adversary. The only assumption: quantum mechanics. BB84 states |> = |1> 1 2 | >= | >= |0 1 2 1 2 |0 |1 |> = |0> 1 2 |1 BB84 QKD Alice ... Bob ... No Yes Yes ... Yes ... 0 0 1 BB84 QKD Alice sends n qubits. Bob chooses the same basis n/2 times. If there is no eavesdropping/transmission errors, they share the same n/2 bits. Eavesdropping Assume that Eve measures some qubits in , | basis and resends them. If the qubit she measures is |> or |>, Eve resends a different state ( or | ). If Bob chooses |>, |> basis, he gets each answer with probability 1/2. With probability 1/2, Alice and Bob have different bits. Eavesdropping Theorem: Impossible to obtain information about non-orthogonal states without disturbing them. In this protocol: Check for eavesdropping Alice randomly chooses a fraction of the final string and announces it. Bob counts the number of different bits. If too many different bits, reject (eavesdropper found). If Eve measured many qubits, she gets caught. Next step Alice and Bob share a string most of which is unknown to Eve. Eve might know a few bits. There could be differences due to transmission errors. Classical post-processing Information reconciliation: Alice and Bob apply error correcting code to correct transmission errors. They now have the same string but small number of bits might be known to Eve. Privacy amplification: apply a hash function to the string. QKD summary Alice and Bob generate a shared bit string by sending qubits and measuring them. Eavesdropping results in different bits. That allows to detect Eve. Error correction. Privacy amplification (hashing). Eavesdropping models Simplest: Eve measures individual qubits. Most general: coherent measurements. Eve gathers all qubits, performs a joint measurement, resends. Security proofs Mayers, 1998. Lo, Chau, 1999. Preskill, Shor, 2000. Boykin et.al., 2000. Ben-Or, 2000. EPR state 1 2 1 | 0 | 0 2 | | 1 2 1 | 1 | 1 2 | | • First qubit to Alice, second to Bob. • If they measure, same answers. • Same for infinitely many bases. Bell’s theorem Alice’s basis: |1> cos x 0 sin x 1 sin x 0 cos x 1 Bob’s basis: y instead of x. |0> Bell’s theorem Pr[b=0] Pr[b=1] Pr[a=0] 1 cos 2 x y 2 1 sin 2 x y 2 Pr[a=1] 1 2 sin x y 2 1 cos 2 x y 2 Classical simulation Alice and Bob share random variables. Someone gives to them x and y. Can they produce the right distribution without communication? Bell’s theorem Classical simulation impossible: 3 x , , 4 4 3 y , 4 4 Bell’s inequality: constraint satisfied by any result produced by classical randomness. Ekert’s QKD Alice generates n states 1 2 | 0 | 0 1 2 | 1 | 1 sends 2nd qubits to Bob. They use half of states for Bell’s test. If test passed, they error-correct/amplify the rest and measure. Equivalence In BB84 protocol, Alice could prepare the state 1 1 1 1 0 1 2 3 2 2 2 2 keep the first register and send the second to Bob. Ekert and BB84 states UI BB E 1 2 | 0 | 0 1 | 1 | 1 2 1 1 1 1 0 1 2 3 2 2 2 2 1 1 1 U | 0 2 0 2 2 2 3 1 1 1 U | 1 1 2 3 2 2 2 QKD summary Key distribution requires hardness assumptions classically. QKD based on quantum mechanics. Higher degree of security. Showed two protocols for QKD. QKD implementations First: Bennett et.al., 1992. Currently: 67km, 1000 bits/second. Commercially available: Id Quantique, 2002. Next lectures Tomorrow: quantum algorithms for factoring. Friday: quantum coin flipping.