We present a new approach to the synthesis of quantum automata. In previous research, reversible quantum automata were designed from tabular specifications or state graphs, and minimum length codes, which lead to circuits with Toffoli gates with high numbers of inputs and thus to high quantum costs. This paper is the first to present a method to synthesize Sequential Quantum Circuits directly from flowcharts. In this paper, we directly map flowcharts to reversible/quantum circuits, using only inverters, 2*2 Feynman gates and 3*3 Toffoli gates, and thus reducing quantum costs. Our method has been confirmed by experiments on several benchmarks of practical flowcharts.
References
[1]
Benioff, P. (2002) Space Searches with a Quantum Robot. AMS Contemporary Math Series, 305, 1-12. https://doi.org/10.1090/conm/305/05212
[2]
Benioff, P. (1982) Quantum Mechanical Models of Turing Machines That Dissipate No Energy. Physical Review Letter, 48, 1581-1585.
https://doi.org/10.1103/PhysRevLett.48.1581
[3]
Lukac, M. and Perkowski, M. (2009) Quantum Finite State Machines as Sequential Quantum Circuits. 2009 39th International Symposium on Multiple-Valued Logic, Naha, 21-23 May 2009, 92-97. https://doi.org/10.1109/ISMVL.2009.46
[4]
Lukac, M. and Perkowski, M. (2010) Evolving Logic Synthesis of Quantum Finite State Machines for Sequence Detection. In: Korosec, P., Ed., New Achievements in Evolutionary Computation, IntechOpen, London, 77-112.
https://doi.org/10.5772/8049
[5]
Lukac, M., Kameyama, M. and Perkowski, M. (2013) Quantum Finite State Machines—A Circuit Based Approach. International Journal of Unconventional Computing, 9, 267-301.
[6]
Fiszer, R. (2014) Synthesis of Irreversible Incompletely Specified Multi-Output Functions to Reversible EOSOPS Circuits with PSE Gates. Master’s Thesis, Portland State University, Portland.
[7]
Lukac, M. (2009) Quantum Inductive Learning and Quantum Logic Synthesis. Ph.D. Thesis, Portland State University, Portland.
[8]
Nielsen, M.A. and Chuang, I.L. (2011) Quantum Computation and Quantum Information. 10th Anniversary Edition, Cambridge University Press, Cambridge.
https://doi.org/10.1017/CBO9780511976667
[9]
Kumar, M., Boshra-riad, S., Nachimuthu, Y. and Perkowski, M.A. (2010) Comparison of State Assignment Methods for “Quantum Circuit” Model of Permutative Quantum State Machines. IEEE Congress on Evolutionary Computation, Barcelona, 18-23 July 2010, 1-8. https://doi.org/10.1109/CEC.2010.5586003
[10]
Wakerly, J.F. (2005) Digital Design: Principles and Practices. 4th Edition, Pearson, London.
[11]
Brodsky, A. and Pippenger, N. (2002) Characterization of 1-Way Quantum Finite Automata. SIAM Journal on Computing, 31, 1456-1478.
https://doi.org/10.1137/S0097539799353443
[12]
Khan, M.H.A. and Perkowski, M.A. (2011) Synthesis of Reversible Synchronous Counters. 2011 41st IEEE International Symposium on Multiple-Valued Logic, Tuusula, 23-25 May 2011, 242-247. https://doi.org/10.1109/ISMVL.2011.25
[13]
Thapliyal, H. and Srinivas, M.B. (2005) A Beginning in the Reversible Logic Synthesis of Sequential Circuits. Proceedings of Military and Aerospace Applications of Programmable Devices and Technologies International Conference (MAPLD), Washington, DC, 6-8 September 2005, 1-5.
[14]
Morris Mano, M. and Ciletti, M.D. (2012) Digital Design with an Introduction to the Verilog HDL. 5th Edition, Pearson, London.
[15]
Drechsler, R. and Wille, R. (2011) From Truth Tables to Programming Languages: Progress in the Design of Reversible Circuits. 2011 41st IEEE International Symposium on Multiple-Valued Logic, Tuusula, 23-25 May 2011, 78-85.
https://doi.org/10.1109/ISMVL.2011.40
[16]
Bernasconi, A., Ciriani, V., Luccio, F. and Pagli, L. (2013) Compact DSOP and Partial DSOP Forms. Theory of Computing Systems, 53, 583-608.
https://doi.org/10.1007/s00224-013-9447-2
[17]
Hawash, M., Perkowski, M., Bleiler, S., Caughman, J. and Hawash, A. (2011) Reversible Function Synthesis of Large Reversible Functions with No Ancillary Bits Using Covering Set Partitions. 2011 Eighth International Conference on Information Technology: New Generations, Las Vegas, 11-13 April 2011, 1008-1013.
https://doi.org/10.1109/ITNG.2011.174
[18]
Schaeffer, B. (2017) Synthesis of Linear Reversible Circuit and EXOR-AND-Based Circuits for Incompletely Specified Multi-Output Functions. Ph.D. Thesis, Portland State University, Portland.
[19]
Maslov, D. and Dueck, G.W. (2003) Improved Quantum Cost for n-Bit Toffoli Gates. Electronics Letters, 39, 1790-1791. https://doi.org/10.1049/el:20031202
[20]
Miller, D.M., Maslov, D. and Dueck, G.W. (2003) A Transformation Based Algorithm for Reversible Logic Synthesis. Proceedings of the 40th Annual Design Automation Conference, Anaheim, 2-6 June 2003, 318-232.
https://doi.org/10.1145/775832.775915
[21]
Maslov, D., Dueck, G.W. and Miller, D.M. (2007) Techniques for the Synthesis for Reversible Toffoli Networks. ACM Transactions on Design Automation of Electronics Systems, 12, 42-es. https://doi.org/10.1145/1278349.1278355
[22]
Maslov, D., Dueck, G.W. and Miller, D.M. (2005) Synthesis of Fredkin-Toffoli Reversible Networks. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 13, 765-769. https://doi.org/10.1109/TVLSI.2005.844284
[23]
Meuli, G., Schmitt, B., Ehlers, R., Riener, H. and Micheli, G.D. (2019) Evaluating ESOP Optimization Methods in Quantum Compilation Flows. In: Thomsen, M. and Soeken, M., Eds., RC 2019: Reversible Computation, Springer, Cham, 191-206.
https://doi.org/10.1007/978-3-030-21500-2_12
[24]
Schmitt, B., Soeken, M., Micheli, G.D. and Mishchenko, A. (2019) Scaling-Up ESOP Synthesis for Quantum Compilation. 2019 IEEE 49th International Symposium on Multiple-Valued Logic (ISMVL), Fredericton, 21-23 May 2019, 13-18.
https://doi.org/10.1109/ISMVL.2019.00011
[25]
Dhawan, S. and Perkowski, M. (2012) ESOP-Inspired Synthesis Method for Ternary Permutative Quantum Circuits. 2012 IEEE 42nd International Symposium on Multiple-Valued Logic, Victoria, 14-16 May 2012, 57-62.
https://doi.org/10.1109/ISMVL.2012.25
[26]
Riener, H., Ehlers, R., Schmitt, B.O. and Micheli, G.D. (2018) Exact Synthesis of ESOP Forms. In: Drechsler, R. and Soeken, M., Eds., Advanced Boolean Techniques, Springer, Cham, 177-194. https://doi.org/10.1007/978-3-030-20323-8_8
[27]
Choe, S. and Perkowski, M. (2022) Continuous Variable Quantum MNIST Classifiers—Classical-Quantum Hybrid Quantum Neural Networks. Journal of Quantum Information Science, 12, 37-51. https://doi.org/10.4236/jqis.2022.122005
[28]
Courtemanche, N. and Crépeau, C. (2021) A Sufficient Clarification of “Super-Quantum Correlations: A Necessary Clarification” by Pierre Uzan. Journal of Quantum Information Science, 11, 65-70. https://doi.org/10.4236/jqis.2021.112005
[29]
Raghuvanshi, A. and Perkowski, M.A. (2010) Fuzzy Quantum Circuits to Model Emotional Behaviors of Humanoid Robots. IEEE Congress on Evolutionary Computation, Barcelona, 18-23 July 2010, 1-8.
https://doi.org/10.1109/CEC.2010.5586038
[30]
Raghuvanshi, A., Fan, Y., Woyke, M. and Perkowski, M. (2007) Quantum Robots for Teenagers. Proceedings of the IEEE 37th International Symposium on Multiple-Valued Logic, Oslo, 13-16 May 2007, 18.
https://doi.org/10.1109/ISMVL.2007.46
[31]
Deng, R., Huang, Y. and Perkowski, M. (2021) Quantum Motions and Emotions for a Humanoid Robot Actor. Proceedings of the IEEE 51st International Symposium on Multiple-Valued Logic, Nur-sultan, 25-27 May 2021, 207-214.
https://doi.org/10.1109/ISMVL51352.2021.00043
[32]
Sarkar, V. and Simons, B. (1993) Parallel Programs Graphs and Their Classification. Proceedings of Languages and Compilers for Parallel Computing Conference, 6th International Workshop, Portland, 12-14 August 1993, 633-655.
