Oftimizer.ipynb

{
    "cells": [
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": "# Minimum Eigen Optimizer\n"
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": "Qiskit is an open source SDK for working with quantum computers at the level of pulses, circuits and application modules.\n\nThis notebook shows how to use Qiskit to convert a quadratic program to an Ising Hamiltonian to solve Quadratic Unconstrained Binary Optimization (QUBO) problems. \n\nThe Qiskit Optimization package covers the whole range from high-level modeling of optimization problems, with automatic conversion of problems to different required representations, to a suite of easy-to-use quantum optimization algorithms that are ready to run on classical simulators, as well as on real quantum systems."
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": "## Table of Contents\n\n1. [Introduction](#intro)\n2. [Import the libraries](#import)\n3. [Converting a QUBO to an Operator](#convert-qubo)\n4. [Solving a QUBO with the MinimumEigenOptimizer](#solve-qubo)\n5. [Reduce the QUBO problem size](#reduce-qubo)"
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": "## Introduction"
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": "An interesting class of optimization problems to be addressed by quantum computing are Quadratic Unconstrained Binary Optimization (QUBO) problems.\nFinding the solution to a QUBO is equivalent to finding the ground state of a corresponding Ising Hamiltonian, which is an important problem not only in optimization, but also in quantum chemistry and physics. For this translation, the binary variables taking values in $\\{0, 1\\}$ are replaced by spin variables taking values in $\\{-1, +1\\}$, which allows to replace the resulting spin variables by Pauli Z matrices, and thus, an Ising Hamiltonian. For more details on this mapping we refer to [1].\n\nQiskit provides automatic conversion from a suitable `QuadraticProgram` to an Ising Hamiltonian, which then allows to leverage all the `MinimumEigenSolver` such as\n- `VQE`,\n- `QAOA`, or\n- `NumpyMinimumEigensolver` (classical exact method).\n\nQiskit wraps the translation to an Ising Hamiltonian (in Qiskit Aqua also called `Operator`), the call to an `MinimumEigensolver` as well as the translation of the results back to `OptimizationResult` in the `MinimumEigenOptimizer`.\n\nIn the following we first illustrate the conversion from a `QuadraticProgram` to an `Operator` and then show how to use the `MinimumEigenOptimizer` with different `MinimumEigensolver` to solve a given `QuadraticProgram`.\nThe algorithms in Qiskit automatically try to convert a given problem to the supported problem class if possible, for instance, the `MinimumEigenOptimizer` will automatically translate integer variables to binary variables or add a linear equality constraints as a quadratic penalty term to the objective. It should be mentioned that Aqua will through a `QiskitOptimizationError` if conversion of a quadratic program with integer variable is attempted.\n\nThe circuit depth of `QAOA` potentially has to be increased with the problem size, which might be prohibitive for near-term quantum devices.\nA possible workaround is Recursive QAOA, as introduced in [2].\nQiskit generalizes this concept to the `RecursiveMinimumEigenOptimizer`, which is introduced at the end of this tutorial."
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": "<a id = \"import\"></a>\n## Import the libraries\n\n### Installation\nWe encourage installing Qiskit via the pip tool (a python package manager).\n\n`pip` will handle all dependencies automatically and you will always install the latest (and well-tested) version.\n\nIf you want to work on the very latest work-in-progress versions, learn more about Qiskit, or if you want to contribute to Qiskit Optimization visit `qiskit.org` for more information"
        },
        {
            "cell_type": "code",
            "execution_count": 1,
            "metadata": {
                "scrolled": true
            },
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": "/opt/conda/envs/Python-3.7-main/lib/python3.7/site-packages/secretstorage/dhcrypto.py:16: CryptographyDeprecationWarning: int_from_bytes is deprecated, use int.from_bytes instead\n  from cryptography.utils import int_from_bytes\n/opt/conda/envs/Python-3.7-main/lib/python3.7/site-packages/secretstorage/util.py:25: CryptographyDeprecationWarning: int_from_bytes is deprecated, use int.from_bytes instead\n  from cryptography.utils import int_from_bytes\nNote: you may need to restart the kernel to use updated packages.\n"
                }
            ],
            "source": "pip install -q qiskit"
        },
        {
            "cell_type": "code",
            "execution_count": 2,
            "metadata": {
                "scrolled": true
            },
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": "/opt/conda/envs/Python-3.7-main/lib/python3.7/site-packages/secretstorage/dhcrypto.py:16: CryptographyDeprecationWarning: int_from_bytes is deprecated, use int.from_bytes instead\n  from cryptography.utils import int_from_bytes\n/opt/conda/envs/Python-3.7-main/lib/python3.7/site-packages/secretstorage/util.py:25: CryptographyDeprecationWarning: int_from_bytes is deprecated, use int.from_bytes instead\n  from cryptography.utils import int_from_bytes\nNote: you may need to restart the kernel to use updated packages.\n"
                }
            ],
            "source": "pip install -q qiskit_optimization"
        },
        {
            "cell_type": "code",
            "execution_count": 3,
            "metadata": {},
            "outputs": [],
            "source": "from qiskit import BasicAer\nfrom qiskit.utils import algorithm_globals, QuantumInstance\nfrom qiskit.algorithms import QAOA, NumPyMinimumEigensolver\nfrom qiskit_optimization.algorithms import MinimumEigenOptimizer, RecursiveMinimumEigenOptimizer\nfrom qiskit_optimization import QuadraticProgram"
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": "<a id = \"convert-qubo\"></a>\n## Converting a QUBO to an Operator"
        },
        {
            "cell_type": "code",
            "execution_count": 4,
            "metadata": {
                "scrolled": true,
                "tags": []
            },
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": "\\ This file has been generated by DOcplex\n\\ ENCODING=ISO-8859-1\n\\Problem name: CPLEX\n\nMinimize\n obj: x - 2 y + 3 z + [ 2 x*y - 2 x*z + 4 y*z ]/2\nSubject To\n\nBounds\n 0 <= x <= 1\n 0 <= y <= 1\n 0 <= z <= 1\n\nBinaries\n x y z\nEnd\n\n"
                }
            ],
            "source": "# create a QUBO\nqubo = QuadraticProgram()\nqubo.binary_var('x')\nqubo.binary_var('y')\nqubo.binary_var('z')\nqubo.minimize(linear=[1,-2,3], quadratic={('x', 'y'): 1, ('x', 'z'): -1, ('y', 'z'): 2})\nprint(qubo.export_as_lp_string())"
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": "Next we translate this QUBO into an Ising operator. This results not only in an `Operator` but also in a constant offset to be taking into account to shift the resulting value."
        },
        {
            "cell_type": "code",
            "execution_count": 5,
            "metadata": {
                "tags": []
            },
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": "offset: 1.5\noperator:\n-1.75 * ZII\n+ 0.25 * IZI\n+ 0.5 * ZZI\n- 0.5 * IIZ\n- 0.25 * ZIZ\n+ 0.25 * IZZ\n"
                }
            ],
            "source": "op, offset = qubo.to_ising()\nprint('offset: {}'.format(offset))\nprint('operator:')\nprint(op)"
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": "Sometimes an `QuadraticProgram` might also directly be given in the form of an `Operator`. For such cases, Qiskit also provides a converter from an `Operator` back to a `QuadraticProgram`, which we illustrate in the following."
        },
        {
            "cell_type": "code",
            "execution_count": 6,
            "metadata": {
                "tags": []
            },
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": "\\ This file has been generated by DOcplex\n\\ ENCODING=ISO-8859-1\n\\Problem name: CPLEX\n\nMinimize\n obj: x_0 - 2 x_1 + 3 x_2 + [ 2 x_0*x_1 - 2 x_0*x_2 + 4 x_1*x_2 ]/2\nSubject To\n\nBounds\n 0 <= x_0 <= 1\n 0 <= x_1 <= 1\n 0 <= x_2 <= 1\n\nBinaries\n x_0 x_1 x_2\nEnd\n\n"
                }
            ],
            "source": "qp=QuadraticProgram()\nqp.from_ising(op, offset, linear=True)\nprint(qp.export_as_lp_string())"
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": "This converter allows, for instance, to translate an `Operator` to a `QuadraticProgram` and then solve the problem with other algorithms that are not based on the Ising Hamiltonian representation, such as the `GroverOptimizer`."
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": "<a id = \"qubo\"></a>\n## Solving a QUBO with the MinimumEigenOptimizer"
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": "We start by initializing the `MinimumEigensolver` we want to use."
        },
        {
            "cell_type": "code",
            "execution_count": 7,
            "metadata": {},
            "outputs": [],
            "source": "algorithm_globals.random_seed = 10598\nquantum_instance = QuantumInstance(BasicAer.get_backend('statevector_simulator'),\n                                   seed_simulator=algorithm_globals.random_seed,\n                                   seed_transpiler=algorithm_globals.random_seed)\nqaoa_mes = QAOA(quantum_instance=quantum_instance, initial_point=[0., 0.])\nexact_mes = NumPyMinimumEigensolver()"
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": "Then, we use the `MinimumEigensolver` to create `MinimumEigenOptimizer`."
        },
        {
            "cell_type": "code",
            "execution_count": 8,
            "metadata": {},
            "outputs": [],
            "source": "qaoa = MinimumEigenOptimizer(qaoa_mes)   # using QAOA\nexact = MinimumEigenOptimizer(exact_mes)  # using the exact classical numpy minimum eigen solver"
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": "We first use the `MinimumEigenOptimizer` based on the classical exact `NumPyMinimumEigensolver` to get the optimal benchmark solution for this small example."
        },
        {
            "cell_type": "code",
            "execution_count": 9,
            "metadata": {
                "tags": []
            },
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": "optimal function value: -2.0\noptimal value: [0. 1. 0.]\nstatus: SUCCESS\n"
                }
            ],
            "source": "exact_result = exact.solve(qubo)\nprint(exact_result)"
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": "Next we apply the `MinimumEigenOptimizer` based on `QAOA` to the same problem."
        },
        {
            "cell_type": "code",
            "execution_count": 10,
            "metadata": {
                "tags": []
            },
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": "optimal function value: -2.0\noptimal value: [0. 1. 0.]\nstatus: SUCCESS\n"
                }
            ],
            "source": "qaoa_result = qaoa.solve(qubo)\nprint(qaoa_result)"
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": "<a id = \"reduce-qubo\"></a>\n## Reduce the QUBO problem size"
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": "The `RecursiveMinimumEigenOptimizer` takes a `MinimumEigenOptimizer` as input and applies the recursive optimization scheme to reduce the size of the problem one variable at a time.\nOnce the size of the generated intermediate problem is below a given threshold (`min_num_vars`), the `RecursiveMinimumEigenOptimizer` uses another solver (`min_num_vars_optimizer`), e.g., an exact classical solver such as CPLEX or the `MinimumEigenOptimizer` based on the `NumPyMinimumEigensolver`.\n\nIn the following, we show how to use the `RecursiveMinimumEigenOptimizer` using the two `MinimumEigenOptimizer` introduced before."
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": "First, we construct the `RecursiveMinimumEigenOptimizer` such that it reduces the problem size from 3 variables to 1 variable and then uses the exact solver for the last variable. Then we call `solve` to optimize the considered problem."
        },
        {
            "cell_type": "code",
            "execution_count": 11,
            "metadata": {},
            "outputs": [],
            "source": "rqaoa = RecursiveMinimumEigenOptimizer(qaoa, min_num_vars=1, min_num_vars_optimizer=exact)"
        },
        {
            "cell_type": "code",
            "execution_count": 12,
            "metadata": {
                "tags": []
            },
            "outputs": [
                {
                    "name": "stdout",
                    "output_type": "stream",
                    "text": "optimal function value: -2.0\noptimal value: [0. 1. 0.]\nstatus: SUCCESS\n"
                }
            ],
            "source": "rqaoa_result = rqaoa.solve(qubo)\nprint(rqaoa_result)"
        },
        {
            "cell_type": "code",
            "execution_count": 13,
            "metadata": {},
            "outputs": [
                {
                    "data": {
                        "text/html": "<h3>Version Information</h3><table><tr><th>Qiskit Software</th><th>Version</th></tr><tr><td>Qiskit</td><td>0.25.2</td></tr><tr><td>Terra</td><td>0.17.1</td></tr><tr><td>Aer</td><td>0.8.1</td></tr><tr><td>Ignis</td><td>0.6.0</td></tr><tr><td>Aqua</td><td>0.9.1</td></tr><tr><td>IBM Q Provider</td><td>0.12.3</td></tr><tr><th>System information</th></tr><tr><td>Python</td><td>3.7.10 (default, Feb 26 2021, 18:47:35) \n[GCC 7.3.0]</td></tr><tr><td>OS</td><td>Linux</td></tr><tr><td>CPUs</td><td>56</td></tr><tr><td>Memory (Gb)</td><td>440.8884086608887</td></tr><tr><td colspan='2'>Wed Apr 28 03:55:43 2021 UTC</td></tr></table>",
                        "text/plain": "<IPython.core.display.HTML object>"
                    },
                    "metadata": {},
                    "output_type": "display_data"
                },
                {
                    "data": {
                        "text/html": "<div style='width: 100%; background-color:#d5d9e0;padding-left: 10px; padding-bottom: 10px; padding-right: 10px; padding-top: 5px'><h3>This code is a part of Qiskit</h3><p>&copy; Copyright IBM 2017, 2021.</p><p>This code is licensed under the Apache License, Version 2.0. You may<br>obtain a copy of this license in the LICENSE.txt file in the root directory<br> of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.<p>Any modifications or derivative works of this code must retain this<br>copyright notice, and modified files need to carry a notice indicating<br>that they have been altered from the originals.</p></div>",
                        "text/plain": "<IPython.core.display.HTML object>"
                    },
                    "metadata": {},
                    "output_type": "display_data"
                }
            ],
            "source": "import qiskit.tools.jupyter\n%qiskit_version_table\n%qiskit_copyright"
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": "### References\n[1] [A. Lucas, *Ising formulations of many NP problems,* Front. Phys., 12 (2014).](https://arxiv.org/abs/1302.5843)\n\n[2] [S. Bravyi, A. Kliesch, R. Koenig, E. Tang, *Obstacles to State Preparation and Variational Optimization from Symmetry Protection,* arXiv  preprint arXiv:1910.08980 (2019).](https://arxiv.org/abs/1910.08980)"
        },
        {
            "cell_type": "markdown",
            "metadata": {},
            "source": "# <hr>\nCopyright \u00a9 2021 IBM. This notebook and its source code are released under the terms of the Apache License."
        }
    ],
    "metadata": {
        "kernelspec": {
            "display_name": "Python 3",
            "language": "python",
            "name": "python3"
        },
        "language_info": {
            "codemirror_mode": {
                "name": "ipython",
                "version": 3
            },
            "file_extension": ".py",
            "mimetype": "text/x-python",
            "name": "python",
            "nbconvert_exporter": "python",
            "pygments_lexer": "ipython3",
            "version": "3.8.8"
        },
        "toc": {
            "base_numbering": 1,
            "nav_menu": {},
            "number_sections": true,
            "sideBar": true,
            "skip_h1_title": false,
            "title_cell": "Table of Contents",
            "title_sidebar": "Contents",
            "toc_cell": false,
            "toc_position": {},
            "toc_section_display": true,
            "toc_window_display": false
        }
    },
    "nbformat": 4,
    "nbformat_minor": 2
}