A Web-based Tool for Visual Identification of Novel Genes

1 slides
0.75 MB
536 views

Presentation Transcript

1

Quantum Algorithms for the Moving-Target Traveling Salesperson ProblemUnitary Transform changes states - Conjugate Transpose = InverseJennifer Mifflin and Gabriel RobinsComputer ScienceDepartment ofSchool of Engineeringand Applied ScienceUniversity of Virginia{jmm6ad, robins}@cs.virginia.edu(434) 982-2207 www.cs.virginia.eduPost-processing CapabilitiesSchroedinger’s CatLike Schroedinger’s Cat, which is in a superposed alive/dead state, a qubit (quantum bit) can be both 0 and 1 simultaneously!Quantum register - the “ket”: Superposition of states: Quantum Computing NotationWhere:Superposition of QubitsMatrix Representation2Nx1 matrix represents N qubits (x-1)th row represents amplitude of x value Example, 1 qubit: is represented by: is represented by: by: Unitary TransformationExample: Hadamard TransformThe Ubiquitous CNot GateThe CNot gate negates the second bit only if the control bit is 1 (true)Visual RepresentationHMoving-Target Traveling Salesperson ProblemOriginGiven N moving targets with constant velocities, find a min-time path that intercepts all targetsMoving-Target TSP is IntractableProof: NP-Complete TSP is a special case of Moving-Target TSP (with zero velocities)abcde(V=0)(V=0)(V=0)(V=0)(V=0)Moving-Target TSP is NP-CompleteContained in NP: Decision version: path with time < T? Non-deterministically travel all paths Check each path length against T Optimization version: What is min-time path? Upper-bound T w/initial random path Binary search the range using T/2, T/4, etc. to find optimal min-time pathHamiltonian Path Solution: Traverse Every Possible Path For N nodes, use N2+N qubits Separate into N+1 equal registers First register - parity of times a node has been visited Last N registers track path After N+1 steps: 1’s in parity register imply Hamiltonian PathStart StateOrFirst StepSecond StepThird StepControl bitHHTransition for 2J Adjacent Nodes At each step, this transition is applied Places 2J qubits into equal superpositionExtend to TSP: Another register: Large enough to hold longest path Each iteration, add edge weight to register Extend to Moving-Target TSP: Add time register Track the total time elapsedExtend to (Moving-Target) TSPGrover’s Search Algorithm Final Steps Obtain superposition of all paths Grover’s algorithm for Hamiltonian paths Grover’s algorithm for min-time path O(2N/2) time complexity Superposition achieved in linear time Need logarithmic search algorithm to achieve linear time complexity Implementation prototypeSummaryQubit 1Qubit 2Hadamard TransformCNotNot1423O( ) for K items Improve (Moving-Target) TSP Complexity Improve search algorithm P=NP for quantum computer? Future WorkQubit 1Qubit 2Qubit 3Qubit 4

Browse More Presentations

Last Updated: 8th March 2018