নোট

এই পৃষ্ঠাটি docs/tutorials/02_converters_for_quadratic_programs.ipynb থেকে বানানো হয়েছে।

দ্বিঘাত (কোয়াড্রাটিক) প্রোগ্রামগুলির জন্য পরিবর্তক (কনভার্টার)¶

Optimization problems in Qiskit’s optimization module are represented with the QuadraticProgram class, which is a generic and powerful representation for optimization problems. In general, optimization algorithms are defined for a certain formulation of a quadratic program, and we need to convert our problem to the right type.

For instance, Qiskit provides several optimization algorithms that can handle Quadratic Unconstrained Binary Optimization (QUBO) problems. These are mapped to Ising Hamiltonians, for which Qiskit uses the qiskit.opflow module, and then their ground state is approximated. For this optimization, commonly known algorithms such as VQE or QAOA can be used as underlying routine. See the following tutorial about the Minimum Eigen Optimizer for more detail. Note that also other algorithms exist that work differently, such as the GroverOptimizer.

To map a problem to the correct input format, the optimization module of Qiskit offers a variety of converters. In this tutorial we’re providing an overview on this functionality. Currently, Qiskit contains the following converters.

InequalityToEquality: convert inequality constraints into equality constraints with additional slack variables.
IntegerToBinary: convert integer variables into binary variables and corresponding coefficients.
LinearEqualityToPenalty: convert equality constraints into additional terms of the objective function.
LinearInequalityToPenalty: convert inequality constraints into additional terms of the objective function.
MaximizeToMinimize: convert to the equivalent minimization problem.
MinimizeToMaximize: convert to the equivalent maximization problem.
QuadraticProgramToQubo: a wrapper that includes InequalityToEquality, IntegerToBinary, LinearEqualityToPenalty, LinearInequalityToPenalty, and MaximizeToMinimize for convenience.

InequalityToEquality¶

InequalityToEqualityConverter টি QuadraticProgram থেকে অসমতার সীমাবদ্ধতা অপসারণ করতে অতিরিক্ত স্ল্যাক চল রাশির সাথে অসমতার সীমাবদ্ধতায় রূপান্তর করে। উপরের সীমা (আবদ্ধ) এবং স্ল্যাক ভেরিয়েবলের নিম্নসীমা বাম দিক এবং সীমাবদ্ধতার ডান দিকের পার্থক্য থেকে গণনা করা হবে। স্ল্যাক চল রাশির চিহ্নগুলি \(\leq\) এবং \(\geq\) এর মতো সীমাবদ্ধতার মধ্যে চিহ্নগুলির উপর নির্ভর করে।

নীচে দুটি অসমতার সীমাবদ্ধতার সাথে সর্বাধিক সমস্যার একটি উদাহরণ রয়েছে। চল রাশি \(x\) এবং \(y\) বাইনারি চল রাশি এবং চল রাশি : \(z\) একটি পূর্ণসংখ্যার চল রাশি ।

QuadraticProgram এর সাহায্যে সমস্যার একটি অপ্টিমাইজেশন মডেল নীচে লেখা আছে।

[1]:

from qiskit_optimization import QuadraticProgram

[2]:

qp = QuadraticProgram()
qp.binary_var("x")
qp.binary_var("y")
qp.integer_var(lowerbound=0, upperbound=7, name="z")

qp.maximize(linear={"x": 2, "y": 1, "z": 1})
qp.linear_constraint(linear={"x": 1, "y": 1, "z": 1}, sense="LE", rhs=5.5, name="xyz_leq")
qp.linear_constraint(linear={"x": 1, "y": 1, "z": 1}, sense="GE", rhs=2.5, name="xyz_geq")
print(qp.prettyprint())

Problem name:

Maximize
  2*x + y + z

Subject to
  Linear constraints (2)
    x + y + z <= 5.5  'xyz_leq'
    x + y + z >= 2.5  'xyz_geq'

  Integer variables (1)
    0 <= z <= 7

  Binary variables (2)
    x y

রূপান্তর করতে InequalityToEquality` এর ``convert পদ্ধতিটি কল করুন।

[3]:

from qiskit_optimization.converters import InequalityToEquality

[4]:

ineq2eq = InequalityToEquality()
qp_eq = ineq2eq.convert(qp)
print(qp_eq.prettyprint())

Problem name:

Maximize
  2*x + y + z

Subject to
  Linear constraints (2)
    x + [email protected]_slack + y + z == 5  'xyz_leq'
    x - [email protected]_slack + y + z == 3  'xyz_geq'

  Integer variables (3)
    0 <= z <= 7
    0 <= [email protected]_slack <= 5
    0 <= [email protected]_slack <= 6

  Binary variables (2)
    x y

After converting, the formulation of the problem looks like the above output. As we can see, the inequality constraints are replaced with equality constraints with additional integer slack variables, \(xyz\_leg\text{@}int\_slack\) and \(xyz\_geq\text{@}int\_slack\).

Let us explain how the conversion works. For example, the lower bound of the left side of the first constraint is \(0\) which is the case of \(x=0\), \(y=0\), and \(z=0\). Thus, the upper bound of the additional integer variable must be \(5\) to be able to satisfy even the case of \(x=0\), \(y=0\), and \(z=0\). Note that we cut off the part after the decimal point in the converted formulation since the left side of the first constraint in the original formulation can be only integer values. For the second constraint, basically we apply the same approach. However, the symbol in the second constraint is \(\geq\), so we add minus before \(xyz\_geq\text{@}int\_slack\) to be able to satisfy even the case of \(x=1, y=1\), and \(z=7\).

IntegerToBinary¶

IntegerToBinary পূর্ণসংখ্যার চল রাশিগুলিকে বাইনারি চল রাশি এবং সহগগুলিকে QuadraticProgram থেকে পূর্ণসংখ্য ভেরিয়েবলগুলি সরাতে রূপান্তর করে। রূপান্তর করার জন্য, প্রস্তাবিত সীমাবদ্ধ-গুণফলের এনকোডিং arxiv:1706.01945 (Eq. (5)) ব্যবহৃত হয়। এনকোডিং পদ্ধতির আরও বিশদের জন্য দয়া করে গবেষণাটি দেখুন।

We use the output of InequalityToEquality as a starting point. Variables \(x\) and \(y\) are binary variables, while the variable \(z\) and the slack variables \(xyz\_leq\text{@}int\_slack\) and \(xyz\_geq\text{@}int\_slack\) are integer variables. We print the problem again for reference.

[5]:

print(qp_eq.prettyprint())

Problem name:

Maximize
  2*x + y + z

Subject to
  Linear constraints (2)
    x + [email protected]_slack + y + z == 5  'xyz_leq'
    x - [email protected]_slack + y + z == 3  'xyz_geq'

  Integer variables (3)
    0 <= z <= 7
    0 <= [email protected]_slack <= 5
    0 <= [email protected]_slack <= 6

  Binary variables (2)
    x y

রূপান্তর করতে IntegerToBinary` এর ``convert পদ্ধতিটি কল করুন।.

[6]:

from qiskit_optimization.converters import IntegerToBinary

[7]:

int2bin = IntegerToBinary()
qp_eq_bin = int2bin.convert(qp_eq)
print(qp_eq_bin.prettyprint())

Problem name:

Maximize
  2*x + y + [email protected] + 2*[email protected] + 4*[email protected]

Subject to
  Linear constraints (2)
    x + [email protected][email protected] + 2*[email protected][email protected] + 2*[email protected][email protected] + y
    + [email protected] + 2*[email protected] + 4*[email protected] == 5  'xyz_leq'
    x - [email protected][email protected] - 2*[email protected][email protected] - 3*[email protected][email protected] + y
    + [email protected] + 2*[email protected] + 4*[email protected] == 3  'xyz_geq'

  Binary variables (11)
    x y [email protected] [email protected] [email protected] [email protected][email protected] [email protected][email protected] [email protected][email protected]
    [email protected][email protected] [email protected][email protected] [email protected][email protected]

After converting, the integer variable \(z\) is replaced with three binary variables \(z\text{@}0\), \(z\text{@}1\) and \(z\text{@}2\) with coefficients 1, 2 and 4, respectively as the above. The slack variables \(xyz\_leq\text{@}int\_slack\) and \(xyz\_geq\text{@}int\_slack\) that were introduced by InequalityToEquality are also both replaced with three binary variables with coefficients 1, 2, 2, and 1, 2, 3, respectively.

টীকা: মূলত সহগের অর্থ হল সহগের সাথে এই বাইনারি চল রাশি গুলির যোগফল \(\{1, 2, 4\}\), \(\{1, 2, 2\}\),এবং \(\{1, 2, 3\}\) এর একটি সাবসেটের যোগফল হতে পারে এবং সেই গ্রহণযোগ্য মানগুলি উপস্থাপন করে \(\{0, \ldots, 7\}\), \(\{0, \ldots, 5\}\), এবং \(\{0, \ldots, 6\}\), যা নীচের বাউন্ড এবং মূল সংখ্যার ভেরিয়েবলের উপরের সীমানাকে সঠিকভাবে মেনে চলে ।

IntegerToBinary একটি interpret পদ্ধতিও সরবরাহ করে যা প্রদত্ত বাইনারি ফলাফলটিকে মূল পূর্ণসংখ্যার উপস্থাপনায় ফিরে অনুবাদ করার কার্যকারিতা।

LinearEqualityToPenalty¶

LinearEqualityToPenalty converts linear equality constraints into additional quadratic penalty terms of the objective function to map QuadraticProgram to an unconstrained form. An input to the converter has to be a QuadraticProgram with only linear equality constraints. Those equality constraints, e.g. \(\sum_i a_i x_i = b\) where \(a_i\) and \(b\) are numbers and \(x_i\) is a variable, will be added to the objective function in the form of \(M(b - \sum_i a_i x_i)^2\) where \(M\) is a large number as penalty factor. By default \(M= 1e5\). The sign of the term depends on whether the problem type is a maximization or minimization.

We use the output of IntegerToBinary as a starting point, where all variables are binary variables and all inequality constraints have been mapped to equality constraints. We print the problem again for reference.

[8]:

print(qp_eq_bin.prettyprint())

Problem name:

Maximize
  2*x + y + [email protected] + 2*[email protected] + 4*[email protected]

Subject to
  Linear constraints (2)
    x + [email protected][email protected] + 2*[email protected][email protected] + 2*[email protected][email protected] + y
    + [email protected] + 2*[email protected] + 4*[email protected] == 5  'xyz_leq'
    x - [email protected][email protected] - 2*[email protected][email protected] - 3*[email protected][email protected] + y
    + [email protected] + 2*[email protected] + 4*[email protected] == 3  'xyz_geq'

  Binary variables (11)
    x y [email protected] [email protected] [email protected] [email protected][email protected] [email protected][email protected] [email protected][email protected]
    [email protected][email protected] [email protected][email protected] [email protected][email protected]

রূপান্তর করতে LinearEqualityToPenalty` এর ``convert পদ্ধতিটি কল করুন।.

[9]:

from qiskit_optimization.converters import LinearEqualityToPenalty

[10]:

lineq2penalty = LinearEqualityToPenalty()
qubo = lineq2penalty.convert(qp_eq_bin)
print(qubo.prettyprint())

Problem name:

Maximize
  -22*x^2 + 22*x*[email protected][email protected] + 44*x*[email protected][email protected]
  + 66*x*[email protected][email protected] - 22*x*[email protected][email protected]
  - 44*x*[email protected][email protected] - 44*x*[email protected][email protected] - 44*x*y - 44*x*[email protected]
  - 88*x*[email protected] - 176*x*[email protected] - 11*[email protected][email protected]^2
  - 44*[email protected][email protected]*[email protected][email protected]
  - 66*[email protected][email protected]*[email protected][email protected] - 44*[email protected][email protected]^2
  - 132*[email protected][email protected]*[email protected][email protected] - 99*[email protected][email protected]^2
  - 11*[email protected][email protected]^2 - 44*[email protected][email protected]*[email protected][email protected]
  - 44*[email protected][email protected]*[email protected][email protected] - 44*[email protected][email protected]^2
  - 88*[email protected][email protected]*[email protected][email protected] - 44*[email protected][email protected]^2
  + 22*y*[email protected][email protected] + 44*y*[email protected][email protected]
  + 66*y*[email protected][email protected] - 22*y*[email protected][email protected]
  - 44*y*[email protected][email protected] - 44*y*[email protected][email protected] - 22*y^2 - 44*y*[email protected]
  - 88*y*[email protected] - 176*y*[email protected] + 22*[email protected]*[email protected][email protected]
  + 44*[email protected]*[email protected][email protected] + 66*[email protected]*[email protected][email protected]
  - 22*[email protected]*[email protected][email protected] - 44*[email protected]*[email protected][email protected]
  - 44*[email protected]*[email protected][email protected] - 22*[email protected]^2 - 88*[email protected]*[email protected] - 176*[email protected]*[email protected]
  + 44*[email protected]*[email protected][email protected] + 88*[email protected]*[email protected][email protected]
  + 132*[email protected]*[email protected][email protected] - 44*[email protected]*[email protected][email protected]
  - 88*[email protected]*[email protected][email protected] - 88*[email protected]*[email protected][email protected] - 88*[email protected]^2
  - 352*[email protected]*[email protected] + 88*[email protected]*[email protected][email protected] + 176*[email protected]*[email protected][email protected]
  + 264*[email protected]*[email protected][email protected] - 88*[email protected]*[email protected][email protected]
  - 176*[email protected]*[email protected][email protected] - 176*[email protected]*[email protected][email protected] - 352*[email protected]^2
  + 178*x - 66*[email protected][email protected] - 132*[email protected][email protected]
  - 198*[email protected][email protected] + 110*[email protected][email protected] + 220*[email protected][email protected]
  + 220*[email protected][email protected] + 177*y + 177*[email protected] + 354*[email protected] + 708*[email protected] - 374

Subject to
  No constraints

  Binary variables (11)
    x y [email protected] [email protected] [email protected] [email protected][email protected] [email protected][email protected] [email protected][email protected]
    [email protected][email protected] [email protected][email protected] [email protected][email protected]

রূপান্তর করার পরে, সাম্যতার সীমাবদ্ধতাগুলি ডিফল্ট জরিমানার ফ্যাক্টর \(M=1e5\) এর সাথে অতিরিক্ত পদ হিসাবে নৈর্ব্যক্তিক অন্বয় (অব্জেক্টিভ ফাংশন) যুক্ত হয়। ফলস্বরূপ সমস্যাটি এখন একটি কিউইউবিও (QUBO) এবং অনেকগুলি কোয়ান্টাম অপ্টিমাইজেশন অ্যালগরিদম যেমন ভি কিউ ই (VQE), কিউএওএ (QAOA) ইত্যাদির সাথে সুসংগত।

এটি আগের মতো একই ফলাফল দেয়।.

[11]:

import qiskit.tools.jupyter

%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit Software	Version
`qiskit-terra`	0.21.0.dev0+dbd3961
`qiskit-aer`	0.10.4
`qiskit-ibmq-provider`	0.19.1
`qiskit-optimization`	0.4.0
System information
Python version	3.10.4
Python compiler	GCC 11.2.0
Python build	main, Apr 2 2022 09:04:19
OS	Linux
CPUs	4
Memory (Gb)	14.577545166015625
Wed May 18 16:03:30 2022 JST

This code is a part of Qiskit

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.

[ ]: