Where Are All of the 40-qubit Quantum Algorithms?

  1. Motivation for this paper
  2. My goal: Encourage development of scalable 40-qubit quantum algorithms
  3. This is my challenge — I’m throwing down the gauntlet — I want to see a lot of 40-qubit quantum algorithms within two years
  4. Toy quantum algorithms
  5. Industrial-strength quantum algorithms
  6. Production-scale quantum algorithms
  7. Are any real quantum algorithms using more than 23 qubits?
  8. Late breaking news: Google has simulated up to 30 qubits for Quantum Machine Learning
  9. Google quantum supremacy experiment used 53 qubits, but not to solve a practical problem
  10. Why limit to 40 qubits?
  11. What’s the big benefit of 40 qubits?
  12. Scaling is essential — 40 qubits is merely a stepping stone
  13. What is dramatic quantum advantage?
  14. Don’t we already have real quantum computers with more than 40 qubits?
  15. Quantum Volume of at least one trillion is needed to support 40-qubit quantum algorithms
  16. NISQ quantum computers can’t handle 40-qubit quantum algorithms
  17. Technically, 43 qubits may be needed for 40-qubit quantum parallelism
  18. There just aren’t many 40-qubit quantum algorithms published
  19. It’s a chicken and egg problem
  20. My suggested solution: Simulate 40-qubit quantum algorithms now, be ready for real quantum computers when they become available
  21. Simulation is the best near-term path to supporting 40-qubit quantum algorithms
  22. Target qubit fidelity of 2–5 years from now
  23. So, why isn’t this happening? Where are all of the 40-qubit quantum algorithms?
  24. Why aren’t there any 40-qubit quantum algorithms?
  25. A sampler of excuses for why people aren’t focused on 40-qubit quantum algorithms
  26. Significant resources needed to simulate quantum circuits with a large number of product states
  27. Qubits, circuit depth, and product states
  28. Deep circuits and product states
  29. Is circuit depth a big issue for 40-qubit quantum algorithms?
  30. But in theory, simulating 40 qubits should be practical
  31. In short, there’s no technical excuse for lack of 40-qubit quantum algorithms which can run on simulators
  32. Mindset obstacles to 40-qubit quantum algorithms
  33. Is a focus on variational methods holding back larger algorithms?
  34. Need for fine granularity of phase and probability amplitude
  35. Shouldn’t the promise of support for quantum phase estimation (QPE) and quantum Fourier transform (QFT) be sufficient to draw a focus on 40-qubit quantum algorithms?
  36. Future demand for quantum phase estimation (QPE) and quantum Fourier transform (QFT) will eventually drive 40-qubit quantum algorithms
  37. No real need for 40-qubit quantum algorithms until quantum phase estimation (QPE) and quantum Fourier transform (QFT) create a need
  38. Why little publication of 40-qubit quantum algorithms even if simulation is limited?
  39. Any 40-qubit quantum algorithms in the Quantum Algorithm Zoo?
  40. My full solution: A model for scalable quantum algorithms
  41. Tackling practical, production-scale real-world problems
  42. Will 40-qubits get us to The ENIAC Moment for quantum computing?
  43. Will 40-qubits get us to The FORTRAN Moment for quantum computing?
  44. What would resource requirements be for various application categories?
  45. 40-qubit quantum algorithms which I may not be aware of
  46. Dramatic need for additional research
  47. Open source
  48. What’s a PhD candidate or thesis advisor to do?
  49. Timeframe
  50. Who’s on first?
  51. When will all quantum algorithms be 40-qubit?
  52. Take the 40-qubit challenge!
  53. Inspire the hardware vendors to support 40-qubit algorithms
  54. Summary and conclusions

Motivation for this paper

My goal: Encourage development of scalable 40-qubit quantum algorithms

This is my challenge — I’m throwing down the gauntlet — I want to see a lot of 40-qubit quantum algorithms within two years

Toy quantum algorithms

Industrial-strength quantum algorithms

Production-scale quantum algorithms

Are any real quantum algorithms using more than 23 qubits?

Late breaking news: Google has simulated up to 30 qubits for Quantum Machine Learning

  • TensorFlow Quantum: A Software Framework for Quantum Machine Learning
  • Michael Broughton, et al
  • August 26, 2021
  • https://arxiv.org/abs/2003.02989
  • In the numerical experiments conducted in [22], we consider the simulation of these quantum machine learning models up to 30 qubits. The large-scale simulation allows us to gauge the potential and limitations of different quantum machine learning models better. We utilize the qsim software package in TFQ to perform large scale quantum simulations using Google Cloud Platform. The simulation reaches a peak throughput of up to 1.1 quadrillion floating-point operations per second (petaflop/s). Trends of approximately 300 teraflop/s for quantum simulation and 800 teraflop/s for classical analysis were observed up to the maximum experiment size with the overall floating-point operations across all experiments totaling approximately two quintillions (exaflop).
  • From the caption for Figure 9: “Circuits were of depth 40.

Google quantum supremacy experiment used 53 qubits, but not to solve a practical problem

Why limit to 40 qubits?

What’s the big benefit of 40 qubits?

Scaling is essential — 40 qubits is merely a stepping stone

What is dramatic quantum advantage?

Don’t we already have real quantum computers with more than 40 qubits?

  1. Low qubit fidelity. Noise and error rates that discourage the design of complex algorithms.
  2. Low coherence time. Severely limits circuit depth.
  3. Limited connectivity. Only a few qubits to which any qubit can be directly connected. Forces a reliance on SWAP networks which increases the impact of #1 and #2 — more gates with lower fidelity.

Quantum Volume of at least one trillion is needed to support 40-qubit quantum algorithms

NISQ quantum computers can’t handle 40-qubit quantum algorithms

Technically, 43 qubits may be needed for 40-qubit quantum parallelism

There just aren’t many 40-qubit quantum algorithms published

  • There just aren’t many published algorithms ready to exploit 40 qubits.

It’s a chicken and egg problem

  1. Why bother writing a 40-qubit quantum algorithm if there isn’t sufficient hardware to run it on?
  2. Why bother building 40-qubit quantum computers with sufficient capabilities to run complex 40-qubit quantum algorithms if no such algorithms exit?

My suggested solution: Simulate 40-qubit quantum algorithms now, be ready for real quantum computers when they become available

  • Algorithm designers: Design, develop, and test complex 40-qubit quantum algorithms using advanced classical quantum simulators. Prove that they work. Publish them. Let the hardware engineers know that you are ready for real quantum computers with robust support for 40 qubits.
  • 40-qubit quantum algorithms will then be ready to run on advanced hardware as soon as it becomes available. Presuming that the hardware has enough qubits with sufficient qubit fidelity and connectivity.

Simulation is the best near-term path to supporting 40-qubit quantum algorithms

Target qubit fidelity of 2–5 years from now

So, why isn’t this happening? Where are all of the 40-qubit quantum algorithms?

Why aren’t there any 40-qubit quantum algorithms?

A sampler of excuses for why people aren’t focused on 40-qubit quantum algorithms

  1. It’s just technically too challenging. But I’m skeptical about that, although it’s at least partially true.
  2. Smaller algorithms are sufficient for the publication needs of most academic researchers.
  3. Smaller algorithms are easier to diagram — for publication.
  4. Smaller algorithms are easier to debug and test.
  5. Larger algorithms are very difficult to debug and test.
  6. Limited coherence time limits circuit depth, which limits how many qubits can be manipulated and entangled in a single large quantum computation.
  7. Large algorithms and NISQ quantum computers just don’t mix.
  8. The resource requirements for simulating 40 qubits could be enormous for more than fairly shallow circuits — 2⁴⁰ quantum product states (one trillion) times the circuit depth. Okay, so shoot for 30–32 qubits then.
  9. Large simulations require great patience.
  10. Simulators do exist, but simulation is still a bit immature and doesn’t inspire great confidence. It’s not easy to design, implement, and configure a noise model that does a realistic simulation of a realistic quantum computer.
  11. It’s far more impressive to run on a real quantum computer than a simulator, but current real quantum computers don’t offer robust support for 40 or even 32-qubit algorithms.
  12. People are currently impressed and focused on simply solving problems at all using a quantum computer, even if for only 23, 17, 11, or even 7 qubits. Even just saying the name of the problem being addressed is a reward in itself.
  13. Eventually 40-qubit quantum algorithms will happen, but for now they aren’t a priority.
  14. Easier to go after low-hanging fruit — diminishing returns for solving harder problems. Fewer qubits get the job done — results to be published. Breaking your back to do even just a few more qubits just isn’t worth it.
  15. Hand-coding of quantum algorithms is very tedious. Programmatic generation of quantum circuits is too big a challenge for many.
  16. Generalizing quantum algorithms to enable them to be fully parameterized and scalable is a difficult task, beyond the abilities of many. It’s easy to parameterize and scale based on an integer, but not so easy if the parameter is an atom or molecule or protein or drug.
  17. 24 qubits may be more than sufficient for variational methods. More qubits may be diminishing returns. 2⁴⁰ quantum states may be gross overkill for variational methods. And people are stuck with variational methods until the day when qubit fidelity eventually is sufficient to support full quantum phase estimation (QPE) and quantum Fourier transform (QFT.)
  18. Need for fine granularity of phase and probability amplitude. Not a problem for simulators, but very problematic for real quantum computers, with no certainty of a resolution in the next few years. If real quantum computers won’t support fine granularity of phase angles and probability amplitudes for another five years or more, why bother even simulating such algorithms. This is needed for quantum Fourier transform (QFT) and quantum phase estimation (QPE).

Significant resources needed to simulate quantum circuits with a large number of product states

Qubits, circuit depth, and product states

  1. Qubit count.
  2. Circuit depth.
  3. Product states. Each qubit has a quantum state, but entangled qubits have a combined quantum state, called a product state. Actually, the entangled qubits can have multiple product states. A product state is simply a quantum state involving multiple qubits.

Deep circuits and product states

Is circuit depth a big issue for 40-qubit quantum algorithms?

But in theory, simulating 40 qubits should be practical

In short, there’s no technical excuse for lack of 40-qubit quantum algorithms which can run on simulators

Mindset obstacles to 40-qubit quantum algorithms

Is a focus on variational methods holding back larger algorithms?

Need for fine granularity of phase and probability amplitude

Shouldn’t the promise of support for quantum phase estimation (QPE) and quantum Fourier transform (QFT) be sufficient to draw a focus on 40-qubit quantum algorithms?

Future demand for quantum phase estimation (QPE) and quantum Fourier transform (QFT) will eventually drive 40-qubit quantum algorithms

No real need for 40-qubit quantum algorithms until quantum phase estimation (QPE) and quantum Fourier transform (QFT) create a need

Why little publication of 40-qubit quantum algorithms even if simulation is limited?

Any 40-qubit quantum algorithms in the Quantum Algorithm Zoo?

My full solution: A model for scalable quantum algorithms

Tackling practical, production-scale real-world problems

Will 40-qubits get us to The ENIAC Moment for quantum computing?

Will 40-qubits get us to The FORTRAN Moment for quantum computing?

What would resource requirements be for various application categories?

  1. Qubit count.
  2. Qubit fidelity.
  3. Circuit depth.
  4. Qubit connectivity.
  5. Fineness of granularity required for phase and probability amplitude.

40-qubit quantum algorithms which I may not be aware of

Dramatic need for additional research

  1. Metaphors.
  2. Design patterns.
  3. Algorithmic building blocks.
  4. Libraries.
  5. Frameworks.
  6. Performance characterization and measurement.
  7. Scaling in general, automated scaling, automating more situations currently requiring manual scaling.
  8. Automated algorithm and circuit analysis tools to detect design issues, such as for scaling.

Open source

What’s a PhD candidate or thesis advisor to do?

  1. Focus on smaller algorithms (under 24 qubits) which can run on existing real quantum computers to deliver actual real results. Granted, they can’t handle production-scale practical real-world problems, but they are results sufficient for a PhD project.
  2. Focus on theoretical work with algorithms using 100 to 1,000 qubits — or even thousands of qubits — which not only can’t run on any existing real quantum computers, but are too large for even the best classical quantum simulators, even if they may be what are really needed for the long run to support production-scale practical real-world quantum applications. They can publish their theoretical findings, but nobody can use them in practice now or any time in the relatively near future.

Timeframe

  1. Exhaustion of interest in variational methods. Desire to move significantly beyond what can be done with 12 to 23-qubit algorithms.
  2. Availability of real quantum computers with higher fidelity qubits and Quantum Volume of 2⁴⁰.
  3. Stronger interest in preparing for the real quantum computers which will be available in three to five years rather than on current and near-term quantum computers.
  4. Government research programs place fresh emphasis on 40-qubit quantum algorithms.

Who’s on first?

When will all quantum algorithms be 40-qubit?

Take the 40-qubit challenge!

  • Take the 40-qubit challenge!
  • We’re taking the 40-qubit challenge!
  • We took the 40-qubit challenge!

Inspire the hardware vendors to support 40-qubit algorithms

  • Take the 40-qubit challenge!

Summary and conclusions

  1. Scalable quantum algorithms are needed. 40-qubits may be the near-term limit for simulation, but scalable algorithms will extend beyond 40-qubits once quantum computers with enough qubits and sufficient qubit fidelity and connectivity become available.
  2. There’s no technical obstacle to 40-qubit quantum algorithms. Real quantum computers are not yet available with sufficient qubit fidelity and connectivity, but classical quantum simulators are available.
  3. A desire to run variational methods on a real quantum computer may be distracting people from the greater potential of simulating a larger number of qubits.
  4. There may be proprietary or secret algorithms which utilize 40 qubits.
  5. Research programs for larger algorithms are desperately needed.
  6. Research programs should explicitly call for simulation of 28, 32, 36, and 40-qubit quantum algorithms.
  7. Research is also needed for larger simulators, targeting 44, 48, and 50 qubits. Maybe even 54 to 56 qubits. And maybe even 60 qubits. Or at least call for research into whether there are good reasons not to try to simulate more than 50 qubits.
  8. I encourage people to Take the 40-qubit challenge! — design and develop practical and scalable 40-qubit algorithms and applications addressing realistic real-world problems.
  9. A significant collection of proven 40-qubit quantum algorithms, sitting on the shelf, and ready to go could be what’s needed to inspire the quantum computer hardware vendors to support 40-qubit algorithms. Only then can we realistically expect the hardware vendors to… Take the 40-qubit challenge!
  10. It may take another three or four years before we see the first 40-qubit algorithm and application running on a real quantum computer.
  11. And it could take five to seven years before 40-qubit algorithms become the norm.

--

--

--

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

8. The Toric Code (part 4)

Curiosities on Quantum Computing — Qubit

Qubit, An Intuition #6 — Two Famous Quantum Algorithms, Shor’s and Grover Algorithms

A Dynamic Approach to the Famous Euler Puzzle. Is it Possible?