By -Tarun Kumar
Combining physics, mathematics and computer science, quantum computing has developed in the past two decades from a visionary idea to one of the most fascinating areas of quantum mechanics, in the last few years theoretical study of quantum systems serving as computational devices has achieved tremendous progress. Consequently, experimentalists around the world are engaged in tremendous attempts to tackle the technological difficulties that await the realization of such a large scale quantum computer. But regardless whether these technological problems can be overcome, it is noteworthy that no proof exists yet for the general superiority of quantum computers over their classical counterparts.
The philosophical interest in quantum computing is threefold: First, from a social-historical perspective, quantum computing is a domain where experimentalists find themselves ahead of their fellow theorists. Indeed, quantum mysteries such as entanglement and nonlocality were historically considered a philosophical quibble, until physicists discovered that these mysteries might be harnessed to devise new efficient algorithms. But while the technology for isolating 5 or even 7 qubits is now within reach only a handful of quantum algorithms exist, and the question whether these can solve classically intractable computational problems is still open. Coming to the algorithm design is a highly complicated task, and in quantum computing it becomes even more complicated due to the attempts to harness quantum mechanical features to reduce the complexity of computational problems and to “speed-up” computation. Before attacking this problem, we should first convince ourselves that quantum computers can be harnessed to perform standard, classical, computation without any “speed-up”. In some sense this is obvious, given the belief in the universal character of quantum mechanics, and the observation that any quantum computation that is diagonal in the computational basis, i.e., involves no interference between the qubits, is effectively classical. Obviously, if quantum algorithms could be used only to simulate classical algorithms, then the technological advancement in information storage and manipulation, encapsulated in “Moore’s law”, would have only trivial consequences on computational complexity theory, leaving the latter unaffected by the physical world.
Theoretical as it may seem, the question “what is quantum in quantum computing?” has an enormous practical consequence. One of the embarrassments of quantum computing is the fact that, so far, only one algorithm has been discovered, namely Shor’s, for which a quantum computer is significantly faster than any known classical one. It is almost certain that one of the reasons for this scarcity of quantum algorithms is related to the lack of our understanding of what makes a quantum computer quantum. Quantum computers, unfortunately, do not seem to allow such simple characterization.
April 2011, a team of scientists from Australia and Japan made a breakthrough in quantum teleportation. They successfully transferred a complex set of quantum data with full transmission integrity, without affecting the qubits’ superposition’s. And in May 2013, Google announced that it was launching the Quantum Artificial Intelligence Lab, hosted by NASA’s Ames Research Center, with a 512-qubit D-Wave quantum computer. The USRA (Universities Space Research Association) will invite researchers to share time on it with the goal of studying quantum computing for machine learning.