Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2304.03576 · Physical Review A

Native measurement-based quantum approximate optimization algorithm applied to the Max K -Cut problem

Massimiliano Proietti, Filippo Cerocchi, Massimiliano Dispenza

Published Aug 30, 2022• 23 citations
arXivHTMLPDF

Abstract

Photonic quantum computers, programed within the framework of the measurement-based quantum computing (MBQC), and gate-based platforms are racing toward useful quantum advantage, and some algorithms have emerged as main candidates to reach this goal in the near term. The majority of these algorithms are only expressed in the gate-based model of computation, which is incompatible with photonic platforms. Methods to translate gate-based algorithms into the MBQC framework exist, but they are not always optimal in terms of resource cost. In our work, we propose an MBQC algorithm to run the quantum approximate optimization algorithm (QAOA). Furthermore, we apply the MBQC-QAOA algorithm to the Max $K$-Cut problem, for all values of $K$, expressing the cost Hamiltonian and its constraints in a form easily implementable in the MBQC model. We conclude by analyzing the resource cost of our algorithm, compared to the case of translating a gate-based QAOA algorithm into MBQC rules, and show up to a 30-fold improvement. With our work, we contribute to closing the gap between gate-based and MBQC near-term algorithms, a gap not reflecting the current status of the hardware development.

DOI
10.1103/physreva.106.022437

Related papers

A Max K-Cut Implementation for QAOA in the Measurement Based Quantum Computing Formalism

Sebastiano Corli, Daniele Dragoni, Massimiliano Proietti +3 more

The MaxCut is a combinatorial problem which belongs to the NP-hard class. The algorithm to solve it can be mapped into a quantum system, where the optimal configuration matches the ground state of a target Hamiltonian. It is possible to implement the adiabatic theorem into the circuit model via the QAOA algorithm, by arbitrarily choosing from both the gate-based and the measurement-based quantum computing (MBQC) settings. Recently, the MaxCut problem has been generalized to the Max K-Cut version also in the MBQC frame, where K stands for the number of cuts to implement. Here, the QAOA algorithm for a Max K-Cut is solved for a graph with arbitrary number of vertices V and number of cuts K scaling as a power of 2, along with the circuit depth p. The problem is solved on a emulator based on classical HPC resources. In order to test the performances of a Max K-cut implemented in the MBQC frame, we report how the average runtime and the approximation ratio scale by increasing V, K and p, comparing the results from two different topologies of graphs, 2-regular graphs with null weights on the diagonals versus the the fully-connected graphs. Eventually, the approximation ratio, evaluated as a parameter of success, is shown to yield optimal performances.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•12 citations

Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs

Bence Bakó, Adam Glos, Özlem Salehi +1 more

Current state-of-the-art quantum optimization algorithms require representing the original problem as a binary optimization problem, which is then converted into an equivalent cost Hamiltonian suitable for the quantum device. Implementing each term of the cost Hamiltonian separately often results in high redundancy, significantly increasing the resources required. Instead, we propose to design classical programs for computing the objective function and certifying the constraints, and later compile them to quantum circuits, eliminating the reliance on the binary optimization problem representation. This results in a new variant of the Quantum Approximate Optimization Algorithm (QAOA), which we name the Program-based QAOA (Prog-QAOA). We exploit this idea for optimization tasks like the Travelling Salesman Problem and Max- K -Cut and obtain circuits that are near-optimal with respect to all relevant cost measures, e.g., number of qubits, gates, and circuit depth. While we demonstrate the power of Prog-QAOA only for a particular set of paradigmatic problems, our approach is conveniently applicable to generic optimization problems.

arXiv:2209.03386•Quantum•Mar 20, 2025•36 citations

Edge-based quantum approximate optimization algorithm for MAX-CUT problem

Youngjin Seo, Jun Heo

Quantum computing has emerged as a promising paradigm to tackle computationally intensive problems that classical computers struggle with. In this study, we explore the application of the Edge-based quantum approximate optimization algorithm (QAOA) to the MAX-CUT problem, a well-known combinatorial optimization challenge. MAX-CUT aims to partition the vertices of a graph into two subsets such that the number of edges between the subsets is maximized. We define the edge-based MAX-CUT problem and propose a method for applying QAOA specifically tailored to this formulation. We conduct simulations using IBM’s Qiskit framework, examining both vertex-based and edge-based QAOA implementations across various graph structures. Our results highlight the comparative performance of these approaches in terms of solution quality and computational efficiency. Specifically, we analyze the impact of different graph sizes and edge densities on the complexity and CNOT gate counts of the proposed algorithms. This analysis provides insights into leveraging quantum computing for combinatorial optimization tasks, particularly focusing on the implications for practical applications and future research directions.

Quantum Information Processing•Sep 23, 2025•2 citations

Photonic Quantum Hardware for AI Optimization Tasks

Sarah Daneshzad, Gholam-Mohammad Parsanasab

Recent advances in photonic quantum computing offer a promising route for accelerating combinatorial optimization problems central to artificial intelligence (AI). This paper presents a hardware-aware simulation framework for implementing the Quantum Approximate Optimization Algorithm (QAOA) on photonic hardware platforms, extending prior photonic QAOA implementations for the Max-Cut problem [1] to more general AI-relevant graph optimization tasks. Unweighted, weighted, and balanced graph-partitioning problems are modeled as representative benchmarks, and their cost and mixer unitaries are compiled into integrated-photonics primitives based on Mach–Zehnder interferometers, programmable phase shifters, and cross-Kerr-type interactions. Depth- p photonic QAOA circuits (p = 1-3) are simulated using the Strawberry Fields photonic backend with realistic models of propagation loss, phase noise, and detector inefficiency. The results show monotonic improvement in approximation ratio with increasing depth, achieving up to ρ ≈ 0. 87 for graphs with n ≤ 18 and less than 10% degradation under nominal noise conditions. Warm-start initialization reduces the number of optimization iterations by approximately 30% compared with random initialization. Benchmark comparisons with Goemans–Williamson and simulated annealing demonstrate that photonic QAOA attains near-classical performance for small- to medium-sized graphs, indicating that integrated photonics is a feasible platform for near-term quantum optimization.

International Interdisciplinary Conference on Artificial Intelligence: Engineering, Health, Finance and Humanities (IICAI)•May 1, 2026•3 citations

Quantum approximate optimization algorithm with cat qubits

Pontus Vikstål, Laura García-Álvarez, Shruti Puri +1 more

Abstract The Quantum Approximate Optimization Algorithm (QAOA)–a prominent candidate for near-term quantum computing applications–is tailored to find approximate solutions to combinatorial optimization problems using shallow quantum circuits. In this work, we investigate implementations of QAOA based on cat qubits, where the logical states $$|0\rangle$$ and $$|1\rangle$$ are represented by coherent states of opposite amplitudes, $$|\alpha \rangle$$ and $$|-\alpha \rangle$$ . Within this encoding, the primary source of noise–photon loss–induces a bias toward Z -type errors. We focus specifically on an imlementation employing Kerr resonators. By numerically simulating the gate sequences required for QAOA on these nonlinear resonators, we analyze performance on Max-Cut problems and benchmark it against conventional qubits realized as ideal two-level systems subject to single-photon loss. Our findings indicate that the use of cat qubits leads to improved approximation ratios for random Max-Cut instances compared to standard qubit encodings.

arXiv:2305.05556•Scientific Reports•Nov 10, 2026•6 citations

Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem

Gavin E. Crooks

The Quantum Approximate Optimization Algorithm (QAOA) is a promising approach for programming a near-term gate-based hybrid quantum computer to find good approximate solutions of hard combinatorial problems. However, little is currently know about the capabilities of QAOA, or of the difficulty of the requisite parameters optimization. Here, we study the performance of QAOA on the MaxCut combinatorial optimization problem, optimizing the quantum circuits on a classical computer using automatic differentiation and stochastic gradient descent, using QuantumFlow, a quantum circuit simulator implemented with TensorFlow. We find that we can amortize the training cost by optimizing on batches of problems instances; that QAOA can exceed the performance of the classical polynomial time Goemans-Williamson algorithm with modest circuit depth, and that performance with fixed circuit depth is insensitive to problem size. Moreover, MaxCut QAOA can be efficiently implemented on a gate-based quantum computer with limited qubit connectivity, using a qubit swap network. These observations support the prospects that QAOA will be an effective method for solving interesting problems on near-term quantum computers.

arXiv:1811.08419•Bulletin of the American Physical Society•Nov 20, 2018•340 citations
Photonic quantum computers, programed within the framework of the measurement-based quantum computing (MBQC), and gate-based platforms are racing toward useful quantum advantage, and some algorithms have emerged as main candidates to reach this goal in the near term. The majority of these algorithms are only expressed in the gate-based model of computation, which is incompatible with photonic platforms. Methods to translate gate-based algorithms into the MBQC framework exist, but they are not always optimal in terms of resource cost. In our work, we propose an MBQC algorithm to run the quantum approximate optimization algorithm (QAOA). Furthermore, we apply the MBQC-QAOA algorithm to the Max KKK-Cut problem, for all values of KKK, expressing the cost Hamiltonian and its constraints in a form easily implementable in the MBQC model. We conclude by analyzing the resource cost of our algorithm, compared to the case of translating a gate-based QAOA algorithm into MBQC rules, and show up to a 30-fold improvement. With our work, we contribute to closing the gap between gate-based and MBQC near-term algorithms, a gap not reflecting the current status of the hardware development.
The MaxCut is a combinatorial problem which belongs to the NP-hard class. The algorithm to solve it can be mapped into a quantum system, where the optimal configuration matches the ground state of a target Hamiltonian. It is possible to implement the adiabatic theorem into the circuit model via the QAOA algorithm, by arbitrarily choosing from both the gate-based and the measurement-based quantum computing (MBQC) settings. Recently, the MaxCut problem has been generalized to the Max K-Cut version also in the MBQC frame, where K stands for the number of cuts to implement. Here, the QAOA algorithm for a Max K-Cut is solved for a graph with arbitrary number of vertices V and number of cuts K scaling as a power of 2, along with the circuit depth p. The problem is solved on a emulator based on classical HPC resources. In order to test the performances of a Max K-cut implemented in the MBQC frame, we report how the average runtime and the approximation ratio scale by increasing V, K and p, comparing the results from two different topologies of graphs, 2-regular graphs with null weights on the diagonals versus the the fully-connected graphs. Eventually, the approximation ratio, evaluated as a parameter of success, is shown to yield optimal performances.
Current state-of-the-art quantum optimization algorithms require representing the original problem as a binary optimization problem, which is then converted into an equivalent cost Hamiltonian suitable for the quantum device. Implementing each term of the cost Hamiltonian separately often results in high redundancy, significantly increasing the resources required. Instead, we propose to design classical programs for computing the objective function and certifying the constraints, and later compile them to quantum circuits, eliminating the reliance on the binary optimization problem representation. This results in a new variant of the Quantum Approximate Optimization Algorithm (QAOA), which we name the Program-based QAOA (Prog-QAOA). We exploit this idea for optimization tasks like the Travelling Salesman Problem and Max- K -Cut and obtain circuits that are near-optimal with respect to all relevant cost measures, e.g., number of qubits, gates, and circuit depth. While we demonstrate the power of Prog-QAOA only for a particular set of paradigmatic problems, our approach is conveniently applicable to generic optimization problems.
Quantum computing has emerged as a promising paradigm to tackle computationally intensive problems that classical computers struggle with. In this study, we explore the application of the Edge-based quantum approximate optimization algorithm (QAOA) to the MAX-CUT problem, a well-known combinatorial optimization challenge. MAX-CUT aims to partition the vertices of a graph into two subsets such that the number of edges between the subsets is maximized. We define the edge-based MAX-CUT problem and propose a method for applying QAOA specifically tailored to this formulation. We conduct simulations using IBM’s Qiskit framework, examining both vertex-based and edge-based QAOA implementations across various graph structures. Our results highlight the comparative performance of these approaches in terms of solution quality and computational efficiency. Specifically, we analyze the impact of different graph sizes and edge densities on the complexity and CNOT gate counts of the proposed algorithms. This analysis provides insights into leveraging quantum computing for combinatorial optimization tasks, particularly focusing on the implications for practical applications and future research directions.
Recent advances in photonic quantum computing offer a promising route for accelerating combinatorial optimization problems central to artificial intelligence (AI). This paper presents a hardware-aware simulation framework for implementing the Quantum Approximate Optimization Algorithm (QAOA) on photonic hardware platforms, extending prior photonic QAOA implementations for the Max-Cut problem [1] to more general AI-relevant graph optimization tasks. Unweighted, weighted, and balanced graph-partitioning problems are modeled as representative benchmarks, and their cost and mixer unitaries are compiled into integrated-photonics primitives based on Mach–Zehnder interferometers, programmable phase shifters, and cross-Kerr-type interactions. Depth- p photonic QAOA circuits (p = 1-3) are simulated using the Strawberry Fields photonic backend with realistic models of propagation loss, phase noise, and detector inefficiency. The results show monotonic improvement in approximation ratio with increasing depth, achieving up to ρ ≈ 0. 87 for graphs with n ≤ 18 and less than 10% degradation under nominal noise conditions. Warm-start initialization reduces the number of optimization iterations by approximately 30% compared with random initialization. Benchmark comparisons with Goemans–Williamson and simulated annealing demonstrate that photonic QAOA attains near-classical performance for small- to medium-sized graphs, indicating that integrated photonics is a feasible platform for near-term quantum optimization.
Abstract The Quantum Approximate Optimization Algorithm (QAOA)–a prominent candidate for near-term quantum computing applications–is tailored to find approximate solutions to combinatorial optimization problems using shallow quantum circuits. In this work, we investigate implementations of QAOA based on cat qubits, where the logical states ∣0⟩|0\rangle∣0⟩ and ∣1⟩|1\rangle∣1⟩ are represented by coherent states of opposite amplitudes, ∣α⟩|\alpha \rangle∣α⟩ and ∣−α⟩|-\alpha \rangle∣−α⟩ . Within this encoding, the primary source of noise–photon loss–induces a bias toward Z -type errors. We focus specifically on an imlementation employing Kerr resonators. By numerically simulating the gate sequences required for QAOA on these nonlinear resonators, we analyze performance on Max-Cut problems and benchmark it against conventional qubits realized as ideal two-level systems subject to single-photon loss. Our findings indicate that the use of cat qubits leads to improved approximation ratios for random Max-Cut instances compared to standard qubit encodings.
The Quantum Approximate Optimization Algorithm (QAOA) is a promising approach for programming a near-term gate-based hybrid quantum computer to find good approximate solutions of hard combinatorial problems. However, little is currently know about the capabilities of QAOA, or of the difficulty of the requisite parameters optimization. Here, we study the performance of QAOA on the MaxCut combinatorial optimization problem, optimizing the quantum circuits on a classical computer using automatic differentiation and stochastic gradient descent, using QuantumFlow, a quantum circuit simulator implemented with TensorFlow. We find that we can amortize the training cost by optimizing on batches of problems instances; that QAOA can exceed the performance of the classical polynomial time Goemans-Williamson algorithm with modest circuit depth, and that performance with fixed circuit depth is insensitive to problem size. Moreover, MaxCut QAOA can be efficiently implemented on a gate-based quantum computer with limited qubit connectivity, using a qubit swap network. These observations support the prospects that QAOA will be an effective method for solving interesting problems on near-term quantum computers.