Don Herres : IEEE Lehigh Valley Section Chair 2018 learning to drive a car, goal: drive to AC/casino/ocean/... 1st?: learn how internal combustion engine works; how gasoline is refined from oil; or maybe electric car?, E&M; Maxwell equations; or clean coal? (ref: RP energy secretary) classical computers, goal: use Excel, MS/Word (applications) or C, python, Matlab (programming) 1st?: semiconductor physics, MOS transistors, Boolean logic, Karnough maps, VHDL; VM, cache, instruction set, assembly. --- Goal Simulate quantum algorithms at a high-level, to test correctness and evaluate performance Outline 1. History of Computing 2. Quantum Physics 3. Mathematical Representations 4. Superdense Coding Simulation 5. Addition Simulation 6. Grover's Search Algorithm 7. Shor Factoring Algorithm Eniac 1950: 30 tons, 150 KW, 1 KB, 100 KHz qc today comparable to early days of classical computers in the 1950's predates me; mom developing programs by hand before Eniac,et.al. was built, vs. now using computers (information processing) to create and simulate next generation Phone 2018: 5 oz., 1 W, 4 GB, 2 GHz QC 2018: tons, KW, 20 Qubit (2**20 = 1 Mb), 1 MHz daughter QC 2050: ??? 100 years after Eniac Dwave current, multivariable function minimization, simulated annealing Ion Trap Quantum Device Two energy bands, represent 0/1, blue is applied laser, red is fluorescence Before measurement (c) is in superposition of both states Quantum Key Distribution single photons, initially in superposition of polarizations Horizontal/Vertical polarization, like qubit basis After filter is 100% in one polarization, but vertical is 50/50 diagonal Quantum Key Distribution Public discussion: Alice reveals which bases she used If Bob chose the wrong basis, his result, and thus the bit he reads, will be random. If MITM measures on the incorrect bases, the Heisenberg Uncertainty Principle ensures that the information encoded on the other bases is now lost. One Qubit Math, model of reality, complex amplitudes, magnitude squared = probability. doesn't make sense on macroscopic scale, agrees with experiments/measurements Operations are unitary matrices, preserve norm, reversible (conjugate transpose) Single Qubit Operations 2x2 complex matrices compare with classical bit: can't do much other than NOT (X gate) Hadamard transformation: 0 -> superposition of 0 and 1 Parallelism Two Qubits 3 qubits -> 8 amplitudes, 4 qubits -> 16 amplitudes, etc. keeps doubling: 32 qubits -> 2**32 ~= 4 billion amplitudes Simulation limit: ~50 qubits with some tricks for certain problems Break 2000-bit RSA key: 4000 qubits DWave: ~2000 qubits but only adiabatic, multivariable function minimization, like simulated annealing, not general purpose independent qubits vs. entangled general normalization constraint CNOT - entangled states simple simulator in Python -> generalize using an array b XOR a -> in general b XOR f(a), or b XOR f(a,b) Superdense Coding Protocol 0.707**2 = 0.5 probability After Eve's CNOT, entangled: measure q1 -> determines q2 Simulating Two Qubits - C Code OSP assignment, exercise using complex in C Low-level Simulation flowchart, time -> right like assembly code, 2 and 3-input gates High-level Simulation simulate quantum addition using classical addition reversible, permutation replace "classical addition" with "modular exponentiation", etc. High-level Function Implementation in a Simulator "other operations", e.g. Grover inversion about mean Grover's Search - Quadratic Speedup square root of 2**n vs. 2**n / 2 Grover's Search - 16-bit Example 201 iterations optimum, more gets worse Shor factoring - breaks RSA Also Peter Shor method for discrete logarithm problem, breaks Diffie-Hellman and elliptic curve crypto r must be even, else try again with different y value Shor factoring example, N = 33 Physical QC: measure -> one answer, might not work, start over Simulation: see all of the probabilities References My page has more notes and references Comics simultaneous state of being both totally successful and not even started, like student homework assignment me