การคำนวณแบบย้อนกลับได้คือแบบจำลองการคำนวณ ใดๆ ที่ทุกขั้นตอนของกระบวนการสามารถย้อนกลับได้ตามเวลาซึ่งหมายความว่า เมื่อได้รับผลลัพธ์ของการคำนวณแล้ว ก็สามารถสร้างอินพุตขึ้นมาใหม่ได้อย่างสมบูรณ์แบบ ในระบบที่ดำเนินไปอย่างเป็น ระบบ จากสถานะหนึ่งไปยังอีกสถานะหนึ่ง ข้อกำหนดสำคัญสำหรับความสามารถในการย้อนกลับได้คือการจับคู่แบบหนึ่งต่อหนึ่ง ระหว่างแต่ละสถานะกับสถานะถัดไป การคำนวณแบบย้อนกลับได้ถือเป็นแนวทางการคำนวณที่ไม่ธรรมดาและมีความเชื่อมโยงอย่างใกล้ชิดกับการคำนวณควอนตัมซึ่งหลักการของกลศาสตร์ควอนตัมรับประกันความสามารถในการย้อนกลับได้โดยธรรมชาติ (ตราบใดที่สถานะควอนตัมไม่ได้ถูกวัดหรือ " ยุบตัว ") ^{[ 1 ]}

มีความสามารถในการย้อนกลับที่สำคัญสองประเภทที่เกี่ยวข้องกันอย่างใกล้ชิดซึ่งมีความสำคัญเป็นพิเศษสำหรับวัตถุประสงค์นี้ ได้แก่ความสามารถในการย้อนกลับทางกายภาพและความสามารถในการย้อนกลับเชิงตรรกะ^{[ 2 ]}

กล่าวได้ว่ากระบวนการใด ๆสามารถย้อนกลับได้ทางกายภาพหากไม่ส่งผลให้เอนโทรปี ทางกายภาพเพิ่มขึ้น หรือ เรียก ว่ากระบวนการไอเซนโทรปิ กมีรูปแบบการออกแบบวงจรแบบหนึ่งที่แสดงคุณสมบัตินี้ได้อย่างสมบูรณ์แบบ ซึ่งเรียกว่าตรรกะการกู้คืน ประจุ วงจร อะเดียแบติกหรือการคำนวณอะเดียแบติก (ดูกระบวนการอะเดียแบติก ) แม้ว่าในทางปฏิบัติแล้วกระบวนการทางกายภาพที่ไม่คงที่ใด ๆ ก็ไม่สามารถ ย้อนกลับได้ทางกายภาพหรือเป็นไอเซนโทรปิกได้ อย่างสมบูรณ์แบบแต่ก็ไม่มีขีดจำกัดที่ทราบแน่ชัดว่าเราจะเข้าใกล้ความสามารถในการย้อนกลับได้อย่างสมบูรณ์แบบได้มากแค่ไหน ในระบบที่แยกตัวออกจากปฏิสัมพันธ์กับสภาพแวดล้อมภายนอกที่ไม่รู้จักได้ดีพอ เมื่อ ทราบ กฎทางฟิสิกส์ที่อธิบายวิวัฒนาการของระบบอย่างแม่นยำ

แรงจูงใจในการศึกษาเทคโนโลยีที่มุ่งเป้าไปที่การนำการคำนวณแบบย้อนกลับมาใช้คือเทคโนโลยีเหล่านี้เสนอสิ่งที่คาดการณ์ว่าจะเป็นวิธีเดียวที่เป็นไปได้ในการปรับปรุงประสิทธิภาพการใช้พลังงาน ในการคำนวณ (เช่น การดำเนินการที่เป็นประโยชน์ต่อหน่วยพลังงานที่สูญเสียไป) ของคอมพิวเตอร์ให้เหนือกว่าขีดจำกัดพื้นฐานของ von Neumann–Landauer ^{[ 3 ] [ 4 ]}ของพลังงานที่สูญเสียไปkT ln(2) ต่อ การดำเนินการบิต ที่ ไม่ สามารถย้อนกลับได้

ขีดจำกัดของแลนเดาเออร์ต่ำกว่าการใช้พลังงานของคอมพิวเตอร์ในช่วงปี 2000 หลายล้านเท่า และต่ำกว่าหลายพันเท่าในช่วงปี 2010 ^{[ 5 ]}ผู้สนับสนุนการคำนวณแบบย้อนกลับได้โต้แย้งว่าการใช้พลังงานส่วนใหญ่เกิดจากค่าใช้จ่ายด้านสถาปัตยกรรม ค่าใช้จ่ายเหล่านี้คือต้นทุนด้านพลังงานที่เกี่ยวข้องกับส่วนที่ไม่ใช่การคำนวณของระบบ เช่น สายไฟ ทรานซิสเตอร์ และหน่วยความจำ ซึ่งจำเป็นต่อการทำงานของคอมพิวเตอร์ พวกเขาเชื่อว่าสิ่งนี้ทำให้เทคโนโลยีในปัจจุบันยากที่จะบรรลุประสิทธิภาพการใช้พลังงานที่สูงขึ้นมากหากไม่นำหลักการคำนวณแบบย้อนกลับได้มาใช้^{[ 6 ]}

ตามที่ Rolf Landauerได้โต้แย้งเป็นครั้งแรกขณะทำงานที่IBM [ ^{7 ]}เพื่อให้กระบวนการคำนวณสามารถย้อนกลับได้ทางกายภาพ กระบวนการนั้นจะต้อง^{สามารถ} ย้อนกลับ ได้ทางตรรกะด้วยหลักการของ Landauerคือการสังเกตว่าการลบ ข้อมูลที่ทราบจำนวน nบิตโดยไม่รู้ตัวจะต้องมีค่าใช้จ่ายเท่ากับnkT ln(2)ในเอน โทรปีทางเทอร์โมไดนามิกเสมอ กระบวนการคำนวณแบบแยกส่วนและกำหนดได้จะกล่าวได้ว่าสามารถย้อนกลับได้ทางตรรกะ หากฟังก์ชันการเปลี่ยนผ่านที่แมปสถานะการคำนวณเก่าไปยังสถานะใหม่เป็นฟังก์ชันแบบหนึ่งต่อหนึ่งกล่าวคือ สถานะตรรกะเอาต์พุตจะกำหนดสถานะตรรกะอินพุตของการดำเนินการคำนวณได้อย่างเฉพาะเจาะจง

สำหรับกระบวนการคำนวณที่ไม่แน่นอน (ในแง่ของความน่าจะเป็นหรือความสุ่ม) ความสัมพันธ์ระหว่างสถานะเก่าและสถานะใหม่ไม่ใช่ฟังก์ชันค่าเดียวและข้อกำหนดที่จำเป็นเพื่อให้ได้ความสามารถในการย้อนกลับทางกายภาพจะกลายเป็นเงื่อนไขที่อ่อนลงเล็กน้อย กล่าวคือ ขนาดของกลุ่มสถานะเริ่มต้นที่เป็นไปได้ในการคำนวณจะไม่ลดลงโดยเฉลี่ยเมื่อการคำนวณดำเนินไปข้างหน้า

หลักการของแลนเดาเออร์ (และกฎข้อที่สองของเทอร์โมไดนามิกส์ ) สามารถเข้าใจได้ว่าเป็นผลลัพธ์เชิงตรรกะ โดยตรง จากความสามารถในการย้อนกลับของฟิสิกส์ดังที่สะท้อนให้เห็นในสูตรแฮมิลโทเนียนทั่วไปของกลศาสตร์และในตัวดำเนินการวิวัฒนาการเวลาเอกภาพของกลศาสตร์ควอนตัมโดยเฉพาะ^{[ 8 ]}

การนำการคำนวณแบบย้อนกลับมาใช้จึงหมายถึงการเรียนรู้วิธีการกำหนดลักษณะและควบคุมพลวัตทางกายภาพของกลไกเพื่อดำเนินการคำนวณที่ต้องการได้อย่างแม่นยำ จนกระทั่งการทดลองสะสมความไม่แน่นอนโดยรวมเกี่ยวกับสถานะทางกายภาพทั้งหมดของกลไกในปริมาณที่น้อยมาก สำหรับแต่ละการดำเนินการเชิงตรรกะที่ดำเนินการ กล่าวอีกนัยหนึ่งคือ ติดตามสถานะของพลังงานที่ใช้ในการดำเนินการคำนวณภายในเครื่องอย่างแม่นยำ และออกแบบเครื่องเพื่อให้พลังงานส่วนใหญ่ถูกนำกลับมาใช้ใหม่ในรูปแบบที่เป็นระเบียบซึ่งสามารถนำกลับมาใช้ใหม่สำหรับการดำเนินการครั้งต่อไป แทนที่จะปล่อยให้สูญเสียไปในรูปของความร้อน

แม้ว่าการบรรลุเป้าหมายนี้จะเป็นความท้าทายอย่างมากสำหรับการออกแบบ การผลิต และการกำหนดคุณลักษณะของกลไกทางกายภาพใหม่ที่มีความแม่นยำสูงเป็นพิเศษสำหรับการคำนวณแต่ในปัจจุบันยังไม่มีเหตุผลพื้นฐานใดที่จะคิดว่าเป้าหมายนี้จะไม่สามารถบรรลุได้ในที่สุด ซึ่งจะทำให้สามารถสร้างคอมพิวเตอร์ที่สร้างเอนโทรปีทางกายภาพน้อยกว่า 1 บิต (และกระจายพลังงานน้อยกว่าkT ln 2 ไปเป็นความร้อน) สำหรับการดำเนินการเชิงตรรกะที่มีประโยชน์แต่ละครั้งที่ดำเนินการภายในได้ในอนาคต

ปัจจุบัน สาขานี้มีเอกสารทางวิชาการจำนวนมาก นักฟิสิกส์วิศวกรไฟฟ้าและนักวิทยาศาสตร์คอมพิวเตอร์ได้ ออกแบบและวิเคราะห์แนวคิดเกี่ยวกับอุปกรณ์ย้อนกลับได้หลากหลายประเภท วงจรลอจิกวงจรไฟฟ้าสถาปัตยกรรมโปรเซสเซอร์ภาษาโปรแกรมและอัลกอริธึม ประยุกต์ต่างๆ

สาขาการวิจัยนี้กำลังรอการพัฒนาอย่างละเอียดของ เทคโนโลยีอุปกรณ์ลอจิกที่มีคุณภาพสูง คุ้มค่า และเกือบจะย้อนกลับได้ ซึ่งรวมถึงกลไก การกำหนดจังหวะและการซิงโครไนซ์ ที่มีประสิทธิภาพด้านพลังงานสูง หรือหลีกเลี่ยงความจำเป็นสำหรับสิ่งเหล่านี้ผ่านการออกแบบแบบอะซิงโครนัส ความก้าวหน้าทางวิศวกรรมที่แข็งแกร่งเช่นนี้จะเป็นสิ่งจำเป็นก่อนที่งานวิจัยเชิงทฤษฎีจำนวนมากเกี่ยวกับการคำนวณแบบย้อนกลับได้จะสามารถนำไปประยุกต์ใช้ในทางปฏิบัติเพื่อทำให้เทคโนโลยีคอมพิวเตอร์ จริง สามารถเอาชนะอุปสรรคต่างๆ ในระยะสั้นต่อประสิทธิภาพด้านพลังงาน รวมถึงขอบเขตของ von Neumann–Landauer ซึ่งอาจเอาชนะได้โดยการใช้การคำนวณแบบย้อนกลับได้ทางตรรกะเท่านั้น เนื่องจากกฎข้อที่สองของอุณหพลศาสตร์^{[ 9 ]}

การดำเนินการคำนวณที่สามารถย้อนกลับได้ในเชิงตรรกะ หมายความว่าผลลัพธ์ (หรือสถานะสุดท้าย) ของการดำเนินการสามารถคำนวณได้จากอินพุต (หรือสถานะเริ่มต้น) และในทางกลับกัน ฟังก์ชันที่ย้อนกลับได้ต้องเป็นฟังก์ชันหนึ่งต่อหนึ่ง (injective ) ซึ่งหมายความว่าเกตที่ย้อนกลับได้ (และวงจรเช่น การประกอบของเกตหลายตัว) โดยทั่วไปจะมีจำนวนบิตอินพุตเท่ากับจำนวนบิตเอาต์พุต (โดยสมมติว่าบิตอินพุตทั้งหมดถูกใช้ไปในการดำเนินการ)

เก ต อินเวอร์เตอร์ (NOT) สามารถย้อนกลับได้ในเชิงตรรกะ เนื่องจากสามารถยกเลิกการทำงานได้อย่างไรก็ตาม เกต NOT อาจไม่สามารถย้อนกลับได้ในเชิงกายภาพ ขึ้นอยู่กับการใช้งาน

เก ต เอกซ์คลูซีฟออร์ (XOR) เป็นเกตที่ไม่สามารถย้อนกลับได้ เนื่องจากอินพุตทั้งสองไม่สามารถสร้างขึ้นใหม่ได้อย่างชัดเจนจากเอาต์พุตเดียว หรืออีกนัยหนึ่งคือ การลบข้อมูลไม่สามารถย้อนกลับได้ อย่างไรก็ตาม เกต XOR เวอร์ชันที่ย้อนกลับได้— เกต NOT ควบคุม (CNOT)—สามารถกำหนดได้โดยการคงอินพุตตัวหนึ่งไว้เป็นเอาต์พุตที่สอง เกต CNOT แบบสามอินพุตเรียกว่าเกตToffoliมันคงอินพุตสองตัวคือa และ b ไว้ และแทนที่ตัวที่สามcด้วยเมื่อจะได้ฟังก์ชัน AND และเมื่อจะได้ฟังก์ชัน NOT เนื่องจาก AND และ NOT รวมกันเป็น ชุด ฟังก์ชันที่สมบูรณ์เกต Toffoli จึงเป็นเกตสากลและสามารถใช้งานฟังก์ชันบูลีน ใดๆ ก็ได้ (หากมี บิตเสริมที่เริ่มต้นค่าไว้เพียงพอ) ${\displaystyle c\oplus (a\cdot b)}$${\displaystyle c=0}$${\displaystyle a\cdot b=1}$

มี การสำรวจวงจรย้อนกลับ การสร้างและการเพิ่มประสิทธิภาพรวมถึงความท้าทายในการวิจัยล่าสุด^{[ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ]}

เครื่องจักรทัวริงแบบย้อนกลับได้ (RTM) เป็นแบบจำลองพื้นฐานในการคำนวณแบบย้อนกลับได้ RTM ถูกกำหนดให้เป็นเครื่องจักรทัวริงที่มีฟังก์ชันการเปลี่ยนสถานะที่สามารถผกผันได้ ทำให้มั่นใจได้ว่าการกำหนดค่าเครื่องจักรแต่ละแบบ (สถานะและเนื้อหาเทป) จะมีการกำหนดค่าก่อนหน้าได้ไม่เกินหนึ่งแบบ ซึ่งรับประกันความแน่นอนแบบย้อนกลับ ทำให้สามารถติดตามประวัติการคำนวณได้อย่างไม่ซ้ำกัน^{[ 15 ]}

คำจำกัดความอย่างเป็นทางการของ RTM ได้พัฒนาขึ้นในช่วงหลายทศวรรษที่ผ่านมา ในขณะที่คำจำกัดความในยุคแรกเน้นที่ฟังก์ชันการเปลี่ยนผ่านแบบผกผันได้ สูตรทั่วไปมากขึ้นอนุญาตให้มีการเคลื่อนที่ของหัวที่จำกัดและการปรับเปลี่ยนเซลล์ต่อขั้นตอน การวางนัยทั่วไปนี้ทำให้มั่นใจได้ว่าเซตของ RTM จะปิดภายใต้การประกอบ (การดำเนินการ RTM ตามด้วยการดำเนินการ RTM ส่งผลให้เกิด RTM ใหม่) และการผกผัน (ส่วนกลับของ RTM ก็คือ RTM เช่นกัน) ก่อให้เกิดโครงสร้างกลุ่มสำหรับการคำนวณแบบย้อนกลับได้ ซึ่งแตกต่างจากคำจำกัดความ TM แบบคลาสสิกบางอย่างที่การประกอบอาจไม่ให้เครื่องจักรในคลาสเดียวกัน^{[ 16 ]}พลวัตของ RTM สามารถอธิบายได้ด้วยฟังก์ชันการเปลี่ยนผ่านทั่วโลกที่แมปการกำหนดค่าตามกฎท้องถิ่น^{[ 17 ]}${\displaystyle A}$${\displaystyle B}$

อีฟส์ เลอแซร์ฟเสนอเครื่องจักรทัวริงแบบย้อนกลับได้ในบทความปี 1963 ^{[ 18 ]}แต่ดูเหมือนจะไม่ทราบหลักการของแลนเดาเออร์ จึงไม่ได้ศึกษาเรื่องนี้ต่อ โดยอุทิศอาชีพที่เหลือส่วนใหญ่ให้กับชาติพันธุ์ภาษาศาสตร์

ผลลัพธ์สำคัญโดยCharles H. Bennettในปี 1973 แสดงให้เห็นว่าเครื่องจักรทัวริงมาตรฐานใดๆ ก็สามารถจำลองได้ด้วยเครื่องจักรทัวริงแบบย้อนกลับได้^{[ 19 ]}การสร้างของ Bennett เกี่ยวข้องกับการเสริมเครื่องจักรทัวริงด้วย "เทปประวัติ" เสริม การจำลองดำเนินไปในสามขั้นตอน: ^{[ 20 ]}

1. คำนวณ:การคำนวณของเครื่องทัวริงดั้งเดิมจะถูกจำลองขึ้น และกฎการเปลี่ยนสถานะทุกข้อที่ใช้จะถูกบันทึกไว้ในเทปประวัติ
2. คัดลอกผลลัพธ์:ผลลัพธ์สุดท้ายบนเทปทำงานจะถูกคัดลอกไปยังเทปเอาต์พุตแยกต่างหาก ซึ่งตอนแรกจะว่างเปล่า การดำเนินการคัดลอกนี้จะต้องทำในลักษณะย้อนกลับได้ (เช่น โดยใช้เกต CNOT)
3. ยกเลิกการคำนวณ:การจำลองจะทำงานในทิศทางตรงกันข้าม โดยใช้เทปประวัติเพื่อยกเลิกแต่ละขั้นตอนของการคำนวณไปข้างหน้า กระบวนการนี้จะลบเทปงานและเทปประวัติ ทำให้กลับสู่สถานะว่างเปล่าเริ่มต้น เหลือเพียงข้อมูลป้อนเข้าดั้งเดิม (ที่เก็บรักษาไว้ในเทป) และผลลัพธ์สุดท้ายบนเทปเอาต์พุต

โครงสร้างนี้พิสูจน์ว่า RTM มีความเทียบเท่ากับ TM มาตรฐานในเชิงการคำนวณในแง่ของฟังก์ชันที่สามารถคำนวณได้ ซึ่งแสดงให้เห็นว่าความสามารถในการย้อนกลับไม่ได้จำกัดพลังการคำนวณในเรื่องนี้^{[ 20 ]}อย่างไรก็ตาม เทคนิคการจำลองมาตรฐานนี้มีค่าใช้จ่าย เทปประวัติสามารถเติบโตเชิงเส้นตามเวลาการคำนวณ ซึ่งนำไปสู่ค่าใช้จ่ายพื้นที่ที่อาจสูงมาก มักแสดงเป็น โดยที่และคือพื้นที่และเวลาของการคำนวณดั้งเดิม^{[ 19 ]}นอกจากนี้ แนวทางที่อิงตามประวัติยังเผชิญกับความท้าทายเกี่ยวกับองค์ประกอบเฉพาะที่ การรวมการคำนวณที่ย้อนกลับได้อิสระสองรายการโดยใช้วิธีนี้ไม่ใช่เรื่องง่าย สิ่งนี้บ่งชี้ว่าถึงแม้จะมีศักยภาพทางทฤษฎี แต่โครงสร้างดั้งเดิมของเบนเน็ตต์อาจไม่ใช่แนวทางที่ใช้งานได้จริงหรือมีประสิทธิภาพที่สุดในการบรรลุการคำนวณที่ย้อนกลับได้ ซึ่งกระตุ้นให้เกิดการค้นหาวิธีการที่หลีกเลี่ยงการสะสมประวัติ "ขยะ" จำนวนมาก^{[ 20 ]}${\displaystyle S'(n)=O(S(n)T(n))}$${\displaystyle S}$${\displaystyle T}$

RTM คำนวณชุดฟังก์ชันที่คำนวณได้แบบหนึ่งต่อหนึ่ง (injective) อย่างแม่นยำ พวกมันไม่ได้เป็นสากล อย่างแท้จริง ในความหมายแบบคลาสสิก เพราะพวกมันไม่สามารถคำนวณฟังก์ชันที่ไม่ใช่แบบหนึ่งต่อหนึ่งได้โดยตรง (ซึ่งสูญเสียข้อมูลโดยธรรมชาติ) อย่างไรก็ตาม พวกมันมีรูปแบบของความเป็นสากลที่เรียกว่า "RTM-universality" และสามารถตีความตัวเองได้^{[ 15 ]}

Vaire Computing ซึ่งตั้งอยู่ใน ลอนดอนกำลังสร้างต้นแบบชิปในปี 2025 เพื่อวางจำหน่ายในปี 2027 ^{[ 21 ]}

• Frank, Michael P. (2017). "อนาคตของการคำนวณขึ้นอยู่กับการทำให้สามารถย้อนกลับได้" (เว็บ) / "การโยนการคำนวณกลับด้าน" (สิ่งพิมพ์). IEEE Spectrum . 54 (9): 32–37. doi:10.1109/MSPEC.2017.8012237 .
• Denning, Peter; Lewis, Ted (2017). "คอมพิวเตอร์ที่สามารถทำงานถอยหลังได้". American Scientist . 105 (5): 270. doi : 10.1511/2017.105.5.270 . hdl : 10945/59278 . S2CID  125446656 .
• Glück, Robert; Yokoyama, Tetsuo (2023). "การคำนวณแบบย้อนกลับได้จากมุมมองของภาษาโปรแกรม" . วิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎี . 953 113429. doi : 10.1016/j.tcs.2022.06.010 .
• Lange, Klaus-Jörn; McKenzie, Pierre; Tapp, Alain (เมษายน 2000). "พื้นที่ย้อนกลับได้เท่ากับพื้นที่กำหนด" . วารสารวิทยาการคอมพิวเตอร์และระบบ . 60 (2): 354– 367. doi : 10.1006/jcss.1999.1672 .
• Perumalla KS (2014), บทนำสู่การคำนวณแบบย้อนกลับได้ , CRC Press
• Vitányi, Paul (2005). "เวลา พื้นที่ และพลังงานในการคำนวณแบบย้อนกลับได้". รายงานการประชุมครั้งที่ 2 เรื่องพรมแดนการคำนวณ – CF '05 . หน้า  435–444 . arXiv : cs/0504088 . doi : 10.1145/1062261.1062335 . ISBN 1-59593-019-1S2CID 5252384​ ​

• บทความเบื้องต้นเกี่ยวกับการคำนวณแบบย้อนกลับได้
• การประชุมเชิงปฏิบัติการนานาชาติครั้งแรกเกี่ยวกับการคำนวณแบบย้อนกลับได้
• ผลงานตีพิมพ์ของ Michael P. Frank: Sandia (2015-) , FSU (2004-'15) , UF (1999-2004) , MIT (1996-'99 )
• การประชุมเชิงปฏิบัติการ/ชุดการประชุมเกี่ยวกับการคำนวณแบบย้อนกลับได้
• การประชุมเชิงปฏิบัติการ CCC ว่าด้วยประเด็นทางฟิสิกส์และวิศวกรรมในการคำนวณแบบคลาสสิกเชิงอะเดียแบติก/ย้อนกลับได้
• ชุดเครื่องมือโอเพนซอร์สสำหรับการออกแบบวงจรย้อนกลับได้