Quantum Computing Applied to Optimization

Simple item page
dc.contributor.authorYuzhen, Geen
dc.contributor.authorWatson, Layne T.en
dc.contributor.departmentComputer Scienceen
dc.date.accessioned2013-06-19T14:36:22Zen
dc.date.available2013-06-19T14:36:22Zen
dc.date.issued1999-09-01en
dc.description.abstractOptimization problems represent a class of problems that can be time consuming to solve and very complex. In this paper, a quantum algorithm for solving optimization problems is proposed. The algorithm utilizes the encoding scheme from genetic algorithms to encode the problem and then uses Grover's unitary transformation to seek out a solution. The efficiency of the algorithm depends on the length of the chromosome or the coded variable. As a simple example the satisfiability problem, an NP-complete problem, is examined using the algorithm and the time complexity of solving this problem is greatly improved. The traveling salesman and minimum spanning tree problems are also briefly discussed.en
dc.format.mimetypeapplication/postscripten
dc.identifierhttp://eprints.cs.vt.edu/archive/00000507/en
dc.identifier.sourceurlhttp://eprints.cs.vt.edu/archive/00000507/01/TR-99-03.psen
dc.identifier.trnumberTR-99-03en
dc.identifier.urihttp://hdl.handle.net/10919/20009en
dc.language.isoenen
dc.publisherDepartment of Computer Science, Virginia Polytechnic Institute & State Universityen
dc.relation.ispartofHistorical Collection(Till Dec 2001)en
dc.rightsIn Copyrighten
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.titleQuantum Computing Applied to Optimizationen
dc.typeTechnical reporten
dc.type.dcmitypeTexten

Files

Original bundle
Now showing 1 - 1 of 1
Name:
TR-99-03.ps
Size:
1.35 MB
Format:
Postscript Files
Download

Collections

Computer Science Technical Reports