The Quantum 7 DwarvesSeven Dwarves7 DwarvesWhy Quantum Computing?Slide 5Slide 6Oracle ModelQuantum Lower BoundsDwarves 1,2,63rd Dwarf – Spectral Methods4th,5th Dwarf – Linear Algebra 1/2Linear Algebra 2/27th Dwarf - Monte CarloHidden Markov Models 1/2Hidden Markov Models 2/2I guess we are out of time…The Quantum 7 DwarvesAlexandra KollaGatis MidrijanisUCB CS2522006Seven DwarvesKey time consuming problems for next decade by Phillip ColellaHigh-end simulation in physical sciencesRepresentive codes may vary over time, but these numberical methods will be important for a long timeFor us: help to understand what styles of architectures we need7 Dwarves1,2,6 - structured and unstructured grid problems, particle methods3 - Fast Fourier Transform4, 5 – Linear Algebra (dense and sparse)7 Monte Carlo + search + sorting + HMM+ othersWhy Quantum Computing?Provides a method by bypassing the end of Moore’s LawProvides a way of utilizing the inevitable appearance of quantum phenomena.Factoring (break RSA), simulations of quantum mechanical systems... More efficient on quantum computer than on any classical Cryptography: doesn’t require assumptions about factoringQuantum circuit modelClassicalQuantumUnit: bitUnit: qubit1. Prepare n -bit input1. Prepare n-qubit input in the computational basis.2. 1- and 2-bit logic gates2. Unitary 1- and 2-qubit quantum logic gates3. Readout value of bits3. Readout partial information about qubits1 2, ,...,nx x xExternal control by a classical computer.© C. NielsenUse the quantum analogue of classical reversiblecomputation.The quantum NANDx1y1 x yxyHow to compute classical functions on quantum computersx0xxThe quantum fanoutClassical circuitx( )f xfx0mxg( )f xfUQuantum circuit© C. NielsenOracle ModelBoolean function f:{0,1}n → {0,1} Count only the number of queries, not computational stepsClassical black boxxz( )z f xxfxz( )z f xxfUQuantum black boxQuantum Lower BoundsVery hard to show circuit lower bounds (even classically)Show oracle lower boundsThere is no quantum speed-up for reading and outputing n bit stringThere is no is exponential speed-up for unstructured searchDwarves 1,2,6Not a good match for quantum computingEven reading N*N grid needs Ω(N*N) operationsBut: there is known quantum speed-up for simulating differential operators3rd Dwarf – Spectral Methods Data is represented in the frequency, essential for digital signal processingClassicaly, Θ(N*log N) operationsQuantumly, O((log N)2) gates for simple QFT circuitUsing parallel Fourier state computation and estimation [CW00], O(log N*(log log N)2 *log(log log N))4th,5th Dwarf – Linear Algebra 1/2Determinant of n*n matrix M [A+05]We don’t know quantum speed-upΩ(n2) for computing det(M) over finite fields or realsΩ(n2) for checking if det(M)=0 over finite fieldΩ(n) for checking if det(M)=0 over realsLinear Algebra 2/2Verification of matrix productClassically, Θ(n2) [Freivalds]Quantumly, O(n7/4), Ω(n3/2) [BS05]Triangle finding in a graph (by adjacency matrix)O(n13/10) [MSS05, BDH+05]7th Dwarf - Monte CarloThrow darts u.a.r.Know the area of mapEstimate size of countryWant a = area of the red countryClasiscally, Θ(1)/a throwsQuantumly, Θ(1)/√a ! [BHT’98]Grover’s search++Hidden Markov Models 1/2Markov process with unknown paramatersUsed to solve many problems like speech recognition or bioinformaticsOne canonical type of problems solved by HMM:we know Markov processwe know ouput sequencewe want to know most likely path, ie. Viterbi pathClassically – Viterbi algorithmHidden Markov Models 2/2Output string of length nm-states Markov processViterbi algorithm has O(nm2) stepsQuantum Viterbi – O(nm3/2) stepsOptimal in each parameterΩ(n) (for DNA)Ω(m3/2) (for speech recognition)I guess we are out of
View Full Document
Unlocking...