{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:45:42Z","timestamp":1742913942903,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":54,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662564981"},{"type":"electronic","value":"9783662564998"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-662-56499-8_4","type":"book-chapter","created":{"date-parts":[[2018,1,27]],"date-time":"2018-01-27T07:53:13Z","timestamp":1517039593000},"page":"41-76","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Algebraic and Logical Emulations of Quantum Circuits"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7382-7178","authenticated-orcid":false,"given":"Kenneth","family":"Regan","sequence":"first","affiliation":[]},{"given":"Amlan","family":"Chakrabarti","sequence":"additional","affiliation":[]},{"given":"Chaowen","family":"Guan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,1,28]]},"reference":[{"key":"4_CR1","first-page":"102","volume":"5","author":"C Dawson","year":"2004","unstructured":"Dawson, C., Haselgrove, H., Hines, A., Mortimer, D., Nielsen, M., Osborne, T.: Quantum computing and polynomial equations over the finite field $$Z_2$$ Z 2 . Quantum Inf. Comput. 5, 102\u2013112 (2004)","journal-title":"Quantum Inf. Comput."},{"key":"4_CR2","unstructured":"Butscher, B., Weimer, H.: Simulation eines Quantencomputers (2003). http:\/\/www.libquantum.de\/files\/libquantum.pdf"},{"key":"4_CR3","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1038\/nphys1614","volume":"6","author":"H Weimer","year":"2010","unstructured":"Weimer, H., M\u00fcller, M., Lesanovsky, I., Zoller, P., B\u00fcchler, H.: A Rydberg quantum simulator. Nature Phys. 6, 382\u2013388 (2010)","journal-title":"Nature Phys."},{"key":"4_CR4","unstructured":"Weimer, H., Butscher, B.: libquantum 1.1.1: the C library for quantum computing and quantum simulation (2003\u20132013 (v. 1.1.1)). http:\/\/www.libquantum.de\/"},{"key":"4_CR5","unstructured":"Wybiral, D., Hwang, J.: Quantum circuit simulator (2012). http:\/\/www.davyw.com\/quantum\/"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings of the 35th Annual IEEE Symposium on the Foundations of Computer Science, pp. 124\u2013134 (1994)","DOI":"10.1109\/SFCS.1994.365700"},{"key":"4_CR7","first-page":"203","volume":"46","author":"D Boneh","year":"1999","unstructured":"Boneh, D.: Twenty years of attacks on the RSA cryptosystem. Notices Am. Math. Soc. 46, 203\u2013213 (1999)","journal-title":"Notices Am. Math. Soc."},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"H\u00e4ner, T., Steiger, D., Smelyanskiy, M., Troyer, M.: High performance emulation of quantum circuits. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, Salt Lake City, Utah. IEEE Press, November 2016. Article 74 in e-volume","DOI":"10.1109\/SC.2016.73"},{"key":"4_CR9","unstructured":"Greuel, G.M., Pfister, G., Sch\u00f6nemann, H.: Singular version 1.2 user manual. In: Reports on Computer Algebra, vol. 21. Centre for Computer Algebra, University of Kaiserslautern (1998). http:\/\/www.singular.uni-kl.de\/"},{"key":"4_CR10","unstructured":"Greuel, G.M., Pfister, G., Sch\u00f6nemann, H.: Singular 3.0. A Computer Algebra System for Polynomial Computations, Centre for Computer Algebra, University of Kaiserslautern (2005). http:\/\/www.singular.uni-kl.de"},{"key":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1007\/11814948_38","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2006","author":"M Thurley","year":"2006","unstructured":"Thurley, M.: sharpSAT \u2013 counting models with advanced component caching and implicit BCP. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol. 4121, pp. 424\u2013429. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11814948_38"},{"key":"4_CR12","unstructured":"Sang, T., Bacchus, F., Beame, P., Kautz, H., Pitassi, T.: Combining component caching and clause learning for effective model counting. In: Seventh International Conference on Theory and Applications of Satisfiability Testing, Vancouver (2004)"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Sang, T., Beame, P., Kautz, H.: Heuristics for fast exact model counting. In: Eighth International Conference on Theory and Applications of Satisfiability Testing, Edinburgh, Scotland (2005)","DOI":"10.1007\/11499107_17"},{"key":"4_CR14","unstructured":"Sang, T., Beame, P., Kautz, H.: Performing Bayesian inference by weighted model counting. In: Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI 2005), Pittsburgh, PA (2005)"},{"key":"4_CR15","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/j.nima.2005.11.147","volume":"59","author":"V Gerdt","year":"2006","unstructured":"Gerdt, V., Severyanov, V.: A software package to construct polynomial sets over $$Z_2$$ Z 2 for determining the output of quantum computations. Nucl. Instrum. Methods Phys. Res. A 59, 260\u2013264 (2006)","journal-title":"Nucl. Instrum. Methods Phys. Res. A"},{"key":"4_CR16","unstructured":"Bacon, D., van Dam, W., Russell, A.: Analyzing algebraic quantum circuits using exponential sums (2008). http:\/\/www.cs.ucsb.edu\/vandam\/LeastAction.pdf"},{"key":"4_CR17","doi-asserted-by":"crossref","first-page":"1524","DOI":"10.1137\/S0097539795293639","volume":"26","author":"L Adleman","year":"1997","unstructured":"Adleman, L., DeMarrais, J., Huang, M.: Quantum computability. SIAM J. Comput. 26, 1524\u20131540 (1997)","journal-title":"SIAM J. Comput."},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Rogers, J.: Complexity limitations on quantum computation. In: Proceedings of the 13th Annual IEEE Conference on Computational Complexity, pp. 202\u2013206 (1998)","DOI":"10.1109\/CCC.1998.694606"},{"issue":"20","key":"4_CR19","doi-asserted-by":"crossref","first-page":"4083","DOI":"10.1103\/PhysRevLett.74.4083","volume":"74","author":"A Barenco","year":"1995","unstructured":"Barenco, A., Deutsch, D., Ekert, A., Jozsa, R.: Conditional quantum dynamics and logic gates. Phys. Rev. Lett. 74(20), 4083\u20134086 (1995)","journal-title":"Phys. Rev. Lett."},{"issue":"5","key":"4_CR20","doi-asserted-by":"crossref","first-page":"3457","DOI":"10.1103\/PhysRevA.52.3457","volume":"52","author":"A Barenco","year":"1995","unstructured":"Barenco, A., Bennett, C., Cleve, R., DiVincenzo, D., Margolus, N., Shor, P., Sleator, T., Smolin, J., Weinfurter, H.: Elementary gates for quantum computation. Phys. Rev. A 52(5), 3457\u20133467 (1995)","journal-title":"Phys. Rev. A"},{"key":"4_CR21","unstructured":"Boixo, S., Isakov, S.V., Smelyanskiy, V.N., Babbush, R., Ding, N., Jiang, Z., Bremner, M.J., Martinis, J.M., Neven, H.: Characterizing quantum supremacy in near-term devices (2016). https:\/\/arxiv.org\/pdf\/1608.00263.pdf"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"H\u00e4ner, T., Steiger, D.: 0.5 petabyte simulation of a 45-qubit quantum circuit (2017). arXiv:1704.01127v1","DOI":"10.1145\/3126908.3126947"},{"key":"4_CR23","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/BF02650179","volume":"21","author":"R Feynmann","year":"1982","unstructured":"Feynmann, R.: Simulating physics with computers. Int. J. Theor. Phys. 21, 467\u2013488 (1982)","journal-title":"Int. J. Theor. Phys."},{"key":"4_CR24","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1007\/BF01886518","volume":"16","author":"R Feynmann","year":"1986","unstructured":"Feynmann, R.: Quantum mechanical computers. Found. Phys. 16, 507\u2013531 (1986)","journal-title":"Found. Phys."},{"key":"4_CR25","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1098\/rspa.1985.0070","volume":"400","author":"D Deutsch","year":"1985","unstructured":"Deutsch, D.: Quantum theory, the Church-Turing principle, and the universal quantum computer. Proc. Royal Soc. A 400, 97\u2013117 (1985)","journal-title":"Proc. Royal Soc. A"},{"issue":"1868","key":"4_CR26","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1098\/rspa.1989.0099","volume":"425","author":"D Deutsch","year":"1989","unstructured":"Deutsch, D.: Quantum computational networks. Proc. R. Soc. Lond. A 425(1868), 73\u201390 (1989)","journal-title":"Proc. R. Soc. Lond. A"},{"key":"4_CR27","unstructured":"Yamashita, S., Markov, I.: Fast equivalence-checking for quantum circuits. In: Proceedings of the 2010 IEEE\/ACM Symposium on Nanoscale Architectures, Anaheim, CA, USA (2010). May 2013 update at https:\/\/arxiv.org\/pdf\/0909.4119.pdf"},{"key":"4_CR28","doi-asserted-by":"crossref","unstructured":"Eggersgl\u00fc\u00df, S., Wille, R., Drechsler, R.: Improved SAT-based ATPG: more constraints, better compaction. In: Proceedings of the 2013 International Conference on Computer-Aided Design, San Jos\u00e9, CA, USA, pp. 85\u201390 (2013)","DOI":"10.1109\/ICCAD.2013.6691102"},{"key":"4_CR29","first-page":"281","volume":"7","author":"A Sch\u00f6nhage","year":"1971","unstructured":"Sch\u00f6nhage, A., Strassen, V.: Schnelle Multiplikation grosser Zahlen. Comput. Arch. Elektron. Rechnen 7, 281\u2013292 (1971)","journal-title":"Comput. Arch. Elektron. Rechnen"},{"key":"4_CR30","doi-asserted-by":"crossref","first-page":"052320","DOI":"10.1103\/PhysRevA.71.052320","volume":"71","author":"R Meter van","year":"2005","unstructured":"van Meter, R., Itoh, K.: Fast quantum modular exponentiation. Phys. Rev. A 71, 052320 (2005)","journal-title":"Phys. Rev. A"},{"key":"4_CR31","first-page":"361","volume":"12","author":"I Markov","year":"2012","unstructured":"Markov, I., Saeedi, M.: Constant-optimized quantum circuits for modular multiplication and exponentiation. Quantum Inf. Comput. 12, 361\u2013394 (2012)","journal-title":"Quantum Inf. Comput."},{"key":"4_CR32","first-page":"649","volume":"14","author":"A Pavlidis","year":"2014","unstructured":"Pavlidis, A., Gizopoulos, D.: Fast quantum modular exponentiation architecture for shor\u2019s factoring algorithm. Quantum Inf. Comput. 14, 649\u2013682 (2014)","journal-title":"Quantum Inf. Comput."},{"key":"4_CR33","unstructured":"Cao, Z., Cao, Z., Liu, L.: Remarks on quantum modular exponentiation and some experimental demonstrations of Shor\u2019s algorithm (2014). https:\/\/arxiv.org\/abs\/1408.6252"},{"key":"4_CR34","unstructured":"Gottesman, D.: The Heisenberg representation of quantum computers (1998). http:\/\/arxiv.org\/abs\/quant-ph\/9807006"},{"key":"4_CR35","doi-asserted-by":"crossref","unstructured":"Aaronson, S., Gottesman, D.: Improved simulation of stabilizer circuits. Phys. Rev. A 70 (2004)","DOI":"10.1103\/PhysRevA.70.052328"},{"key":"4_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/978-3-642-14553-7_16","volume-title":"Frontiers in Algorithmics","author":"J-Y Cai","year":"2010","unstructured":"Cai, J.-Y., Chen, X., Lipton, R., Lu, P.: On tractable exponential sums. In: Lee, D.-T., Chen, D.Z., Ying, S. (eds.) FAW 2010. LNCS, vol. 6213, pp. 148\u2013159. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14553-7_16"},{"key":"4_CR37","doi-asserted-by":"crossref","first-page":"924","DOI":"10.1137\/110840194","volume":"42","author":"J-Y Cai","year":"2013","unstructured":"Cai, J.-Y., Chen, X., Lu, P.: Graph homomorphisms with complex values: a dichotomy theorem. SIAM J. Comput. 42, 924\u20131029 (2013)","journal-title":"SIAM J. Comput."},{"key":"4_CR38","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/j.jcss.2013.07.003","volume":"80","author":"JY Cai","year":"2014","unstructured":"Cai, J.Y., Lu, P., Xia, M.: The complexity of complex weighted Boolean #CSP. J. Comp. Syst. Sci. 80, 217\u2013236 (2014)","journal-title":"J. Comp. Syst. Sci."},{"key":"4_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/978-3-540-89994-5_5","volume-title":"Mathematical Methods in Computer Science","author":"R Jozsa","year":"2008","unstructured":"Jozsa, R.: Invited Talk: embedding classical into quantum computation. In: Calmet, J., Geiselmann, W., M\u00fcller-Quade, J. (eds.) Mathematical Methods in Computer Science. LNCS, vol. 5393, pp. 43\u201349. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-89994-5_5 . arXiv:0812.4511 [quant-ph]"},{"key":"4_CR40","unstructured":"Spec.org, Butscher, B., Weimer, H.: 462.libquantum SPEC CPU2006 benchmark description (2006). https:\/\/www.spec.org\/cpu2006\/Docs\/462.libquantum.html"},{"key":"4_CR41","doi-asserted-by":"crossref","first-page":"1034","DOI":"10.1103\/PhysRevA.54.1034","volume":"54","author":"D Beckman","year":"1996","unstructured":"Beckman, D., Chari, A., Devabhaktuni, S., Preskill, J.: Efficient networks for quantum factoring. Phys. Rev. A 54, 1034\u20131063 (1996)","journal-title":"Phys. Rev. A"},{"issue":"012310","key":"4_CR42","first-page":"1","volume":"87","author":"I Markov","year":"2013","unstructured":"Markov, I., Saeedi, M.: Faster quantum number factoring via circuit synthesis. Phys. Rev. A 87(012310), 1\u20135 (2013)","journal-title":"Phys. Rev. A"},{"key":"4_CR43","first-page":"175","volume":"3","author":"S Beauregard","year":"2003","unstructured":"Beauregard, S.: Circuit for shor\u2019s algorithm using 2n\u00a0+\u00a03 qubits. Quantum Inf. Comput. 3, 175 (2003)","journal-title":"Quantum Inf. Comput."},{"key":"4_CR44","first-page":"673","volume":"17","author":"T H\u00e4ner","year":"2017","unstructured":"H\u00e4ner, T., Roetteler, M., Svore, K.: Factoring using 2n\u00a0+\u00a02 qubits with toffoli based modular multiplication. Quantum Inf. Comput. 17, 673\u2013684 (2017)","journal-title":"Quantum Inf. Comput."},{"key":"4_CR45","doi-asserted-by":"crossref","unstructured":"Viamontes, G., Rajagopalan, M., Markov, I., Hayes, J.: Gate-level simulation of quantum circuits. In: Proceedings of the ACM\/ IEEE Asia and South-Pacific Design Automation Conference (ASPDAC), Kitakyushu, Japan, pp. 295\u2013301, January 2003","DOI":"10.1145\/1119772.1119829"},{"key":"4_CR46","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1023\/B:QINP.0000022725.70000.4a","volume":"2","author":"G Viamontes","year":"2003","unstructured":"Viamontes, G., Markov, I., Hayes, J.: Improving gate-level simulation of quantum circuits. Quantum Inf. Process. 2, 347\u2013380 (2003)","journal-title":"Quantum Inf. Process."},{"key":"4_CR47","unstructured":"Greve, D.: QDD: a quantum computer emulation library (1999\u20132007). http:\/\/thegreves.com\/david\/QDD\/qdd.html"},{"key":"4_CR48","doi-asserted-by":"crossref","first-page":"103","DOI":"10.7494\/csci.2015.16.1.103","volume":"16","author":"J Patrzyk","year":"2015","unstructured":"Patrzyk, J., Patrzyk, B., Rycerz, K., Bubak, M.: Towards a novel environment for simulation of quantum computing. Comput. Sci. 16, 103\u2013129 (2015)","journal-title":"Comput. Sci."},{"key":"4_CR49","doi-asserted-by":"crossref","unstructured":"Lee, Y., Khalil-Hani, M., Marsono, M.: An FPGA-based quantum computing emulation framework based on serial-parallel architecture. J. Reconfigurable Comput. 2016, 18 pages (2016)","DOI":"10.1155\/2016\/5718124"},{"key":"4_CR50","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1103\/PhysRevA.54.139","volume":"54","author":"A Barenco","year":"1996","unstructured":"Barenco, A., Ekert, A., Suominen, K.A., T\u00f6rm\u00e4, P.: Approximate quantum Fourier transform and decoherence. Phys. Rev. A 54, 139\u2013146 (1996)","journal-title":"Phys. Rev. A"},{"key":"4_CR51","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1109\/TC.2007.35","volume":"56","author":"Z Zilic","year":"2007","unstructured":"Zilic, Z., Radecka, K.: Scaling and better approximating quantum fourier transform by higher radices. IEEE Trans. Comp. 56, 202\u2013207 (2007)","journal-title":"IEEE Trans. Comp."},{"key":"4_CR52","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/s00200-008-0072-2","volume":"19","author":"M R\u00f6tteler","year":"2008","unstructured":"R\u00f6tteler, M., Beth, T.: Representation-theoretical properties of the approximate quantum Fourier transform. Appl. Algebra Eng. Commun. Comput. 19, 117\u2013193 (2008)","journal-title":"Appl. Algebra Eng. Commun. Comput."},{"key":"4_CR53","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/978-3-319-24021-3_29","volume-title":"Computer Algebra in Scientific Computing","author":"AN Prokopenya","year":"2015","unstructured":"Prokopenya, A.N.: Approximate quantum fourier transform and quantum algorithm for phase estimation. In: Gerdt, V.P., Koepf, W., Seiler, W.M., Vorozhtsov, E.V. (eds.) CASC 2015. LNCS, vol. 9301, pp. 391\u2013405. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-24021-3_29"},{"key":"4_CR54","unstructured":"Aaronson, S., Chen, L.: Complexity-theoretic foundations of quantum supremacy experiments (2016). https:\/\/arxiv.org\/abs\/1612.05903"}],"container-title":["Lecture Notes in Computer Science","Transactions on Computational Science XXXI"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-56499-8_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,9]],"date-time":"2019-10-09T17:54:06Z","timestamp":1570643646000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-56499-8_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783662564981","9783662564998"],"references-count":54,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-56499-8_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]}}}