RESEARCH AND DEVELOPMENT OF DEPTH OPTIMIZED CIRCUITS IN QUANTUM APPROXIMATE OPTIMIZATION ALGORITHM
Abstract
One of the main challenges faced by researchers in the field of quantum computing is the problem
of noise in quantum systems. Noise can significantly limit the performance of quantum algorithms.
It is in this context that our research, aimed at the development and optimization of quantum
algorithms with a focus on depth, is updated. The depth of quantum circuits is one of the critical parameters
in the development of quantum algorithms. Optimized circuits with improved depth have the potential to significantly reduce the impact of noise, which in turn should lead to improved efficiency.
We aim to provide solutions that not only address technical constraints, but also provide practical
results for quantum computing in the context of optimization problems. This study analyzes the use of
a quantum approximate optimization algorithm for solving complex combinatorial optimization
problems. However, in the process of using this algorithm we encounter a serious limitation – noise
in the quantum system, which significantly reduces its efficiency. To overcome the influence of noise
and improve the efficiency of quantum algorithms, several methods have been proposed. This paper
presents a greedy heuristic algorithm aimed at reducing the impact of noise. The main goal of this
algorithm is to find a spanning tree of minimum height. This, in turn, reduces the overall depth of
quantum circuits and minimizes the number of CNOT gates, which is key to optimizing quantum
computing. Through numerical analysis, it was demonstrated that the proposed greedy heuristic
algorithm is capable of significantly increasing the probability of successful completion of each iteration
in the problem of finding the maximum cut in a graph by 10 times. Moreover, the study confirms
that the average depth of the quantum circuit generated by the proposed heuristic algorithm is still
linearly dependent on the size of the input data, but the slope of this linear dependence is reduced
from 1 to 0.11 by using the proposed method.
References
preprint arXiv:1411.4028, 2014.
2. Cerezo M., Arrasmith A., Babbush R., Benjamin S., Endo S., Fujii K., McClean J., Mitarai K.,
Yuan X., Cincio L., et al. Variational quantum algorithms, arXiv preprint arXiv:2012.09265,
2020.
3. Linke N.M., Gutierrez M., Landsman K.A., et al. Fault-tolerant quantum error detection, Science
Advances, 2017, 3 (10): e1701074. Available from: https://doi.org/10.1126/
sciadv.1701074.
4. Vuillot C. Is error detection helpful on IBM 5q chips?, Quantum Information and Computation,
2018, Vol. 18, No. 11-12, pp. 0949-0964.
5. Barron G. and Wood C. Measurement error mitigation for variational quantum algorithms,
arXiv preprint arXiv:2010.08520, 2020.
6. Endo S., Benjamin S., and Li Y. Practical quantum error mitigation for near-future applications,
Physical Review X, 2018, 8 (3):031027.
7. Endo S., Cai Z., Benjamin S., and Yuan X. Hybrid quantum-classical algorithms and quantum
error mitigation, Journal of the Physical Society of Japan, 2021, 90 (3):032001.
8. Zhu L., Tang H., Barron G., Calderon-Vargas F., Mayhall N., Barnes E., and Economou S. An
adaptive quantum approximate optimization algorithm for solving combinatorial problems on
a quantum computer, arXiv preprint arXiv:2005.10258, 2020.
9. Larkin J., Jonsson M., Justice D., and Guerreschi G. Evaluation of quantum approximate optimization
algorithm based on the approximation ratio of single samples, arXiv e-prints, pages
arXiv–2006, 2020.
10. Barkoutsos P., Nannicini G., Robert A., Tavernelli I., and Woerner S. Improving variational
quantum optimization using cvar, Quantum, 2020, 4:256.
11. Harper R, Flammia S.T. Fault-tolerant logical gates in the IBM quantum experience, Phys.
Rev. Lett., 2019, 122:080504. Available from: https://link.aps.org/doi/10.1103/
PhysRevLett.122.080504.
12. Hales S. Hallgren An improved quantum Fourier transform algorithm and applications, Proceedings
of the 41st Annual Symposium on Foundations of Computer Science, November
12–14, 2000, pp. 515.
13. Guzik V., Gushanskiy S., Polenov M., Potapov V. Complexity Estimation of Quantum Algorithms
Using Entanglement Properties, 16th International Multidisciplinary Scientific
GeoConference, Bulgaria, 2016, pp. 20-26.
14. Guzik V., Gushanskiy S., Polenov M., Potapov V. Models of a quantum computer, their characteristics
and analysis, 9th International Conference on Application of Information and Communication
Technologies (AICT). Institute of Electrical and Electronics Engineers, 2015,
pp. 583-587.
15. Collier D. The Comparative Method. In: Finifter A.W. (ed.) Political Sciences: The State of
the Discipline II. American Science Association. Washington, DC, 1993, pp. 105-119.
16. Olukotun K. Chip Multiprocessor Architecture – Techniques to Improve Throughput and Latency.
Morgan and Claypool Publishers, San Rafael, 2007.
17. Raedt K.D., Michielsen K., De Raedt H., Trieu B., Arnold G., Marcus Richter, Th Lip-pert,
Watanabe H., and Ito N. Massively parallel quantum computer simulator, Computer Physics
Communications, 176, pp. 121-136.
18. Williams C.P. Explorations in Quantum Computing, Texts in Computer Science, Chapter 2.
Quantum Gates. Springer, 2011, pp. 51-122.
19. Potapov V., Gushanskiy S., Guzik V., Polenov M. The Computational Structure of the Quantum
Computer Simulator and Its Performance Evaluation, In: Software Engineering Perspectives
and Application in Intelligent Systems. Advances in Intelligent Systems and Computing.
Springer, 2019, Vol. 763, pp. 198-207.
20. Rahman M. and Kaykobad M. Complexities of some interesting problems on spanning trees,
Information Processing Letters, 2005, 94 (2), pp. 93-97.
21. Bennett С.H., Shor P.W., Smolin J.A., Thapliyal A.V. Entanglement-assisted Capacity of a
Quantum Channel and the Reverse Shannon Theorem, IEEE Transactions on Information
Theory, 2002, 48, 2637.
22. Hector A. et al. Qiskit: An open-source framework for quantum computing, 2019.
23. Milner R.G. A Short History of Spin., In: Contribution to the XV International Workshop on
Polarized Sources, Targets, and Polarimetry. Charlottesville, Virginia, USA, September 9 –
13, 2013. arXiv:1311.5016 (2013);
24. Boneh D., Zhandry M. Quantum-secure message authentication codes, In: Proceedings of
Eurocrypt, 2013, pp. 592-608;
25. Potapov V., Gushansky S., Guzik V., Polenov M. Architecture and Software Implementation of
a Quantum Computer Model, In: Advances in Intelligent Systems and Computing. Springer,
2016, Vol. 465, pp. 59-68.
