In August 2016, China\u2019s first,\nand also the world\u2019s first, quantum communication satellite \u2018MoZi\u2019 was\nlaunched. In June 2017, the world\u2019s first experiment on quantum information\nacross the earth and space \u2013 the separation of a pair of entangled photons over\n1200km \u2013 was realised through the satellite. The first quantum computer was\nsold by the Canadian company D-Wave at a price tag of USD10 million in 2011.\nGoogle established its quantum AI lab in 2013. IBM made a 50 quantum-bit cloud\ncomputer in 2017. Over the past decade, the topics of quantum information and\nquantum computation have appeared constantly in media; but what do they really\nmean? Would we stop using the current computers and switch to quantum computers\nin the future? <\/p>
Probabilistic Algorithm and Parallel Computing<\/b><\/p>
To answer these questions, we\nhave to begin our story in the last century. With the invention of the\ntransistor in 1947 and the integrated circuit in the 1950s, the power of\ncomputers greatly increased. Computer scientists made use of the newly acquired\npower to solve problems that are beyond the calculation capacity of humans,\nsuch as factoring large integers or encrypting messages by scrambling some\nspecial functions. To reduce computation complexity and thus elevate the\ncomputing speed in these tasks, the scientists proposed what they called\n\u2018probabilistic algorithms\u2019 to compress the computing time from days to minutes\nby increasing the parallel concurrence in the algorithms. <\/p>
In order to appreciate the\ndifference of probabilistic algorithms from regular algorithms we can consider\na specific example: for example, to find the factors of 14. Besides the trivial\nfactors 1 and 14, the stupidest way to solve the problem is to try dividing 14\nby the numbers 2 up to 7 one-by-one. If it is divisible with a remainder of 0,\nthen we can determine the relevant number is a factor. Computers are good at\ntrying one-by-one. Hence, it\u2019s easy to figure out that 2 and 7 are the only two\nfactors for 14 and these brute-force methods are also easy to program. However,\nwe would soon realise that the brute-force methods are useful to deal with\nintegers within 100,000 or 1,000,000 given a powerful computer. If we are to\ndeal with an integer with, say, 14 digits, we are going to hit a brick wall\nsince the number of integers we need try dividing is simply too many. <\/p>
Parallel computing is our\nsaviour. Suppose we use two computers to try factoring 14, one trying the\nfactors from 2 to 4 and the other 5 to 7; then the computing time is\ninstantaneously reduced to half the original. In other words, if the processing\nunit of a computer can integrate N computing cores, the computing time\ncomplexity would be reduced to 1\/N. Nonetheless, this type of simplification is\nstill not efficient enough for factoring a very large integer. <\/p>
Yet, if we are allowed to try\nfactoring randomly, the efficiency of successfully finding a factor would be\ngreatly improved, probabilistically speaking. For instance, we have six numbers\n2, 3, 4, 5, 6, 7 between 2 and 7. If we do the division of 14 not sequentially\nbut by picking randomly the candidate factors from these six numbers, it\u2019s\nlikely that the first one we pick is 7 and the second one 2. In that case, we\ndon\u2019t even need to try 3, 4, 5, and 6 before we have found all factors of 14.\nThis is the motivation behind the so-called \u2018probabilistic algorithms.\u2019<\/p>
<\/p>
The Merits of Quantum Computing<\/b> <\/p>
Inspired by the concepts of\nparallel computing and probabilistic algorithms, Deutsch, C C Yao, and other\ncomputer scientists employed the world view of quantum mechanics \u2013 a system can\nretain a superposition state to simultaneously coexist on two different\nphysical settings \u2013 in 1980\u2019s to have invented the mathematical model of\nquantum Turing machines. In other words, supposing every integer between 2 and\n7 can be represented as a physical state, we then only need one quantum system\nto form their superposition state and try out the factors in parallel without\nincreasing the number of computing cores.<\/p>
Meanwhile, since there is a\nprobability associated with each state of integer out of the collective\nsuperposition state, these probabilities would increase or decrease\nconcurrently through the execution of quantum algorithms. The probabilities\nassociated with the real factors of 14 would gradually approach 1 in\nconsequence. Therefore, the advantage of quantum computation is that it reduces\nthe consumption of memory space while alleviating the computing time in\ntemporal complexity. Shor of Bell Laboratory proposed just such a probabilistic\ninteger-factoring algorithm geared specifically for quantum computer in 1995.\nBut so far quantum computation still rests on paper. <\/p>
After the year 2000, quantum\nphysicists including Girvin, Martinis, and Tsai successfully fabricated what\nthey called superconducting quantum-bit (or qubit) systems by carefully\nmanipulating the Josephson effects on superconducting materials. Thereafter,\nthe superposition state necessary for quantum computation can be generated in a\nsolid-state circuit in a controllable fashion. The Martinis group has\nimplemented Shor\u2019s algorithm to factor the integer 15 using a superconducting\ncircuit comprising four qubits.<\/p>
It seems then the making of the\nquantum computer has already succeeded and we can make a head start on\ncommercialising them. But in reality, there is a long road ahead before one can\nbuy a personal quantum computer. The two most imminent problems are: (i) the\neffective data storage time in a qubit is not sufficiently long, being only on\nthe scale of microseconds; and (ii) the scaling mechanism to share data across\nqubits has not yet existed. The latter is also the reason why we can only\nfactor a small integer like 15 so far. Therefore, one of the current research\ndirections in our research group at UM is to make use the properties of\nsolitons on superconducting circuits to prolong the effective storage time,\nthus solving the first problem. <\/p>
\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n<\/p>
But even if the two\naforementioned problems are completely solved, does that mean that the mission\nto conquer quantum computation is accomplished? Not quite. Because up to now we\nare only using the principles of quantum mechanics to improve the algorithms\nfor factoring, searching, etc. within the conceptual framework of conventional\ncomputers. Is it possible to employ the postulates of quantum mechanics to\nexceed the given structure of Turing machines, making some tasks originally\nincomputable computable? About this, we do not yet know the answer.<\/p>
The author is an associate\nprofessor of the Institute of Applied Physics and Materials Engineering,\nUniversity of Macau. He has established the cryogenic quantum computation\nlaboratory and conducted research studies on quantum optics and quantum\ninformation processing using superconducting circuits. Through his research\nexperience at the Institute of Theoretical Physics of the Chinese Academy of\nSciences, he has developed an interest in astrophysics, and currently teaches a\ngeneral education course on the mysteries of the universe.<\/p>
<\/p>