Many Known Quantum Algorithms Are Optimal: Symmetry-Based Proofs
DOI:
https://doi.org/10.47839/ijc.21.4.2776Keywords:
quantum computing, optimal algorithms, invariance, symmetryAbstract
Many quantum algorithms have been proposed which are drastically more efficient that the best of the non-quantum algorithms for solving the same problems. A natural question is: are these quantum algorithms already optimal – in some reasonable sense – or they can be further improved? In this paper, we review recent results showing that many known quantum algorithms are actually optimal. Several of these results are based on appropriate invariances (symmetries). Specifically, we show that the following algorithms are optimal: Grover’s algorithm for fast search in an unsorted array, teleportation algorithm – which is important for parallel quantum computations, and quantum annealing optimization algorithm. This covers many algorithms related to quantum computing. We also mention that algorithms for quantum communication and Deutsch-Josza algorithm – for fast checking whether a bit affect computation results – are optimal. In all these cases, optimality is shown not just for one specific optimality criterion, but for all possible optimality criteria that satisfy the natural invariance requirement.
References
J. Aczél and J. Dhombres, Functional Equations in Several Variables, Cambridge University Press, 2008.
I. Bautista, V. Kreinovich, O. Kosheleva, and H. P. Nguyen, “Why it is sufficient to have real-valued amplitudes in quantum computing”, In: Nguyen Hoang Phuong and V. Kreinovich (Eds.), Soft Computing: Biomedical and Related Applications, Springer: Cham, Switzerland, 2021, pp. 131–136. https://doi.org/10.1007/978-3-030-76620-7_11
C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters, “Teleporting an unknown quantum state via dual classical and Einstein-Podolsky–Rosen channels", Physical Review Letters, vol. 70, pp. 1895–1899, 1993.https://doi.org/10.1103/PhysRevLett.70.1895
S. Boixo, T. F. Ronnow, S. V. Isakov, Z. Wang, D. Wecker, D. A. Lidar, J. M. Martinis, and M. Troyer, “Evidence for quantum annealing with more than one hundred qubits", Nature Physics, vol. 10, pp. 218–224, 2014. https://doi.org/10.1038/nphys2900
J. Brooke, D. Bitko, T. F. Rosenbaum, and G. Aeppli, “Quantum annealing of a disordered magnet”, Science, vol. 284, pp. 779–781, 1999. https://doi. org/10.1126/science.284.5415.779
E. Crosson, E. Farhi, C. Y.-Y. Lin, H.-H. Lin, and P. Shor, Different Strategies for Optimization Using the Quantum Adiabatic Algorithm, 2014, arXiv:1401.7320.
A. Das, B. K. Chakrabarti, and R. B. Stinhcombe, “Quantum annealing in a kinetically constrained system”, Physical Review Letters, vol. 72, Paper 026701, 2005. https://doi.org/10.1103/PhysRevE.72.026701
E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Ludgren, and D. Preda, “A quantum adiabatic evolution algorithm applied to random instances of an NP-complete problem", Science, vol. 292, pp. 472–475, 2001. https: //doi.org/10.1126/science.1057726
R. Feynman, R. Leighton, and M. Sands, The Feynman Lectures on Physics, Addison Wesley, Boston, Massachusetts, 2005.
A. B. Finnila, M. A. Gomez, C. Sebenik, C. Stenson, and J. D. Doll, “Quantum annealing: A new method for minimizing multidimensional functions", Chemical Physics Letters, vol. 219, no. 5–6, pp. 343–348, 1994. https://doi.org/10.1016/0009-2614(94)00117-0
O. Galindo, L. Bokati, and V. Kreinovich, “Towards a more efficient representation of functions in quantum and reversible computing", Proceedings of the Joint 11th Conference of the European Society for Fuzzy Logic and Technology EUSFLAT’2019 and International Quantum Systems Association (IQSA) Workshop on Quantum Structures, Prague, Czech Republic, September 9–13, 2019. https://doi.org/10.2991/eusflat-19.2019.10
O. Galindo, O. Kosheleva, and V. Kreinovich, “Towards parallel quantum computing: standard quantum teleportation algorithm is, in some reasonable sense, unique", In: H. Seki, C. H. Nguyen, V.-N. Huynh, and M. Inuiguchi (Eds.), USB Proceedings of the 7th International Symposium on Integrated Uncertainty in Knowledge Modelling and Decision Making IUKM’2019, Nara, Japan, March 27–29, 2019, pp. 23–34.
O. Galindo, O. Kosheleva, and V. Kreinovich, “How to efficiently store intermediate results in quantum computing: theoretical explanation of the current algorithm", In: S. Sriboonchitta, V. Kreinovich, and W. Yamaka (Eds.), Credible Asset Allocation, Optimal Transport Methods, and Related Topics, Springer, Cham, Switzerland, 2022, pp. 51–64. https: //doi.org/10.1007/978-3-030-97273-8_5
O. Galindo and V. Kreinovich, “What is the optimal annealing schedule in quantum annealing", Proceedings of the IEEE Series of Symposia on Computational Intelligence SSCI’2020, Canberra, Australia, December 1– 4, 2020. https://doi.org/10.1109/SSCI47803.2020.9308407
O. Galindo, V. Kreinovich, and O. Kosheleva, “Current quantum cryptography algorithm is optimal: a proof", Proceedings of the IEEE Symposium on Computational Intelligence for Engineering Solutions CIES’2018, Bengaluru, India, November 18–21, 2018. https://doi.org/10.1109/SSCI.2018. 8628876
L. K. Grover, “A fast quantum mechanical algorithm for database search", Proceedings of the 28th ACM Symposium on Theory of Computing, 1996, pp. 212 – 219. https://doi.org/10.1145/237814.237866
L. K. Grover, “Quantum mechanics helps in searching for a needle in a haystack", Physical Reviews Letters, vol. 79, no. 2, pp. 325–328, 1997. https://doi.org/10.1103/PhysRevLett.79.325
B. Heim, T. F. Ronnow, S. V. Isakov, and M. Troyer, “Quantum versus classical annealing of Ising spin glasses", Science, vol. 348, pp. 215–217, 2015. https://doi.org/10.1126/science.aaa4170
T. Kadowaki and H. Nishimori, “Quantum annealing in the transverse Ising model", Physical Reviews E, vol. 58, Paper 5355, 1998. https: //doi.org/10.1103/PhysRevE.58.5355
V. Kreinovich, M. Ceberio, and R. Alvarez, “How to use quantum computing to check which inputs are relevant: a proof that Deutsch-Jozsa algorithm is, in effect, the only possibility", Proceedings of the 2019 IEEE Symposium Series on Computational Intelligence SSCI’2019, Xiamen, China, December 6–9, 2019, pp. 828–832. https://doi.org/10.1109/ SSCI44817.2019.9002709
T. Lanting, A. J. Przybysz, A. Yu. Smirnov, F. M. Spedalieri, M. H. Amin, A. J. Berkley, R. Harris, F. Altomare, S. Boixo, P. Bunyk, N. Dickson, C. Enderud, J. P. Hilton, E. Hoskinson, M. W. Johnson, E. Ladizinsky, N. Ladizinsky, R. Neufeld, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva, S. Uchaikin, S. B. Wilson, and G. Rose, Entanglement in a quantum annealing processor, Physical Review X, vol. 4, no. 2, Paper 021041, 2014. https://doi.org/10.1103/PhysRevX.4.021041
S. Morita and H. Nishimori, “Mathematical foundation of quantum annealing”, Journal of Mathematical Physics, vol. 49, Paper 125210, 2008. https://doi.org/10.1063/1.2995837
S. Mukherjee and B. K. Chakrabarti, “Multivariable optimization: Quantum annealing and computation”, The European Physical Journal Special Topics, vol. 224, pp. 17–24, 2015. https://doi.org/10.1140/epjst/ e2015-02339-y
D. Muthukrishnan, T. Albash, and D. A. Lidar, When Diabatic Trumps Adiabatic in Quantum Optimization, 2015, arXiv:1505.01249.
H. T. Nguyen and V. Kreinovich, Applications of Continuous Mathematics to Computer Science, Kluwer, Dordrecht, 1997. https://doi.org/10.1007/ 978-94-017-0743-5
M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, U.K., 2000.
S. Pirandola, J. Eisert, C. Weedbrook, A. Furusawa, and S. L. Braunstein, “Advances in quantum teleportation”, Nature Photonics, vol. 9, no. 10, pp. 641–652. https://doi.org/10.1038/nphoton.2015.154
G. E. Santoro and E. Tosatti, “Optimization using quantum mechanics: quantum annealing through adiabatic evolution", Journal of Physics A, vol. 39, Paper R393, 2006. https://doi.org/10.1088/0305-4470/39/36/R01
P. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, November 20–22, 1994.
P. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM Journal on Computing, vol. 26, pp. 1484–1509, 1997. https://doi.org/10.1137/S0097539795293172
V. N. Smelyanskiy, E. G. Rieffel, S. I. Knysh, C. P. Williams, M. W. Johnson, M. C. Thom, W. G. Macready, and K. L. Pudenz, A Near-Term Quantum Computing Approach for Hard Computational Problems in Space Exploration, 2012, arXiv:1204.2821.
S. Steiger, B. Heim, T. Ronnow, and M. Troyer, “Performance of quantum annealing hardware", In: D. A. Huckridge, R. Ebert, M. T. Gruneisen, M. Dusek, and J. G. Rarity (Eds.), Electro-Optical and Infrared Systems: Technology and Applications XII; and Quantum Information Science and Technology, SPIE Proceedings, 2015, Vol. 9648, Paper 964816. https: //doi.org/10.1117/12.2202661
K. S. Thorne and R. D. Blandford, Modern Classical Physics: Optics, Fluids, Plasmas, Elasticity, Relativity, and Statistical Physics; Princeton University Press, Princeton, New Jersey, 2017.
S. E. Venegas-Andraca, W. Cruz-Santos, C. McGeoch, and M. Lanzagorta, “A cross-disciplinary introduction to quantum annealing-based algorithms”, Contemporary Physics, vol. 59, no. 2, pp. 174–196, 2018. https://doi.org/10.1080/00107514.2018.1450720
C. P. Williams and S. H. Clearwater, Ultimate Zero and One, Copernicus, New York, 2000. https://doi.org/10.1007/978-1-4612-0495-4
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
