Abstract
The authors survey and analyze the main concepts and postulates of the quantum computing model, efficient quantum algorithms, and recent results, capabilities, and prospects in constructing a scalable quantum computer. A certain class of algebraic problems in the quantum computing model is considered for which there exists an efficient quantum solution algorithm. A detailed analysis of available quantum computer implementations was carried out, and it is shown that sufficient progress has not yet been made in constructing a scalable quantum computing device; nevertheless, most researchers expect that a full-fledged quantum computer will be created in the next 10–15 years.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
C. Bennett and G. Brassard, “Quantum cryptography: Public-key distribution and coin tossing,” in: Proc. Intern. Conf. on Computers, Systems and Signal Processing (Bangalore, India) (1984), pp. 175–179.
Quantum Computer and Quantum Computing, Izhevsk Republican Printing House, Izhevsk (1999).
J. Preskill, Quantum Information and Computation [Russian translation], Volume 1, Research Center “Regular and chaotic dynamics;” Computer Research Institute, Moscow–Izhevsk (2008).
S. Aaronson, Quantum Computing since Democritus [Russian translation], Alpina Non-Fiction, Moscow (2018).
M. N. Savchuk, “Works of the Kiev school of theoretical cryptography,” Cybernetics and Systems Analysis, Vol. 46, No. 3, 386–404 (2010).
M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge (2000).
A. Kitaev, “Quantum Computations: Algorithms and Error Correction,” Russian Mathematical Surveys, Vol. 52, No. 6, 53–112 (1997).
A. Yao, “Quantum circuit complexity,” in: Proc. 34th Annual Symposium on Foundations of Computer Science (1993), pp. 352–361.
R. Boneh and R. Lipton, “Quantum cryptanalysis of hidden linear functions,” in: Proc. 15th Annual International Cryptology Conference (Santa Barbara, California, USA, August 27, 1995), Advances in Cryptology (Crypto’95); Lecture Notes in Computer Science, Vol. 31, 424–437 (1995).
D. Deutsch and R. Jozsa, “Rapid solution of problems by quantum computation,” Proc. Royal Society of London, Series A, No. 439, 553–558 (1992).
P. W. Shor, “Algorithms for quantum computation: Discrete logs and factoring,” in: Proc. 35th Symposium on the Foundations of Computer Science (Santa Fe, NM, USA, Nov. 20–22, 1994) (1994), pp. 124-134.
P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” SIAM Journal on Computing, Vol. 26, Iss. 5, 1484–1509 (1997).
W. Van Dam, S. Hallgren, and L. Ip, “Quantum algorithms for some hidden shift problems,” SIAM Journal on Computing, Vol. 36, No. 3, 763–778 (2006).
A. V. Fesenko, “Vulnerability of cryptographic primitives based on power conjugacy search problem in quantum computing,” Cybernetics and Systems Analysis, Vol. 50, No. 5, 815–816 (2014).
Z. Bian, F. Chudak, W. Macready, L. Clark, and F. Gaitan, “Experimental determination of Ramsey numbers,” Physical Review Letters, Vol. 111, Iss. 13, p. 130505 (2013). DOI: https://doi.org/10.1103/PhysRevLett.111.130505. URL: https://arxiv.org/abs/1201.1842.
A. Cho, “Quantum or not, controversial computer yields no speedup,” Science, Vol. 344, No. 6190, 1330–1331 (2014). DOI: https://doi.org/10.1126/science.344.6190.1330.
N. S. Dattani and N. Bryans, Quantum Factorization of 56153 with Only 4 Qubits, Quantum Physics Archive. arXiv:1411.6758 [quant-ph]. 2014. URL: https://arxiv.org/abs/1411.6758.
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Kibernetika i Sistemnyi Analiz, No. 1, January–February, 2019, pp. 14–29.
Rights and permissions
About this article
Cite this article
Savchuk, M.M., Fesenko, A.V. Quantum Computing: Survey and Analysis. Cybern Syst Anal 55, 10–21 (2019). https://doi.org/10.1007/s10559-019-00107-w
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10559-019-00107-w