Improve the qubit-efficient MaxCut (QEMC) algorithm and compare it with the quantum approximation optimization algorithm (QAOA) on noisy simulators and real hardware

הרקע לפרויקט:

The Quantum Approximate Optimization Algorithm (QAOA) stands as a pivotal variational quantum algorithm for approximating solutions to combinatorial problems, and is currently a flagship in the field of quantum computing. Recently, we have developed a qubit-efficient algorithm designed to heuristically solve the MaxCut problem, a well-known combinatorial NP-hard problem. Owing to its qubit efficiency, this algorithm necessitates relatively shallow quantum circuits, thereby reducing susceptibility to noise. Consequently, we anticipate that this Qubit-Efficient MaxCut (QEMC) algorithm will outperform the QAOA on existing noisy quantum hardware, a hypothesis supported by our preliminary tests. However, we have also demonstrated that in its present form, the QEMC is classically efficiently simulatable, implying it does not achieve quantum speedup. This raises a critical question: what is the relationship between QAOA and QEMC, and what insights can be gained about QAOA's potential to demonstrate a quantum advantage? The aim of this project is to explore and answer these questions.

מטרת הפרויקט:

The goal of this project is to answer the following question: is there any computational setting \ (non-zero) noise level for which we can expect QAOA to perform better than the QEMC? We will consider the following aspects: noise levels, types of quantum hardware, graph families, and graph sizes.

תכולת הפרויקט:

The students are expected to:

• Understand and implement the QAOA
• Understand and implement the QEMC algorithm
• Improve the QEMC algorithm with respect to the required number of layers.
• Run the QAOA and QEMC on noisy simulations and different types of real quantum hardware for a verity of graphs with up to 20 qubits.
• Present the results in a meaningful way
• Extrapolate the results for larger graphs and identify the condition required for the QAOA to outperform the QEMC algorithm

קורסי קדם:

• Quantum computing
• Quantum machine learning

דרישות נוספות:

Any knowledge on machine learning will be a plus.

מקורות:

https://arxiv.org/abs/2308.10383