oracles.ipynb

Kernel: Python 3

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

বিষয়বস্তু

1. Introduction

2. Consulting and Oracle

3. Taking Out the Garbage

1। ভূমিকা

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

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

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

2. একটি ওরাকলের সাথে পরামর্শ করা

অনেক কোয়ান্টাম অ্যালগরিদম কিছু ফাংশন $f(x)$ এর বিশ্লেষণের উপর ভিত্তি করে। প্রায়শই এই অ্যালগরিদমগুলি এই ফাংশনের কিছু 'ব্ল্যাক বক্স' বাস্তবায়নের অস্তিত্ব অনুমান করে, যা আমরা $x$ ইনপুট দিতে পারি এবং সংশ্লিষ্ট আউটপুট $f(x)$ পেতে পারি। এটি একটি ওরাকল হিসাবে উল্লেখ করা হয়।

এই বিমূর্ত উপায়ে ওরাকল নিয়ে চিন্তা করার সুবিধা আমাদের ফাংশনটি বিশ্লেষণ করার জন্য ফাংশনটির পরিবর্তে কোয়ান্টাম কৌশলগুলিতে মনোনিবেশ করতে দেয়।

একটি কোয়ান্টাম অ্যালগরিদমের মধ্যে একটি ওরাকল কীভাবে কাজ করে তা বোঝার জন্য, সেগুলি কীভাবে সংজ্ঞায়িত করা হয় সে সম্পর্কে আমাদের সুনির্দিষ্ট হতে হবে। ওরাকলগুলি যে প্রধান রূপগুলি গ্রহণ করে তার মধ্যে একটি হল বুলিয়ান ওরাকলের । এগুলি নিম্নলিখিত একক বিবর্তন দ্বারা বর্ণিত হয়েছে,

$$U_f \left|x , \bar 0 \right\rangle = \left|x, f(x)\right\rangle.$$

এখানে $\left|x , \bar 0 \right\rangle = \left|x \right\rangle \otimes \left|\bar 0 \right\rangle$ দুটি রেজিস্টার সমন্বিত একটি মাল্টি-কিউবিট স্টেট উপস্থাপন করতে ব্যবহৃত হয়। প্রথম রেজিস্টারটি $\left|x\right\rangle$ অবস্থায় রয়েছে, যেখানে $x$ হল আমাদের ফাংশনে ইনপুটের একটি বাইনারি উপস্থাপনা। এই রেজিস্টারে qubits সংখ্যা ইনপুট প্রতিনিধিত্ব করতে প্রয়োজনীয় বিট সংখ্যা.

দ্বিতীয় রেজিস্টারের কাজ একইভাবে আউটপুট এনকোড করা। বিশেষভাবে, $U_f$ প্রয়োগ করার পরে এই রেজিস্টারের অবস্থা $\left|f(x)\right\rangle$ আউটপুটের একটি বাইনারি উপস্থাপনা হবে, এবং এই রেজিস্টারে এর জন্য প্রয়োজনীয় যতগুলি qubit থাকবে। এই রেজিস্টারের জন্য এই প্রারম্ভিক অবস্থা $\left|\bar 0 \right\rangle$ সেই স্টেটের প্রতিনিধিত্ব করে যার জন্য সমস্ত qubits $\left|0 \right\rangle$। অন্যান্য প্রাথমিক অবস্থার জন্য, $U_f$ প্রয়োগ করলে ভিন্ন ফলাফল পাওয়া যাবে। উদ্ভূত নির্দিষ্ট ফলাফল নির্ভর করবে আমরা কিভাবে একক $U_f$ সংজ্ঞায়িত করি।

ওরাকলের আরেকটি রূপ হল ফেজ ওরাকল , যা নিম্নরূপ সংজ্ঞায়িত করা হয়েছে,

$$P_f \left|x \right\rangle = (-1)^{f(x)} \left|x \right\rangle,$$

যেখানে আউটপুট $f(x)$ সাধারণত $0$ বা $1$ এর একটি সাধারণ বিট মান।

যদিও এটি বুলিয়ান ওরাকল থেকে আকারে অনেক আলাদা বলে মনে হয়, তবে এটি একই মৌলিক ধারণার অন্য অভিব্যক্তি। প্রকৃতপক্ষে, এটি পূর্ববর্তী বিভাগে বর্ণিত একই 'ফেজ কিকব্যাক' প্রক্রিয়া ব্যবহার করে উপলব্ধি করা যেতে পারে।

এটি দেখতে, বুলিয়ান ওরাকল $U_f$ বিবেচনা করুন যা একই ফাংশনের সাথে সামঞ্জস্যপূর্ণ। এটি এমন কিছু হিসাবে প্রয়োগ করা যেতে পারে যা মূলত নিয়ন্ত্রিত-না-এর একটি সাধারণ রূপ। এটি ইনপুট রেজিস্টারে নিয়ন্ত্রিত হয়, যেমন এটি আউটপুট বিটটিকে $\left|0 \right\rangle$-এ $f(x)=0$-এ ছেড়ে দেয় এবং ParseError: KaTeX parse error: Invalid delimiter '-' after '\left' at position 6: \left-̲এ ফ্লিপ করতে XParseError: KaTeX parse error: Expected 'EOF', got '\right' at position 18: …্রয়োগ করে। |1 \̲r̲i̲g̲h̲t̲\rangle যদি $f(x)=1$। যদি আউটপুট রেজিস্টারের প্রাথমিক অবস্থা $\left|- \right\rangle$ এর পরিবর্তে $\left|0 \right\rangle$ হয়, তাহলে $U_f$ এর প্রভাবটি হবে $(--এর পর্যায়টিকে ঠিকভাবে প্ররোচিত করবে। 1)^{f(x)}$ প্রয়োজন।

$$U_f \left( \left|x \right\rangle \otimes \left| - \right\rangle \right) = (P_f \otimes I) \left( \left|x \right\rangle \otimes \left| - \right\rangle \right)$$

যেহেতু $\left|- আউটপুট qubit-এর \right\rangle$ অবস্থা পুরো প্রক্রিয়ার দ্বারা অপরিবর্তিত রাখা হয়েছে, এটি নিরাপদে উপেক্ষা করা যেতে পারে। তাই শেষ প্রভাব হল যে ফেজ ওরাকলটি কেবল সংশ্লিষ্ট বুলিয়ান ওরাকল দ্বারা প্রয়োগ করা হয়।

3. আবর্জনা বের করা

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

একটি বিষয় যা আমাদের অবশ্যই যত্ন নিতে হবে তা হ'ল বিপরীততা। $U = \sum_x \left| ফর্মের একক f(x) \right\rangle \left\langle x \right|$ শুধুমাত্র তখনই সম্ভব যদি প্রতিটি অনন্য ইনপুট $x$ এর ফলে একটি অনন্য আউটপুট $f(x)$ হয়, যা সাধারণভাবে সত্য নয়। যাইহোক, আমরা আউটপুটে ইনপুটের একটি অনুলিপি অন্তর্ভুক্ত করে এটিকে সত্য হতে বাধ্য করতে পারি। এটিই আমাদেরকে বুলিয়ান ওরাকলের ফর্মে নিয়ে যায় যেমনটি আমরা আগে দেখেছি $$U_f \left|x,\bar 0 \right\rangle = \left| x,f(x) \right\rangle$$

একক হিসাবে লেখা গণনার সাথে, আমরা সুপারপজিশন অবস্থায় এটি প্রয়োগ করার প্রভাব বিবেচনা করতে সক্ষম। উদাহরণস্বরূপ, আসুন আমরা সমস্ত সম্ভাব্য ইনপুট $x$ (সরলতার জন্য অস্বাভাবিক) উপর সুপারপজিশন নিই। এর ফলে সম্ভাব্য সব ইনপুট/আউটপুট জোড়ার একটি সুপারপজিশন হবে,

$$U_f \sum_x \left|x,0\right\rangle = \sum_x \left|x,f(x)\right\rangle.$$

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

উদাহরণস্বরূপ, বিবেচনা করুন যে একটি ক্লাসিক্যাল অ্যালগরিদম নিম্নলিখিত প্রক্রিয়াটি সম্পাদন করে, $$V_f \left|x,\bar 0, \bar 0 \right\rangle = \left| x,f(x), g(x) \right\rangle$$ এখানে আমরা একটি তৃতীয় রেজিস্টার দেখতে পাচ্ছি, যা ক্লাসিক্যাল অ্যালগরিদমের জন্য 'স্ক্র্যাচপ্যাড' হিসেবে ব্যবহৃত হয়। আমরা গণনার শেষে এই রেজিস্টারে অবশিষ্ট তথ্যগুলিকে 'আবর্জনা', $g(x)$ হিসাবে উল্লেখ করব। আসুন আমরা $V_f$ ব্যবহার করি একটি ইউনিটারি বোঝাতে যা উপরেরটি প্রয়োগ করে।

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

উদাহরণস্বরূপ, ধরুন আমাদের কোয়ান্টাম কম্পিউটেশনের মধ্যে কিছু প্রক্রিয়া আমাদেরকে সুপারপজিশন স্টেট দিয়েছে $\sum_x \left|x,f(x)\right\rangle$, এবং আমাদের এটিকে $\sum_x \left| অবস্থায় ফেরত দিতে হবে। x,0\right\rangle$। এর জন্য আমরা কেবল $U_f^\dagger$ প্রয়োগ করতে পারি। এটি প্রয়োগ করার ক্ষমতা সরাসরি $U_f$ প্রযোজ্য একটি সার্কিট জানার পরে অনুসরণ করে, যেহেতু আমাদের কেবল সার্কিটের প্রতিটি গেটকে তার বিপরীত দিয়ে প্রতিস্থাপন করতে হবে এবং ক্রমটি বিপরীত করতে হবে।

যাইহোক, ধরুন আমরা জানি না কিভাবে $U_f$ প্রয়োগ করতে হয়, কিন্তু এর পরিবর্তে জানি কিভাবে $V_f$ প্রয়োগ করতে হয়। এর মানে হল আমরা এখানে $U_f^\dagger$ প্রয়োগ করতে পারি না, তবে $V_f^\dagger$ ব্যবহার করতে পারি। দুর্ভাগ্যবশত, আবর্জনার উপস্থিতি মানে এটি একই প্রভাব ফেলবে না।

এর একটি সুস্পষ্ট উদাহরণের জন্য আমরা একটি খুব সাধারণ কেস নিতে পারি। আমরা $x$, $f(x)$ এবং $g(x)$ সীমাবদ্ধ করব সবগুলিকে মাত্র একটি বিট নিয়ে গঠিত। আমরা $f(x) = x$ এবং $g(x) = x$ও ব্যবহার করব, যার প্রতিটি ইনপুট রেজিস্টারে নিয়ন্ত্রিত একটি একক cx গেট দিয়ে অর্জন করা যেতে পারে।

বিশেষভাবে, $U_f$ বাস্তবায়নের সার্কিটটি ইনপুট এবং আউটপুট রেজিস্টারের একক বিটের মধ্যে নিম্নলিখিত একক cx ।

from qiskit import QuantumCircuit, QuantumRegister

input_bit = QuantumRegister(1, 'input')
output_bit = QuantumRegister(1, 'output')
garbage_bit = QuantumRegister(1, 'garbage')

Uf = QuantumCircuit(input_bit, output_bit, garbage_bit)
Uf.cx(input_bit[0], output_bit[0])

Uf.draw()

$V_f$ এর জন্য, যেখানে আমাদের আবর্জনার জন্য ইনপুটের একটি অনুলিপি তৈরি করতে হবে, আমরা নিম্নলিখিত দুটি cx গেট ব্যবহার করতে পারি।

Vf = QuantumCircuit(input_bit, output_bit, garbage_bit)
Vf.cx(input_bit[0], garbage_bit[0])
Vf.cx(input_bit[0], output_bit[0])
Vf.draw()

এখন আমরা প্রথমে $U_f$ প্রয়োগ করার এবং তারপর $V_f^{\dagger}$ প্রয়োগ করার প্রভাব দেখতে পারি। নেট প্রভাব নিম্নলিখিত সার্কিট হয়.

qc = Uf + Vf.inverse()
qc.draw()

এই সার্কিট দুটি অভিন্ন cx গেট দিয়ে শুরু হয়, যার প্রভাব একে অপরকে বাতিল করে দেয়। যা অবশিষ্ট থাকে তা হল ইনপুট এবং আবর্জনা রেজিস্টারের মধ্যে চূড়ান্ত cx । গাণিতিকভাবে, এর মানে

$$V_f^\dagger U_f \left| x,0,0 \right\rangle = V_f^\dagger \left| x,f(x),0 \right\rangle = \left| x , 0 ,g(x) \right\rangle.$$

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

এই কারণে আমাদের কোয়ান্টাম অ্যালগরিদম থেকে ক্লাসিক্যাল আবর্জনা অপসারণের একটি উপায় প্রয়োজন। এটি 'আনকম্পিউটেশন' নামে পরিচিত একটি পদ্ধতি দ্বারা করা যেতে পারে। আমাদের কেবল আরেকটি ফাঁকা ভেরিয়েবল নিতে হবে এবং $V_f$ প্রয়োগ করতে হবে

$$\left| x, 0, 0, 0 \right\rangle \rightarrow \left| x,f(x),g(x),0 \right\rangle.$$

তারপরে আমরা নিয়ন্ত্রিত-নট গেটের একটি সেট প্রয়োগ করি, প্রতিটি আউটপুট এনকোড করতে ব্যবহৃত কিউবিটগুলির একটিতে নিয়ন্ত্রিত, এবং অতিরিক্ত ফাঁকা ভেরিয়েবলের সংশ্লিষ্ট কিউবিটের উপর লক্ষ্যবস্তু।

একক কিউবিট রেজিস্টার ব্যবহার করে আমাদের উদাহরণের জন্য এটি করার সার্কিটটি এখানে।

final_output_bit = QuantumRegister(1, 'final-output')

copy = QuantumCircuit(output_bit, final_output_bit)
copy.cx(output_bit, final_output_bit)

copy.draw()

এর প্রভাব হল তথ্য অনুলিপি করা (যদি আপনি নো-ক্লোনিং উপপাদ্য শুনে থাকেন তবে মনে রাখবেন এটি একই প্রক্রিয়া নয়)। বিশেষত, এটি নিম্নলিখিত উপায়ে রাষ্ট্রকে রূপান্তরিত করে।

$$\left| x,f(x),g(x),0 \right\rangle \rightarrow \left| x,f(x),g(x),f(x) \right\rangle.$$

অবশেষে আমরা $V_f^\dagger$ প্রয়োগ করি, যা মূল গণনাকে পূর্বাবস্থায় ফিরিয়ে আনে।

$$\left| x,f(x),g(x),0 \right\rangle \rightarrow \left| x,0,0,f(x) \right\rangle.$$

কপি করা আউটপুট তবুও রয়ে গেছে। নেট প্রভাব হল আবর্জনা ছাড়াই গণনা সম্পাদন করা, এবং তাই আমাদের কাঙ্খিত $U_f$ অর্জন করে।

আমাদের উদাহরণের জন্য একক কিউবিট রেজিস্টার ব্যবহার করে এবং যার জন্য $f(x) = x$, পুরো প্রক্রিয়াটি নিম্নলিখিত সার্কিটের সাথে মিলে যায়।

(Vf.inverse() + copy + Vf).draw()

cx গেটগুলি কীভাবে কাজ করে সে সম্পর্কে আপনি এখন পর্যন্ত যা জানেন তা ব্যবহার করে, আপনি দেখতে সক্ষম হবেন যে দুটি আবর্জনা রেজিস্টারে প্রয়োগ করা একে অপরকে বাতিল করবে। তাই আমরা সফলভাবে আবর্জনা অপসারণ করেছি।

দ্রুত অনুশীলন

1. দেখান যে আউটপুট সঠিকভাবে 'ফাইনাল আউটপুট' রেজিস্টারে লেখা হয়েছে (এবং শুধুমাত্র এই রেজিস্টারে) যখন 'আউটপুট' রেজিস্টার $|0\rangle$ হিসাবে আরম্ভ করা হয়।

2. 'আউটপুট' রেজিস্টার $|1\rangle$ হিসাবে আরম্ভ হলে কি হবে তা নির্ধারণ করুন।

এই পদ্ধতির সাথে, এবং এই অধ্যায়ে কভার করা অন্য সকলের সাথে, আমাদের কাছে এখন কোয়ান্টাম অ্যালগরিদম তৈরি করার জন্য প্রয়োজনীয় সমস্ত সরঞ্জাম রয়েছে। এখন আমরা সেই অ্যালগরিদমগুলিকে কর্মে দেখতে যেতে পারি।

import qiskit.tools.jupyter
%qiskit_version_table