When I was a teenager, I believed that we could compute everything thanks to computers. But soon, as an undergraduate, I quickly found their limits. We call them “NP-Complete” cases in software engineer words. Something as simple as finding the best way to deliver packets to hundreds of cities or arrange the packets of different sizes in a truck is untrackable for current computers. This leads, for instance, to tons of waste in time, energy, and profit for supply chains.
But the hope was renewed last year, thanks to IBM and Google’s POC and commitment to quantum computers. They will get it to work. It’s possible; they understood how. It seems magic: a weird computer able to manipulate petabytes encoded only in few atoms. How could this be possible? No one knows, but we know that it does work. Einstein himself could not believe it until he proposed the experiment that proved it. Here is the trick: benefit from the strange quantum behavior of matter to enhance our computers and, thanks to this, optimize the routes and loads of the traveling salesmen.
Quantum Computers (QC) promises to be ways faster than our current computers. It seems appealing; you would like to start to master this next revolution, you start some tutorials, and then you realized that you have to face complex-valued matrices, qubits, and probability distributions… The entry cost for a classical programmer is high.
Fortunately enough, a guy named Toffoli already thought about this and came up with a theory named Reversible Computation. The idea is straightforward: mapping every classical (binary) to quantum (qubit) operation.
Wait, I heard it is impossible to perform every classical computation based on a quantum computer but only specific ones ?! Yes, it is true… under some hypotheses, like using only pure quantum operations, which will never be the case since initializing and measuring a qubit are both non-quantum operations. This is what used Toffoli to bypass the so-called “non-cloning theorem” and achieve a complete mapping between classical and quantum logic: adding ancillae and allowing qubit initialization and measurement to complete the truth table.
Then in principle, it is possible to compile and run any classical software on a Quantum Computer. But, wait a minute. The advantage of using Quantum Computing is speed, and by using Toffoli’s computation, the number of elementary operations is conserved from the classical program. Ok, then, at this step, this general quantum compiler works but is useless. Can this be solved thanks to an optimization step? It might, but it is not sure because optimizing a quantum program is an “NP” problem; in other words, there is no general solution at the theoretical level, even if good solutions can be found in practice. So we have to try in practice.
The best strategy to compress a quantum circuit is often to use the so-called ZX-calculus, a graph representation that allows modifications helpful to reduce the size of the circuit.
Using both tricks, Reversible Computing and ZX optimization can lead to a general way to benefit from quantum computing, starting only with a classical program written in Python or Java and run it on an IBM quantum computer, for instance. All of this without understanding a clue about matrix multiplication. Wonderful, isn’t it?
We are implementing this at ColibrITD, the startup that will provide the best framework as the surfboard to ride the upcoming quantum computing revolution wave.