qcr:2604.10563.1

Variational Quantum Algorithms for Combinatorial Optimization

The promise of quantum computing to address complex problems requiring high computational resources has long been hindered by the intrinsic and demanding requirements of quantum hardware development. Nonetheless, the current state of quantum computing, denominated Noisy Intermediate-Scale Quantum (NISQ) era, has introduced algorithms and methods that are able to harness the computational power of current quantum computers with advantages over classical computers (referred to as quantum advantage). Achieving quantum advantage is of particular relevance for the combinatorial optimization domain, since it often implies solving an NP-Hard optimization problem. Moreover, combinatorial problems are highly relevant for practical application areas, such as operations research, or resource allocation problems. Among quantum computing methods, Variational Quantum Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems. This paper explores the current state and recent developments of VQAs, emphasizing their applicability to combinatorial optimization. We identify the Quantum Approximate Optimization Algorithm (QAOA) as the leading candidate for these problems. Furthermore, we implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes, demonstrating the potential and challenges of using VQAs in practical optimization tasks. We release our code, dataset and optimized circuit parameters under https://github.com/DanielFPerez/VQA-for-MaxCut.

Optimization

Qubit

Circuit-based

Uploaded 2 months ago

Views

View Publication

GitHub

Citing this entry? Use this QCR ID

Uploaded by

QCR Librarian

DanielFPerez/VQA-for-MaxCut

README.md

Variational Quantum Circuits for MaxCut Problem

This repository implements the QAOA algorithm for solving the MaxCut problem on Erdős-Rényi random graphs.

Installation

It is recommended to create a new Python virtual environment first:

$ python3 -m venv /path/to/vnevs/quantum_cirq

Activate the python environment and install the required packages with the provided quantum_requirements.txtfile:

$ source /path/to/vnevs/quantum_cirq/bin/activate
$ cd /path/to/this/repo
$ pip install -r ./quantum_requirements.txt

Run files

Generate random Graphs: go to the Jupyter script main_generate_random_graphs.ipynb
Optimize QAOA Circuit: this is done with the python file main_qaoa.py. Usage:
- How to run the file (e.g., using a file for 20-node graphs with 100 elements, the gradient optimizer for a QAOA circuit of depth 1 and saving results disk):
```
$ cd /path/to/this/repo
$ python main_qaoa.py --graph_file "./data/graphs-20nodes_100elems.pkl" --optimizer "gradient" --depth 1 --out_path "./results/grad_p1_20nodes.pkl"
```
- Help guide:
```
$ python main_qaoa.py --help
```
Evaluate circuit: load an optimized circuit and compare it to a classical MaxCut algorithm, make some plots comparing their performance. This is done in the jupyter notebook main_evaluate_circuits.ipynb.

Folder structure

data: path where the random graphs are saved. Each file here is a pickled object of Python list containing the graphs.
logs: text log files.
results: here the results from quantum circuit optimizations are saved (output of running main_qaoa.py). The structure of the pickled object is a dictionary with following keys:
- p: QAOA circuit depth.
- optimizer: string, either "gradient" (BFGS) or "non-gradient" (Nelder-Mead).
- graphs: list of graphs.
- optimized_parameters: list of optimal parameters of the quantum circuit (size 2p).
src: source code for building circuit, utils, and evaluating circuits.
plots: figures after post-processing.

Join the Discussion

Comments (0)

No comments yet. Be the first to share your thoughts!

Indexed by QCR Librarian

This entry was created automatically from publicly available records. QCR links to public sources and only stores repository content where the license permits redistribution.

Claim this entry →