CAPTCHA and Quantum Supremacy
I would like to run a very secure and safe city, I want everyone to quarantine for two days before I let them in. How do I manage to do this at all costs, without relying on a centralized authority and ensuring this happens even at the cost of all forms of collusion with the security? The only law then I can rely on are the laws of nature, ones that are impossible to break but easy to verify. I devise a tunnel as the only entrance to my city. These tunnels fit a person, it can fit no vehicles, no contraptions that would allow them to go faster. If the tunnels are long enough to take a healthy person atleast two days to walk, it'll ensure that a person has gone through a quarantine of two days before they could enter my city.
I hadn't realised, but this is similar to the idea of Proof of Work that is being employed in popular blockchain ledgers, such as Bitcoin ledger. Rather than walking for two days to reach the city, we talk about performing computation to add transactions to the ledger. The computation is devised in a way that brute-force calculation is the only way to do so. The computation is performed by miners that are rewarded for their computation only if they find a solution, else their computation is gone to waste. To add a set of transactions to the ledger, the miner needs to calculate billions of hash values and find one that starts with x number of 0s. The number x is adjusted so that the total computation happening across the world combined to find it takes approximately 10 minutes. This is a simple way to ensure that set of transactions are added every 10 minutes. What happens when computation power increases? We increase x. In analogy, it is similar to increasing the length of the tunnel when the average walking speed has increased.
Walking back to tunnels, what if I want more from the mechanism? Let's say there is an outbreak of this hypothetical disease that does not allow people to climb too many stairs at once, when an infected person tries to do so they lose their ability to walk for a few days, let's call it "The Climber's Knee." This disease activates within one day and takes longer than two days to fade. It is very absurd and wonky, but bear with me. I want to improve my tunnels to ensure that only a healthy, i.e. a non-infected person is able to make it. If I put a bunch of stairs at the end of tunnel, then I would be certain that this person has been in quarantine for two days, and has not been infected when he reaches the top.
I have now made my mechanism stronger, not only it ensures that a person goes through quarantine, but also they make out of it only if they are healthy. Climbing stairs is an easy task for the healthy, impossible for the infected. This core mechanism is used to tell apart entities across a lot of different domains. It's a very simple and generic idea but I find it very powerful.
The Perfect CAPTCHA
CAPTCHA's are different from traditional cryptography, they are more ad-hoc and not based on any particular laws. Their reliability is often due to the closed-sourceness. We define a perfect CAPTCHA by a task which is easy to certify, impossible for bots to solve but a mere chore for humans. The nature of this problem make it impossible to have a tunnel-like mechanism due to a blur-line that splits bots and users.
We shift to an easier setting of the problem, what if there is a way of climbing the stairs at the end of tunnel by paying someone to carry you but it is quite expensive, and you'd rather just wait out till you are okay. This problem is no longer bounded by physical laws, but of financial ones. We separate the ones that are infected, as well as poor from the rest. Brutal, but this analogy makes sense in the CAPTCHA setting. We distinguish a human from a bot that has limited computing time and power, i.e. finance limitation. This problem is still relevant, because beyond a certain cost, it would be cheaper to hire a human to break it for you with ease rather than create a bot for it. As AI advances, the problems would have to get more creative to avoid the pitfalls of being solved by strong image models that are well capable and do not consume too much compute resource. This field is vast, and we leave the discussion of CAPTCHA at this state to move on to something more tangible.
Achievable Quantum Supremacy
We have talked about the physical impossibility, and we defined the notion of financial impossibility for given hardware status. When we are talking about CAPTCHA, it is difficult to measure this mathematically, or provide fundamental guarantees. That also explains the closed-source nature of their mechanism. Now we shift our problem to quantum supremacy, which can again be backed by physical laws.
So far it has been difficult to find a use-case of quantum computing that have an edge over their classical counterparts. It is theoretically established that a quantum computer can do whatever a classical computer can, but we are yet to get a provable problem that a quantum computer can certainly do much faster than what our classical computers can. Finding such a case where the quantum computer is able to compute a solution which our current classical computers did not manage to would be quantum supremacy.
But what we require is very different, theoretical limits of a classical computers are very far from what we can compute on our computers today. We require a solution that can be certified but not computable on the current state-of-the-art classical computers. This solution would be a computation that would be done on nature, a computation which humans can't artificially create, but one that requires computation impossible by current standards to even reverse-engineer the solution as one could do with factoring.
Financial way of verification
A non-theoretical way of verifying quantum supremacy would be to reverse the winning direction. Let's say we are talking about a task that is financially profitable, and by minimizing the resources required to perform this task would increase their profit margin. If a company claims that their quantum computer managed to solve this task, and it hasn't been solved by any classical computer we can trust their claim with high confidence. We do so because if the company had solved a task that no one else had classically, then it would be more beneficial for them to claim classical solution as it would be more feasible and profitable than running it on quantum computer. Such verification reduces the margin of advantage a quantum computer would have to show over the current classical computers, but would have to provide utility to the world.
Why not factoring? Details
Shor's algorithm has an exponential advantage over the current classical algorithms. One could think that this could be sufficient to prove quantum supremacy. Just try factorizing a number no classical computer can currently factor? The issue here is that it is difficult to verify whether the number picked to factor was not artificially chosen to be a product of known primes. If the party giving the number and factoring the number collude, this test would be easy to pass.
Suppose a company claims quantum supremacy by factoring a number N=pq such that p and q are very large primes. It is not testifiable that the company did not pick these numbers before hand and multiplied them, multiplication is much easier than factoring. If the company claims they did not pick the number, but a separate party gave them, it is still easy to doubt, as there is very little guarantee that the parties did not decide N beforehand. Theoretically and practically, factoring is not the tunnel we are hunting for.
The hunt for quantum supremacy is the hunt for stairs that current classical computers can't climb anytime soon, but a quantum computer was succcessful at.