arXiv:2008.08615 · PRX Quantum

Low-Depth Mechanisms for Quantum Optimization

Jarrod R. McClean, Matthew P. Harrigan, Masoud Mohseni, Nicholas C. Rubin, Jiang Zhang, Sergio Boixo, Vadim Smelyanskiy, Ryan Babbush, Hartmut Neven

Published Jul 21, 2021• 44 citations

arXiv HTML PDF

Abstract

By gaining intuition about the mechanisms by which quantum optimization algorithms solve problems, approaches are identified that substantially improve the performance of quantum algorithms for this task.

DOI: 10.1103/prxquantum.2.030312

Related papers

Advancements in Quantum Algorithms for Solving Complex Optimization Problems

Emmanuel Adediran, Iyanuoluwa Fatoki, Taiwo Ogunyinka

Jan 1, 20242 citations

Core Claim: Design a novel quantum optimization algorithm based on quantum entanglement, capable of rapidly solving complex non-linear optimization problems.

Jincheng Zhang

Quantum optimization is a rapidly growing field with the potential to revolutionize various computational tasks, particularly those involving complex, non-linear problems. Classical optimization algorithms often struggle to efficiently handle these challenges. This paper investigates the application of quantum entanglement to develop a new optimization method, aiming to overcome these limitations. We propose a novel quantum optimization framework that leverages entanglement to accelerate the solution of complex non-linear optimization problems. The core mechanism of this approach centers around exploiting the correlated states of entangled quantum bits to guide the search process, fostering a significantly enhanced efficiency compared to classical approaches. We detail the algorithm's architecture, the quantum circuit design employed for entanglement generation and manipulation, and a preliminary analysis of its performance on benchmark optimization problems. This research explores the potential for quantum optimization to fundamentally alter the landscape of computational optimization, offering a pathway towards solving previously intractable problems. The presented algorithm demonstrates promising results through simulations, suggesting that it can provide substantial speedups and improved solution quality for specific types of non-linear optimization tasks.

Sep 3, 20260 citations

A study of the performance of classical minimizers in the Quantum Approximate Optimization Algorithm

Mario Fernández-Pendás, Elías F. Combarro, Sofia Vallecorsa +2 more

Journal of Computational and Applied MathematicsJan 14, 202152 citations

Alignment between initial state and mixer improves QAOA performance for constrained optimization

Zichang He, Ruslan Shaydulin, Shouvanik Chakrabarti +4 more

Abstract Quantum alternating operator ansatz (QAOA) has a strong connection to the adiabatic algorithm, which it can approximate with sufficient depth. However, it is unclear to what extent the lessons from the adiabatic regime apply to QAOA as executed in practice with small to moderate depth. In this paper, we demonstrate that the intuition from the adiabatic algorithm applies to the task of choosing the QAOA initial state. Specifically, we observe that the best performance is obtained when the initial state of QAOA is set to be the ground state of the mixing Hamiltonian, as required by the adiabatic algorithm. We provide numerical evidence using the examples of constrained portfolio optimization problems with both low (p ≤ 3) and high (p = 100) QAOA depth. Additionally, we successfully apply QAOA with XY mixer to portfolio optimization on a trapped-ion quantum processor using 32 qubits and discuss our findings in near-term experiments.

arXiv:2305.03857npj Quantum InformationNov 27, 202348 citations

Quantum Algorithms for Optimization Problems

Dilnoz Muhamediyeva, Rustam Raximov, Shavkat Urokov

Lecture notes in computer scienceJul 29, 20250 citations

Role of Quantum Computing in Solving Optimization Problems in Artificial Intelligence

Yuri Alexeev, Tanbir Hasan Taz, Mohammad Zobair Hossain

Quantum computing, leveraging quantum mechanics, promises to enhance optimization processes in artificial intelligence (AI) by addressing challenges faced by classical computing in solving complex problems. This study investigates the role of quantum computing in optimizing AI tasks, focusing on algorithms such as Quantum Approximate Optimization Algorithm (QAOA) and Quantum Annealing (QA) for improved efficiency in optimization. A hybrid quantum-classical approach was used to evaluate the performance of quantum algorithms in optimization tasks, including combinatorial optimization and machine learning model tuning. QAOA and QA were applied to benchmark problems, such as Max-Cut and Traveling Salesman Problem (TSP). The study involved a comparative analysis between quantum algorithms and classical optimization techniques using performance metrics like solution quality, computational time, and scalability. Data were gathered through simulation on a quantum computing platform, and results were analyzed using statistical methods to assess improvements. The results showed that quantum computing significantly outperformed classical methods in solving large-scale optimization problems. QAOA demonstrated a 30% improvement in solution quality for Max-Cut problems, and QA showed a 25% faster convergence in TSP compared to classical algorithms. Quantum algorithms demonstrated scalability advantages as the problem size increased, with quantum methods achieving up to a 40% reduction in computational time for large instances. Furthermore, 70% of the tested cases showed significant improvements in solution accuracy, confirming the potential of quantum computing in real-world AI applications. Quantum computing, through QAOA and QA, offers substantial improvements in solving complex optimization problems in AI, presenting a transformative opportunity for the future of optimization algorithms.

Pacific Journal of Advanced Engineering InnovationsDec 31, 20243 citations