Quantum Search Algorithms for Multiple Solution ProblemsOutlineReferencesNotationGrover’s Algorithm for Unique Solution CaseUnique Solution Case Recap (…contd)Slide 7Multiple Solutions: Multiplicity knownSlide 9Slide 10Slide 11Slide 12Multiple Solutions: unknown MultiplicitySlide 14Slide 15Quantum CountingSlide 17Slide 18Slide 19Quantum Search Algorithms for Multiple Solution ProblemsEECS 598 Class PresentationManoj RajagopalanOutline1. Recap of Grover’s algorithm for the unique solution case2. Grover’s algorithm for multiple solutions: multiplicity known3. Quantum search algorithm for multiple solutions: multiplicity unknown4. Quantum counting to determine multiplicityReferences1. Quantum Computing and Quantum Information textbook2. “A fast quantum mechanical algorithm for database search”, LK Grover, 19963. “Tight bounds on quantum searching”, M Boyer, G Brassard, P Hoyer, 19964. “Quantum counting”, G Brassard, P Hoyer, A Tapp, 19981. n = # qubits in the system2. N = # of possible values of n qubits = 2n3. M = multiplicity of solution4. k = probability amplitude of system in solution state5. l = probability amplitude of system in non-solution state6. A = set of indices that denote solutions (good states)7. B = set of indices denoting bad states.8  = rotation angle corresponding to Grover operatorNotationGiven F:{0,1}n  {0,1}, find i0  F(i0)=1 and  i  i0 F(i)=01. Set up initial state |0 n2. Apply the Hadamard transformHn |0  | = Let i0 be the solution: | = k |i0 + 3. Grover operator made of 4 steps•Apply the oracle•Apply Hn•Conditional phase shift:•Apply HnGrover’s Algorithm for Unique Solution CaseNiiN02/11 0ijjlxxx 0)1(Unique Solution Case Recap (…contd)NlkNlNNlNklNNkNNklklkjjjjjjjjGj1221)1(22),(),(0110114. Apply the Grover operator. After j iterations,• Need bound on the number of iterationsUnique Solution Case Recap (…contd)Let sin2 = 0 <   N1))12cos((11))12sin(( jNljkjjFor km = 1, (2m+1) =  /2 => For large N,   sin  =  m  214~mN1N42Multiple Solutions: Multiplicity knownGiven F:{0,1}n  {0,1}, find all i{0,1}n  F(i)=1M = number of solutions > 1Define ‘good states’ A = {i | F(i) = 1} |A| = M‘bad states’ B = {j | F(j) = 0 } |B| = N - MSuffices to tackle good and bad states as groupsk = probability amplitude of each solution (element of set A)l = probability amplitude of each element of set BMk2 + (N-M)l2 = 1Multiple Solutions: Multiplicity knownGrover’s algorithm for the multiple solution case• Structurally the same as that in the case of unique solution1. Set up initial state |0 n2. Apply the Hadamard transform3. Apply Grover operator repeatedly•Apply the oracle•Apply Hn•Conditional phase shift•Apply Hn• Differs in the oracle implementation: Oracle lends a relative phase shift of –1 to all solutionsMultiple Solutions: Multiplicity knownDefineBiAiiliklk ),(20sin))12cos((1))12sin((1),(),(2NMjMNljMklklkjjjjGjAfter j iterations:Multiple Solutions: Multiplicity knownLet m = upper bound on number of iterationsWe want lm = 0cos ((2m+1)) = => 2214~m21~4 mmm| cos(2m+1) |  | sin  |Probability of failure after exactly m iterations(N-M) lm2 = cos2((2m+1))  sin2 = NMNegligible for M << NMultiple Solutions: Multiplicity knownFor M << N,   sin  MNm4sin44Knowing M, we can predetermine the upper bound on the number of iterations, m.Unique solution problem is a special case of this for M=1.Multiple Solutions: unknown MultiplicityNumber of iterations required to obtain a solution with significant confidence depends on the solution’s multiplicity.If M is not known, then there is no way of telling how many iterations will suffice.Take m = to be on the safe side? (max # iterations)No! Probability of success minuscule when M = 4a2 where a is a small integer.N4Multiple Solutions: unknown MultiplicityModified procedure for unknown M:1. Initialize m = 1 and  = 8/7 (actually 1 <  < 4/3)2. Choose integer j such that 0  j  m3. Apply j iterations of Grover’s algorithm4. Measure and let outcome be i5. If F(i) == 1 then solution found: exit program6. Else m = min(m, ): goto step #2Theorem: This algorithm finds a solution in O( )NMN /Multiple Solutions: unknown MultiplicityFor M > 3N/4 constant expected time by classical samplingFor 0 < M  3N/4, runtime = O( )For M << N, runtime < 6 times runtime_if_M_were_knownKnowing the number of solutions helps in reducing runtime. This motivates quantum countingMN /Quantum CountingAim: To determine the number of solutions M to an N item unstructured search problemClassical computing consults the oracle (N) times to determine MQuantum computing can combine Grover’s algorithm and phase estimation to determine M much faster!Why count?• Fast estimation of M => rapid solution detection• Is there a solution at all? NP-Complete problemsQuantum CountingRecall: The computational bases can be partitioned into two subsets, the ‘good states’ set A containing all the solutions, andBiAiiliklk ),(NMNMNLetting,sin,cosNMNMNwe get,2cos2sin2sin2cosGin the basis.,Quantum CountingEigenvalues of G are ei2 and ei(2-2)The value of  can be determined by phase estimationFrom , the value of M can be calculatedPHASE ESTIMATIONGiven a unitary operator U and one of its eigenvectors, the phase  of its corresponding eigenvalue ei2 is determinedQuantum CountingComplexity of phase estimation algorithmsProbabilityof successError in MAbsolute, maxRuntime, PEvaluations of FP  428222cMcNc28NPMNP22243cM))loglog(( MNNc