#7/100: Classical reversible instructions || Quantum Computer Programming in 100 Easy Lessons

In this lesson, Ryan O’Donnell introduces the concept of classical reversible instructions in quantum computing. He begins by distinguishing between edge-case instructions (like new qubit and extract all) and main instructions that manipulate qubit states. He then focuses on a set of basic classical reversible instructions: toggle (NOT), if A then toggle B (CNOT), and if A and B then toggle C (CCNOT), along with composite ones like OR, NOT-controlled, and SWAP. He explains that these instructions are called ‘classical’ because they map basic states to basic states, meaning they would make sense if the variables were classical bits. However, not all classical bit operations are valid quantum instructions; for example, setting a variable to 1 is not allowed. The key property that makes an instruction valid is reversibility: every valid qubit manipulation must have an undo instruction. He illustrates this with the toggle instruction, which is its own inverse, and the left cyclic shift, which requires a right cyclic shift to undo. He emphasizes that reversibility is a fundamental law of physics and that all valid classical-type instructions must be reversible. The lesson concludes by noting that these basic instructions can be combined to build more complex operations, and that future lessons will cover superposition-creating instructions.