QUANTUM computing
BACK TO BASICS
Figure 2. Analogy between interferometry in optics and quantum phase estimation with a quantum circuit. Left: interference between more waves leads to enhanced accuracy( sharper peaks) in the determination of the phase. Likewise, more phase qubits lead to a better precision.
outside of physics can also be regarded as many-body problems: a number of challenging optimization problems, like the famous travelling salesperson problem( find the shortest route to visit each city once and only once in a road network), can also be expressed as“ interacting” Hamiltonians. Here, instead of physical interactions, interactions translate the fact that the different conditions on the sought-after solutions are interdependent. Thus, quantum time-evolution algorithms that relax the system to its resting state— which is hopefully the solution to the problem— were developed in this field of combinatorial optimization. Specialized computers called quantum annealers were even specifically constructed for tackling these very problems, with a major limitation: in principle, reaching the resting state takes very long times …
A second large class of quantum algorithms combines the natural time evolution afforded by quantum processors with another central physical phenomenon called interference: as in optics, adding two( or more) coherent waves yields a signal where the phase difference between the waves is easy to read out( see Fig. 2). Likewise, quantum computers engineer interferences between two( or more) signals whose phase difference contains the solution to a hard problem [ 6 ]. This algorithm, called quantum phase estimation, underlies Shor’ s factoring algorithm:
the fact that the final distribution is peaked, as mentioned earlier, is a direct result of having many signals interfere in a smart way. Surprisingly, this phenomenon can also be used to invert systems of linear equations Ax = b. In this algorithm, the inversion is realized in a time that is exponentially faster than inverting the same linear system with classical algorithms [ 7 ]. Since linear systems are central to many application fields like solving partial differential equations, this has prompted many industrial companies to enter the field of quantum computing.
WILL QUANTUM COMPUTERS BEAT CLASSICAL COMPUTERS? With the increasing availability of prototype quantum processors at the turn of the 2010s, these optimistic ideas were put to the test of reality in the last decade. In particular, practical implementations all face the exponential fidelity wall that we discussed above. With the error rates of current prototypes, between 1 % and 0.1 %, the number of gates that can be executed before decoherence sets in is limited to a few hundreds or thousands. This rules out all algorithms based on interference, which use a quantum Fourier transform and / or long, and therefore gate-intensive, time evolutions: applications like factoring numbers or inverting linear systems of equations are out of reach due to current( and mid-term) noise levels. In fact, even drastic improvements will not
Photoniques 131 I www. photoniques. com 69