English
Languages
English
Japanese
German
Korean
Portuguese, Brazilian
Shortcuts

Source code for qiskit.optimization.applications.ising.graph_partition

# This code is part of Qiskit.
#
# (C) Copyright IBM 2018, 2021.
#
# This code is licensed under the Apache License, Version 2.0. You may
# obtain a copy of this license in the LICENSE.txt file in the root directory
# of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.
#
# Any modifications or derivative works of this code must retain this
# copyright notice, and modified files need to carry a notice indicating
# that they have been altered from the originals.

"""
Convert graph partitioning instances into Pauli list
Deal with Gset format. See https://web.stanford.edu/~yyye/yyye/Gset/
"""

import logging

import numpy as np

from qiskit.quantum_info import Pauli
from qiskit.aqua.operators import WeightedPauliOperator

logger = logging.getLogger(__name__)


[docs]def get_operator(weight_matrix): r"""Generate Hamiltonian for the graph partitioning Notes: Goals: 1 separate the vertices into two set of the same size 2 make sure the number of edges between the two set is minimized. Hamiltonian: H = H_A + H_B H_A = sum\_{(i,j)\in E}{(1-ZiZj)/2} H_B = (sum_{i}{Zi})^2 = sum_{i}{Zi^2}+sum_{i!=j}{ZiZj} H_A is for achieving goal 2 and H_B is for achieving goal 1. Args: weight_matrix (numpy.ndarray) : adjacency matrix. Returns: WeightedPauliOperator: operator for the Hamiltonian float: a constant shift for the obj function. """ num_nodes = len(weight_matrix) pauli_list = [] shift = 0 for i in range(num_nodes): for j in range(i): if weight_matrix[i, j] != 0: x_p = np.zeros(num_nodes, dtype=bool) z_p = np.zeros(num_nodes, dtype=bool) z_p[i] = True z_p[j] = True pauli_list.append([-0.5, Pauli(z_p, x_p)]) shift += 0.5 for i in range(num_nodes): for j in range(num_nodes): if i != j: x_p = np.zeros(num_nodes, dtype=bool) z_p = np.zeros(num_nodes, dtype=bool) z_p[i] = True z_p[j] = True pauli_list.append([1, Pauli(z_p, x_p)]) else: shift += 1 return WeightedPauliOperator(paulis=pauli_list), shift
[docs]def objective_value(x, w): """Compute the value of a cut. Args: x (numpy.ndarray): binary string as numpy array. w (numpy.ndarray): adjacency matrix. Returns: float: value of the cut. """ # pylint: disable=invalid-name X = np.outer(x, (1 - x)) w_01 = np.where(w != 0, 1, 0) return np.sum(w_01 * X)
[docs]def get_graph_solution(x): """Get graph solution from binary string. Args: x (numpy.ndarray) : binary string as numpy array. Returns: numpy.ndarray: graph solution as binary numpy array. """ return 1 - x

© Copyright 2020, Qiskit Development Team. Last updated on 2021/03/04.

Built with Sphinx using a theme provided by Read the Docs.