June 30, 2017

Quantum Computers

Quantum mechanics is a subject that has the strange property of simultaneously being logically rigorous and yet completely counterintuitive. So much so, that even a towering intellect like Einstein could never bring himself to accept its principles even though products based on the same exist all around us. The earliest oddity, identified by Schrodinger, one of the founders of quantum mechanics is about a hypothetical cat that is neither dead nor alive until someone actually observes it. A similar oddity is that of quantum entanglement, where the behaviour of one particle is instantly affected by the behaviour of another particle, however distant it may be -- an example of “spooky” action-at-a-distance. Explaining these phenomena is beyond the scope and temerity of this article and so the reader would have to accept them here in good, almost religious, faith and carry on with the belief that such phenomenon has been observed and explained by scientists under the most rigorous experimental circumstances.

Image borrowed from Quanta Magazine
Any programmable digital computer that we use, the desktop,the smartphone or the ones at Google, is based on a finite state machine (FSM). It can, at any instant of time, be in one of a large, but finite, number of well defined states. The state of a FSM is defined by the value stored in each of its memory locations and we know that these can either be 0 or 1. So an FSM with, say, 16 bits of memory could in principle be in any one of 2^16 states. Any instruction to the FSM changes the value of one or more bits and and the FSM moves to a different state. An FSM along with the ability to read binary input, from an infinite tape, and write back on the same tape, is the Turing machine that is the theoretical basis of any modern computer.

The fundamental principle of computer science is that the world is computable, meaning that any logically decidable problem can be represented and solved on a Turing machine and hence by extension on some, possibly very powerful, digital computer. This is the basis of our immense belief in computer technology that powers everything from smartphones to artificial intelligence. But even as long back as 1982, Richard Feynman had questioned this principle because he realised that Turing / FSM based computers could not solve the problem of simulating the movement of multiple particles whereas nature was doing it all the time! Did the quantum mechanical behaviour of nature mean that nature had a computing device that was inherently superior to the Turing machines built by classical computer technology? This is where the concept of a quantum computer was born.

A computer, is a state-machine where it’s state is defined by the collective states of each of its memory locations. In a classical computer, each memory location, or bit, can either be 0 or 1 certainly not both, but in a quantum computer it can be both 0 and 1 simultaneously -- very much like Schrodinger’s cat that was dead and alive at the same time!  This is where the going gets really rough for anyone who has spent a lifetime in classical computer science because this is something that is completely counter-intuitive. A memory location, a bit, is a transistor, or switch, made of silicon that is either ON or OFF. How can it be both? Turns out, that if you keep aside computer science and open your books on quantum mechanics, it is indeed possible that a body can be in two states at the same time based on the well established principle of quantum superposition. Now if we go back to our 16 bit classical computer with its 2^16 states and replace it with a quantum computer with 16 quantum bits, or qubits, of memory we have a machine that can be in 2^16 states simultaneously. If that is not mind-bending enough, all these 2^16 states will collapse into any one of the states as soon as we try to observe it. It is almost as if nature is playing a game with us, pretending to be classical whereas it is actually quantum.

But why are we obsessed with this counter-intuitive phenomenon? Will it have a drastic improvement on existing digital computer technology? Not really. Your spreadsheet, email, YouTube, eCommerce, smartphone will hardly change but two things could. First, current cybersecurity systems, that are based on our inability to decompose integers into their prime factors in a reasonable amount of time, could be ripped apart by quantum computers, leaving all passwords vulnerable to hackers. Second artificial intelligence could be taken to altogether and unbelievable levels of sophistication. So quantum computers will soon have a very important role to play -- but how far away are we from real, practical systems?

The biggest challenge is the construction of the physical memory locations and the complexity of the engineering problem is evident from the following : A modern IBM classical computer chip has anything between 2 and 7 billion transistors each of which can be ON or OFF. The corresponding IBM quantum computer chip, that powers the IBM Quantum Experience machine, has only 5, yes just 5, qubits of memory that can be in quantum superposition of ON and OFF. Why so? First, the memory locations have to be cooled to near zero Kelvin to exhibit their quantum superposition behaviour and if the cryogenic challenge was not enough, the second challenge is even bigger. Unlike the memory locations of classical computers whose state can be determined by sensing the presence or absence of an electrical voltage, the multiple, superimposed quantum states collapse as soon as any effort is made to observe them. This is as if a room has a house of cards that collapse as soon as the door is opened by the observer and the observer has to figure out what the house looked like by observing the disposition of the cards on the floor! Since the qubits can never be accessed directly, as in a classical computer with read and write statements, they can only be “influenced” indirectly.

To put things in perspective, ENIAC, one of the world’s first, 1st generation, vacuum tube based classical computer had 20 memory units, or accumulators, in 1945, and a 2nd generation, transistor-based computer from the University of Manchester had only 200 transistors in 1955. Since then we have moved through 3rd generation integrated chips and the current 4th generation of microprocessors have scaled up to billions of transistors thanks to the inexorable pressure of Moore’s Law. If we remember that even with its 20 memory units, ENIAC was used to solve problems in weather forecasting, atomic energy calculations, wind tunnel design, the current 5 qubit IBM machine does not look as hopeless, or helpless, as it seems to be.

But actually things are a little better off. D-Wave a Canadian company that has been building quantum computers since 1999  have come out with a 128 qubit machine in 2010, a 512 qubit machine in 2012 and 1000 qubit machine in 2015. Initially there were some doubts about whether these were quantum machines at all but after these machines were actually installed and used first by Lockheed Martin at the University of Southern California and later at the Quantum AI Lab of NASA Ames Research Centre by a team from Google, these doubts have receded to a large extent. But even though some doubts persist, there is enough evidence of quantum behaviour or at least great promise that these doubts will be removed soon. In early 2017, D-wave announced the sale of their first, commercial available $15 million 2000-qubit machine to cyber-security firm, Temporal Defence Systems.

IBM’s 5-qubit Quantum Experience is positioned as general purpose computer. It could be used for any computational task but would be efficient only if the program was designed to use quantum properties -- a colour TV is useful only if the broadcast is in colour. Very few programs can do this today but Shor’s algorithm, used to crack passwords, is definitely one such. D-Wave systems on the other hand are designed to solve one class of problems that minimise the weighted sum of large number of interrelated, or entangled, variables. This may sound restrictive but the reason why everyone from Google to Temporal is interested is because this class of problems is similar to the ones that occur in artificial neural networks that lie at the heart of systems based on machine learning.

Spectacular progress in machine learning with artificial neural networks using classical computers itself, is rapidly closing the gap between biological and nonbiological intelligence or even between carbon and silicon “life-forms”. With the advent of quantum computers one more crucial barrier between the natural world and it’s man-made, artificial model could break down -- as could the increasingly thin line that delineates man from machine. Will this drag man down to the level of machines? Or will these machines push man up towards his eventual union, or Yoga, with the transcendent omniscience that some refer to as God or Brahman?


This article originally appeared in Swarajya -- The magazine that reads India right!

June 03, 2017

Order, Stability or Chaos?

Global, national and local societies face many threats. We are threatened by enemies -- internal and external -- who want to destroy our way of life. We are plagued with environmental degradation as we quickly try to ramp up the economy and improve our living standards. Finally our own social systems are in tatters because efforts to mitigate the effects of the first two reasons are stymied by venal corruption and a cynical disregard for the rule of law. In fact the last reason is perhaps the most over arching reason, because it leads to the other two.

image from 5rhythms
We have solutions to most of our problems. Technology solutions are available to grow more food, generate more energy, combat disease and check crime. There are public structures like hospitals, schools, municipal, state and central governments, the legislature, each having its own set of rules and procedures, to guide and govern matters. There are commercial structures, like corporates, cooperatives and professional networks that transform natural and human resources into disposable surplus that can be used for material pleasure. Then there are clubs, non-profits and political parties that lubricates the gears and facilitates the work of the public and private structures. Finally, we have a whole set of checks and balances, like police, the courts of law, and institutions that recursively keep checks on the checks and balances, like Vigilance Department, the CBI and the LokPal to ensure that everyone does what they should. So in principle, if everything were to work like clockwork, there should not be any unresolved problems on the planet.

But obviously this is absurd. Unlike the precise determinism of classical mechanics, the social mechanism that governs society is based on the non-deterministic behaviour of human beings. No two persons are alike and so no two will respond to a situation in an identical manner. One may be afraid to break the law even if there is a benefit but another may be willing to do so. So there is an element of randomness that permeates society and it is this randomness that is key determinant of social outcomes.

Randomness leads the environment from order to disorder. Physics equates disorder with entropy and the Second Law of Thermodynamics states that entropy of a closed system can only increase over time. In fact the direction of the “arrow of time” is often determined by the level of entropy between two states of the system. Information theory also associates entropy with randomness. Uncertain, random events are associated with high information content and hence high entropy. Certain events, like the daily sunrise, that have a probability of 1, are associated with zero entropy, as are impossible events like a horse giving birth to a dog, that have a probability of 0. But entropy is high when there is uncertainty and unpredictability as in the outcome of a toss of a fair coin, the results of an election or a war.

Increase in entropy, in randomness, in unpredictability, leads to chaos that can be analysed in terms of Chaos Theory. Chaos is the inevitable outcome of any adaptive, dynamic and complex system which is exactly what human society is. Chaos is unpredictability in the face of apparent determinism -- and as Edward Lorenz puts it so elegantly, Chaos is when the present determines the future, but the approximate present does not approximately determine the future. What this means is that a slight change in initial conditions -- a crow flapping its wings in Calcutta -- can cause a major upheaval far away -- a tornado in Texas. Mapped to human society, it means that social uncertainty caused by the erratic, unpredictable behaviour of a even a small group of people can cause ripples and upheavals across the world.

Chaos theory allows for strange attractors, or periodic repetitions of somewhat predictable outcomes, which is why human society settles into equilibria that gives us a sense of stability.  But given its colossal complexity even one incident, like 9/11, can tip it into a new, possibly more uncomfortable and anarchic equilibrium. Complexity is in fact impossible to manage in large organisations which is why we have the eventual collapse of centrally governed empires -- the Kaurava, the Pharaonic, the Roman, the Mauryan, the Holy Roman, the Ottoman, the Mughal, the British, the Soviet and finally the European Union. We can only hope that India will not join this list. Well governed human societies are based on the rule of law and order and it is this order that is under threat from the Second Law of thermodynamics and Chaos Theory. While we all crave for order, the reason why we rarely attain it is because the laws of the universe inexorably push us towards disorder and anarchy.

But will entropy always increase? Not really. In a small closed system -- as in a school, a company, a factory, a state like Singapore, or perhaps a human colony on Mars -- it is possible to reduce the local entropy within the system and impose perfect order, but this needs one of two prerequisites. Either we need an external agency imposing order from outside -- a non-popular dictatorship -- or there has to exist a mechanism of self-organisation, that resolves contradictions and guides the system towards greater order. A small school or factory is an example of the first while well governed US cities that are cleaner and more habitable than anarchic municipalities in India is an example of the second.

But even in a small society, that is somehow isolated from the random anarchy of the global environment, the ability to self regulate is not guaranteed. Self regulation is actually an outcome of enlightened self-interest that seeks to create the proverbial win-win situation that benefits all at the cost of none. But this is not easy. To understand why, consider the Prisoner’s Dilemma, a special case of a mathematical oddity called Nash Equilibrium that is a part of Game Theory.

Consider two persons who have been arrested for a murder but the police do not have any clinching evidence, with which they can ensure a conviction. So both prisoners are offered a plea-bargain offer. If any one turns approver and betrays the other, then the betrayer will be let off but the other will serve twenty years in jail. If both turn approver, then both serve ten years in jail. But if both cooperate and neither betrays the other, then the police will imprison them for a year on a lesser crime. Unfortunately, neither do the prisoners have any knowledge of what the other prisoner will do and nor do they trust each other. Ideally neither should betray the other, because this will ensure light punishment for both which is the best solution. But in reality, given the uncertainty, neither will trust the other, both will betray each other and so ensure ten year hardship for both. A classic lose-lose scenario.

This scenario is reflected in many real life situations like women wearing makeup to look more elegant, athletes using steroids to enhance performance, over-exploitation of resources like fishes or minerals, countries spending money on arms and ammunitions, countries refusing restrictions on environmental pollutants that hamper economic growth, advertisers spending money to push competing products or bidders at an auction being afflicted with the winner’s curse. In India, aggressive drivers break traffic rules to squeeze past others and in the process create  massive traffic jam whereas everyone could reach home earlier by waiting and obeying traffic rules.

If only people would cooperate with each other, the world will be a better place but the inexorable laws of Game Theory says that this will never happen. If all political parties were to cooperate on matters of national interest, like implementing labour reforms or fighting Islamic terror, many of the social and economic problems that bedevil India can be quickly eliminated but as in the case of the Prisoner’s Dilemma, each political party thinks that cooperating with the other means sealing one’s own electoral fate and facilitating a landslide victory for the other.

Human society is in a bind. The Second Law and Chaos Theory pushes us towards anarchy while Game Theory prevents us from self-organising. So we are forced to reconcile ourselves to a chaotic future. Given the inevitability of chaos in complex systems, our only hope for stability and order would be to have smaller, simpler systems that are easier to manage. Small states, municipalities, panchayats and even gated communities, where the number of players, or variables, is small and where complexity is manageable, have a far better chance of avoiding anarchy.  Going forward, as complex social and security challenges -- both international and now more often intra-national -- overwhelm the world, a loosely-coupled federation of small, self-sustainable, technology enabled, well-managed, elitist communities or “smart-cities”, spread across the Earth and nearby planets, may be the only way towards a reasonably stable future.

The Prisoner’s Dilemma and the inability of people to collaborate for the common good may be a persistent roadblock on the path to global peace with prosperity.


This article first appeared in Swarajya - the magazine that reads India right