2022/09/02 by Eunou Lee, Lee, Eunou · 8 citations
Computer Science · Mathematics · #Algorithm #Computer science #Convex optimization #Electronic circuit #FOS: Physical sciences #Graph #Mathematical optimization #Mathematics #Parameterized complexity #Physics #Polynomial #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum algorithm #Quantum circuit #Quantum computer #Quantum error correction #Quantum gate #Quantum mechanics #Regular polygon #Rounding #Set (abstract data type) #Theoretical computer science
paper · pdf · doi:10.48550/arxiv.2209.00789
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2022/09/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In recent years, parameterized quantum circuits have become a major tool to design quantum algorithms for optimization problems. The challenge in fully taking advantage of a given family of parameterized circuits lies in finding a good set of parameters in a non-convex landscape that can grow exponentially to the number of parameters. We introduce a new framework for optimizing parameterized quantum circuits: round SDP solutions to circuit parameters. Within this framework, we propose an algorithm that produces approximate solutions for a quantum optimization problem called Quantum Max Cut. The rounding algorithm runs in polynomial time to the number of parameters regardless of the underlying interaction graph. The resulting 0.562-approximation algorithm for generic instances of Quantum Max Cut improves on the previously known best algorithms, which give approximation ratios of less than 0.54.