C&SA | Contents

Volume 55 >>> № 1 JANUARY — FEBRUARY 2019

UDC 004.383

M.M. Savchuk¹, A.V. Fesenko²

¹ National Technical University of Ukraine “Igor Sikorsky
Kyiv Polytechnic Institute,” Kyiv, Ukraine

² National Technical University of Ukraine “Igor Sikorsky
Kyiv Polytechnic Institute,” Kyiv, Ukraine

QUANTUM COMPUTING: SURVEY AND ANALYSIS

Abstract. The authors conduct a survey and analysis of the main concepts and postulates of the quantum computing model, efficient quantum algorithms, recent results, capabilities, and prospects in constructing a scalable quantum computer. A certain class of algebraic problems in a quantum computation model is considered, for which there and efficient quantum solution algorithm exists. A detailed analysis of available quantum computer implementations has been carried out and it has been shown that sufficient progress has yet been made in constructing a scalable quantum computing device; nevertheless, most of researchers expect a quantum computer to be created in the next 10–15 years.

Keywords: quantum computing model, quantum cryptography, quantum computer, efficient quantum algorithms, postquantum cryptographic primitives.

FULL TEXT

REFERENCES

Bennett C., Brassard G. Quantum cryptography: Public-key distribution and coin tossing. Proc. International Conference on Computers, Systems and Signal Processing (Bangalore, India. 1984). P. 175–179.

Квантовый компьютер и квантовые вычисления. Ижевск: Ижевская республиканская типография, 1999. 288 с.

Preskill J. Quantum information and computation (Russian translation). Vol 1. Moskva-Izhevsk: NITS «Regulyarnaya i khaoticheskaya dinamika»; Institut komp'yuternykh issledovaniy, 2008. 464 с.

Ааронсон С. Квантовые вычисления со времен Демокрита. Москва: Альпина нон-пикшн, 2018. 494 с.

Savchuk M.N. On the work of the Kiev school of theoretical cryptography (in Russian). Kibernetika i Sistemnyj Analiz. 2010. Vol. 46, № 3. С. 52–68.

Nielsen M.A., Chuang I.L. Quantum computation and quantum information. Cambridge: Cambridge University Press,. 2000. 676 p.

Kitaev A. Quantum computations: algorithms and error correction. Russian Mathematical Surveys. 1997. Vol. 52, N 6. P. 53–112.

Yao A. Quantum circuit complexity. Proc. 34th Annual Symposium on Foundations of Computer Science. 1993. P. 352–361.

Boneh R., Lipton R. Quantum cryptanalysis of hidden linear functions. Proc. 15th Annual International Cryptology Conference, (Santa Barbara, California, USA, August 27, 1995). Advances in Cryptology. Crypto’95. Lecture Notes in Computer Science. 1995. Vol. 31. P. 424–437.

Deutsch D., Jozsa R. Rapid solution of problems by quantum computation. Proc. Royal Society of London, Series A. 1992. N 439. P. 553–558.

Shor P.W. Algorithms for quantum computation: discrete logs and factoring. Proc. 35th Symposium on the Foundations of Computer Science (20–22 Nov. 1994, Santa Fe, NM, USA), 1994. P. 124–134.

Shor P.W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing. 1997. Vol. 26, Iss. 5. P. 1484–1509.

van Dam W., Hallgren S., Ip L. Quantum algorithms for some hidden shift problems. SIAM Journal on Computing. 2006. Vol. 36, N 3. P. 763–778.

Fesenko A.V. Vulnerabilities of crypto-primitives based on the problem of searching for a conjugating element and degree in the quantum model of computing (in Russian). Kibernetika i Sistemnyj Analiz. 2014. Vol. 50, № 5. С. 184–186.

Bian Z., Chudak F., Macready W., Clark L. , Gaitan F. Experimental determination of Ramsey numbers. Physical Review Letters. 2012 Vol. 111, Iss. 13. P. 130505. DOI: https://doi.org/10.1103/PhysRevLett.111.130505. URL: https://arxiv.org/abs/1201.1842.

Cho A. Quantum or not, controversial computer yields no speedup. Science. 2014. Vol. 344, N 6190. P. 1330–1331. DOI: https://doi.org/10.1126/science.344.6190.1330.

Dattani N.S. , Bryans N. Quantum factorization of 56153 with only 4 qubits. Quantum Physics Archive. arXiv:1411.6758 [quant-ph]. 2014. URL: https//arxiv.org/abs/1411.6758.