Quantum Computing Algorithms and Computational Complexity

• Other Authors: Pelayo, Fernando L. (Editor), Mezzini, Mauro (Editor)
• Format: Electronic Book Chapter
• Language: English
• Published: Basel MDPI - Multidisciplinary Digital Publishing Institute 2023
• Subjects: Research & information: general; Mathematics & science; quantum Markov chains; maximum von Neumann entropy; QSZK-completeness; amplitude amplification; subset sum problem; quantum algorithms; computational efficiency; quantum computation; string processing; sorting; quantum computing; quantum annealing; combinatorial optimization; QUBO; TSP; VRP; quantum weighted fractional Fourier transform; quantum Fourier transform; quantum algorithm; variatonal algorithms; QAOA; quantum circuit optimization; quantum image processing; image component labeling; local operator; Levialdi shrinking operator; n/a
• Online Access: DOAB: download the publication; DOAB: description of the publication

This reprint is mainly concerned with quantum algorithms, their mathematics from behind and the complexity issues arising from them. It comprises seven papers: Two of them are focused on improving the performance by means of quantum algorithms over the best instances of classical ones: "A Fast Quantum Image Component Labeling Algorithm" [1] by Yan Li, Dapeng Hao, Yang Xu and Kinkeung Lai. "Quantum Algorithms for Some Strings Problems Based on Quantum String Comparator" [2] by Kamil Khadiev, Artem Ilikaev and Jevgenijs Vihrovs. Another four papers deal with enhanced quantum algorithms: "Progress towards Analytically Optimal Angles in Quantum Approximate Optimisation": [3] by Daniil Rabinovich, Richik Sengupta, Ernesto Campos, Vishwanathan Akshay and Jacob Biamonte. "Quantum Weighted Fractional Fourier Transform" [4] by Tieyu Zhao, Tianyu Yang and Yingying Chi. "On the Amplitude Amplification of Quantum States Corresponding to the Solutions of the Partition Problem" [5] by Mauro Mezzini, Jose J. Paulet, Fernando Cuartero, Hernan I. Cruz and Fernando L. Pelayo. "On the Complexity of Finding the Maximum Entropy Compatible Quantum State" [6] by Serena Di Giorgio and Paulo Mateus. Last, but not least, one paper researched a classical operational research problem by means of quantum annealing: "GPS: A New TSP Formulation for Its Generalizations Type QUBO" [7] by Saul Gonzalez-Bermejo, Guillermo Alonso-Linaje and Parfait Atchade-Adelomou. As Guest Editors, we would like to thank the authors and reviewers who made this possible by promoting, spreading research on and supporting quantum computing.