Gast ::
| Hauptseite > Publikationsdatenbank > Solving constrained combinatorial optimization problems on quantum devices with linear penalty terms |
| Hauptseite > Publikationsdatenbank > Solving constrained combinatorial optimization problems on quantum devices with linear penalty terms |
| Poster (After Call) | FZJ-2024-05358 |
; ; ;
2024
This record in other databases:
Please use a persistent id in citations: doi:10.34734/FZJ-2024-05358
Abstract: Quantum computing approaches to solving constrained combinatorial optimization problems, such as Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA), are often impeded by the fact that constraints are typically implemented as costly quadratic penalty terms in the cost function. It was recently found that linear penalty terms might suffice to solve a specific class of constrained optimizationproblems [1]. Here, conditions are outlined under which linear penalty terms can correctly encode two other constrained optimization problems, namely the Quadratic Knapsack Problem (QKP) and the Portfolio Optimization (PO) problem. For these two problems, our QAOA simulations suggest that problem Hamiltonians with a linear penaltyterm can yield a higher success probability than those with the usual quadratic penaltyterm. However, algorithm performance depends on the precise specification of the problems, e.g., the distribution of the covariances between assets in the PO problem. Additionally, for the fully connected PO problem it seems possible to neglect some of the connections between qubits by setting the corresponding problem coefficients to zero,while maintaining similar performance. Since the linear penalty terms can be implemented as single-qubit gates or biases, such problems require lower connectivity of thequantum hardware or can be run with shallower circuits, which should lead to improvedperformance on today’s noisy quantum processors.[1] Puya Mirkarimi, Ishaan Shukla, David C. Hoyle, Ross Williams, and Nicholas Chancellor. Quantum optimization with linear Ising penalty functions for customer data science. 2024. arXiv: 2404.05467[quant-ph].
|
The record appears in these collections: |
PDF