KEG PARTY!!!!!Trugenberger’s Quantum Optimization AlgorithmOverviewSlide 4Two Main Sources of InspirationWhat is quantum parallelism?What is Simulated Annealing?Slide 8Basic IdeaThe high-level algorithmSlide 11Representing the Problem: Graph ColoringCost Functions in GeneralSkeleton of the U operatorWhat is Cnor?Slide 16And Cmin and Cmax?Fleshing out U for Graph ColoringStill don’t quite have our magic operatorTake Advantage of Phase DifferencesUcs: The Answer to our ProblemsControl Bits also need some modificationMatlab results for Graph ColoringMeasurementSlide 25Slide 26Slide 27Matlab Results after 26 “Ideal” IterationsLife Isn’t FairThe TradeoffSlide 31Some good newsAnalogy to Simulated AnnealingA Whole New Meaning for kEquations affected by generalizationEquations effected by generalizationSlide 37U operatorCost Function Oracle?Only a HeuristicSlide 41Future WorkReferenceKEG PARTY!!!!!Keg Party tomorrow nightProf. Markov will give out extra credit to anyone who attends**Note: This statement is a lieTrugenberger’s Quantum Optimization AlgorithmOverview and ApplicationOverviewInspirationBasic IdeaMathematical and Circuit RealizationsLimitationsFuture WorkOverviewInspirationBasic IdeaMathematical and Circuit RealizationsLimitationsFuture WorkTwo Main Sources of InspirationExploiting Quantum ParallelismAnalogy of Simulated AnnealingWhat is quantum parallelism?What is quantum parallelism?We can represent super-positions of specific instances of data in a single quantum stateWe can then apply a single operator to this quantum state and thereby change all instances of data in a single stepWhat is Simulated Annealing?Comes from physical annealingIteratively heat and cool a material until there’s a high probability of obtaining a crystalline structureCan be represented as a computational algorithmIteratively make changes to your data until there is a high probability of ending up with the data you wantOverviewInspirationBasic IdeaMathematical and Circuit RealizationsLimitationsFuture WorkBasic IdeaUse this inspiration to come up with a more generalized quantum searching algorithmTrugenberger’s algorithm does a heuristic search on the entire data set by applying a cost function to each element in the data setGoal is to find a minimal cost solutionThe high-level algorithmUse quantum parallelism to apply the cost function to all elements of the data set simultaneously in one stepIteratively apply this cost function to the data setNumber of iterations is analogous to an instance of simulated annealingOverviewInspirationBasic IdeaMathematical and Circuit RealizationsLimitationsFuture WorkRepresenting the Problem: Graph ColoringSuper-position of the data elementsN instancesUse n qubits to represent the N instancesEach instance encoded as a binary number I^k whose value is between 0 and 2^nNkkINS1|1|Cost Functions in General should return a cost for that data elementIn this algorithm we will want to minimize costData elements with lower cost are better solutions)(kICSkeleton of the U operatorThe imaginary exponential of the cost function is the main engine of the quantum optimization))(2exp(knorIallforCiUWhat is Cnor?We know in general that exp(i*theta) = cos(theta) + i*sin(theta)Since U will need the imaginary exponential of the cost function, we want to normalize the cost functionBy normalizing, we ensure that the cost function result is between 0 and pi/2What is Cnor?C(I^k) can at most be Cmax and is at least CminCnor is always between 1 and 0minmaxmin)()(CCCICICkknorAnd Cmin and Cmax?Simple to determine for graph coloringCmin = 0 (no pair connected vertices shares the same color)Cmax = # of edges (every pair of connected vertices shares the same color)More general method for determining Cmin and Cmax will be introduced laterFleshing out U for Graph Coloring),...,()1,... ,1(2)0,... ,0(211 nnnorCnoriCieediagUStill don’t quite have our magic operatorAs written, U by itself will not lower the probability amplitude of bad states and increase the amplitude of good statesIf we apply U now, the probability amplitudes of both the best and worst data elements will be the same and differ only in phaseTake Advantage of Phase DifferencesWe can accomplish the proper amplitude modifications by using a controlled form of the U gateCan’t be an ordinary controlled gate thoughUcs: The Answer to our ProblemsUcs is a controlled gate that applies U to the data elements when the control bit is |0> and applies the inverse of U when the control bit is |1>1|11||00| UUUcccccsControl Bits also need some modificationControl bit always starts out in |0> stateBefore applying Ucs, we run the control bit through a Hadamard gateAfter applying Ucs, we run it through another Hadamard gateThis gives us a nice super-position of minimal and maximal cost elementsMatlab results for Graph Coloring Data element Probability amplitude000 0001 0.25010 0.3536011 0.25100 0.25101 0.3536111 0-----------------------------------------------------------------000 i*0.3536001 i*0.25010 0011 i*0.25100 i*0.25101 0110 i*0.25111 i*0.3536MeasurementIf we were to measure the control bit now and get a |0>, we’d know that the data will get the “first half” of the super-position: Data element Probability amplitude000 0001 0.25010 0.3536011 0.25100 0.25101 0.3536111 0MeasurementHowever if we got a |1> instead, we’d know that the data will get the “second half” of the super-position: Data element Probability amplitude000 i*0.3536001 i*0.25010 0011 i*0.25100 i*0.25101 0110 i*0.25111 i*0.3536MeasurementA control qubit measurement of |0> means we have a better chance of getting a lower cost state (a good solution)A control qubit measurement of |1> means we have a better chance of getting a higher cost state (a bad solution)MeasurementAssume the world is perfect and we always get a |0> when we measure the control qubitWe can effectively increase our probability of getting good solutions and decrease the probability of getting bad solutions by iterating the H,Ucs,H operationsWe iterate by duplicating the circuit and adding more control qubitsMatlab Results after 26 “Ideal”