Quantum Variational Algorithms: The Good, the Bad and the Ugly
Jakub Mareček, Czech Technical University in Prague
Abstract: There is an increasing interest in quantum algorithms for problems of integer programming and combinatorial optimization. Classical solvers for such problems employ relaxations, which replace binary variables with continuous ones, for instance in the form of higher-dimensional matrix-valued problems (semidefinite programming). Under the Unique Games Conjecture, these relaxations often provide the best performance ratios available classically in polynomial time. Here, we discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of a combinatorial optimization problem and how to analyze properties of the associated quantum algorithms. In particular, this allows the quantum algorithm to inherit the performance guarantees of the classical algorithm. We illustrate this in the context of portfolio optimization, where our results indicate that warm-starting the Quantum Approximate Optimization Algorithm (QAOA) is particularly beneficial at low depth. Likewise, Recursive QAOA for MAXCUT problems shows a systematic increase in the size of the obtained cut for fully connected graphs with random weights, when Goemans-Williamson randomized rounding is utilized in a warm start. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.
Видео Quantum Variational Algorithms: The Good, the Bad and the Ugly канала Gemini Center on Quantum Computing
Abstract: There is an increasing interest in quantum algorithms for problems of integer programming and combinatorial optimization. Classical solvers for such problems employ relaxations, which replace binary variables with continuous ones, for instance in the form of higher-dimensional matrix-valued problems (semidefinite programming). Under the Unique Games Conjecture, these relaxations often provide the best performance ratios available classically in polynomial time. Here, we discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of a combinatorial optimization problem and how to analyze properties of the associated quantum algorithms. In particular, this allows the quantum algorithm to inherit the performance guarantees of the classical algorithm. We illustrate this in the context of portfolio optimization, where our results indicate that warm-starting the Quantum Approximate Optimization Algorithm (QAOA) is particularly beneficial at low depth. Likewise, Recursive QAOA for MAXCUT problems shows a systematic increase in the size of the obtained cut for fully connected graphs with random weights, when Goemans-Williamson randomized rounding is utilized in a warm start. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.
Видео Quantum Variational Algorithms: The Good, the Bad and the Ugly канала Gemini Center on Quantum Computing
Показать
Комментарии отсутствуют
Информация о видео
6 апреля 2022 г. 23:03:50
00:32:59
Другие видео канала
Quantum Error Correction from a Classical-Friendly World-ViewSolid-state spin qubitsEmergent computations for emerging technologiesQuantum-Resistant Cryptography From LatticesFault-tolerant Coding for Quantum CommunicationPost-Quantum Signature Schemes and the Oil-and-Vinegar ProblemA Mathematical Approach to Coupled Cluster MethodsQuantum reservoir computing for machine learningCoupled-Cluster Theory for ground- and excited eigenstatesLearning to measure - A new adaptive approach to extract information in algorithms for NISQ devicesMachine Learning for Variational Quantum AlgorithmsSynchronization in two-level quantum systemsQuantum groups and quantum information theoryCryptography in a (post-)quantum worldMultireference quantum chemistry on NISQ devicesLimitations of noisy quantum algorithmsAutomated, Systematic, and Optimized Testing of Quantum Programs with Q&AFrom Quantum Computing to Quantum Machine LearningArchitecting (Quantum) Computer Systems, with Q&AQuantum computing applications in quantum chemistry