SOME THOUGHTS REGARDING PRACTICAL QUANTUM COMPUTING

Marco Lanzagorta, PhD

NCI/NRL/GMU

qubit@2020foresight.us

 

INTRODUCTION

  1. Moore’s Law: miniaturization packs more transistors inside microchips
  2. Miniaturization limit will be reached by 2020
  3. Moore’s barrier is a technological problem, not computational: CC model remains valid.
  4. Trivial solution: extend the size of microchip, causes several other problems.
  5. Impact on the future development of real-life software systems
  6. Example: Computer Graphics and Final Fantasy
  7. There is a clear need for a new type of computing hardware to continue with Moore’s exponential growth.

 

PART I: PROBLEMS WITH THE QUANTUM COMPUTATIONAL MODEL

 

THE QUANTUM COMPUTATIONAL MODEL

  1. Rule #1: Qubit vs. Bit.
  2. Rule #2: Probabilistic computing.
  3. Rule #3: Exponentially large computational space.
  4. Example: 800 qubits simulation of a toy model of the entire universe.
  5. Rule #4: Measurements are destructive.
  6. Rule #5: QC requires reversible logic.
  7. Rule #6: QC has intrinsic parallelism.
  8. Rule #7: No-Cloning, no-copying.
  9. QC is a computational model for superpositions.
  10. QC is a new type of hardware and a new computational model.
  11. CC still can work in QH.
  12. QC model can be reduced to CC by avoiding superpositions.
  13. Clear advantages of QC: Rules #3 & #6.
  14. Clear disadvantages of QC: Rules #4 & #7.
  15. Also, quantum algorithms on N qubits usually require the same number of ancillary qubits (this is not a problem or disadvantage per se).
  16. Quantum information processing: Use advantages, while avoiding the disadvantages, and be careful with the probabilistic nature of QC!
  17. Another solution: CC running with QH goes beyond Moore’s law barrier.

 

GROVER’S ALGORITHM

  1. Solves the unsorted, unstructured dataset search problem.
  2. Useless problem as it is: most datasets of interest can be sorted and ordered.
  3. Classical solution using some type of data structure for ordered datasets is much more efficient.
  4. A big problem: Grover only allows you to extract a single solution. For most practical problems you require the entire set of solutions.
  5. Another big problem: You need to know the exact number of solutions before the search, as otherwise quantum counting may become a very expensive operation.

 

MEMORY

  1. If we use a real database for any type of quantum computation, we require the data to be stored somewhere using a quantum memory without superposition (pseudo-classical quantum memory).
  2. Possible architecture: register has superpositions while cache does not.
  3. Therefore, the advantage of having exponentially large space goes away in the cache.
  4. If we use dynamically generated datasets, we may not require such a pseudo-classical quantum cache.
  5. Another problem: memory-addressing schemes are very complex and require a large number of quantum switches.

 

COPYING

  1. The destructive nature of quantum measurement and the no-cloning theorem imply that QC is great for cryptographic applications, because quantum information cannot be forged.
  2. But a general-purpose computational system may be completely useless if we cannot make copies; by analogy to CC it is difficult to think otherwise.
  3. Approximate copies are fine, but in practical situations that require multiple copies from a single original, the quality of these copies decreases very quickly and the original is completely lost.

 

LOGICAL DEBUGGING

  1. We cannot know the exact state of a quantum register.
  2. It seems to be impossible to debug the logic of a quantum program without measuring (and therefore destroying) the state of the register.
  3. This is a potential problem for large, time-consuming computations.

 

INPUT/OUTPUT

  1. Most probably, the only type of input for a quantum register will be the “0” state and simple generalizations such as the uniform superposition.
  2. Because of technological constraints, it may be impossible to force the initial state of a quantum register to point at an arbitrary input state.
  3. On the other hand, if the quantum register holds data in its superposition after a computation, we cannot output the entire dataset.
  4. We could output a single item with certain probability, but this makes QC highly inconvenient, as the entire computation has to be repeated multiple times until we extract the entire dataset.

 

SEMICLONING

  1. Semicloning is a quantum protocol that creates approximate copies while preserving the original, so it can be applied iteratively multiple times.
  2. Semicloning offers a partial and imperfect solution to the output problem, the register state estimation, the logical debugging problem, and the applicability of Grover’s algorithm.
  3. On the negative side, semicloning introduces more qubits and requires several more operations per computation.

 

COMPILERS & ORACLES

  1. All the details available in the literature regarding quantum compilers look fishy and incomplete to say the least.
  2. Compiling oracles for dynamical searches also looks extremely complicated.

 

FAST FOURIER TRANSFORMS

  1. The quantum version of the Fast Fourier Transform appears to be the single greatest advantage of QC over CC.
  2. The improved complexity of QFT is great news for optics, holography, image processing, signal analysis, simulation, graphics, data compression, and many other fields.
  3. This is true if, and only if, we can overcome all the other problems.
  4. Does QFT justify the problem of engineering large superpositions?

 

SHOR’S ALGORITHM

  1. Classical RSA cryptography is not perfectly secure.
  2. Computationally secure protocols solve key distribution problem.
  3. Perfectly secure protocols have the public key distribution problem.
  4. Shor’s algorithm can find the prime factorization of a large integer exponentially faster than any known classical algorithm.
  5. A QC running Shor’s algorithm could break exponentially faster RSA-type cryptocodes and become a threat to classical cryptography.
  6. The main motivation for QC is to obtain one working machine before anybody else.
  7. But note that it is possible that a classical algorithm for exponentially faster prime factorization of large integers does exist.
  8. Quite ironically, Shor’s algorithm offers QC an advantage over CC based on a non-proved fact: exact same problem as when we evaluate RSA! (RSA is secure as long as no classical fast factorization algorithmic is found) (QC is important as long as no classical fast factorization algorithmic is found).

 

QUANTUM CRYPTOGRAPHY

  1. If QC can break RSA-type codes, we will have to rely on quantum cryptographic protocols for secure communications.
  2. Another solution equally valid: create a new type of computationally secure protocol resilient against classical and quantum hacking (see below).
  3. Quantum Key Distribution protocols are perfectly secure, and solve the public key distribution problem.
  4. However, QKD protocols do not solve the authentication problem, and therefore do no offer any real practical advantage over current systems.
  5. Networking problem: so far, they are peer-to-peer protocols, and therefore useless in real scenarios.
  6. Real operational need for QKD today? Not really!

 

QC AS A SOLUTION TO NP PROBLEMS

  1. NP problems are solved in a classical computer in exponential time.
  2. QC has been proposed to solve NP problems in polynomial time.
  3. Some quantum algorithms solve NP problems in polynomial time.
  4. So far, only Grover’s algorithm offers a general solution to NP problems.
  5. However, Grover’s advantage is only rootic, the problem remains exponential, and therefore it is not very impressive.
  6. It may well be the case that some NP problems cannot be solved in polynomial time, even with QC.
  7. If so, maybe we could use one of these problems as the basis for a new classical key distribution cryptographic protocol.

 

PART I: PROBLEMS WITH THE QUANTUM HARDWARE

 

FINITE TEMPERATURE QUANTUM COMPUTING

  1. From a technological point of view, QC using isolated (“pure”) quantum systems may not be feasible.
  2. Most probably, QC will use ensembles of pure quantum states.
  3. Temperature mismatch problem: QC using ensembles of pure quantum states requires very low temperatures, while the classical circuits required to control the quantum gates are designed for higher temperatures.
  4. The technological issue of low temperature classical circuits for gate control presents a very difficult problem.
  5. Another solution is to develop a framework for QC at room temperature, but quantum dynamics at finite temperature is much more complicated.
  6. Limits, bounds and probabilities of quantum algorithms may have to be recalculated for a specific finite temperature.

 

SCALING

  1. All of the proposed technologies for QC face the so-called scaling problem: it is very difficult to scale the number of qubits in an arbitrary superposition.
  2. This does not mean that it is difficult just to have a bunch of qubits working together with no superposition. This is actually very easy to do.
  3. Trivial solution to the scaling problem: avoid superpositions in the engineering of next generation of computers, that is, use CC running with QH.

 

QUANTUM ERROR CORRECTION

  1. Quantum registers are extremely sensitive to the effects of noise.
  2. Quantum error correction codes are proved to protect quantum registers.
  3. A big problem is that QEC require a bunch of extra qubits: at least 5 qubits are necessary to encode 1 and protect it against arbitrary 1-qubit errors.
  4. Fault tolerant QC: we require even more qubits and computational steps.
  5. All things considered, QEC and FTQC require so many qubits to guarantee that a long computation is feasible, that the advantage of a computationally large space goes away very quickly.

 

CONCLUSIONS

  1. The practical application of QC as a general computational device is not as easy or straightforward as advertised in the literature.
  2. Most of the problems discussed here are usually ignored.
  3. These problems relate to the computational model as well as the hardware.
  4. QC is a good technology for specific problems, but not as a general tool.
  5. Remember: a machine that is a good FFT solver and a good quantum physics simulator does not imply a good computational platform.
  6. All things considered, it is not clear what are the advantages of QC over CC for general, real-life software systems.
  7. In spite of its popularity, QC has yet to find a killer application.
  8. Even if the hardware technology matures to the point of large scale QC, it may remain so inconvenient that it will never become a general computational tool (remember the beta vs. vhs battle in the 1980s).
  9. Unless things change in a radical way, and real practical applications with significant improvements over CC are developed, it is very likely we may end up with CC running in QH for a few more decades after 2020, and only dedicated devices will work with true QC.
  10. Return to a previous example: in the most optimistic scenario, the 800 qubit computer requires QEC (1/5), Cache (1/2), Semicloning (1/2), and Ancillary (1/2) qubits. Then, we end up with 800/40 = 20 qubits for algorithmic and information processing, or an effective quantum memory of 130 MB. This is not very impressive compared to today’s systems, and certainly it is not enough to simulate the entire universe. And remember, largest QC today is about 8 qubits.