Towards a novel environment for simulation of quantum computing

• Autorzy: Patrzyk J. , Patrzyk B. , Rycerz K. , Bubak M.

Identyfikatory

DOI

10.7494/csci.2015.16.1.103

• Języki publikacji: EN

Abstrakty

EN

In this paper, we analyze existing quantum computer simulation techniques and their realizations to minimize the impact of the exponential complexity of simulated quantum computations. As a result of this investigation, we propose a quantum computer simulator with an integrated development environment – QuIDE – supporting the development of algorithms for future quantum computers. The simulator simplifies building and testing quantum circuits and understanding quantum algorithms in an efficient way. The development environment provides flexibility of source code edition and ease of the graphical building of circuit diagrams. We also describe and analyze the complexity of algorithms used for simulation as well as present performance results of the simulator as well as results of its deployment during university classes.

Słowa kluczowe

EN

quantum computation; quantum computer simulators; development environment; quantum algorithms; SUS survey

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2015
• Tom: Vol. 16 (1)
• Strony: 103--129
• Opis fizyczny: Bibliogr. 60 poz., rys., wykr., tab.

Twórcy

autor

Patrzyk J.

• AGH University of Science and Technology, Department of Computer Science, Krakow, Poland

autor

Patrzyk B.

• AGH University of Science and Technology, Department of Computer Science, Krakow, Poland

autor

Rycerz K.

• AGH University of Science and Technology, Department of Computer Science, Krakow, Poland
• ACC Cyfronet AGH, Krakow, Poland

autor

Bubak M.

• AGH University of Science and Technology, Department of Computer Science, Krakow, Poland
• ACC Cyfronet AGH, Krakow, Poland
• University of Amsterdam, Institute for Informatics, Faculty of Science Park 904, 1098XH Amsterdam, The Netherlands

Bibliografia

• [1] Aaronson S., Gottesman D.: Improved simulation of stabilizer circuits. Phys. Rev. A, vol. 70, p. 052328, 2004. http://dx.doi.org/10.1103/PhysRevA.70.052328.
• [2] AGH: Syllabus – module Matematyka w informatyce przyszłości, 2012. http://syllabuskrk.agh.edu.pl/2014-2015/en/magnesite/study_plans/stacjonarne-informatyka-systemy-rozproszone-i-sieci-komputerowe/module/iin-2-101-sr-s-matematyka-w-informatyce-przyszlosci.
• [3] 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, vol. 52, pp. 3457–3467, 1995. http://dx.doi.org/10.1103/PhysRevA.52.3457.
• [4] Belkner P.: Eqcs-0.0.8, 2012. http://home.snafu.de/pbelkner/eqcs/. Accessed May 10, 2014.
• [5] Bennett C. H., Brassard G.: Quantum cryptography: Public key distribution and coin tossing. Proceedings of IEEE International Conference on Computers, Systems, and Signal Processing, p. 175. India, 1984.
• [6] Bennett C. H., Brassard G., Cr ́epeau C., Jozsa R., Peres A., Wootters W. K.: Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. Phys. Rev. Lett., vol. 70, pp. 1895–1899, 1993. http://dx.doi.org/10.1103/PhysRevLett.70.1895.
• [7] Bernstein E., Vazirani U.: Quantum Complexity Theory. In: SIAM J. Comput., vol. 26(5), pp. 1411–1473, 1997. ISSN 0097-5397. http://dx.doi.org/10.1137/S0097539796300921.
• [8] Black P. E., Lane A. W.: Modeling Quantum Information Systems. Proc. Quantum Information and Computation II, Defense and Security Symposium. 2004.
• [9] Bouvarel B., Oudin O., Vallier L.: Simulateur de Cryptographie Quantique, 2009. http://sourceforge.net/projects/simu-quantique/. Accessed Sep 18, 2014.
• [10] Brooke J.: SUS – A quick and dirty usability scale. In: P. W. Jordan, B. Thomas, B. A. Weerdmeester, A. L. McClelland, eds, Usability Evaluation in Industry. Taylor and Francis, 1996.
• [11] Butscher B., Weimer H.: Simulation eines Quantencomputers, 2003. http://www.libquantum.de/files/libquantum.pdf.
• [12] Cabral G. E.: Zeno – Quantum Circuit Simulator, 2006. http://dsc.ufcg.edu.br/~iquanta/zeno/index_en.html. Accessed Sep 18, 2014.
• [13] Cybernet: Q++. http://sourceforge.net/projects/qplusplus/. Accessed May 10, 2014.
• [14] Deutsch D.: Quantum theory, the Church-Turing principle and the universal quantum computer. Royal Society of London Proceedings Series A, vol. 400, pp. 97–117, 1985. http://dx.doi.org/10.1098/rspa.1985.0070.
• [15] Dixon L., Duncan R., Kissinger A.: Quantomatic, 2011. https://sites.google.com/site/quantomatic/. Accessed Sep 18, 2014.
• [16] Ekert A., Knight P. L.: Entangled quantum systems and the Schmidt decomposition. American Journal of Physics, vol. 63(5), pp. 415–423, 1995. http://dx.doi.org/http://dx.doi.org/10.1119/1.17904.
• [17] Feynman R., Shor P. W.: Simulating Physics with Computers. SIAM Journal on Computing, vol. 26, pp. 1484–1509, 1982.
• [18] Greve D.: QDD: A Quantum Computer Emulation Library. http://thegreves.com/david/QDD/qdd.html. Accessed May 10, 2014.
• [19] Grover L. K.: A fast quantum mechanical algorithm for database search. STOC’96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing , pp. 212–219. ACM Press, New York, NY, USA, 1996. http://citeseer.ist.psu.edu/175549.html.
• [20] Johansson J., Nation P., Nori F.: QuTiP 2: A Python framework for the dynamics of open quantum systems. Computer Physics Communications, vol. 184(4), pp. 1234–1240, 2013, ISSN 0010-4655. http://dx.doi.org/10.1016/j.cpc.2012.11.019.
• [21] Johnson M. W., Amin M. H. S., et al.: Quantum annealing with manufactured spins. In: Nature, vol. 473(7346), pp. 194–198, 2011, ISSN 0028-0836. http://dx.doi.org/10.1038/nature10012.
• [22] Jozsa R., Linden N.: On the role of entanglement in quantum-computational speed-up. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, vol. 459(2036), pp. 2011–2032, 2003. http://dx.doi.org/10.1098/rspa.2002.1097.
• [23] Kempe J.: Quantum random walks – an introductory overview. Contemporary Physics, vol. 44(4), pp. 302–327, 2003. Lanl-arXive quant-ph/0303081.
• [24] Lanting T., Przybysz A. J., et al.: Entanglement in a Quantum Annealing Processor. Phys. Rev. X, vol. 4, p. 021041, 2014. http://dx.doi.org/10.1103/PhysRevX.4.021041.
• [25] Lanyon B. P., Weinhold T. J., Langford N. K., Barbieri M., James D. F. V., Gilchrist A., White A. G.: Experimental Demonstration of a Compiled Version of Shor’s Algorithm with Quantum Entanglement. Phys. Rev. Lett., vol. 99, p. 250505, 2007. http://dx.doi.org/10.1103/PhysRevLett.99.250505.
• [26] Leforestier C., Bisseling R., et al.: A comparison of different propagation schemes for the time dependent Schr ̈odinger equation. Journal of Computational Physics, vol. 94(1), pp. 59–80, 1991.
• [27] Lomont C.: SimQubit, Cybernet’s quantum circuit simulator, 2005. http://sourceforge.net/projects/simqubit/. Accessed Sep 18, 2014.
• [28] Mariantoni M., Wang H., et al.: Implementing the Quantum von Neumann Architecture with Superconducting Circuits. Science, vol. 334(6052), pp. 61–65, 2011. http://dx.doi.org/10.1126/science.1208517.
• [29] Markov I., Shi Y.: Simulating Quantum Computation by Contracting Tensor Networks. SIAM Journal on Computing, vol. 38(3), pp. 963–981, 2008. http://dx.doi.org/10.1137/050644756.
• [30] Martin-Lopez E., Laing A., Lawson T., Alvarez R., Zhou X. Q., O’Brien J.: Experimental realisation of Shor’s quantum factoring algorithm using qubit recycling. Lasers and Electro-Optics Europe (CLEO EUROPE/IQEC), 2013 Conference on and International Quantum Electronics Conference, pp. 1–1. 2013. http://dx.doi.org/10.1109/CLEOE-IQEC.2013.6801701.
• [31] Mavridi P., Tsimpouris C.: Demo: Quantum Computer Simulator, 2010. http://www.wcl.ece.upatras.gr/ai/resources/demo-quantum-simulation. Accessed Sep 18, 2014.
• [32] Mermin N.: Quantum Computer Science: An Introduction . Cambridge University Press, 2007, ISBN 9781139466806. http://books.google.pl/books?id=q2S9APxFdUQC.
• [33] Miszczak J. A.: Probabilistic aspects of quantum programming. Ph.D. thesis, Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, 2008.
• [34] Mlnaˇrik H.: Quantum Programming Language LanQ. Ph.D. thesis, Masaryk University, 2007.
• [35] Nielsen M. A., Chuang I. L.: Quantum Computation and Quantum Information. Cambridge University Press, 2000, ISBN 521635039. http://www.amazon.ca/exec/obidos/redirect?tag=citeulike09-20&path= ASIN/0521635039
• [36] Nowotniak R.: Wykorzystanie metod ewolucyjnych sztucznej inteligencji w projektowaniu algorytmów kwantowych. Master’s thesis, Politechnika Łódzka, 2008.
• [37] Obenland K. M., Despain A. M.: A Parallel Quantum Computer Simulator, 1997. http://arxiv.org/abs/quant-ph/9804039.
• [38] Omer B.: Quantum Programming in QCL. Master’s thesis, Technical University of Vienna, 2000.
• [39] Purkeypile M. D.: Cove: A Practical Quantum Computer Programming Frame-work. Ph.D. thesis, Colorado Technical University, 2009. http://arxiv.org/abs/0911.2423.
• [40] Raedt H. D., Michielsen K.: Computational Methods for Simulating Quantum Computers. M. Rieth, W. Schommers, eds., Handbook of Theoretical and Computational Nanotechnology, vol. 3: Quantum and molecular computing, quantum simulations, chap. 1, p. 248. American Scientific Publisher, 2006. http://arxiv.org/abs/quant-ph/0406210
• [41] Raedt K. D., Michielsen K., Raedt H. D., Trieu B., Arnold G., Richter M., Lippert T., Watanabe H., Ito N.: Massively parallel quantum computer simulator.Computer Physics Communications, vol. 176(2), pp. 121–136, 2007, ISSN 0010-4655. http://dx.doi.org/http://dx.doi.org/10.1016/j.cpc.2006.08.007.
• [42] Samad Abdel W., Ghandour R., Hajj Ch ́ehade M. N.: Memory Efficient Quantum Circuit Simulator Based on Linked List Architecture, 2005. http://arxiv.org/abs/quant-ph/0511079.
• [43] Shary S., Cahay M.: Bloch Sphere Simulation, 2012. http://www.ece.uc.edu/~mcahay/blochsphere/. Accessed Sep 18, 2014.
• [44] Shor P. W.: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput., vol. 26(5), pp. 1484–1509, 1997, ISSN 0097-5397. http://dx.doi.org/10.1137/S0097539795293172.
• [45] Skibinski J.: Haskell Simulator of Quantum Computer. http://web.archive.org/web/20010803034527/http://www.numericquest.com/haskell/QuantumComputer.html. Accessed May 10, 2014.
• [46] Smith J.: WPF Apps With The Model-View-ViewModel Design Pattern. MSDN Magazine, 2009.
• [47] Suzuki M.: Decomposition formulas of exponential operators and Lie exponentials with some applications to quantum mechanics and statistical physics. Journal of Mathematical Physics , vol. 26(4), pp. 601–612, 1985. http://dx.doi.org/http://dx.doi.org/10.1063/1.526596.
• [48] Tonder van A.: A Lambda Calculus for Quantum Computation. SIAM Journal on Computing, vol. 33(5), pp. 1109–1135, 2004. http://dx.doi.org/10.1137/S0097539703432165.
• [49] Tucci R.: Graphical computer method for analyzing quantum systems, 1998. http://www.google.com/patents/US5787236 . US Patent 5,787,236.
• [50] Vaccaro J.: Quantum computer simulator, 2009. http://www.ict.griffith.edu.au/joan/qucomp/qucompApplet.html. Accessed Sep 18, 2014.
• [51] V ́azquez J.M.C.d.P.:qMIPS Quantum processor simulator, 2013. http://institucional.us.es/qmipsmaster/qMIPS/documentation.php. Accessed September 18, 2014.
• [52] V ́azquez J.M.C.d.P.: Qubit101 Quantum circuit simulator, 2013. http://institucional.us.es/qmipsmaster/Qubit101/documentation.php. Accessed September 18, 2014.
• [53] Viamontes G. F., Markov I. L., Hayes J. P.: Improving Gate-Level Simulation of Quantum Circuits. Quantum Information Processing , vol. 2(5), pp. 347–380, 2003, ISSN 1570-0755. http://dx.doi.org/10.1023/B:QINP.0000022725.70000.4a .
• [54] Viamontes G. F., Markov I. L., Hayes J. P.: Quantum Circuit Simulation. Springer, 2009.
• [55] Vidal G.: Efficient Classical Simulation of Slightly Entangled Quantum Computations. Phys. Rev. Lett., vol. 91, p. 147902, 2003. http://dx.doi.org/10.1103/PhysRevLett.91.147902.
• [56] Vries de A.: math IT – Mathematics and Information Technology. http://www.math-it.org/. Accessed May 10, 2014.
• [57] Vries de A.: jQuantum: A Quantum Computer Simulator, 2010. http://jquantum.sourceforge.net/jQuantum.pdf . Accessed May 10, 2014.
• [58] Watanabe H., Suzuki M., Yamazaki J.: QCAD, GUI environment for Quantum Computer Simulator, 2011. http://qcad.sourceforge.jp/ . Accessed Sep 18, 2014.
• [59] Wecker D., Svore K. M.: LIQUid: A Software Design Architecture and Domain- Specific Language for Quantum Computing, 2014. http://research.microsoft.com/apps/pubs/default.aspx?id=209634 .
• [60] Wybiral D.: Quantum Circuit Simulator, 2012. http://www.davyw.com/quantum/. Accessed Sep 18, 2014