Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Cover of the book

2017 | OriginalPaper | Chapter

Tools for Quantum and Reversible Circuit Compilation

Author : Martin Roetteler

Published in: Reversible Computation

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We present tools for resource-aware compilation of higher-level, irreversible programs into lower-level, reversible circuits. Our main focus is on optimizing the memory footprint of the resulting reversible networks. We discuss a number of examples to illustrate our compilation strategy for problems at scale, including a reversible implementation of hash functions such as SHA-256, automatic generation of reversible integer arithmetic from irreversible descriptions, as well as a test-bench of Boolean circuits that is used by the classical Circuits and Systems community. Our main findings are that, when compared with Bennett’s original “compute-copy-uncompute”, it is possible to reduce the space complexity by 75% or more, at the price of having an only moderate increase in circuit size as well as in compilation time. Finally, we discuss some emerging new paradigms in quantum circuit synthesis, namely the use of dirty ancillas to save overall memory footprint, probabilistic protocols such as the RUS framework which can help to reduce the gate complexity of rotations, and synthesis methods for higher-dimensional quantum systems.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Erratum to: Designing Parity Preserving Reversible Circuits
next chapter Foundations of Generalized Reversible Computing
Footnotes
1
In quantum computing literature, such subroutines are often implementing “oracles”.
 
2
Indeed, the only non-Toffoli gates in the quantum circuit presented in [24] are single qubit Hadmard gates, single qubit phase rotations, and single qubit measurements. The vast majority of other gates in the circuit form one big circuit component which can be classically simulated and tested.
 
Literature
1.
2.
Abdessaied, N., Amy, M., Drechsler, R., Soeken, M.: Complexity of reversible circuits and their quantum implementations. Theor. Comput. Sci. 618, 85–106 (2016)MathSciNetCrossRefMATH
3.
Amy, M., Maslov, D., Mosca, M., Roetteler, M.: A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Trans. Comput. Aided Des. Integr. Circ. Syst. 32(6), 818–830 (2013)CrossRef
4.
Amy, M., Di Matteo, O., Gheorghiu, V., Mosca, M., Parent, A., Schanck, J.M.: Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3. IACR Cryptol. ePrint Arch. 2016, 992 (2016)
5.
Barenco, A., Bennett, C.H., Cleve, R., DiVincenzo, D.P., Margolus, N., Shor, P., Sleator, T., Smolin, J.A., Weinfurter, H.: Elementary gates for quantum computation. Phys. Rev. A 52(5), 3457 (1995)CrossRef
6.
7.
8.
Berry, D.W., Childs, A.M., Cleve, R., Kothari, R., Somma, R.D.: Exponential improvement in precision for simulating sparse hamiltonians. In: Symposium on Theory of Computing (STOC 2014), pp. 283–292 (2014)
9.
Berry, D.W., Childs, A.M., Kothari, R.: Hamiltonian simulation with nearly optimal dependence on all parameters. In: IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 792–809 (2015)
10.
Bocharov, A., Cui, S.X., Kliuchnikov, V., Wang, Z.: Efficient topological compilation for weakly-integral anyon model. Phys. Rev. A 93, 012313 (2016)CrossRef
11.
Bocharov, A., Cui, S.X., Roetteler, M., Svore, K.M.: Improved quantum ternary arithmetics. Quantum Inf. Comput. 16(9&10), 862–884. arXiv preprint (2016). arXiv:​1512.​03824
12.
Bocharov, A., Roetteler, M., Svore, K.M.: Efficient synthesis of probabilistic quantum circuits with fallback. Phys. Rev. A 91, 052317 (2015)CrossRef
13.
Bocharov, A., Roetteler, M., Svore, K.M.: Efficient synthesis of universal repeat-until-success circuits. Phys. Rev. Lett. 114, 080502. arXiv preprint (2015). arXiv:​1404.​5320
14.
Bocharov, A., Roetteler, M., Svore, K.M.: Factoring with qutrits: Shor’s algorithm on ternary and metaplectic quantum architectures. arXiv preprint (2016). arXiv:​1605.​02756
15.
Chrzanowska-Jeske, M., Mishchenko, A., Perkowski, M.A.: Generalized inclusive forms - new canonical reed-muller forms including minimum esops. VLSI Des. 2002(1), 13–21 (2002)MathSciNetCrossRef
16.
Clader, B.D., Jacobs, B.C., Sprouse, C.R.: Preconditioned quantum linear system algorithm. Phys. Rev. Lett. 110, 250504 (2013)CrossRef
17.
18.
19.
Fowler, A.G., Mariantoni, M., Martinis, J.M., Cleland, A.N.: Surface codes: towards practical large-scale quantum computation. Phys. Rev. A 86, 032324 (2012). arXiv:​1208.​0928
20.
Gidney, C.: StackExchange: creating bigger controlled nots from single qubit, toffoli, and CNOT gates, without workspace (2015)
21.
Green, A.S., Lumsdaine, P.L.F., Ross, N.J., Selinger, P., Valiron, B.: An introduction to quantum programming in quipper. In: Dueck, G.W., Miller, D.M. (eds.) RC 2013. LNCS, vol. 7948, pp. 110–124. Springer, Heidelberg (2013). doi:10.​1007/​978-3-642-38986-3_​10 CrossRef
22.
Green, A.S., Lumsdaine, P.L., Ross, N.J., Selinger, P., Valiron, B.: Quipper: a scalable quantum programming language. In: Proceedings of Conference on Programming Language Design and Implementation (PLDI 2013). ACM (2013)
23.
Grover, L.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Symposium on Theory of Computing (STOC 1996), pp. 212–219. ACM Press (1996)
24.
Häner, T., Roetteler, M., Svore, K.M. Factoring using \(2n{+}2\) qubits with Toffoli based modular multiplication. arXiv preprint (2016). arXiv:​1611.​07995
25.
Aram, W., Harrow, A.H., Lloyd, S.: Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103(15), 150502 (2009)MathSciNetCrossRef
26.
Heckey, J., Patil, S., JavadiAbhari, A., Holmes, A., Kudrow, D., Brown, K.R., Franklin, D., Chong, F.T., Martonosi, M.: Compiler management of communication and parallelism for quantum computation. In: Proceedings of the Twentieth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2015), pp. 445–456. ACM (2015)
27.
Kempe, J.: Quantum random walks - an introductory overview. Contemporary Phys. 44(4), 307–327 (2003)CrossRef
28.
Kliuchnikov, V., Maslov, D., Mosca, M.: Practical approximation of single-qubit unitaries by single-qubit quantum Clifford and \(T\) circuits. IEEE Trans. Comput. 65(1), 161–172 (2016)MathSciNetCrossRefMATH
29.
Maslov, D.: On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization. Phys. Rev. A 93, 022311 (2016)CrossRef
30.
Mishchenko, A., Brayton, R.K., Chatterjee, S.: Boolean factoring and decomposition of logic networks. In: Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, pp. 38–44. IEEE Press (2008)
31.
Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)MATH
32.
33.
Paetznick, A., Svore, K.M.: Repeat-until-success: non-deterministic decomposition of single-qubit unitaries. Quantum Inf. Comput. 4(15&16), 1277–1301 (2014)MathSciNet
34.
35.
Ross, N.J., Selinger, P.: Optimal ancilla-free Clifford+T approximation of z-rotations. arXiv preprint (2014). arXiv:​403.​2975
36.
Selinger, P.: Quantum circuits of \(T\)-depth one. Phys. Rev. A 87, 042302 (2013)CrossRef
37.
Selinger, P.: Efficient Clifford\(+T\) approximation of single-qubit operators. Quantum Inf. Comput. 15(1–2), 159–180 (2015)MathSciNet
38.
Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5), 1484–1509 (1997)MathSciNetCrossRefMATH
39.
40.
Wecker, D., Svore, K.M.: LIQ Ui\(|\rangle \): a software design architecture and domain-specific language for quantum computing. arXiv preprint arXiv:​1402.​4467
Metadata
Title
Tools for Quantum and Reversible Circuit Compilation
Author
Martin Roetteler
Copyright Year
2017
Book
Reversible Computation

Print ISBN: 978-3-319-59935-9

Electronic ISBN: 978-3-319-59936-6

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-59936-6_1

Premium Partner

    Image Credits