Quantum Algorithms for Optimization

Владик Крейнович, Oscar Galindo, Olga M. Kosheleva

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.

Dilnoz Muhamediyeva, Rustam Raximov, Shavkat Urokov

Sergio Boixo, Rolando D. Somma

Justus Shunza, Mary Akinyemi, Chika Yinka-Banjo

This article proposes a new, more efficient quantum algorithm for portfolio optimization and uses quantum combinatorial optimization (QCO) techniques. The recent construction developed in 2021 has sparked the field of financial portfolio optimization through the Quantum Walk Optimization Algorithm (QWOA). We study the complexity and efficiency of quantum optimization algorithms with a special interest in QWOA. The objective is to minimize the risk of investing by having a good combination of assets in the portfolio. We also focus on reducing the number of iterations yet attaining a high-quality resolution through contraction of the solution space that eases computations. We extend QWOA’s idea by constructing a newly outperforming scheme known as ’Quantum Mix Optimization Algorithm (QMOA)’. QMOA algorithm codes are provided for the implementation and simulation of numerical results. In addition, QMOA’s efficiency (better than the existing QCO algorithms) is discussed. For instance, the least QWOA number of computations required to execute the initial state equation is p > 2 while this value is p ≥ 2 in the proposed QMOA.

Jincheng Zhang

This paper introduces the Dynamic Quantum Algorithm Optimization (DQAO) framework, a novel approach to quantum algorithm optimization that goes beyond traditional static optimization techniques. DQAO dynamically adapts to the quantum algorithm's internal state and incorporates its inherent properties to significantly enhance algorithm efficiency. The core mechanism revolves around leveraging the quantum algorithm's own quantum properties, specifically its superposition and entanglement, to refine the optimization process. This allows for a more responsive and effective optimization, achieving improved performance compared to conventional methods, particularly in scenarios involving complex quantum circuits. We present a detailed theoretical analysis and preliminary experimental results demonstrating the effectiveness of this approach.

Jesse Van Griensven Thé, Roydon Andrew Fraser, José R. Rosas-Bustos