Skip to main content
Erschienen in:
Buchtitelbild

2017 | OriginalPaper | Buchkapitel

Tools for Quantum and Reversible Circuit Compilation

verfasst von : Martin Roetteler

Erschienen in: Reversible Computation

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Fußnoten
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.
 
Literatur
2.
Zurück zum Zitat Abdessaied, N., Amy, M., Drechsler, R., Soeken, M.: Complexity of reversible circuits and their quantum implementations. Theor. Comput. Sci. 618, 85–106 (2016)MathSciNetCrossRefMATH 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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) 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.
Zurück zum Zitat 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 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
8.
Zurück zum Zitat 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) 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.
Zurück zum Zitat 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) 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.
Zurück zum Zitat Bocharov, A., Cui, S.X., Kliuchnikov, V., Wang, Z.: Efficient topological compilation for weakly-integral anyon model. Phys. Rev. A 93, 012313 (2016)CrossRef 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Bocharov, A., Roetteler, M., Svore, K.M.: Efficient synthesis of probabilistic quantum circuits with fallback. Phys. Rev. A 91, 052317 (2015)CrossRef Bocharov, A., Roetteler, M., Svore, K.M.: Efficient synthesis of probabilistic quantum circuits with fallback. Phys. Rev. A 91, 052317 (2015)CrossRef
13.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Clader, B.D., Jacobs, B.C., Sprouse, C.R.: Preconditioned quantum linear system algorithm. Phys. Rev. Lett. 110, 250504 (2013)CrossRef Clader, B.D., Jacobs, B.C., Sprouse, C.R.: Preconditioned quantum linear system algorithm. Phys. Rev. Lett. 110, 250504 (2013)CrossRef
17.
19.
Zurück zum Zitat 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 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.
Zurück zum Zitat Gidney, C.: StackExchange: creating bigger controlled nots from single qubit, toffoli, and CNOT gates, without workspace (2015) Gidney, C.: StackExchange: creating bigger controlled nots from single qubit, toffoli, and CNOT gates, without workspace (2015)
21.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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) 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.
Zurück zum Zitat 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) 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.
Zurück zum Zitat Häner, T., Roetteler, M., Svore, K.M. Factoring using \(2n{+}2\) qubits with Toffoli based modular multiplication. arXiv preprint (2016). arXiv:1611.07995 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.
Zurück zum Zitat Aram, W., Harrow, A.H., Lloyd, S.: Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103(15), 150502 (2009)MathSciNetCrossRef Aram, W., Harrow, A.H., Lloyd, S.: Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103(15), 150502 (2009)MathSciNetCrossRef
26.
Zurück zum Zitat 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) 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.
Zurück zum Zitat Kempe, J.: Quantum random walks - an introductory overview. Contemporary Phys. 44(4), 307–327 (2003)CrossRef Kempe, J.: Quantum random walks - an introductory overview. Contemporary Phys. 44(4), 307–327 (2003)CrossRef
28.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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) 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.
Zurück zum Zitat Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)MATH Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)MATH
32.
33.
Zurück zum Zitat 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 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.
Zurück zum Zitat Parent, A., Roetteler, M., Svore, K.M.: Reversible circuit compilation with space constraints. arXiv preprint (2015). arXiv:1510.00377 Parent, A., Roetteler, M., Svore, K.M.: Reversible circuit compilation with space constraints. arXiv preprint (2015). arXiv:​1510.​00377
35.
Zurück zum Zitat Ross, N.J., Selinger, P.: Optimal ancilla-free Clifford+T approximation of z-rotations. arXiv preprint (2014). arXiv:403.2975 Ross, N.J., Selinger, P.: Optimal ancilla-free Clifford+T approximation of z-rotations. arXiv preprint (2014). arXiv:​403.​2975
36.
Zurück zum Zitat Selinger, P.: Quantum circuits of \(T\)-depth one. Phys. Rev. A 87, 042302 (2013)CrossRef Selinger, P.: Quantum circuits of \(T\)-depth one. Phys. Rev. A 87, 042302 (2013)CrossRef
37.
Zurück zum Zitat Selinger, P.: Efficient Clifford\(+T\) approximation of single-qubit operators. Quantum Inf. Comput. 15(1–2), 159–180 (2015)MathSciNet Selinger, P.: Efficient Clifford\(+T\) approximation of single-qubit operators. Quantum Inf. Comput. 15(1–2), 159–180 (2015)MathSciNet
38.
Zurück zum Zitat 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 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.
Zurück zum Zitat Wecker, D., Svore, K.M.: LIQ Ui\(|\rangle \): a software design architecture and domain-specific language for quantum computing. arXiv preprint arXiv:1402.4467 Wecker, D., Svore, K.M.: LIQ Ui\(|\rangle \): a software design architecture and domain-specific language for quantum computing. arXiv preprint arXiv:​1402.​4467
Metadaten
Titel
Tools for Quantum and Reversible Circuit Compilation
verfasst von
Martin Roetteler
Copyright-Jahr
2017
DOI
https://doi.org/10.1007/978-3-319-59936-6_1