Show simple item record

dc.contributor.author
Johannsen, Daniel
dc.contributor.author
Kurur, Piyush P.
dc.contributor.author
Lengler, Johannes
dc.date.accessioned
2021-05-10T04:57:01Z
dc.date.available
2017-06-11T01:22:53Z
dc.date.available
2021-05-10T04:57:01Z
dc.date.issued
2014-01
dc.identifier.issn
0178-4617
dc.identifier.issn
1432-0541
dc.identifier.other
10.1007/s00453-013-9784-1
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/76136
dc.identifier.doi
10.3929/ethz-b-000076136
dc.description.abstract
In this article, we formulate and study quantum analogues of randomized search heuristics, which make use of Grover search (in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 212–219. ACM, New York, 1996) to accelerate the search for improved offsprings. We then specialize the above formulation to two specific search heuristics: Random Local Search and the (1+1) Evolutionary Algorithm. We call the resulting quantum versions of these search heuristics Quantum Local Search and the (1+1) Quantum Evolutionary Algorithm. We conduct a rigorous runtime analysis of these quantum search heuristics in the computation model of quantum algorithms, which, besides classical computation steps, also permits those unique to quantum computing devices. To this end, we study the six elementary pseudo-Boolean optimization problems OneMax, LeadingOnes, Discrepancy, Needle, Jump, and TinyTrap. It turns out that the advantage of the respective quantum search heuristic over its classical counterpart varies with the problem structure and ranges from no speedup at all for the problem Discrepancy to exponential speedup for the problem TinyTrap. We show that these runtime behaviors are closely linked to the probabilities of performing successful mutations in the classical algorithms.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Springer
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.subject
Theory
en_US
dc.subject
Evolutionary computation
en_US
dc.subject
Quantum algorithm
en_US
dc.subject
Runtime analysis
en_US
dc.title
Evolutionary Algorithms for Quantum Computers
en_US
dc.type
Journal Article
dc.rights.license
In Copyright - Non-Commercial Use Permitted
dc.date.published
2013-04-20
ethz.journal.title
Algorithmica
ethz.journal.volume
68
en_US
ethz.journal.issue
1
en_US
ethz.journal.abbreviated
Algorithmica
ethz.pages.start
152
en_US
ethz.pages.end
189
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.notes
It was possible to publish this article open access thanks to a Swiss National Licence with the publisher.
en_US
ethz.identifier.wos
ethz.identifier.scopus
ethz.publication.place
New York
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03672 - Steger, Angelika / Steger, Angelika
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03672 - Steger, Angelika / Steger, Angelika
ethz.date.deposited
2017-06-11T01:25:49Z
ethz.source
ECIT
ethz.identifier.importid
imp5936514fe154f13554
ethz.ecitpid
pub:120392
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-07-12T23:58:52Z
ethz.rosetta.lastUpdated
2018-11-02T11:52:43Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Evolutionary%20Algorithms%20for%20Quantum%20Computers&rft.jtitle=Algorithmica&rft.date=2014-01&rft.volume=68&rft.issue=1&rft.spage=152&rft.epage=189&rft.issn=0178-4617&1432-0541&rft.au=Johannsen,%20Daniel&Kurur,%20Piyush%20P.&Lengler,%20Johannes&rft.genre=article&rft_id=info:doi/10.1007/s00453-013-9784-1&
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record