❗ This repository, which implements quantum random access optimization (QRAO), has been contributed upstream to Qiskit Optimization, and is included with Qiskit Optimization version 0.6.0 and higher. Any future development will continue in the Qiskit Optimization repository instead of in this repository.
- About This Project
- Installation
- Documentation
- Important Usage Notes
- How to Give Feedback
- Contribution Guidelines
- Acknowledgements
- About Prototypes
- Deprecation Policy
- References
- License
The Quantum Random Access Optimization (QRAO) module is designed to enable users to leverage a new quantum method for combinatorial optimization problems. This approach incorporates Quantum Random Access Codes (QRACs) as a tool to encode multiple classical binary variables into a single qubit, thereby saving quantum resources and enabling exploration of larger problem instances on a quantum computer. The encodings produce a local quantum Hamiltonian whose ground state can be approximated with standard algorithms such as VQE and QAOA, and then rounded to yield approximation solutions of the original problem.
The figure at the top of this page illustrates a simple example of encoding a degree-3 graph with 10 vertices into just 4 qubits, instead of 10. The graph is colored (with a largest-degree-first greedy algorithm) such that adjacent vertices are of a different color. Then, vertices of a given color are encoded using a (3,1,p) QRAC so that a maximum of 3 vertices are associated with a single qubit. Check out the background documentation to learn more about the coloring algorithm, QRACs, and building associated local quantum Hamiltonians.
This project evolved out of research at IBM Quantum on Approximate Solutions of Combinatorial Problems via Quantum Relaxations.
Problem Statement
Given a quadratic unconstrained binary optimization (QUBO) problem represented by a relaxation to a local quantum Hamiltonian, find an approximate solution by rounding the energy associated with a candidate ground state. This Hamiltonian is constructed using quantum random access codes for memory compression, which allows each qubit to encode more than one binary variable.
QRAO Flowchart
Quantum random access optimization is composed of two main steps as shown in the flowchart below.
- The input problem is encoded into a quantum Hamiltonian using the
QuantumRandomAccessEncodingclass. The maximum number of original classical binary variables encoded into each qubit is specified bymax_vars_per_qubit. - The encoded problem is solved with the
QuantumRandomAccessOptimizer, which uses a minimum eigensolver on the quantum Hamiltonian, rounds the solution, and returns the processed results.
Python 3.7 or higher is required. Full installation instructions are provided in INSTALL.md, but here is a quick summary:
$ git clone https://github.com/qiskit-community/prototype-qrao.git
$ cd prototype-qrao
$ python3 -m venv venv
$ source venv/bin/activate
$ pip install tox notebook -e '.[notebook-dependencies]'
$ jupyter notebookDocumentation is stored in the docs/ directory. It is organized according to the Diátaxis framework:
- Tutorials: longer examples of end-to-end usage
- How-to guides: targeted answers to common questions
- Background material: in-depth exploration of theoretical concepts
- API Reference: documentation of each individual class and function
The current version of this module has some important usage notes and limitations.
As with qiskit-optimization, this module currently only supports input problems that are of type QuadraticProgram and that can be converted to a QUBO. Furthermore, the conversion to a QUBO must be made before encoding the problem into a quantum Hamiltonian with QuantumRandomAccessEncoding (refer to the tutorial to see an example of this).
Check out the documentation for qiskit-optimization to see how to construct a QuadraticProgram and apply converters to it (including a wrapper that converts a QuadraticProgram to a QUBO).
If you would like to use a statevector simulation for Magic Rounding, we advise using the new AerSimulator (source) with the "statevector" method and not the (soon-to-be-deprecated) StatevectorSimulator. The latter suffers from a very poor runtime scaling when used with the Magic Rounding scheme, as it effectively brute-forces all possible solutions.
We encourage your feedback! You can share your thoughts with us by:
- Opening an issue in the repository
- Starting a conversation on GitHub Discussions
- Filling out our survey
For information on how to contribute to this project, please take a look at our contribution guidelines.
This prototype is based on the research described in [1].
The initial codebase was written by Takashi Imamichi, Toshinari Itoko, and Bryce Fuller.
Prototypes is a collaboration between developers and researchers that will give users access to prototypes from cutting-edge research in areas like quantum simulation and machine learning. These software packages are built on top of, and may eventually be integrated into the Qiskit SDK. They are a contribution as part of the Qiskit community.
Check out our blog post for more information!
Prototypes are meant to evolve rapidly and, as such, do not follow Qiskit's deprecation policy. We may occasionally make breaking changes in order to improve the user experience. When possible, we will keep old interfaces and mark them as deprecated, as long as they can co-exist with the new ones. Each substantial improvement, breaking change, or deprecation will be documented in NEWS.md.
[1] Bryce Fuller, Charles Hadfield, Jennifer R. Glick, Takashi Imamichi, Toshinari Itoko, Richard J. Thompson, Yang Jiao, Marna M. Kagele, Adriana W. Blom-Schieber, Rudy Raymond, and Antonio Mezzacapo. Approximate Solutions of Combinatorial Problems via Quantum Relaxations. arXiv:2111.03167.