TY  - CONF
AU  - van den Heuvel, Pim
AU  - Montanez-Barrera, Jhon Alejandro
AU  - Willsch, Dennis
AU  - Michielsen, Kristel
TI  - Solving constrained combinatorial optimization problems on quantum devices with linear penalty terms
M1  - FZJ-2024-05358
PY  - 2024
AB  - 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].
T2  - Adiabatic Quantum Computing 2024
CY  - 10 Jun 2024 - 14 Jun 2024, Glasgow (UK)
Y2  - 10 Jun 2024 - 14 Jun 2024
M2  - Glasgow, UK
LB  - PUB:(DE-HGF)24
DO  - DOI:10.34734/FZJ-2024-05358
UR  - https://juser.fz-juelich.de/record/1030625
ER  -