A complete set of transformation rules for reversible circuits

यहाँ शिगुआंग फेंग और लुज़ौ ली के शोध पत्र "A complete set of transformation rules for reversible circuits" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

रिवर्सिबल लॉजिक सिंथेसिस (Reversible logic synthesis), क्वांटम इलेक्ट्रॉनिक डिज़ाइन ऑटोमेशन (EDA) का एक मौलिक घटक है। इस क्षेत्र में एक महत्वपूर्ण चुनौती सर्किट अनुकूलन (circuit optimization) है, जहाँ लक्ष्य रूपांतरण नियमों (rewriting rules) या टेम्पलेट्स का उपयोग करके दिए गए रिवर्सिबल सर्किट को एक छोटे, समकक्ष (equivalent) सर्किट में बदलना होता है।

यद्यपि कई नियम-आधारित अनुकूलन विधियाँ मौजूद हैं, लेकिन एक दीर्घकालिक सैद्धांतिक समस्या इन नियमों के सेट की पूर्णता (completeness) रही है। एक नियमों का सेट तब "पूर्ण" माना जाता है यदि किन्हीं भी दो समकक्ष रिवर्सिबल सर्किट्स को केवल उन्हीं नियमों का उपयोग करके एक-दूसरे में बदला जा सके। पिछले कार्यों ने विशिष्ट उप-वर्गों (जैसे, केवल CNOT या Toffoli गेट्स का उपयोग करने वाले सर्किट) या एकल-आउटपुट बूलियन फलनों के लिए पूर्णता स्थापित की थी, लेकिन सामान्य रिवर्सिबल सर्किट्स (Mixed Polarity Multiple-Control Toffoli गेट्स का उपयोग करने वाले) के लिए रूपांतरण नियमों का एक पूर्ण सेट एक खुला प्रश्न बना हुआ था। पूर्ण सेट के बिना, अनुकूलन एल्गोरिदम इष्टतम (optimal) सर्किट खोजने की गारंटी नहीं दे सकते।

2. कार्यप्रणाली (Methodology)

लेखक रूपांतरण नियमों के एक नए सेट ($R_C$) की पूर्णता को सिद्ध करने के लिए एक व्यवस्थित दृष्टिकोण प्रस्तावित करते हैं। यह कार्यप्रणाली एक कैनोनिकल फॉर्म (Canonical Form) की अवधारणा पर आधारित है।

A. रूपांतरण नियमों का सेट ($R_C$)

लेखक पाँच मौलिक रूपांतरण नियमों ($R_C$) का परिचय देते हैं जो X, CNOT, Toffoli, और Mixed Polarity Multiple-Control Toffoli (MPMCT) गेट्स से बने रिवर्सिबल सर्किट्स के हेरफेर को नियंत्रित करते हैं।

1. नियम 1 (Cancellation): दो आसन्न (adjacent) समान गेट एक दूसरे को रद्द कर देते हैं ($AA \equiv \epsilon$)।
2. नियम 2 (Polarity Reduction): दो आसन्न गेट जिनके नियंत्रण बिट्स (control bits) समान हों लेकिन ठीक एक बिट पर ध्रुवीयता (polarity) विपरीत हो, उन्हें उस बिट को हटाकर एक एकल गेट में बदला जा सकता है।
3. नियम 3 (Commutation): दो गेट तब कम्यूट (commute) करते हैं जब वे विपरीत ध्रुवीयता वाले साझा नियंत्रण बिट साझा करते हैं।
4. नियम 4 (SWAP Interaction): दो CNOT गेट्स और एक तीसरे गेट से संबंधित एक विशिष्ट इंटरेक्शन नियम, जो नियंत्रण/लक्ष्य भूमिकाओं को बदलकर एक गेट के माध्यम से SWAP ऑपरेशन को ले जाने की अनुमति देता है।
5. नियम 5 (Polarity Change): एक जटिल नियम जो विशिष्ट "रैपर" गेट्स ($A_0, A_1$) के साथ एक गेट अनुक्रम को घेरकर नियंत्रण बिट की ध्रुवीयता बदलने की अनुमति देता है। यह पूर्णता सिद्ध करने के लिए सबसे महत्वपूर्ण नियम है।

लेखक प्रमाणों को सरल बनाने के लिए $R_C$ से कई सहायक नियम (नियम 6-10) भी प्राप्त करते हैं, जैसे कि MPMCT गेट्स को MCT और X गेट्स में विघटित करना।

B. कैनोनिकल फॉर्म का निर्माण (Canonical Form Construction)

पूर्णता को सिद्ध करने के लिए, लेखक $n$-आयामी हाइपरक्यूब ग्राफ के एक हैमिल्टोनियन पथ (Hamiltonian path - $H$) के आधार पर किसी भी $n$-बिट रिवर्सिबल सर्किट के लिए एक कैनोनिकल फॉर्म को परिभाषित करते हैं।

• हैमिल्टोनियन पथ (Hamiltonian Path): एक ऐसा पथ जो प्रत्येक शीर्ष (n-लंबाई की बाइनरी स्ट्रिंग) पर ठीक एक बार जाता है, जहाँ आसन्न शीर्ष एक बिट से भिन्न होते हैं।
• गेट सेट ($\Delta_H$): MPMCT गेट्स का एक सेट जहाँ प्रत्येक गेट $M_i$ हैमिल्टोनियन पथ में दो आसन्न शीर्षों को बदल (swap) देता है।
• कैनोनिकल संरचना (Canonical Structure): कोई भी रिवर्सिबल फलन $H$ में शीर्षों के एक अद्वितीय क्रम (permutation) के अनुरूप होता है। लेखक सिद्ध करते हैं कि ऐसा कोई भी क्रम $\Delta_H$ के गेट्स के एक अद्वितीय अनुक्रम द्वारा साकार किया जा सकता है, जो एक विशिष्ट क्रम में व्यवस्थित होते हैं (कैनोनिकल फॉर्म)।

C. प्रमाण रणनीति (Proof Strategy)

पूर्णता का प्रमाण एक "कन्फ्लुएंस" (confluence) रणनीति का पालन करता है (जैसा कि पेपर के चित्र 1 में दर्शाया गया है):

1. सत्यता (Soundness): यह सिद्ध करना कि $R_C$ के सभी नियम सर्किट द्वारा गणना किए गए फलन को सुरक्षित रखते हैं (अर्थात, यदि $A \leftrightarrow B$, तो $A \equiv B$)।
2. सार्वभौमिकता (Universality): यह सिद्ध करना कि $\Delta_H$ के गेट्स सार्वभौमिक हैं और किसी भी रिवर्सिबल फलन को एक अद्वितीय कैनोनिकल सर्किट के माध्यम से गणना कर सकते हैं।
3. रूपांतरणीयता (Transformability): यह सिद्ध करना कि किसी भी अनिश्चित रिवर्सिबल सर्किट को उसके अद्वितीय कैनोनिकल फॉर्म में रूपांतरित किया जा सकता है।
   • इसमें यह दिखाना शामिल है कि $\Delta_H$ में न होने वाला कोई भी गेट $\Delta_H$ के गेट्स में विघटित किया जा सकता है।
   • इसमें यह दिखाना शामिल है कि $\Delta_H$ के किसी भी अनुक्रम को कम्यूटेशन और रिडक्शन नियमों का उपयोग करके कैनोनिकल अनुक्रम में पुनर्व्यवस्थित और कम किया जा सकता है।
4. निष्कर्ष: चूंकि किन्हीं भी दो समकक्ष सर्किट्स $A$ और $B$ को एक ही अद्वितीय कैनोनिकल फॉर्म $C$ में बदला जा सकता है ($A \leftrightarrow C$ और $B \leftrightarrow C$), इसलिए यह निष्कर्ष निकलता है कि $A \leftrightarrow B$।

3. मुख्य योगदान (Key Contributions)

1. प्रथम पूर्ण नियम सेट: यह पेपर सामान्य रिवर्सिबल सर्किट्स (MPMCT गेट्स सहित) के लिए पहला पूर्ण रूपांतरण नियमों का सेट प्रस्तुत करता है।
2. कैनोनिकल प्रतिनिधित्व: यह हाइपरक्यूब ग्राफ पर हैमिल्टोनियन पथों से प्राप्त एक नवीन कैनोनिकल सर्किट प्रतिनिधित्व पेश करता है, जो सिद्ध करता है कि प्रत्येक रिवर्सिबल फलन का इस रूप में एक अद्वितीय सर्किट होता है।
3. औपचारिक पूर्णता प्रमाण: यह एक कठोर गणितीय प्रमाण प्रदान करता है कि प्रस्तावित पाँच नियम किन्हीं भी दो समकक्ष रिवर्सिबल सर्किट्स को एक-दूसरे में बदलने के लिए पर्याप्त हैं।
4. EDA के लिए सैद्धांतिक आधार: यह कार्य क्वांटम EDA में नियम-आधारित अनुकूलन के लिए गणितीय आधार स्थापित करता है, यह गारंटी देता है कि इन नियमों को शामिल करने वाला कोई भी अनुकूलन सिस्टम सैद्धांतिक रूप से इष्टतम सर्किट आकार तक पहुँचने में सक्षम है।

4. परिणाम (Results)

• प्रमेय 1 (Soundness): पुष्टि करता है कि प्रस्तावित नियम सर्किट के तार्किक फलन को नहीं बदलते हैं।
• प्रस्तावना 2 (Universality): प्रदर्शित करता है कि विशिष्ट गेट सेट $\Delta_H$ किसी भी $n$-ary रिवर्सिबल फलन को कैनोनिकल रूप में अद्वितीय रूप से गणना कर सकता है।
• प्रमेय 2: सिद्ध करता है कि किसी भी $n$-बिट रिवर्सिबल सर्किट को उसके अद्वितीय कैनोनिकल फॉर्म में $R_C$ का उपयोग करके रूपांतरित किया जा सकता है।
• प्रमेय 3 (Completeness): निष्कर्ष निकालता है कि यदि दो सर्किट कार्यात्मक रूप से समकक्ष हैं ($A \equiv B$), तो वे नियमों के माध्यम से एक-दूसरे में रूपांतरित योग्य हैं ($A \leftrightarrow B$)।
• एल्गोरिदम 1: दिए गए रिवर्सिबल फलन से कैनोनिकल सर्किट बनाने के लिए $O(n \cdot 4^n)$ एल्गोरिदम प्रदान करता है।

5. महत्व और सीमाएँ (Significance and Limitations)

महत्व:

• एक खुले प्रश्न का समाधान: यह कार्य सामान्य रिवर्सिबल सर्किट्स के रूपांतरण नियमों की पूर्णता के संबंध में दशकों पुराने खुले प्रश्न को हल करता है।
• अनुकूलन गारंटी: यह एक सैद्धांतिक गारंटी प्रदान करता है कि नियम-आधारित अनुकूलन केवल एक ह्यूरिस्टिक (heuristic) नहीं है; यदि कोई सिस्टम इन नियमों का उपयोग करता है, तो वह सैद्धांतिक रूप से इष्टतम समाधान खोजने में सक्षम है।
• टेम्पलेट जनरेशन: इन नियमों का उपयोग मौजूदा टेम्पलेट्स की शुद्धता को सत्यापित करने और अनुकूलन उपकरणों के लिए नए, अधिक जटिल टेम्पलेट बनाने के लिए किया जा सकता है।

सीमाएँ और भविष्य का कार्य:

• घातांकीय जटिलता (Exponential Complexity): कैनोनिकल फॉर्म निर्माण (एल्गोरिदम 1) के परिणामस्वरूप घातांकीय आकार ($O(2^n)$) के सर्किट हो सकते हैं। फलस्वरूप, एक बड़े सर्किट को उसके कैनोनिकल रूप में बदलने के लिए घातांकीय चरणों की आवश्यकता हो सकती है, जिससे इस विधि का प्रत्यक्ष अनुप्रयोग बड़े पैमाने के सर्किट्स के लिए अव्यावहारिक हो जाता है।
• ह्यूरिस्टिक की आवश्यकता: लेखक सुझाव देते हैं कि हालांकि नियम सिद्धांत में इष्टतमता की गारंटी देते हैं, व्यावहारिक अनुकूलन को कम्प्यूटेशनल लागत को प्रबंधित करने के लिए अभी भी ह्यूरिस्टिक्स और व्युत्पन्न टेम्पलेट्स पर निर्भर रहना होगा।
• सहायक बिट्स (Ancillary Bits): वर्तमान कार्य सहायक बिट्स के बिना सर्किट्स पर केंद्रित है। सहायक बिट्स का उपयोग करने वाले सर्किट्स के लिए रूपांतरण नियमों की पूर्णता एक खुला प्रश्न बना हुआ है।
• भौतिक कार्यान्वयन: लॉजिकल गेट काउंट में कमी स्वतः ही विशिष्ट क्वांटम हार्डवेयर आर्किटेक्चर में भौतिक लागत (जैसे, क्यूबिट कोहेरेंस समय, गेट डेप्थ) को कम नहीं करती है।

संक्षेप में, यह शोध पत्र रिवर्सिबल लॉजिक सिंथेसिस के लिए एक मौलिक सैद्धांतिक सफलता प्रदान करता है, जो एक पूर्ण स्वयंसिद्ध (axiomatization) स्थापित करता है जो क्वांटम सर्किट डिज़ाइन में कार्यात्मक समानता और संरचनात्मक रूपांतरण के बीच के अंतर को पाटता है।