Little Data With a Big Solution Space — the Sweet Spot for Quantum Computing

  1. In a nutshell
  2. Quantum computer as a coprocessor
  3. Centrality of quantum parallelism
  4. Quantum advantage is the whole point
  5. Quantum supremacy
  6. Combinatorial explosion
  7. The essential goal: exponential speedup
  8. Big solution space
  9. Little data — limited input data, limited results
  10. Little computation — quantum computations must be simple
  11. No, large computations are not appropriate for quantum computing
  12. Big data
  13. 3 Vs of big data
  14. Big data data models
  15. Structured big data is not amenable to quantum computing
  16. Big data graphs are not amenable to quantum computing either
  17. Big data images are not amenable to quantum computing
  18. Big data text is not amenable to quantum computing
  19. Semi-structured big data is not amenable to quantum computing
  20. Big data media is not amenable to quantum computing
  21. 3Vs of big data are not amenable to quantum computing
  22. Caveat — no good examples, yet
  23. Variational methods as little data
  24. Hybrid quantum/classical computing
  25. Shor’s algorithm exemplifies little data with big solution space
  26. Quantum computers have no I/O or database access
  27. Big data with a quantum computer
  28. Hadamard transform to achieve parallelism
  29. The basic model for quantum parallel computation
  30. The challenge: extracting results
  31. Extracting values from a large solution space
  32. Using interference to select values from a large solution space
  33. Quantum phase estimation (QPE) to extract a value
  34. Quantum Fourier transform (QFT) to extract a value
  35. How many qubits does a quantum computer need?
  36. Solution space size
  37. Shot count or circuit repetitions
  38. Circuit repetitions could dramatically reduce any quantum advantage
  39. Pay attention to net or effective quantum advantage
  40. Don’t forget wall clock time
  41. Classical sampling, Monte Carlo simulation
  42. Approximate solutions
  43. Input data and parameters for a quantum circuit
  44. Generally, at least twenty qubits will be needed for significant quantum advantage
  45. Generally, over fifty qubits will yield a dramatic quantum advantage — and even quantum supremacy
  46. But what about super-exponential problems?
  47. Will quantum error correction (QEC) be required?
  48. Where are we today?
  49. Will quantum computing ever be able to process big data?
  50. Caveat for D-Wave Systems
  51. What about IBM’s new quantum roadmap for one million qubits?
  52. Future advanced quantum computer architectures
  53. Universal quantum computers
  54. Conclusions

In a nutshell

  1. Little data in.
  2. Little computation in a big solution space. Quantum parallelism.
  3. Little data out.
  4. Repeat enough times to get a statistically-meaningful result.

Quantum computer as a coprocessor

Centrality of quantum parallelism

Quantum advantage is the whole point

Quantum supremacy

Combinatorial explosion

The essential goal: exponential speedup

Big solution space

Little data — limited input data, limited results

  1. Small amount of input data. And parameters.
  2. Relatively simple calculation applied in parallel to a very big number of combinations of the limited amount of input data. This is the big solution space.
  3. Extraction of a small amount of result data.

Little computation — quantum computations must be simple

No, large computations are not appropriate for quantum computing

Big data

3 Vs of big data

  1. Volume. Lots of data.
  2. Velocity. At a high rate.
  3. Variety. In a lot of different formats.

Big data data models

  1. Rows. Large number of linear rows of structured data.
  2. Graphs. With large numbers of nodes and edges.
  3. Images. Large numbers of large images, possibly with deep color.
  4. Text. Large amounts of unstructured text. Or semi-structured text.
  5. Semi-structured data. A combination of any of the above. Such as structured documents or XML files.
  6. Media. Audio, video, etc. Large sizes, in complex data formats.

Structured big data is not amenable to quantum computing

Big data graphs are not amenable to quantum computing either

Big data images are not amenable to quantum computing

Big data text is not amenable to quantum computing

Semi-structured big data is not amenable to quantum computing

Big data media is not amenable to quantum computing

3Vs of big data are not amenable to quantum computing

  1. Volume. No quantum advantage for big data.
  2. Velocity. Again no quantum advantage for big data.
  3. Variety. Not appropriate for quantum computing.

Caveat — no good examples, yet

Variational methods as little data

  1. Pick an initial trial value. Possibly at random or guided by some a priori domain knowledge about the problem. This is called an ansatz.
  2. Perform one iteration of the quantum calculation, producing an intermediate result.
  3. Use classical code to examine the intermediate quantum result and optimize it to guide it in a presumably more fruitful path — or decide whether it is close enough to a final solution to the problem. This optimization yields a revised ansatz.
  4. Rinse and repeat. Repeat steps 2 and 3 until either the classical code decides the quantum result is close enough to a final solution, or if so many iterations have been attempted without achieving an acceptable solution that continuing to search for a solution is fruitless — and the computation fails.

Hybrid quantum/classical computing

Shor’s algorithm exemplifies little data with big solution space

Quantum computers have no I/O or database access

Big data with a quantum computer

  1. A very small amount of data for each computation.
  2. A relatively small number of those computations.

Hadamard transform to achieve parallelism

The basic model for quantum parallel computation

  1. Initialize an n-qubit quantum register to a superposition of all 2^n discrete values of the range of the desired parameter to be varied using a Hadamard transform (H gate on each qubit.)
  2. Perform the desired computation on the n-qubit register. Any input values must be encoded in the gate structure of the quantum circuit.
  3. Transform the 2^n computation results (quantum states) to an n-qubit result register, such as using quantum phase estimation (QPE), a quantum Fourier transform (QFT), or some other method which exploits quantum interference to map the 2^n computed values (quantum states) to a single n-qubit value to be extracted from the solution space.
  4. Measure the n-qubit result register, producing an n-bit classical result.
  5. Perform classical processing on the n-bit classical measured result.
  6. Repeat the above to develop an expectation value (distribution) for the results. The shot count input parameter specifies how many circuit repetitions to perform. Exactly how to select the actual result from the distribution will depend on the application.

The challenge: extracting results

Extracting values from a large solution space

  1. Interference
  2. Quantum phase estimation (QPE)
  3. Quantum Fourier transform (QFT)

Using interference to select values from a large solution space

Quantum phase estimation (QPE) to extract a value

Quantum Fourier transform (QFT) to extract a value

How many qubits does a quantum computer need?

Solution space size

  1. 4 qubits = 2⁴ = 16 quantum states (or discrete values.)
  2. 6 qubits = 2⁶ = 64 quantum states.
  3. 8 qubits = 2⁸ = 256 quantum states.
  4. 10 qubits = 2¹⁰ = 1024 = 1K quantum states.
  5. 12 qubits = 2¹² = 4096 = 4K quantum states.
  6. 16 qubits = 2¹⁶ = 64K quantum states.
  7. 18 qubits = 2¹⁸ = 256K quantum states.
  8. 20 qubits = 2²⁰ = 1M (one million) quantum states.
  9. 24 qubits = 2²⁴ = 16M (sixteen million) quantum states.
  10. 28 qubits = 2²⁸ = 256M (256 million) quantum states.
  11. 30 qubits = 2³⁰ = 1G (one billion) quantum states.
  12. 40 qubits = 2⁴⁰ = 1T (one trillion) quantum states.
  13. 50 qubits = 2⁵⁰ = 1Q (one quadrillion or one million billion) quantum states.

Shot count or circuit repetitions

Circuit repetitions could dramatically reduce any quantum advantage

  1. Shot count = 10. Very unrealistic, but to establish a baseline or best case. Reduces 1,000,000 to 1 advantage to 100,000 to 1.
  2. Shot count = 100. Also unrealistic. Reduces 1,000,000 to 1 advantage to 10,000 to 1.
  3. Shot count = 1,000. Possible, but not guaranteed. Reduces 1,000,000 to 1 advantage to 1,000 to 1.
  4. Shot count = 2,000. Possible, but not guaranteed. Reduces 1,000,000 to 1 advantage to 500 to 1.
  5. Shot count = 5,000. Reduces 1,000,000 to 1 advantage to 200 to 1.
  6. Shot count = 10,000. Reduces 1,000,000 to 1 advantage to 100 to 1.
  7. Shot count = 50,000. Reduces 1,000,000 to 1 advantage to 20 to 1.
  8. Shot count = 100,000. Reduces 1,000,000 to 1 advantage to 10 to 1.
  9. Shot count = 1,000,000. Reduces 1,000,000 to 1 advantage to 1 to 1 — no advantage at all.

Pay attention to net or effective quantum advantage

Don’t forget wall clock time

Classical sampling, Monte Carlo simulation

Approximate solutions

Input data and parameters for a quantum circuit

Generally, at least twenty qubits will be needed for significant quantum advantage

  1. Shot count = 10. 24 qubits.
  2. Shot count = 100. 27 qubits.
  3. Shot count = 1,000. 30 qubits.
  4. Shot count = 2,500. 32 qubits.
  5. Shot count = 5,000. 33 qubits.
  6. Shot count = 10,000. 34 qubits.
  7. Shot count = 25,000. 35 qubits.
  8. Shot count = 50,000. 36 qubits.
  9. Shot count = 100,000. 37 qubits.
  10. Shot count = 250,000. 38 qubits.
  11. Shot count = 1,000,000. 40 qubits.
  12. Shot count = 10,000,000. 44 qubits.
  1. 19 qubits = 512K quantum states. Net quantum advantage 512.
  2. 18 qubits = 256K quantum states. Net advantage 256.
  3. 17 qubits = 128K quantum states. Net advantage 128.
  4. 16 qubits = 64K quantum states. Net advantage 64.
  5. 15 qubits = 32K quantum states. Net advantage 32.
  6. 14 qubits = 16K quantum states. Net advantage 16.
  7. 13 qubits = 8K quantum states. Net advantage 8.
  8. 12 qubits = 4K quantum states. Net advantage 4.
  9. 11 qubits = 2K quantum states. Net advantage 2.
  10. 10 qubits = 1K quantum states. Net advantage 1 — no net advantage.

Generally, over fifty qubits will yield a dramatic quantum advantage — and even quantum supremacy

But what about super-exponential problems?

Will quantum error correction (QEC) be required?

Where are we today?

Will quantum computing ever be able to process big data?

Caveat for D-Wave Systems

What about IBM’s new quantum roadmap for one million qubits?

  1. One million qubits or even 5, 10, 20, 50, or 100 million qubits just won’t cut it for truly big data. And even a single million qubits is a whole decade away, or more.
  2. It’s not clear if one million qubits is physical qubits or logical qubits. Either way is still not enough for big data. I suspect it is one million physical qubits, which at 16 to 25 physical qubits per logical qubit would have a capacity of 40,000 to 62,500 logical qubits, which is certainly not appropriate for big data.
  3. The 1,121-qubit Condor system planned for late 2023 still has a relatively limited capacity for data.
  4. Still no prospect of I/O, file or database access, or network connectivity to access large amounts of data from within a quantum circuit.
  5. Still no prospect for rich data and media types.
  6. Still no prospect for structured data.
  7. Still no prospect for complex processing, especially for large amounts of data. Still focused on the little data with a big solution space model detailed in this paper. The roadmap does refer to “feedback and feed-forward system capabilities, where we’ll be able to control qubits based on classical conditions while the quantum circuit runs”, but that is too vague and sounds too limited to suggest true complex processing, let alone for large amounts of data.

Future advanced quantum computer architectures

  1. Quantum communication.
  2. Quantum networking.
  3. Quantum measurement.
  4. Quantum sensing.

Universal quantum computers

Conclusions

  1. A quantum computation using anything less than 20 qubits will not deliver a substantial quantum advantage — like one million to one.
  2. Shot count significantly reduces the quantum advantage. If a shot count of 25,000 is needed, you would need a computation using at least 35 qubits for a single parallel computation before you would see a net quantum advantage of one million to one.
  3. Shot count may not scale well for some algorithms so that the net quantum advantage might be relatively small — 4 to 64 — even when a significant number of qubits are used.
  4. Some algorithms may always take longer than on a classical computer if the shot count is too high.
  5. A net quantum advantage of less than 256 may not be very useful since it is relatively easy to run a quantum algorithm in parallel on that many classical machines.
  6. Sure, you may be able to demonstrate quantum advantage on under 20 qubits, but it won’t be very impressive for computations using less than about 32 to 40 qubits.
  7. Although 50 qubits or so (maybe 53–60) is nominally enough to get to quantum supremacy, shot count requirements may add another 10 to 20 qubits to achieve quantum supremacy. 60–80 is a safer bet. And this is the number of qubits used in a single parallel computation, not total qubits on the machine or used by the overall algorithm.
  8. There may be applications which are very sensitive to wall clock time, so that even a very modest quantum advantage could be significant. But the potential of running the classical algorithm in parallel on dozens or hundreds of classical machines should be taken into account as well before deriving the true net quantum advantage.
  9. Even with IBM’s ten-year roadmap, we’re still limited to relatively small amounts of input data.
  10. The discussion here is based on current conceptions of quantum computer architectures — all bets are off for more advanced notions of quantum computer architectures, including some form of universal quantum computer which may in fact be perfect for super-big data.

--

--

--

Freelance Consultant

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jack Krupansky

Jack Krupansky

Freelance Consultant

More from Medium

Quantum Chemistry: Using Application-Specific Quantum Computers to Accelerate Pharmaceutical Drug…

Quantum Entanglement

Example vs. Reality. How can I train a Quantum Machine Learning model using data from a CSV?

Quantum computing: Genius or dangerous?