<commit_before>Quantum Approximate Optimization Algorithm (QAOA)
=================================================

Overview
--------

pyQAOA is a Python module for running the Quantum Approximate Optimization
Algorithm on an instance of a quantum abstract machine.

The pyQAOA package contains separate modules for each type of problem
instance: MAX-CUT, graph partitioning, etc.
For each problem instance the user specifies the driver Hamiltonian,
cost Hamiltonian, and the approximation order of the algorithm.

``qaoa.py`` contains the base QAOA class and routines for finding optimal
rotation angles via Grove's
`variational-quantum-eigensolver method <http://grove-docs.readthedocs.io/en/latest/vqe.html>`_.

Cost Functions
--------------

* ``maxcut_qaoa.py`` implements the cost function for MAX-CUT problems.

* ``numpartition_qaoa.py`` implements the cost function for bipartitioning a list of numbers.


Quickstart Examples
-------------------

To test your installation and get going we can run QAOA to solve MAX-CUT on a square ring with
4 nodes at the corners. In your python interpreter import the packages and connect to your QVM:

.. code-block:: python

    import numpy as np
    from grove.pyqaoa.maxcut_qaoa import maxcut_qaoa
    import pyquil.forest as qvm
    qvm_connection = qvm.Connection()

Next define the graph on which to run MAX-CUT

.. code-block:: python

    square_ring = [(0,1),(1,2),(2,3),(3,0)]

The optional configuration parameter for the algorithm is given by the number of
steps to use (which loosely corresponds to the accuracy of the optimization computation).
We instantiate the algorithm and run the optimization routine on our QVM:

.. code-block:: python

    steps = 2
    inst = maxcut_qaoa(graph=square_ring, steps=steps)
    betas, gammas = inst.get_angles()

to see the final \\(\\mid \\beta, \\gamma \\rangle \\) state we can rebuild the
quil program that gives us \\(\\mid \\beta, \\gamma \\rangle \\)  and evaluate the wave function using the QVM

.. code-block:: python

    t = np.hstack((betas, gammas))
    param_prog = inst.get_parameterized_program()
    prog = param_prog(t)
    wf = qvm_connection.wavefunction(prog)

``wf`` is now a numpy array of complex-valued amplitudes for each computational
basis state.  To visualize the distribution iterate over the states and
calculate the probability.

.. code-block:: python

    for state_index in range(2**inst.n_qubits):
        print inst.states[state_index], np.conj(wf[state_index])*wf[state_index]

You should then see that the algorithm converges on the expected solutions of 0101 and 1010! ::

    0000 (4.38395094039e-26+0j)
    0001 (5.26193287055e-15+0j)
    0010 (5.2619328789e-15+0j)
    0011 (1.52416449345e-13+0j)
    0100 (5.26193285935e-15+0j)
    0101 (0.5+0j)
    0110 (1.52416449362e-13+0j)
    0111 (5.26193286607e-15+0j)
    1000 (5.26193286607e-15+0j)
    1001 (1.52416449362e-13+0j)
    1010 (0.5+0j)<commit_msg>fixup qaoa docs<commit_after>Quantum Approximate Optimization Algorithm (QAOA)
=================================================

Overview
--------

pyQAOA is a Python module for running the Quantum Approximate Optimization
Algorithm on an instance of a quantum abstract machine.

The pyQAOA package contains separate modules for each type of problem
instance: MAX-CUT, graph partitioning, etc.
For each problem instance the user specifies the driver Hamiltonian,
cost Hamiltonian, and the approximation order of the algorithm.

``qaoa.py`` contains the base QAOA class and routines for finding optimal
rotation angles via Grove's
`variational-quantum-eigensolver method <http://grove-docs.readthedocs.io/en/latest/vqe.html>`_.

Cost Functions
--------------

* ``maxcut_qaoa.py`` implements the cost function for MAX-CUT problems.

* ``numpartition_qaoa.py`` implements the cost function for bipartitioning a list of numbers.


Quickstart Examples
-------------------

To test your installation and get going we can run QAOA to solve MAX-CUT on a square ring with
4 nodes at the corners. In your python interpreter import the packages and connect to your QVM:

.. code-block:: python

    import numpy as np
    from grove.pyqaoa.maxcut_qaoa import maxcut_qaoa
    import pyquil.forest as qvm
    qvm_connection = qvm.Connection()

Next define the graph on which to run MAX-CUT

.. code-block:: python

    square_ring = [(0,1),(1,2),(2,3),(3,0)]

The optional configuration parameter for the algorithm is given by the number of
steps to use (which loosely corresponds to the accuracy of the optimization computation).
We instantiate the algorithm and run the optimization routine on our QVM:

.. code-block:: python

    steps = 2
    inst = maxcut_qaoa(graph=square_ring, steps=steps)
    betas, gammas = inst.get_angles()

to see the final \\(\\mid \\beta, \\gamma \\rangle \\) state we can rebuild the
quil program that gives us \\(\\mid \\beta, \\gamma \\rangle \\)  and evaluate the wave function using the QVM

.. code-block:: python

    t = np.hstack((betas, gammas))
    param_prog = inst.get_parameterized_program()
    prog = param_prog(t)
    wf, _ = qvm_connection.wavefunction(prog)

``wf`` is now a numpy array of complex-valued amplitudes for each computational
basis state.  To visualize the distribution iterate over the states and
calculate the probability.

.. code-block:: python

    for state_index in range(2**inst.n_qubits):
        print inst.states[state_index], np.conj(wf[state_index])*wf[state_index]

You should then see that the algorithm converges on the expected solutions of 0101 and 1010! ::

    0000 (4.38395094039e-26+0j)
    0001 (5.26193287055e-15+0j)
    0010 (5.2619328789e-15+0j)
    0011 (1.52416449345e-13+0j)
    0100 (5.26193285935e-15+0j)
    0101 (0.5+0j)
    0110 (1.52416449362e-13+0j)
    0111 (5.26193286607e-15+0j)
    1000 (5.26193286607e-15+0j)
    1001 (1.52416449362e-13+0j)
    1010 (0.5+0j)
{'fraction_non_alphanumeric': 0.11574309439078122, 'fraction_numerical': 0.06880189798339265, 'mean_word_length': 3.7216, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '599013', 'n_tokens_mistral': 2123, 'n_tokens_neox': 1796, 'n_words': 659}