A native measurement-based QAOA algorithm, applied to the MAX K-CUT problem

Abstract

Photonic quantum computers, programmed within the framework of the measurement-based quantum computing (MBQC), currently concur with gate-based platforms in the race towards useful quantum advantage, and some algorithms emerged as main candidates to reach this goal in the near term. Yet, 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, working for all values of $K$, expressing the cost Hamiltonian and its constraints in a form easily implementable in the MBQC model. We conclude analyzing the resource-cost of our algorithm, compared to the case of translating a gate-based QAOA algorithm into MBQC rules showing up to a 30-fold improvement. With our work, we contribute to close the gap between gate-based and MBQC near-term algorithms, a gap not reflecting the current status of the hardware development.

arXiv commentPublished on PRA

References in corpus (20)

• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• Quantum computational advantage using photons
• A Quantum Approximate Optimization Algorithm
• Experimental One-Way Quantum Computing
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum optimization using variational algorithms on near-term quantum devices
• Ultra-Large-Scale Continuous-Variable Cluster States Multiplexed in the Time Domain
• Quantum circuits with many photons on a programmable nanophotonic chip
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Experimental realization of one-way quantum computing with two-photon four-qubit cluster states
• $XY$-mixers: analytical and numerical results for QAOA
• Hardware-efficient variational quantum algorithms for time evolution
• Reachability Deficits in Quantum Approximate Optimization
• A measurement-based variational quantum eigensolver
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer
• Creation of Entangled Photonic States Using Linear Optics
• Analytic Constructions of General n-Qubit Controlled Gates
• Measurement-based interleaved randomised benchmarking using IBM processors

Cited by in corpus (6)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters
• A Novel Quantum Realization of Jet Clustering in High-Energy Physics Experiments
• Simulating photonic devices with noisy optical elements
• Applicability of Measurement-based Quantum Computation towards Physically-driven Variational Quantum Eigensolver
• Minimally Universal Parity Quantum Computing