Bengali
ভাষাসমূহ
English
Bengali
Japanese
Shortcuts

নোট

এই পৃষ্ঠাটি docs/tutorials/06_examples_max_cut_and_tsp.ipynb থেকে বানানো হয়েছে।

সর্বোচ্চ লাভ এবং ট্রাভেলিং সেলসম্যান সমস্যা

ভূমিকা

পরিমাণ ক্ষেত্রের অনেকগুলি সমস্যা যেমন ব্যবস্থাপনাবিদ্যা এবং ইঞ্জিনিয়ারিং হল অনুকূলায়ন (অপ্টিমাইজেশন) সমস্যাসমূহ। অনুকূলায়ন (অপ্টিমাইজেশন) সমস্যাগুলি জটিল সিদ্ধান্ত গ্রহণ এবং কৌশলগুলির সংজ্ঞার মূল ভিত্তিতে থাকে।

অপ্টিমাইজেশন (বা সমাবেশীয় অনুকূলায়ন (অপ্টিমাইজেশন)) এর অর্থ সীমাবদ্ধ বা সম্ভাব্য সমাধানের অসীম সেটগুলিতে একটি অনুকূল সমাধান অনুসন্ধান করা। অনুকূলতাটি কিছু মানদণ্ডের ফাংশনের প্রতি সম্মানের সাথে সংজ্ঞায়িত করা হয়, যা ছোট বা সর্বাধিক করতে হবে। একে সাধারণত কস্ট ফাংশন বা নৈর্ব্যক্তিক অন্বয় (অব্জেক্টিভ ফাংশন) বলা হয়।

সাধারণ অনুকূলায়ন (অপ্টিমাইজেশন) সমস্যাসমূহ

হ্রাসকরণ: ব্যয়, দূরত্ব, একটি ট্র্যাভারসাল দৈর্ঘ্য, ওজন, প্রক্রিয়াকরণের সময়, উপাদান, শক্তি খরচ, বস্তুর (অবজেক্ট) সংখ্যা

সর্বাধিকীকরণ: লাভ, মান, আউটপুট, রিটার্ন, ফলন, উপযোগ, দক্ষতা, ক্ষমতা, বস্তুর (অবজেক্ট) সংখ্যা

আমরা এখানে অনেক ক্ষেত্রে ব্যবহারিক আগ্রহের সর্বোচ্চ লাভ সমস্যাগুলি বিবেচনা করি এবং দেখি কীভাবে সেগুলি ম্যানুয়ালি কোয়ান্টাম কম্পিউটারগুলিতে ম্যাপ করা যায় এবং কিস্কিটের অপ্টিমাইজেশন মডিউলটি এটি সমর্থন করে।

Weighted Max-Cut

ক্লাস্টারিং, নেটওয়ার্ক সায়েন্স এবং স্ট্যাটিস্টিকাল ফিজিক্সে অ্যাপ্লিকেশন সহ ম্যাক্স-কাট একটি এনপি-কমপ্লিট সমস্যা। প্রদত্ত ম্যাক্স-কাট দৃষ্টান্তগুলিতে কীভাবে ব্যবহারিক অ্যাপ্লিকেশনগুলি ম্যাপ করা হয় তা বুঝতে, অনেক মানুষ যুক্ত এমন একটি ব্যবস্থা বিবেচনা করুন যারা একে অপরকে যোগাযোগ করতে এবং প্রভাবিত করতে পারে। কোনও গ্রাফের শীর্ষে (vertex) এবং তাদের ইন্টারঅ্যাকশনগুলি গ্রাফের শীর্ষে (vertex) বা প্রান্তগুলির (edge) মধ্যে জোড়াযুক্ত সংযোগ হিসাবে দেখা যায়। এই উপস্থাপনাটিকে মনে রেখে, সাধারণত বিপণনের সমস্যার মডেল করা সহজ। উদাহরণস্বরূপ, ধরুন, যে ব্যক্তিরা একে অপরের ক্রয়ের সিদ্ধান্তকে প্রভাবিত করবে এবং তারা একে অপরকে কতটা শক্তিশালী করবে সে সম্পর্কে জ্ঞান দেওয়া হয়। প্রতিটি প্রান্তে নির্ধারিত ওজন দ্বারা এই প্রভাব টি মডেল করা যেতে পারে। তারপরে এমন বিপণন কৌশলটির ফলাফল সম্পর্কে ভবিষ্যদ্বাণী করা সম্ভব হয় যেখানে কিছু ব্যক্তিকে বিনামূল্যে পণ্য সরবরাহ করা হয়, এবং তারপরে জিজ্ঞাসা করা হয় যে আয়গুলি সর্বাধিকতর করার জন্য নিখরচায় পণ্যগুলি পাওয়া উচিত এমন ব্যক্তিদের সর্বোত্তম সাবসেট টি কোনটি।

এই সমস্যার আনুষ্ঠানিক সংজ্ঞাটি হল:

একটি \(n\) নোড পুনর্নির্দেশিত গ্রাফ G = (V, E) বিবেচনা করুন যেখানে |V| = n জন্য প্রান্তের ওজন \(w_{ij}>0\), \(w_{ij}=w_{ji}\) , সহ \((i, j)\in E\)। একটি কাট দুটি সাব সেট এর মূল সেট V এর পার্টিশন হিসাবে সংজ্ঞায়িত করা হয়। অনুকূলিতকরণের জন্য কাট টি ক্রস করে ব্যয় ফাংশনটি এই ক্ষেত্রে দুটি পৃথক উপধারায় সংযোগকারী পয়েন্টের ওজনগুলির যোগফল। প্রতিটি নোডে \(x_i=0\) বা \(x_i=1\) নির্ধারণের মাধ্যমে \(i\), একজন সামগ্রিক লাভের ফাংশন সর্বাধিক করার চেষ্টা করে (এখানে এবং নিচের সংক্ষেপে সূচকগুলির উপরে 0,1,… n -1 চালানো হয়)

\[\tilde{C}(\textbf{x}) = \sum_{i,j} w_{ij} x_i (1-x_j) ।\]

আমাদের সাধারণ বিপণন মডেলটিতে, \(w_{ij}\) এই সম্ভাব্যতা উপস্থাপন করে যে \(j\) ব্যক্তি \(i\) ফ্রি পাওয়ার পরে কোনও পণ্য কিনবে। নোট করুন যে ওজন \(w_{ij}\) নীতিগতভাবে \(1\) (বা এমনকি নেতিবাচক) এর চেয়েও বেশি হতে পারে, সেই ক্ষেত্রে যেখানে পৃথক \(j\) একাধিক পণ্য কেনে। মোট কেনার সম্ভাব্যতা সর্বাধিকীকরণ মোট ভবিষ্যতের আয়কে সর্বাধিক করার সাথে মিলে যায়। এই মডেলটির একটি বর্ধনের সাথে নোডগুলি ওজন বহন করে, যা আমাদের বিপণনের মডেল হিসাবে বিবেচনা করা যেতে পারে, সম্ভাবনা হিসাবে পণ্যটির একটি নিখরচায় নমুনা দেওয়া কোনও ব্যক্তি ভবিষ্যতে আবার কিনবে। আমাদের মডেলটিতে এই অতিরিক্ত তথ্য সহ, সর্বাধিকীকরণের অব্জেক্টিভ ফাংশনটি হয়ে ওঠে।

\[C(\textbf{x}) = \sum_{i,j} w_{ij} x_i (1-x_j)+\sum_i w_i x_i ।\]

কোয়ান্টাম কম্পিউটারে এই সমস্যার সমাধানের জন্য, প্রথমে একটি আইসিং হ্যামিলটনিয়ানকে এটির ম্যাপিং করা উচিত। এটি অ্যাসাইনমেন্ট \(x_i\rightarrow (1-Z_i)/2\) সহ করা যেতে পারে, যেখানে \(Z_i\) i হ’ল পাওলি Z অপারেটর যার আইগেনভ্যালু \(\pm 1\)। এটি করে আমরা এটি খুঁজে পাই

\[C(\textbf{Z}) = \sum_{i,j} \frac{w_{ij}}{4} (1-Z_i)(1+Z_j) + \sum_i \frac{w_i}{2} (1-Z_i) = -\frac{1}{2}\left( \sum_{i<j} w_{ij} Z_i Z_j +\sum_i w_i Z_i\right)+\mathrm{const},\]

যেখানে :math:`mathrm{const} = sum_{i<j}w_{ij}/2+sum_i w_i/2। অন্য কথায়, ওয়েটেড সর্বোচ্চ লাভ সমস্যাটি আইসিং হ্যামিলটনিয়ানকে হ্রাস করার সমতুল্য

\[H = \sum_i w_i Z_i + \sum_{i<j} w_{ij} Z_iZ_j.\]

Qiskit অপ্টিমাইজেশন মডিউলটি প্রথম লাভ ফাংশন \(\tilde{C}\)-র জন্য আইসিং হ্যামিলটোনিয়ান তৈরি করতে পারে। এই পরিমাণে, ফাংশন \(\tilde{C}\) একটি QuadraticProgram হিসাবে মডেল করা হবে, যা to_ising () পদ্ধতি সরবরাহ করে।

অপ্টিমাইজেশন সমস্যার জন্য আনুমানিক ইউনিভার্সাল কোয়ান্টাম কম্পিউটিং

সমাবেশীয় অনুকূলায়ন (অপ্টিমাইজেশন) সমস্যাসমূহর সমাধানের জন্য কোয়ান্টাম কম্পিউটার ব্যবহার সম্পর্কে সাম্প্রতিক সময়ে যথেষ্ট পরিমাণে আগ্রহ তৈরি হয়েছে। বলা বাহুল্য যে, সমাবেশ সমস্যাগুলির প্রথাগত (ক্লাসিক্যাল) প্রকৃতির পরিপ্রেক্ষিতে, সর্বোত্তম প্রথাগত (ক্লাসিক্যাল) অ্যালগরিদমের তুলনায় কোয়ান্টাম কম্পিউটার ব্যবহারে সূচকীয় গতির গ্যারান্টি নেই। যাইহোক, লক্ষ্য (টার্গেট) সমস্যার প্রকৃতি এবং গুরুত্বের কারণে, এটি কোয়ান্টাম কম্পিউটারে হিউরিস্টিক পন্থাগুলি তদন্তের জন্য মূল্যবান যা প্রকৃতপক্ষে কিছু সমস্যাগুলির উদাহরণগুলিকে গতিতে পারে। এখানে আমরা এমন একটি পদ্ধতির প্রদর্শন করি যা ফারহি, গোল্ডস্টোন এবং গুটম্যান (২০১৪) দ্বারা কোয়ান্টাম আনুমানিক অপ্টিমাইজেশন অ্যালগরিদম (কিউ.এ.ও.এ.) এর উপর ভিত্তি করে। আমরা আলগরিদমকে আনুমানিক কোয়ান্টাম কম্পিউটিং এর প্রাসঙ্গিক আকারে এর ফ্রেমযুক্ত প্রকৃতির উপর ভিত্তি করে ফ্রেম করি।

অ্যালগরিদম টি নিম্নলিখিত উপায়ে কাজ করে :

  1. টার্গেট আইসিং সমস্যা: \(w_i\) এবং \(w_{ij}\) চয়ন করুন। নীতিগতভাবে, Z-র উচ্চতর ক্ষমতাগুলিও অনুমোদিত।

  2. কোয়ান্টাম সার্কিট :math:`m -র গভীরতা চয়ন করুন। টীকা: গভীরতাটি অভিযোজিতভাবে সংশোধন করা যেতে পারে।.

  3. কনট্রোল \(\theta\) এর একটি সেট চয়ন করুন এবং সি-ফেজ ( C-Phase ) গেটস এবং একক কিউবিট ওয়াই (Y) রোটেশনগুলির তৈরি কোয়ান্টাম সার্কিট ব্যবহার করে তৈরি করে ট্রায়াল ফাংশন \(|\psi(\boldsymbol\theta)\rangle\) করুন, যা \(\boldsymbol\theta\) এর উপাদানগুলি দ্বারা প্যারামিটারাইজড |

  4. মূল্যায়ন

    \[C(\boldsymbol\theta) = \langle\psi(\boldsymbol\theta)~|H|~\psi(\boldsymbol\theta)\rangle = \sum_i w_i \langle\psi(\boldsymbol\theta)~|Z_i|~\psi(\boldsymbol\theta)\rangle+ \sum_{i<j} w_{ij} \langle\psi(\boldsymbol\theta)~|Z_iZ_j|~\psi(\boldsymbol\theta)\rangle\]

    জেড-বেসিস সার্কিটের ফলাফল নমুনা করে এবং পৃথক আইসিং পদগুলির প্রত্যাশা মানগুলি একসাথে যুক্ত করে। সাধারণভাবে, নির্বাচিত প্রথাগত (ক্লাসিক্যাল) অনুকূলায়ক এর উপর নির্ভর করে, :math:`boldsymboltheta এর চারপাশের বিভিন্ন নিয়ন্ত্রণ পয়েন্টগুলি অনুমান করতে হবে।

  5. নতুন সেট নিয়ন্ত্রণ চয়ন করতে একটি প্রথাগত (ক্লাসিক্যাল) অনুকূলায়ক বা অপ্টিমাইজার ব্যবহার করুন।.

  6. যতক্ষণ না \(C(\boldsymbol\theta)\) ন্যূনতমে পৌঁছে যায়, যা কিনা \(\boldsymbol\theta^*\) সমাধানের জন্য খুব কাছাকাছি, ততক্ষন চালিয়ে যান।

  7. শেষ \(\boldsymbol\theta\) ব্যবহার করুন \(\Big|\langle z_i\big|\psi(\boldsymbol\theta)\rangle\Big|^2\;\forall i\) বণ্টন থেকে অন্তিম নমুনা (স্যাম্পল) সমূহ উৎপন্ন করে উত্তর পাওয়ার জন্যে।

এটি আমাদের বিশ্বাস যে ভাল হিউরিস্টিক অ্যালগরিদমগুলি খুঁজে পেতে অসুবিধাটি একটি উপযুক্ত ট্রায়াল ওয়েভ ফাংশন পছন্দে একীভূত হবে। উদাহরণস্বরূপ, কেউ একটি ট্রায়াল ফাংশন বিবেচনা করতে পারে যার এনট্যাঙ্গেলমেন্ট, লক্ষ্য সমস্যাটির সাথে সর্বোত্তমভাবে প্রান্তিক হয় বা কেবল এনট্যাঙ্গেলমেন্ট হওয়ার পরিমাণকে পরিবর্তনশীল করে তোলে। এই টিউটোরিয়ালে, আমরা ফর্মটির একটি সাধারণ ট্রায়াল ফাংশন বিবেচনা করব

\[|\psi(\theta)\rangle = [U_\mathrm{single}(\boldsymbol\theta) U_\mathrm{entangler}]^m |+\rangle\]

যেখানে \(U_\mathrm{entangler}\) হল সি-ফেজ গেটস (সম্পূর্ণরূপে এনট্যাঙ্গেল বা পরিসাংখ্যিক যোগাযোগ বা বিজড়িত দরজা) এবং \(U_\mathrm{single}(\theta) = \prod_{i=1}^n Y(\theta_{i})\), যেখানে \(n\) কিউবিট সংখ্যা এবং \(m\) কোয়ান্টাম সার্কিটের গভীরতা। এই পছন্দটির অনুপ্রেরণা হ’ল, এই প্রথাগত (ক্লাসিক্যাল) সমস্যার জন্য এটি কোয়ান্টাম স্টেটের যে স্থানগুলিতে কেবল প্রকৃত সহগ রয়েছে তার সন্ধানের অনুমতি দেয়, তবুও সম্ভাব্যভাবে সমাধানে আরও দ্রুত রূপান্তরিত করতে এনট্যাঙ্গেলমেন্ট প্রবণতাটিকে কাজে লাগিয়ে।

অ্যাডিয়াব্যাটিক পদ্ধতির তুলনায় এই স্যাম্পলিং পদ্ধতিটি ব্যবহার করার একটি সুবিধা হল টার্গেট আইসিং হ্যামিল্টনিয়ানকে সরাসরি হার্ডওয়্যারে প্রয়োগ করা উচিত নয়, এই অ্যালগরিদমটিকে ডিভাইসের সংযোগের মধ্যে সীমাবদ্ধ না। তদুপরি, ব্যয় কার্যক্রমে উচ্চতর অর্ডার শর্তাদি, যেমন :math:`Z_iZ_jZ_k , এগুলিও দক্ষতার সাথে নমুনাযুক্ত করা যেতে পারে, যেখানে অ্যাডিয়াব্যাটিক বা অ্যানিলিং পদ্ধতির ক্ষেত্রে তারা সাধারণত মোকাবেলা করতে অযৌক্তিক হয়।

References:

  •  A. Lucas, Frontiers in Physics 2, 5 (2014)

  •  E. Farhi, J. Goldstone, S. Gutmann, e-print arXiv 1411.4028 (2014)

  •  D. Wecker, M. B. Hastings, M. Troyer, Phys. Rev. A 94, 022309 (2016)

  •  E. Farhi, J. Goldstone, S. Gutmann, H. Neven, e-print arXiv 1703.06199 (2017)

অ্যাপ্লিকেশন ক্লাস

আমরা সর্বোচ্চ লাভ সমস্যা ও ভ্রাম্যমান বিক্রেতার সমস্যার জন্য অ্যাপ্লিকেশন ক্লাস ব্যবহার করতে পারি। অন্যান্য অনুকূলায়ন (অপ্টিমাইজেশন) সমস্যাসমূহর জন্য আরো অ্যাপ্লিকেশন ক্লাস আছে। বিস্তারিত জানতে Application Classes for Optimization Problems দেখ।

[1]:
# useful additional packages
import matplotlib.pyplot as plt
import matplotlib.axes as axes
import numpy as np
import networkx as nx

from qiskit import Aer
from qiskit.tools.visualization import plot_histogram
from qiskit.circuit.library import TwoLocal
from qiskit_optimization.applications import Maxcut, Tsp
from qiskit.algorithms import VQE, NumPyMinimumEigensolver
from qiskit.algorithms.optimizers import SPSA
from qiskit.utils import algorithm_globals, QuantumInstance
from qiskit_optimization.algorithms import MinimumEigenOptimizer
from qiskit_optimization.problems import QuadraticProgram

সর্বোচ্চ লাভ সমস্যা (Max-Cut problem)

[2]:
# Generating a graph of 4 nodes

n = 4  # Number of nodes in graph
G = nx.Graph()
G.add_nodes_from(np.arange(0, n, 1))
elist = [(0, 1, 1.0), (0, 2, 1.0), (0, 3, 1.0), (1, 2, 1.0), (2, 3, 1.0)]
# tuple is (i,j,weight) where (i,j) is the edge
G.add_weighted_edges_from(elist)

colors = ["r" for node in G.nodes()]
pos = nx.spring_layout(G)


def draw_graph(G, colors, pos):
    default_axes = plt.axes(frameon=True)
    nx.draw_networkx(G, node_color=colors, node_size=600, alpha=0.8, ax=default_axes, pos=pos)
    edge_labels = nx.get_edge_attributes(G, "weight")
    nx.draw_networkx_edge_labels(G, pos=pos, edge_labels=edge_labels)


draw_graph(G, colors, pos)
../_images/tutorials_06_examples_max_cut_and_tsp_5_0.png
[3]:
# Computing the weight matrix from the random graph
w = np.zeros([n, n])
for i in range(n):
    for j in range(n):
        temp = G.get_edge_data(i, j, default=0)
        if temp != 0:
            w[i, j] = temp["weight"]
print(w)
[[0. 1. 1. 1.]
 [1. 0. 1. 0.]
 [1. 1. 0. 1.]
 [1. 0. 1. 0.]]

ব্রুট ফোর্স পদ্ধতি

সমস্ত সম্ভাব্য \(2^n সমন্বয় চেষ্টা করুন। যেমন :math:\), উদাহরণস্বরূপ, একজন কেবলমাত্র 16 টি সংমিশ্রণের সাথে ডিল করে তবে n = 1000 এর জন্য একটিতে 1.071509e + 30 সংমিশ্রণ রয়েছে, যা ব্রুট ফোর্স পদ্ধতির ব্যবহার করে মোকাবেলা করা অযৌক্তিক।

[4]:
best_cost_brute = 0
for b in range(2**n):
    x = [int(t) for t in reversed(list(bin(b)[2:].zfill(n)))]
    cost = 0
    for i in range(n):
        for j in range(n):
            cost = cost + w[i, j] * x[i] * (1 - x[j])
    if best_cost_brute < cost:
        best_cost_brute = cost
        xbest_brute = x
    print("case = " + str(x) + " cost = " + str(cost))

colors = ["r" if xbest_brute[i] == 0 else "c" for i in range(n)]
draw_graph(G, colors, pos)
print("\nBest solution = " + str(xbest_brute) + " cost = " + str(best_cost_brute))
case = [0, 0, 0, 0] cost = 0.0
case = [1, 0, 0, 0] cost = 3.0
case = [0, 1, 0, 0] cost = 2.0
case = [1, 1, 0, 0] cost = 3.0
case = [0, 0, 1, 0] cost = 3.0
case = [1, 0, 1, 0] cost = 4.0
case = [0, 1, 1, 0] cost = 3.0
case = [1, 1, 1, 0] cost = 2.0
case = [0, 0, 0, 1] cost = 2.0
case = [1, 0, 0, 1] cost = 3.0
case = [0, 1, 0, 1] cost = 4.0
case = [1, 1, 0, 1] cost = 3.0
case = [0, 0, 1, 1] cost = 3.0
case = [1, 0, 1, 1] cost = 2.0
case = [0, 1, 1, 1] cost = 3.0
case = [1, 1, 1, 1] cost = 0.0

Best solution = [1, 0, 1, 0] cost = 4.0
../_images/tutorials_06_examples_max_cut_and_tsp_8_1.png

আইসিং সমস্যার ম্যাপিং (চিত্রায়ন)

Qiskit সমস্যা বিবরণ থেকে QuadraticProgram তৈরি করতে এবং সম্পর্কিত আইসিং হ্যামিল্টোনিয়ান বানাতে প্রয়োজনীয় কার্যকারিতা সরবরাহ করে।

[5]:
max_cut = Maxcut(w)
qp = max_cut.to_quadratic_program()
print(qp.prettyprint())
Problem name: Max-cut

Maximize
  -2*x_0*x_1 - 2*x_0*x_2 - 2*x_0*x_3 - 2*x_1*x_2 - 2*x_2*x_3 + 3*x_0 + 2*x_1
  + 3*x_2 + 2*x_3

Subject to
  No constraints

  Binary variables (4)
    x_0 x_1 x_2 x_3

[6]:
qubitOp, offset = qp.to_ising()
print("Offset:", offset)
print("Ising Hamiltonian:")
print(str(qubitOp))
Offset: -2.5
Ising Hamiltonian:
0.5 * IIZZ
+ 0.5 * IZIZ
+ 0.5 * IZZI
+ 0.5 * ZIIZ
+ 0.5 * ZZII
[7]:
# solving Quadratic Program using exact classical eigensolver
exact = MinimumEigenOptimizer(NumPyMinimumEigensolver())
result = exact.solve(qp)
print(result.prettyprint())
objective function value: 4.0
variable values: x_0=1.0, x_1=0.0, x_2=1.0, x_3=0.0
status: SUCCESS

যেহেতু সমস্যাটি একটি মিনিমাইজেশন সমস্যার জন্য ফেলে দেওয়া হয়েছিল, তাই \(-4\) সমাধানটি সর্বোত্তমের সাথে মিলে যায়।.

সম্পূর্ণ হ্যামিল্টোনিয়ান সঠিক ব্যয় দেয় তা পরীক্ষা করা হচ্ছে

[8]:
# Making the Hamiltonian in its full form and getting the lowest eigenvalue and eigenvector
ee = NumPyMinimumEigensolver()
result = ee.compute_minimum_eigenvalue(qubitOp)

x = max_cut.sample_most_likely(result.eigenstate)
print("energy:", result.eigenvalue.real)
print("max-cut objective:", result.eigenvalue.real + offset)
print("solution:", x)
print("solution objective:", qp.objective.evaluate(x))

colors = ["r" if x[i] == 0 else "c" for i in range(n)]
draw_graph(G, colors, pos)
energy: -1.5
max-cut objective: -4.0
solution: [1 0 1 0]
solution objective: 4.0
../_images/tutorials_06_examples_max_cut_and_tsp_16_1.png

কোয়ান্টাম কম্পিউটারে চালানো

আমরা কোয়ান্টাম কম্পিউটারের সাথে ফিডব্যাক লুপ ব্যবহার করে অপ্টিমাইজেশন রুটিন চালাই যা Y একক-কিউবিট ঘূর্ণন, \(U_\mathrm{single}(\theta) = \prod_{i=1}^n Y(\theta_{i})\), এবং এন্ট্যাঙ্গলারের ধাপগুলি \(U_\mathrm{entangler}\) এর সাহায্যে নির্মিত ট্রায়াল ফাংশন ব্যবহার করে।

[9]:
algorithm_globals.random_seed = 123
seed = 10598
backend = Aer.get_backend("aer_simulator_statevector")
quantum_instance = QuantumInstance(backend, seed_simulator=seed, seed_transpiler=seed)
[10]:
# construct VQE
spsa = SPSA(maxiter=300)
ry = TwoLocal(qubitOp.num_qubits, "ry", "cz", reps=5, entanglement="linear")
vqe = VQE(ry, optimizer=spsa, quantum_instance=quantum_instance)

# run VQE
result = vqe.compute_minimum_eigenvalue(qubitOp)

# print results
x = max_cut.sample_most_likely(result.eigenstate)
print("energy:", result.eigenvalue.real)
print("time:", result.optimizer_time)
print("max-cut objective:", result.eigenvalue.real + offset)
print("solution:", x)
print("solution objective:", qp.objective.evaluate(x))

# plot results
colors = ["r" if x[i] == 0 else "c" for i in range(n)]
draw_graph(G, colors, pos)
energy: -1.49968614555873
time: 1.9054765701293945
max-cut objective: -3.99968614555873
solution: [0. 1. 0. 1.]
solution objective: 4.0
../_images/tutorials_06_examples_max_cut_and_tsp_19_1.png
[11]:
# create minimum eigen optimizer based on VQE
vqe_optimizer = MinimumEigenOptimizer(vqe)

# solve quadratic program
result = vqe_optimizer.solve(qp)
print(result.prettyprint())

colors = ["r" if result.x[i] == 0 else "c" for i in range(n)]
draw_graph(G, colors, pos)
objective function value: 4.0
variable values: x_0=1.0, x_1=0.0, x_2=1.0, x_3=0.0
status: SUCCESS
../_images/tutorials_06_examples_max_cut_and_tsp_20_1.png

ট্রাভেলিং সেলসম্যান সমস্যা

দুই শতাব্দীরও বেশি সময় ধরে কম্পিউটার বিজ্ঞানী এবং গণিতবিদদের দৃষ্টি আকর্ষণ করে এমন একটি কুখ্যাত এনপি-সম্পূর্ণ সমস্যা হওয়ার পাশাপাশি, ট্র্যাভেলিং সেলসম্যান প্রব্লেম (টি.এস.পি) এর অর্থ এবং বিপণনের ক্ষেত্রে গুরুত্বপূর্ণ ভারবহন রয়েছে। কথোপকথনের ভাষায়, ট্র্যাভেলিং সেলসম্যান এমন ব্যক্তি যিনি শহর থেকে শহরে পণ্যদ্রব্য বিক্রয় করতে যান। এক্ষেত্রে উদ্দেশ্যটি হ’ল সংক্ষিপ্ততম পথটি সন্ধান করা যা বিক্রয়কেন্দ্রকে সমস্ত শহর ঘুরে দেখার এবং তার শহরে ফিরে যেতে সক্ষম করবে, অর্থাৎ যে শহরে সে যাত্রা শুরু করেছিল। এটি করার মাধ্যমে বিক্রয়কটি সর্বনিম্ন সময়ে সম্ভাব্য বিক্রয় সর্বাধিক অর্জন করতে পারে।

অনুশীলনে উত্থাপিত অন্যান্য প্রাসঙ্গিক সমন্বয়মূলক সমস্যাগুলির সাথে এর "কঠোরতা" ("hardness") এবং সর্বব্যাপী সমতা থেকে সমস্যাটি তার গুরুত্ব অর্জন করে।

কিছু প্রাথমিক বিশ্লেষণের সাথে গাণিতিক সূত্রটি ডাব্লু.আর. হ্যামিল্টন ১৯ শতকের গোড়ার দিকে প্রস্তাব করেছিলেন। গাণিতিকভাবে সমস্যাটি হ’ল ম্যাক্স-কাটের গ্রাফের ক্ষেত্রে সবচেয়ে ভাল বিমূর্ত। কোনও গ্রাফের নোডের টিএসপি সর্বনিম্ন * হ্যামিলটোনিয়ান চক্র * যা প্রতিটি নোডের মধ্য দিয়ে নেওয়া যায় তা জিজ্ঞাসা করে। একটি হ্যামিল্টোনিয়ান চক্র এমন একটি বদ্ধ পথ যা একবারে গ্রাফের প্রতিটি প্রান্তকে একবার ব্যবহার করে। সাধারণ সমাধানটি অজানা এবং একটি অ্যালগরিদম (উদাঃ, বহু-কালীন সময়ে) এর উপস্থিতি প্রত্যাশিত নয় যা কার্যকরভাবে এটি খুঁজে পায় ।

\(n=|V|\) নোড এবং দূরত্ব \(w_{ij}\) (ভার্টেক্স \(i\) থেকে ভার্টেক্স \(j\) দূরত্ব) সহ একটি গ্রাফ \(G=(V,E)\) চল রাশি (ভেরিয়েবল) math:N^2 দ্বারা বর্ণিত হয়, যেখানে \(i\) নোডকে উপস্থাপন করে এবং \(p সম্ভাব্য চক্রের মধ্যে তার ক্রমটি উপস্থাপন করে। সময় ক্রম :math:\) এ সমাধান ঘটে তবে সিদ্ধান্ত ভেরিয়েবলের মান ১ হয়। আমাদের প্রয়োজন যে প্রতিটি নোড কেবল চক্রের মধ্যে একবার উপস্থিত হতে পারে এবং প্রতিটি বারের জন্য একটি নোড ঘটতে হয়। এটি দুটি সীমাবদ্ধতার পরিমান (এখানে এবং নীচে, যখনই নির্দিষ্ট করা হয়নি, যোগফলগুলি ০,১ থেকে,… এন -1)

\[\sum_{i} x_{i,p} = 1 ~~\forall p\]
\[\sum_{p} x_{i,p} = 1 ~~\forall i।\]

আমাদের সম্ভাব্য ক্রমান্বয়ে নোডের জন্য, \(x_{i,p}\) এবং \(x_{j,p+1}\) উভয়ই যদি ১ হয় তবে সেখানে শক্তির জরিমানা থাকতে হবে যদি: \((i,j) \notin E\) (গ্রাফের সাথে সংযুক্ত নয়)। এই জরিমানার ফর্মটি হ’ল

\[\sum_{i,j\notin E}\sum_{p} x_{i,p}x_{j,p+1}>0,\]

যেখানে এটি হ্যামিল্টোনিয়ান চক্র \((p=N)\equiv (p=0)\) সীমানা শর্ত হিসাবে ধরে নেওয়া হয়। তবে, এখানে এটি সম্পূর্ণ সংযুক্ত গ্রাফ হিসাবে ধরে নেওয়া হবে এবং এই পদটি অন্তর্ভুক্ত করা হবে না। যে দূরত্বটি হ্রাস করা দরকার তা হ’ল

\[C(\textbf{x})=\sum_{i,j}w_{ij}\sum_{p} x_{i,p}x_{j,p+1}।\]

এগুলি হ্রাস করতে একটি একক নৈর্ব্যক্তিক অন্বয় (অব্জেক্টিভ ফাংশন) একসাথে রাখলে আমরা নিম্নলিখিতটি পাই:

\[C(\textbf{x})=\sum_{i,j}w_{ij}\sum_{p} x_{i,p}x_{j,p+1}+ A\sum_p\left(1- \sum_i x_{i,p}\right)^2+A\sum_i\left(1- \sum_p x_{i,p}\right)^2,\]

যেখানে \(A\) একটি নিখরচায় প্যারামিটার। একজনকে নিশ্চিত করতে হবে যে \(A\) যথেষ্ট বড় যাতে এই প্রতিবন্ধকতাগুলি সম্মানিত হয়। এটি করার একটি উপায় হ’ল \(A\)

আবারও, এই আকারে সমস্যাটি একটি কোয়ান্টাম কম্পিউটারে ম্যাপ করা সহজ, এবং একটি আইসিং হ্যামিলটনিয়ানকে হ্রাস করে সমাধানটি পাওয়া যাবে।

[12]:
# Generating a graph of 3 nodes
n = 3
num_qubits = n**2
tsp = Tsp.create_random_instance(n, seed=123)
adj_matrix = nx.to_numpy_matrix(tsp.graph)
print("distance\n", adj_matrix)

colors = ["r" for node in tsp.graph.nodes]
pos = [tsp.graph.nodes[node]["pos"] for node in tsp.graph.nodes]
draw_graph(tsp.graph, colors, pos)
distance
 [[ 0. 48. 91.]
 [48.  0. 63.]
 [91. 63.  0.]]
../_images/tutorials_06_examples_max_cut_and_tsp_22_1.png

ব্রুট ফোর্স পদ্ধতি

[13]:
from itertools import permutations


def brute_force_tsp(w, N):
    a = list(permutations(range(1, N)))
    last_best_distance = 1e10
    for i in a:
        distance = 0
        pre_j = 0
        for j in i:
            distance = distance + w[j, pre_j]
            pre_j = j
        distance = distance + w[pre_j, 0]
        order = (0,) + i
        if distance < last_best_distance:
            best_order = order
            last_best_distance = distance
            print("order = " + str(order) + " Distance = " + str(distance))
    return last_best_distance, best_order


best_distance, best_order = brute_force_tsp(adj_matrix, n)
print(
    "Best order from brute force = "
    + str(best_order)
    + " with total distance = "
    + str(best_distance)
)


def draw_tsp_solution(G, order, colors, pos):
    G2 = nx.DiGraph()
    G2.add_nodes_from(G)
    n = len(order)
    for i in range(n):
        j = (i + 1) % n
        G2.add_edge(order[i], order[j], weight=G[order[i]][order[j]]["weight"])
    default_axes = plt.axes(frameon=True)
    nx.draw_networkx(
        G2, node_color=colors, edge_color="b", node_size=600, alpha=0.8, ax=default_axes, pos=pos
    )
    edge_labels = nx.get_edge_attributes(G2, "weight")
    nx.draw_networkx_edge_labels(G2, pos, font_color="b", edge_labels=edge_labels)


draw_tsp_solution(tsp.graph, best_order, colors, pos)
order = (0, 1, 2) Distance = 202.0
Best order from brute force = (0, 1, 2) with total distance = 202.0
../_images/tutorials_06_examples_max_cut_and_tsp_24_1.png

আইসিং সমস্যার ম্যাপিং (চিত্রায়ন)

[14]:
qp = tsp.to_quadratic_program()
print(qp.prettyprint())
Problem name: TSP

Minimize
  48*x_0_0*x_1_1 + 48*x_0_0*x_1_2 + 91*x_0_0*x_2_1 + 91*x_0_0*x_2_2
  + 48*x_0_1*x_1_0 + 48*x_0_1*x_1_2 + 91*x_0_1*x_2_0 + 91*x_0_1*x_2_2
  + 48*x_0_2*x_1_0 + 48*x_0_2*x_1_1 + 91*x_0_2*x_2_0 + 91*x_0_2*x_2_1
  + 63*x_1_0*x_2_1 + 63*x_1_0*x_2_2 + 63*x_1_1*x_2_0 + 63*x_1_1*x_2_2
  + 63*x_1_2*x_2_0 + 63*x_1_2*x_2_1

Subject to
  Linear constraints (6)
    x_0_0 + x_0_1 + x_0_2 == 1  'c0'
    x_1_0 + x_1_1 + x_1_2 == 1  'c1'
    x_2_0 + x_2_1 + x_2_2 == 1  'c2'
    x_0_0 + x_1_0 + x_2_0 == 1  'c3'
    x_0_1 + x_1_1 + x_2_1 == 1  'c4'
    x_0_2 + x_1_2 + x_2_2 == 1  'c5'

  Binary variables (9)
    x_0_0 x_0_1 x_0_2 x_1_0 x_1_1 x_1_2 x_2_0 x_2_1 x_2_2

[15]:
from qiskit_optimization.converters import QuadraticProgramToQubo

qp2qubo = QuadraticProgramToQubo()
qubo = qp2qubo.convert(qp)
qubitOp, offset = qubo.to_ising()
print("Offset:", offset)
print("Ising Hamiltonian:")
print(str(qubitOp))
Offset: 7581.0
Ising Hamiltonian:
-1282.5 * IIIIIIIIZ
- 1282.5 * IIIIIIIZI
- 1282.5 * IIIIIIZII
- 1268.5 * IIIIIZIII
- 1268.5 * IIIIZIIII
- 1268.5 * IIIZIIIII
- 1290.0 * IIZIIIIII
- 1290.0 * IZIIIIIII
- 1290.0 * ZIIIIIIII
+ 606.5 * IIIIIIIZZ
+ 606.5 * IIIIIIZIZ
+ 606.5 * IIIIIIZZI
+ 606.5 * IIIIIZIIZ
+ 12.0 * IIIIIZIZI
+ 12.0 * IIIIIZZII
+ 12.0 * IIIIZIIIZ
+ 606.5 * IIIIZIIZI
+ 12.0 * IIIIZIZII
+ 606.5 * IIIIZZIII
+ 12.0 * IIIZIIIIZ
+ 12.0 * IIIZIIIZI
+ 606.5 * IIIZIIZII
+ 606.5 * IIIZIZIII
+ 606.5 * IIIZZIIII
+ 606.5 * IIZIIIIIZ
+ 22.75 * IIZIIIIZI
+ 22.75 * IIZIIIZII
+ 606.5 * IIZIIZIII
+ 15.75 * IIZIZIIII
+ 15.75 * IIZZIIIII
+ 22.75 * IZIIIIIIZ
+ 606.5 * IZIIIIIZI
+ 22.75 * IZIIIIZII
+ 15.75 * IZIIIZIII
+ 606.5 * IZIIZIIII
+ 15.75 * IZIZIIIII
+ 606.5 * IZZIIIIII
+ 22.75 * ZIIIIIIIZ
+ 22.75 * ZIIIIIIZI
+ 606.5 * ZIIIIIZII
+ 15.75 * ZIIIIZIII
+ 15.75 * ZIIIZIIII
+ 606.5 * ZIIZIIIII
+ 606.5 * ZIZIIIIII
+ 606.5 * ZZIIIIIII
[16]:
result = exact.solve(qubo)
print(result.prettyprint())
objective function value: 202.0
variable values: x_0_0=1.0, x_0_1=0.0, x_0_2=0.0, x_1_0=0.0, x_1_1=1.0, x_1_2=0.0, x_2_0=0.0, x_2_1=0.0, x_2_2=1.0
status: SUCCESS

সম্পূর্ণ হ্যামিল্টোনিয়ান সঠিক ব্যয় দেয় তা পরীক্ষা করা হচ্ছে

[17]:
# Making the Hamiltonian in its full form and getting the lowest eigenvalue and eigenvector
ee = NumPyMinimumEigensolver()
result = ee.compute_minimum_eigenvalue(qubitOp)

print("energy:", result.eigenvalue.real)
print("tsp objective:", result.eigenvalue.real + offset)
x = tsp.sample_most_likely(result.eigenstate)
print("feasible:", qubo.is_feasible(x))
z = tsp.interpret(x)
print("solution:", z)
print("solution objective:", tsp.tsp_value(z, adj_matrix))
draw_tsp_solution(tsp.graph, z, colors, pos)
energy: -7379.0
tsp objective: 202.0
feasible: True
solution: [0, 1, 2]
solution objective: 202.0
../_images/tutorials_06_examples_max_cut_and_tsp_30_1.png

কোয়ান্টাম কম্পিউটারে চালানো

আমরা কোয়ান্টাম কম্পিউটারের সাথে ফিডব্যাক লুপ ব্যবহার করে অপ্টিমাইজেশন রুটিন চালাই যা Y একক-কিউবিট ঘূর্ণন, \(U_\mathrm{single}(\theta) = \prod_{i=1}^n Y(\theta_{i})\), এবং এন্ট্যাঙ্গলারের ধাপগুলি \(U_\mathrm{entangler}\) এর সাহায্যে নির্মিত ট্রায়াল ফাংশন ব্যবহার করে।

[18]:
algorithm_globals.random_seed = 123
seed = 10598
backend = Aer.get_backend("aer_simulator_statevector")
quantum_instance = QuantumInstance(backend, seed_simulator=seed, seed_transpiler=seed)
[19]:
spsa = SPSA(maxiter=300)
ry = TwoLocal(qubitOp.num_qubits, "ry", "cz", reps=5, entanglement="linear")
vqe = VQE(ry, optimizer=spsa, quantum_instance=quantum_instance)

result = vqe.compute_minimum_eigenvalue(qubitOp)

print("energy:", result.eigenvalue.real)
print("time:", result.optimizer_time)
x = tsp.sample_most_likely(result.eigenstate)
print("feasible:", qubo.is_feasible(x))
z = tsp.interpret(x)
print("solution:", z)
print("solution objective:", tsp.tsp_value(z, adj_matrix))
draw_tsp_solution(tsp.graph, z, colors, pos)
energy: -7326.024699521837
time: 5.199239253997803
feasible: True
solution: [1, 2, 0]
solution objective: 202.0
../_images/tutorials_06_examples_max_cut_and_tsp_33_1.png
[20]:
algorithm_globals.random_seed = 123
seed = 10598
backend = Aer.get_backend("aer_simulator_statevector")
quantum_instance = QuantumInstance(backend, seed_simulator=seed, seed_transpiler=seed)
[21]:
# create minimum eigen optimizer based on VQE
import warnings

warnings.filterwarnings("ignore", category=UserWarning)
vqe_optimizer = MinimumEigenOptimizer(vqe)

# solve quadratic program
result = vqe_optimizer.solve(qp)
print(result.prettyprint())

z = tsp.interpret(x)
print("solution:", z)
print("solution objective:", tsp.tsp_value(z, adj_matrix))
draw_tsp_solution(tsp.graph, z, colors, pos)
objective function value: 202.0
variable values: x_0_0=0.0, x_0_1=0.0, x_0_2=1.0, x_1_0=1.0, x_1_1=0.0, x_1_2=0.0, x_2_0=0.0, x_2_1=1.0, x_2_2=0.0
status: SUCCESS
solution: [1, 2, 0]
solution objective: 202.0
../_images/tutorials_06_examples_max_cut_and_tsp_35_1.png
[22]:
import qiskit.tools.jupyter

%qiskit_version_table
%qiskit_copyright

Version Information

Qiskit SoftwareVersion
qiskit-terra0.21.0.dev0+dbd3961
qiskit-aer0.10.4
qiskit-ibmq-provider0.19.1
qiskit-optimization0.4.0
System information
Python version3.10.4
Python compilerGCC 11.2.0
Python buildmain, Apr 2 2022 09:04:19
OSLinux
CPUs4
Memory (Gb)14.577545166015625
Wed May 18 16:05:11 2022 JST

This code is a part of Qiskit

© Copyright IBM 2017, 2022.

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.

[ ]: