Implementation of Variational Quantum Factoring algorithm.
This repository contains implementation of the algorithm presented in the article "Variational Quantum Factoring", by Eric R. Anschuetz, Jonathan P. Olson, Alán Aspuru-Guzik, Yudong Cao. It's available on arxiv.
The notation in the code refers directly to the notation in the paper.
I gave a talk about this project, which might be a good introduction to it.
You can find it on YouTube and the slides are in this repository in the presentation.pdf
file.
Since QAOA is an important part of the algorithm, if you're unfamiliar with it you might find my blogpost about QAOA helpful.
This project relies heavily on pyquil
and grove
libraries. Unfortunately, at the time I was developing this project, released versions had bugs that were critical for this project.
Therefore, I've installed them from source:
f22a851d5803e0a6aa73b236c25d28a5fcdb0116
dc6bf6ec63e8c435fe52b1e00f707d5ce4cdb9b3
All the packages that don't get installed automatically during instalation of pyquil and grove are listed in the requirements.txt
file.
List of all the installed packages that has been used for this project can be found in pip_freeze.txt
.
Below you can find a list of points where I'm aware that my implementation differs from the one provided in the paper.
research/2019_05_08_performance_checks
).Research performed using this implementation can be found in the research
directory. I follow the convention presented here.
To run tests please run python -m pytest
from the main directory.
For some reason, the preprocessing is not deterministic. Running the same case sporadically leads to getting different results. It seems to come from the fact, that there is some randomness inside sympy when it comes to ordering operations. Hence, preprocessing sometimes assigns x=y
and sometimes y=x
, which leads to different expressions after substition. From the mathematical point of view it doesn't matter, but from the practical - it does. Since set of implemented rules is incomplete, different substitution may occasionally lead to form which this algorithm cannot simplify. This effect diminished over time of development - i.e. improving rules and fixing bugs.
I do not claim that the preprocessing part is perfect, though from manual inspection it seems to be working in most cases. Below are some known bugs.
preprocessing.py
).