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