Show simple item record

dc.contributor.author
Häner, Thomas
dc.contributor.author
Roetteler, Martin
dc.contributor.author
Svore, Krysta M.
dc.date.accessioned
2020-07-13T09:27:31Z
dc.date.available
2017-06-12T18:21:56Z
dc.date.available
2020-05-11T10:48:25Z
dc.date.available
2020-07-13T09:27:31Z
dc.date.issued
2016-11-23
dc.identifier.uri
http://hdl.handle.net/20.500.11850/126075
dc.description.abstract
We describe an implementation of Shor's quantum algorithm to factor n-bit integers using only 2n+2 qubits. In contrast to previous space-optimized implementations, ours features a purely Toffoli based modular multiplication circuit. The circuit depth and the overall gate count are in O(n^3) and O(n^3 log(n)), respectively. We thus achieve the same space and time costs as Takahashi et al., while using a purely classical modular multiplication circuit. As a consequence, our approach evades most of the cost overheads originating from rotation synthesis and enables testing and localization of faults in both, the logical level circuit and an actual quantum hardware implementation. Our new (in-place) constant-adder, which is used to construct the modular multiplication circuit, uses only dirty ancilla qubits and features a circuit size and depth in O(n log(n)) and O(n), respectively.
en_US
dc.language.iso
en
en_US
dc.publisher
Cornell University
en_US
dc.subject
Quantum circuits
en_US
dc.subject
quantum arithmetic
en_US
dc.subject
Shor’s algorithm
en_US
dc.title
Factoring using 2n+2 qubits with Toffoli based modular multiplication
en_US
dc.type
Working Paper
ethz.journal.title
arXiv
ethz.pages.start
1611.07995
en_US
ethz.size
12 p.
en_US
ethz.identifier.arxiv
1611.07995
ethz.publication.place
Ithaca, NY
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02010 - Dep. Physik / Dep. of Physics::02511 - Institut für Theoretische Physik / Institute for Theoretical Physics::03622 - Troyer, Matthias (ehemalig) / Troyer, Matthias (former)
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02010 - Dep. Physik / Dep. of Physics::02511 - Institut für Theoretische Physik / Institute for Theoretical Physics::03622 - Troyer, Matthias (ehemalig) / Troyer, Matthias (former)
ethz.date.deposited
2017-06-12T18:22:07Z
ethz.source
ECIT
ethz.identifier.importid
imp5936551a5041267697
ethz.ecitpid
pub:188746
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2017-07-12T14:50:52Z
ethz.rosetta.lastUpdated
2020-07-13T09:27:46Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Factoring%20using%202n+2%20qubits%20with%20Toffoli%20based%20modular%20multiplication&rft.jtitle=arXiv&rft.date=2016-11-23&rft.spage=1611.07995&rft.au=H%C3%A4ner,%20Thomas&Roetteler,%20Martin&Svore,%20Krysta%20M.&rft.genre=preprint&
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record