Масштабируемость и оценка ресурсов

Как мы видели, есть множество вещей, которые язык Quipper может делать со сгенерированными квантовыми схемами. Однако если генерировать огромные схемы, то не всегда возможно сгенерировать такую схему сразу в полном объёме. Язык Quipper предоставляет механизм, при помощи которого можно подсчитать количество ресурсов, ассоциированных со схемой (то есть, количество гейтов, количество кубитов, количество вспомогательных кубитов). Комбинируя эту возможность со схемами в виде чёрных ящиков, можно произвести оценку ресурсов, потребных для очень больших квантовых схем. Например, наша реализация алгоритма поиска треугольника [14] на языке Quipper создала квантовую схему с 30-ью триллионами гейтов, которые могут быть подсчитаны за две минуты на ноутбуке с 1.2 ГГц.

Искусство

В литературе (см. [8]) было описано некоторое количество квантовых языков программирования. Несмотря на это, были реализованы только C-подобный язык QCL [16] с оптимизацией квантовой симуляции; квантовая монада IO [2], которая также является квантовым языком программирования, встроенным в язык Haskell; язык LQPL [9], являющийся функциональным квантовым языком программирования с линейными типами. Однако большиинство языков программирования, описанных в литературе, не могут быть смасштабированы на задачи огромных размеров.

Проблема генерации описания схем на основе функциональных программ также изучалась вне контекста квантовых вычислений; см., например, [4, 6].

Заключение

В языке Quipper имеется большое количество возможностей, и только часть из них была описана в этой вводной статье. Инсталляционный пакет языка Quipper также содержит несколько библиотек с наиболее часто используемыми квантовыми функциями. Например, мы предоставляем библиотеку арифметических функций для целочисленных операций и операций с фиксированной точностью, а также функции для произвольного доступа к квантовому регистру при помощи квантовой индексации. Несмотря на то, что язык Quipper всё ещё находится в стадии разработки, мы считаем, что текущая стабильная версия предоставляет полноценный и масштабируемый язык программирования. Мы планируем сделать много улучшений, в частности в системе типизации, такие как внедрение линейных типов, что позволит отловить многие ошибки на стадии первоначальной компиляции программы, а не на стадии генерации квантовой схемы.

Список источников

1. Aaronson, S., Gottesman, D.: Improved simulation of stabilizer circuits. Physical Review A 70(5), 052328 (Nov 2004), arXiv:quant-ph/0406196.

2. Altenkirch, T., Green, A.S.: The Quantum IO Monad. In: Gay, S., Mackie, I. (eds.) Semantic Techniques in Quantum Computation, pp. 173{205. Cambridge University Press (2009).

3. Ambainis, A., Childs, A.M., Reichardt, B.W., Spalek, R., Zhang, S.: Any AND-OR formula of size n can be evaluated in time n^1/2+o(1) on a quantum computer. SIAM J. Comput. 39, 2513{2530 (2010).

4. Bjesse, P., Claessen, K., Sheeran, M., Singh, S.: Lava: hardware design in Haskell. In: Proceedings of the third ACM SIGPLAN international conference on Functional programming. pp. 174{184. ICFP '98, ACM, New York, NY, USA (1998), doi:10.1145/289423.289440.

5. Childs, A.M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., Spielman, D.A.: Exponential algorithmic speedup by a quantum walk. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing. pp. 59{68 (2003).

6. Claessen, K.: Embedded Languages for Describing and Verifying Hardware. Ph.D. thesis, Chalmers University of Technology and Goteborg University (2001).

7. Draper, T.G.: Addition on a Quantum Computer (Aug 2000), arXiv:quant-ph/0008033.

8. Gay, S.J.: Quantum programming languages: Survey and bibliography. Mathematical Structures in Computer Science 16(4) (2006), http://www.dcs.gla.ac.uk/~simon/publications/QPLsurvey.pdf.

9. Giles, B.: Programming with a Quantum Stack. Master's thesis, Department of Computer Science, University of Calgary (Apr 2007), http://pages.cpsc.ucalgary.ca/~gilesb/research/lqpl.html.

10. Green, A.S., Lumsdaine, P.L., Ross, N.J., Selinger, P., Valiron, B.: Quipper: A scalable quantum programming language (2012), to appear in PLDI 2013, arXiv:1304.3390.

11. Hallgren, S.: Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem. J. ACM 54(1), 4:1{4:19 (Mar 2007), doi:10.1145/1206035.1206039.

12. Harrow, A.W., Hassidim, A., Lloyd, S.: Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103(15), 150502 (2009).

13. IARPA Quantum Computer Science Program: Broad Agency Announcement IARPA-BAA-10-02 (April 2010), https://www.fbo.gov/notices/637e87ac1274d030ce2ab69339ccf93c.

14. Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem (Nov 2003), arXiv:quant-ph/0310134.

15. Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press (2002).

16. Omer, B.: A Procedural Formalism for Quantum Computing. Master's thesis, Dept. of Theoretical Physics, Tech. Univ. Vienna (Jul 1998), http://tph.tuwien.ac.at/~oemer/qcl.html.

17. Regev, O.: Quantum computation and lattice problems. SIAM J. Comput. 33(3), 738{760 (2004).

18. Whiteld, J.D., Biamonte, J., Aspuru-Guzik, A.: Simulation of electronic structure hamiltonians using quantum computers. Molecular Physics 109(5), 735{750 (2011).