Grover’s Algorithm: Single SolutionApplicationApplication: DESAmplitude AmplificationInitial StateOracleSlide 7AlgorithmInversion about meanSlide 11Slide 12Complexity O(sqrt(N))LimitationsGrover’s Algorithm:Grover’s Algorithm:Single SolutionSingle SolutionBy Michael KontzBy Michael KontzApplicationApplicationGrover’s algorithm can identify an item Grover’s algorithm can identify an item from a list of N elements infrom a list of N elements in What’s this good for?What’s this good for? Unstructured database searchUnstructured database search (virtual database)(virtual database)•breaking DES (Data Encryption Standard)breaking DES (Data Encryption Standard)•SAT (Satisfyability of boolean formula)SAT (Satisfyability of boolean formula)•map coloring with 4 colorsmap coloring with 4 colors NOApplication: DESApplication: DESclear text + key = ciphertextclear text + key = ciphertext““attackatdawn” + 3726495784 = “ojbevjewbvv”attackatdawn” + 3726495784 = “ojbevjewbvv”56-bit key56-bit keyBest classical algorithmBest classical algorithm•36 quadrillion36 quadrillionGrover’s algorithmGrover’s algorithm•118 million118 million2256Amplitude AmplificationAmplitude AmplificationOverviewOverview•Start in an initial state that is equally every Start in an initial state that is equally every statestate•Over time (iterations) amplify amplitude of Over time (iterations) amplify amplitude of solutionsolution•Measure (collapse system) when amplitutde^2 Measure (collapse system) when amplitutde^2 is greater than 0.5 (50%)is greater than 0.5 (50%)11...11...01...0100...01NNNInitial StateInitial StateHadamard GateHadamard GateSteps: N = 2^nSteps: N = 2^n•begin in state begin in state •transform into equal superposition of all states transform into equal superposition of all states using Hadamardusing Hadamard21201 ,21200 0...000  n11...11...01...0100...0100...0 NNNHnOracleOracleOracle picks out which state to amplifyOracle picks out which state to amplifyBlack box:Black box:Oracle is unitary operator UOracle is unitary operator UOO::statesolution - state some - 0xx   0 ,10 xfxf xfqxqxOUOracleOracleConjugate oracle with Hadamard Conjugate oracle with Hadamard transforms so only changes phase (sign)transforms so only changes phase (sign)210201 210210 210000xxxxxOOUU xxxfUO)(1  xfqxqxOUAlgorithmAlgorithmSetup initial stateSetup initial stateRepeat these 4 steps times Repeat these 4 steps times Measure answerMeasure answerN4nnHxxxHxx 00 4.0 , 3. 2. 1.statesolution - state some - 0xx  xxUxfO1kkN00 1. xx 12345670OUInversion about meanInversion about meanUnitary operator describing phase shift:Unitary operator describing phase shift:0 , 3.  xxxnnHxxxH 4.0 , 3. 2.1000110001002IUPInversion about meanInversion about meanUnitary operator describing 2-4:Unitary operator describing 2-4: IHIHnn2002 nnHxxxH 4.0 , 3. 2.122221212222122NNNNNNNNNNIUM xxUxxxxM2MUInversion about meanInversion about mean xxUxxxxM2Complexity O(sqrt(N))Complexity O(sqrt(N))How many calls to oracle does it take to How many calls to oracle does it take to achieve amplitude^2 > 0.5?achieve amplitude^2 > 0.5?•assume all states but one have assume all states but one have •other state is other state is •each iteration each iteration •as long as as long as •for large N this is true long enough for for large N this is true long enough for amplitude^2 > 0.5amplitude^2 > 0.52C21 CNC2by increases  truebe will thisN21LimitationsLimitationsBlack box limitationsBlack box limitationsPhysical implementation (classical Physical implementation (classical memory) implementationsmemory)