Optimization
============


Quadratic Unconstrained Binary Optimization (QUBO) problems
-----------------------------------------------------------

| QUBO problems are among the most widely used framework for solving
  classical optimization problems on quantum computers, and they are
  also one of the most interesting optimization challenges. These
  problems are generally NP-hard, requiring the identification of a
  binary vector :math:`\boldsymbol{x} \in \left\{0, 1\right\}^{n}`
  that minimizes the following quadratic cost function:

    .. math::
        \begin{equation}
            f\left(\boldsymbol{x}\right)
            =
            \boldsymbol{x}^T \ \mathcal{Q} \ \boldsymbol{x}
            =
            \sum\limits_{j=1}^n \sum\limits_{j^{\prime}=j}^n
            \mathcal{Q}_{jj^{\prime}} \ x_j \ x_{j}^{\prime}
        \end{equation}

| where :math:`n` is the number of optimization binary variables
  involved in the problem.
| A QUBO problem is fully defined by its QUBO matrix :math:`\mathcal{Q}`,
  a square symmetric matrix. The diagonal elements, :math:`\mathcal{Q}_{jj}`,
  represent the self-interaction (or local bias) of each binary variable
  :math:`x_j`, while the off-diagonal ones describe the pair-interactions
  between different binaries.
  As the QUBO matrix is symmetric, we can limit the computations to its upper
  triangular part, as defined by the equation above.

Tensor-network based QUBO solver
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

| The approach implemented in this submodule is based on the **ground-state search**
  algorithm from :mod:`qtealeaves` and involves the following steps:

  - The defined QUBO problem, represented by the :math:`\mathcal{Q}` matrix,
    is mapped to an equivalent ground-state search problem of the following
    **spin glass Hamiltonian**:

    .. math::

      \begin{equation}
        \mathcal{H}
        =
        \sum\limits_{j=1}^n h_j \sigma_j +
        \sum\limits_{j=1}^n \sum\limits_{j^{\prime}=j+1}^n
        \mathcal{J}_{jj^{\prime}} \sigma_j \sigma_{j^{\prime}}
      \end{equation}

    where the spin glass couplings can be obtained from the QUBO matrix elements.
    This mapping is achieved through the following linear invertible transformation:

    .. math::

      \begin{equation}
        \sigma_j = 2 x_j - 1
      \end{equation}

    which maps each QUBO binary variable :math:`x_j \in \left\{0, 1\right\}`
    into a spin-:math:`1\mathbin{/}2` variable :math:`\sigma_j \in \left\{-1, +1\right\}`.

  - After constructing the Hamiltonian and representing it as a tensor network operator,
    the :mod:`qtealeaves` QUBO solver applies the ground-state search algorithm to find
    the ground state. Once the ground state is found, the mapping is reversed to reconstruct
    the solution bitstring, and the cost function value is calculated for the optimized
    bitstring.

| Several exact solvers are also implemented to benchmark the tensor network solution for
  small instances.
| The available tensor-network representation for the QUBO ground-state wavefunction are
  **Matrix Product States (MPSs)** and **Tree Tensor Networks (TTNs)** from :mod:`qtealeaves.emulator`.
| Various options for the ground-state search are available through the
  :doc:`convergence parameters <convergence_parameters>` object from :mod:`qtealeaves`.

.. automodule:: qtealeaves.optimization.qubo_solver
  :members:


Optimization tooling
--------------------

| This submodule implements tools and support methods for the QUBO solver class.
| The documentation below reports the list of utility functions for the sake of completeness.\

.. autofunction:: qtealeaves.optimization.opt_tooling.spins_to_binaries
  :members:

.. autofunction:: qtealeaves.optimization.opt_tooling.construct_exact_observables
  :members:

.. autofunction:: qtealeaves.optimization.opt_tooling.construct_exact_spinglass_hamiltonian
  :members:

.. autoclass:: qtealeaves.optimization.opt_tooling.get_exact_spectrum
  :members:

.. autofunction:: qtealeaves.optimization.opt_tooling.measure_exact_observables
  :members:

.. autofunction:: qtealeaves.optimization.opt_tooling.generate_perturbation_transverse_fields
  :members:

.. autofunction:: qtealeaves.optimization.opt_tooling.construct_spinglass_driver_state
  :members:

.. autofunction:: qtealeaves.optimization.opt_tooling.construct_tn_state_from_local
  :members:

.. autofunction:: qtealeaves.optimization.opt_tooling.read_tn_state
  :members:
