Exploring QUBOs, QAOA, and circuit knitting

Travis-S-IBM commented 1 year ago

Description

The Quantum Approximate Optimization Algorithm (QAOA) is one of the workhorses of near-term algorithms for tackling optimization problems with quantum computers. One of the core aspects of the QAOA is particular circuit structure it uses: repeated layers of unitary operations corresponding to a cost Hamiltonian (derived from the particular optimization problem being solved) and a mixing Hamiltonian.

Scaling out the QAOA to practical problem sizes (e.g., hundreds to thousands of variables) has been hindered by the fact that, typically, each variable in the problem is mapped to 1 qubit. Thus, naively, addressing such problems would require very large (high-qubit-count) quantum systems.

However, recent research has shown how high-width circuits can be decomposed (cut) into circuits with lower widths, via techniques that have come to be known collectively as circuit knitting.

In this project, we would explore the QAOA at scale, through the use of circuit knitting, to understand the factors which would affect the scaling of QAOA to extremely large problem instances. (Here, I envision these instances as being random instances of quadratic unconstrained binary optimization (QUBO) problems).

More specifically, I'd like to understand the following:

How does the overhead of circuit knitting scale with QUBO problem size? Is there a well-defined formula for modeling this scaling?
Are there families of QUBOs for which the overhead behaves "nicely"?
What is the impact of using alternative variable encodings (ex: quantum random access codes )?

I envision using the Qiskit Optimization module to study these questions, along with the circuit knitting toolbox.

The only prior work I've seen on QAOA + circuit knitting is this: https://scirate.com/arxiv/2302.01792 Note this work studies the impact of circuit knitting on the outcomes of running QAOA; this project would stop short of that, and not actually run the QAOA.

Deliverables

For the project:

Code implementing numerical experiments
Numerical results (ex: "Circuit Knitting Overhead vs. QUBO problem size")
Any theoretical/modeling work
Depending on how well-progressed the work is, a white paper

For you:

Growth in your research skills
Growth in use of Qiskit

For me:

A better understanding of how circuit knitting can impact one particular quantum optimization algorithm, and one particular kind of optimization problem

Mentors details

Mentor 1
- Name: Travis L Scholten (http://travisscholten.com/)
- GitHub ID: https://github.com/Travis-S-IBM
- What they do: Quantum Applications Architect

Number of mentees

2

Type of mentees

Mentee 1
- Required:
- Proficiency in research in quantum computing
- Proficiency with Qiskit
- A desire to learn and grow
- An ability to take an idea and run with it
- Nice to have:
- Experience with circuit knitting
- Experience writing white papers

For mentee 2, the same profile would apply.

MarcoBarroca commented 1 year ago

Also interested in this. I haven't used the knitting toolbox for circuit cutting but I have played around with Entanglement Forging.

gideonuchehara commented 1 year ago

Hello @Travis-S-IBM, I am a PhD student working on quantum circuit cutting. In my work titled "Rotation-inspired circuit optimization" https://arxiv.org/abs/2211.07358#:~:text=We%20propose%20Rotation%2DInspired%20Circuit,to%20solve%20an%20optimization%20problem., I explored an alternative circuit cutting method which reduces the post-processing overhead of circuit cutting, at the cost of having to solve an optimization problem. I am currently working on applications of this method to VQE with plans to extend it to QAOA as part of my PhD work. This project naturally aligns with my area of interest and I would like to be one of your mentees.

hsanthan commented 1 year ago

Hello @Travis-S-IBM, I'm interested in working on this project. I haven't used the circuit knitting toolbox, but I do have a ton of interest in learning in-depth entanglement forging. I was a mentee in QAMP 22 under Daniel Sierra-Sosa in which we analyzed x-ray images using hybrid QML methods. I wish to be one of your mentees and learn more. Thanks!

hsanthan commented 1 year ago

QAMP3_Project11_CP1.pptx