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.
Benioff, P. (2002) Space Searches with a Quantum Robot. AMS Contemporary Math Series, 305, 1-12. https://doi.org/10.1090/conm/305/05212
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
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
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
Lukac, M., Kameyama, M. and Perkowski, M. (2013) Quantum Finite State Machines—A Circuit Based Approach. International Journal of Unconventional Computing, 9, 267-301.
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.
Lukac, M. (2009) Quantum Inductive Learning and Quantum Logic Synthesis. Ph.D. Thesis, Portland State University, Portland.
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
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
Wakerly, J.F. (2005) Digital Design: Principles and Practices. 4th Edition, Pearson, London.
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
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
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.
Morris Mano, M. and Ciletti, M.D. (2012) Digital Design with an Introduction to the Verilog HDL. 5th Edition, Pearson, London.
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
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
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
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.
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
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
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
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
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
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
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
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
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
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
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
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
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
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.