Efficient encoding of the weighted MAX k-CUT on a quantum computer using QAOA

Abstract

The weighted MAX k-CUT problem consists of finding a k-partition of a given weighted undirected graph G(V,E) such that the sum of the weights of the crossing edges is maximized. The problem is of particular interest as it has a multitude of practical applications. We present a formulation of the weighted MAX k-CUT suitable for running the quantum approximate optimization algorithm (QAOA) on noisy intermediate scale quantum (NISQ)-devices to get approximate solutions. The new formulation uses a binary encoding that requires only |V|log_2(k) qubits. The contributions of this paper are as follows: i) A novel decomposition of the phase separation operator based on the binary encoding into basis gates is provided for the MAX k-CUT problem for k >2. ii) Numerical simulations on a suite of test cases comparing different encodings are performed. iii) An analysis of the resources (number of qubits, CX gates) of the different encodings is presented. iv) Formulations and simulations are extended to the case of weighted graphs. For small k and with further improvements when k is not a power of two, our algorithm is a possible candidate to show quantum advantage on NISQ devices.

14 pages

References in corpus (3)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A Quantum Approximate Optimization Algorithm
• Warm-starting quantum optimization

Cited by in corpus (10)

• Error mitigation for variational quantum algorithms through mid-circuit measurements
• Constrained mixers for the quantum approximate optimization algorithm
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Qubit Reduction and Quantum Speedup for Wireless Channel Assignment Problem
• Numerical Gate Synthesis for Quantum Heuristics on Bosonic Quantum Processors
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• A Novel Quantum Realization of Jet Clustering in High-Energy Physics Experiments
• Detection of energy levels of a spin system on a quantum computer by probe spin evolution
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs
• Energy levels estimation on a quantum computer by evolution of a physical quantity