What Is a Universal Quantum Computer?

Topics

  1. Glossary
  2. Origins of quantum computing
  3. Later developments
  4. Quantum computing in the maw of modern marketing
  5. Where we are today on the technical front
  6. Key elements of a universal quantum computer
  7. Deutsch’s vision — integration of classical and quantum operations
  8. Current quantum computers are only half of Deutsch’s vision
  9. Can we achieve parity with pure quantum?
  10. Can a quantum-only computer do everything a classical computer can do?
  11. Universal quantum gate sets alone don’t make a universal quantum computer
  12. Levels or types of universal quantum computers
  13. Some details
  14. Beyond the qubit?
  15. How much physics can be simulated with only two states?
  16. How many degrees of freedom are needed to simulate physics?
  17. How large a physical system can be simulated?
  18. QISC — Quantum Instruction Set Computer?
  19. Photonic computing
  20. QRAM — Quantum Random Access Memory
  21. Virtual memory?
  22. Balancing and exploiting parallel and sequential operation
  23. Data types for quantum computation?
  24. Can we simply graft a QPU onto a classical CPU?
  25. Hybrid mode of operation as a stopgap measure?
  26. Is a quantum coprocessor good enough?
  27. Poor man’s universal quantum computer
  28. Direct integration of classical and quantum operations
  29. Quantum registers
  30. What size integer is most appropriate for a universal quantum computer?
  31. What size floating point operations make sense for a universal quantum computer?
  32. What precision is needed for simulation of physics?
  33. Planck constant
  34. Simulation of chemistry
  35. Simulation of cosmology
  36. Exact simulation versus approximation
  37. Support for character, string, and text operations
  38. Any impact from running a CPU at colder temperatures?
  39. What to do about coherence time
  40. Multipartite entanglement?
  41. Mixing simulated and real quantum operations
  42. Cryptography
  43. Artificial intelligence?
  44. Turing a, c, o, and u-machines
  45. Analog?
  46. Horrendous mountains of code
  47. Database operations
  48. Time-series data operations
  49. Taylor series expansion
  50. Challenges of algorithms
  51. Data modeling
  52. Achieving statistical stability from probabilistic computation
  53. PL/Q — Need for a programming language to match the full potential of a universal quantum computer
  54. Great barriers to architectural progress: qubit count, coherence time, and connectivity
  55. What can a classical computer do?
  56. What should we expect a quantum computer to do?
  57. Criteria for judging progress
  58. How soon before we see the first real universal quantum computers?
  59. No, a Noisy Intermediate-Scale Quantum (NISQ) computer is not a universal quantum computer
  60. Simulate a universal quantum computer
  61. My definition
  62. What’s next?

Glossary

Origins of quantum computing

Later developments

Quantum computing in the maw of modern marketing

  • getting enough qubits to work together to run any such algorithm — in what is known as a universal quantum computer — has proved extremely challenging
  • D-Wave’s machines are not ‘universal’ computers’, and can only run a limited range of quantum algorithms
  • IBM (NYSE: IBM) announced today an industry-first initiative to build commercially available universal quantum computing systems.
  • On Monday, March 6, IBM announced that it will build commercially available universal quantum computing systems. IBM Q quantum systems and services will be delivered via the IBM Cloud platform and will be designed to tackle problems that are too complex and exponential in nature for classical computing systems to handle.
  • For more information on IBM’s universal quantum computing efforts, visit www.ibm.com/ibmq.

Where we are today on the technical front

  • Building more than just a few qubits. How do we scale to practical numbers, like hundreds and thousands, and eventually millions?
  • Dramatically longer coherence times. 100 microseconds is an amazing achievement, but too toy-like to base a practical quantum computer. Seconds, minutes, hours, and days are so far off in the distance.
  • Error correction. Even with longer quantum coherence, interference from environmental noise is unavoidable, so correction schemes are needed, which means more qubits are needed.
  • Alternative technologies and approaches to constructing individual qubits. There are a number of competing approaches today, but it wouldn’t hurt to have many more. Innovation in this area might well be the gating factor for improvements in the other areas listed above.
  • Cost.
  • Difficulty of operation. Sophisticated staff needed.
  • Cryogenic cooling.
  • Room temperature operation. Not with the current technology. Maybe we can’t achieve room temperature practically anytime soon, but something much closer to freezing is sorely needed. Or, maybe that’s the limit of the current technology, and something like a photonic computer (Xanadu) is a better horse to bet on for true practicality, with current cryogenic temperatures simply being a necessary but transient steppingstone.
  • Size. A standard data center rack, small filing cabinet, desktop, laptop, tablet, smartphone, wristwatch, and embedded Internet of Things are all well beyond the horizon, but still conceivable. For now, a standard data center rack should be the practical goal and benchmark to pursue.

Key elements of a universal quantum computer

  1. An assembly of independent qubits, each of which functions according to the probabilistic nature of quantum mechanics, including superposition and entanglement of quantum states, as well as a universal quantum logic gate set which supports all of the operations possible at the quantum mechanical level for each qubit.
  2. Can simulate or implement any and all operations of a classical computer. A classic Turing machine.
  3. Capable of simulating physics, especially quantum mechanics, but the rest of physics as well.
  1. Functionally capable of those three qualities.
  2. Capacity to handle real-size problems. Up to and including Big Data.

Deutsch’s vision — integration of classical and quantum operations

Current quantum computers are only half of Deutsch’s vision

Can we achieve parity with pure quantum?

Can a quantum-only computer do everything a classical computer can do?

Universal quantum gate sets alone don’t make a universal quantum computer

Levels or types of universal quantum computers

  1. Level 1 or Type A. A functional universal quantum Turing machine, capable of simulation of all operations of a classical Turing machine, plus Deutsch’s eight quantum operations, but only just barely. Not capable of handling a program of any significant size.
  2. Level 2 or Type B. Capable of handling programs of some significant size, large enough to be useful running as a coprocessor, comparable to a GPU, but well short of running a full-featured, complex operating system.
  3. Level 3 or Type C. Fully capable of running anything which can be run on any classical computer. Not necessarily better, but roughly comparable. This doesn’t meet the goal of exceeding classical computers, but at least achieves parity, the minimum. There might need to be separate metrics for performance (speed) and capacity (size) since they are not directly linked.
  4. Level 4 or Type D. Significantly exceeds the capacity and performance of a classical computer. This is it, the real goal for a universal quantum computer.
  1. Level 3.0 or Type C.0. 1940’s style full-room size machine requiring the attention of one or more elite staff to keep the machine running properly. All the cryogenic equipment.
  2. Level 3.1 or Type C.1. Still room-size, but productized so that a trained non-elite operator can supervise the machine, as in the 1950’s. Still probably cryogenic.
  3. Level 3.2 or Type C.2. More compact, less operational challenge. Some smaller models which don’t dominate a large room, as in the 1960’s, especially minicomputers. May still use a large room, but to house multiple machines. May or may not still be cryogenic.
  4. Level 3.3 or Type C.3. Size of a standard data center rack with comparable operating requirements. No longer cryogenic.
  5. Level 3.4 or Type C.4. Size of a small file cabinet and suitable for an office environment, or a unit which fits into a standard data center rack, with multiple units per rack. Room temperature.
  6. Level 3.5 or Type C.5. Desktop form factor, comparable to a desktop PC or a workstation. Definitely room temperature.
  7. Level 3.6 or Type C.6. Laptop form factor.
  8. Level 3.7 or Type C.7. Tablet form factor.
  9. Level 3.8 or Type C.8. Handheld form factor.
  10. Level 3.9 or Type C.9. Wearable form factor, such as a smart watch.
  11. Level 3.10 or Type C.10. Embeddable, such as Internet of Things.

Some details

  1. Formalize the notion of a universal quantum Turing machine, incorporating the classical Turing machine and Deutsch’s notion of eight further quantum operations.
  2. Elaborate on Feynman’s notion of simulating physics, and whether Deutsch’s eight further operations are indeed sufficient, or at least clarify how much of physics those eight operations cover.
  3. Hybrid memory. Both classical and quantum states.
  4. Rapid and high-volume movement of data between classical and quantum states.
  5. Pseudo-quantum data. Expression of an intended quantum superposed and possibly even entangled state in a structured form of classical data, which can be trivially and rapidly transformed into a sequence of quantum operations to achieve that quantum state.
  6. Transparent switch between true, real quantum and simulated quantum mode. For example, be able to run quantum code at full speed, or enable tracing and breakpoints, causing execution to drop into simulation mode.
  7. Significantly greater number of qubits.
  8. Significantly greater degree of connecting (entangling) qubits.
  9. Quantum coherence time for qubits on the order of seconds.
  10. Quantum error correction as needed to maintain quantum coherence.
  11. Multiple quantum processors in a single computer system.
  12. Quantum communication to transmit quantum data and entanglement between quantum processors, at least in nearby systems, but eventually long distances as with quantum communication.
  13. Programming languages with very expressive high-level constructs for both Deutsch’s eight further operations and methods for integrating and coordinating those eight operations and classic data and classical operations.
  14. Debugging tools for working with hybrid, universal quantum programs.
  15. What are the quantum equivalent of classical objects, classes, functions, and basic data structures? What level should average quantum developers be working at compared to raw qubits?
  16. Some initial libraries of building blocks of algorithms, code, and data structures for both working with Deutsch’s eight further operations and for integrating and coordinating those eight operations and classic data and classical operations.
  17. Much richer libraries comparable to and rivaling the libraries for classical computing.
  18. Even richer libraries which significantly exceed those available for classical computing.
  1. I/O. In general.
  2. Mass storage.
  3. Databases. Including access to distributed databases.
  4. Full-featured operating system.
  5. Virtual machines. One physical machine, but any number of processes, each of which appears to be a virtual machine of its own.
  6. User experience. Remote access is sufficient for many uses.
  7. Networking. Must be accessible over the network, but that can be accomplished with a front-end computer.
  8. Quantum networking. Direct quantum communication between quantum processors without transforming to and from non-quantum binary format, fully maintaining all quantum state.
  9. Quantum distributed processing. More than simply disparate systems interacting, tightly integrated distributed systems, each working on a designated subset of a larger problem. Key to tackling Big Data problems beyond the size of even a large quantum computer.
  10. Direct quantum sensor access. Such as video, audio, and Internet of Things, without traditional digital processing which distorts continuous values.
  11. Real-time processing. In a traditional sense — prompt attention to input, time-sensitive response. Interrupts.
  12. Robotic activity. Includes real-time processing, and attention to spatial position, orientation, and velocity. Includes perception and manipulation of objects in the real-world.

Beyond the qubit?

How much physics can be simulated with only two states?

How many degrees of freedom are needed to simulate physics?

How large a physical system can be simulated?

QISC — Quantum Instruction Set Computer?

Photonic computing

QRAM — Quantum Random Access Memory

Virtual memory?

Balancing and exploiting parallel and sequential operation

Data types for quantum computation?

Can we simply graft a QPU onto a classical CPU?

Hybrid mode of operation as a stopgap measure?

Is a quantum coprocessor good enough?

Poor man’s universal quantum computer

Direct integration of classical and quantum operations

Quantum registers

What size integer is most appropriate for a universal quantum computer?

  1. Size of individual integer data values. A single number.
  2. Most efficient way to handle a bunch of bits. As a bundle of bits.
  3. Size of registers. Each holding a single integer value.
  4. Complexity of hardware for basic math operations. Add, subtract, multiply, and divide.
  5. Size of a fixed-width or typical machine language instruction.
  6. Size of a memory address.
  7. Width of the data path to move data between the CPU and memory. For both data values and addresses.
  8. Implies a size for basic floating point operations. Single-precision.
  9. Number of bits which can be manipulated in parallel in a single operation. AND, OR, NOT, and XOR.
  10. The number of memory chips needed. Since each chip supplies only a single bit, n-bit values implies n chips operating in parallel.

What size floating point operations make sense for a universal quantum computer?

What precision is needed for simulation of physics?

Planck constant

Simulation of chemistry

Simulation of cosmology

Exact simulation versus approximation

Support for character, string, and text operations

Any impact from running a CPU at colder temperatures?

What to do about coherence time

Multipartite entanglement?

  1. How difficult is it to implement multipartite entanglement?
  2. What applications require or are significantly advantaged by multipartite entanglement?

Mixing simulated and real quantum operations

  1. Classical computing.
  2. Quantum computing.
  3. Simulated quantum computing.

Cryptography

Artificial intelligence?

Turing a, c, o, and u-machines

  1. a-machine. “a” for automatic. His classic universal Turing machine. Given its original input it runs to completion and halts, having produced the results of the computation.
  2. c-machine. “c” for choice. It runs automatically as a pure a-machine until it reaches points at which an external operator (or another machine) has to make a choice which determines the next state. Technically, it could be a human operator (user), but more likely it is another machine, such as another Turing machine. This enables interactive computing, networked computing, and operating systems controlling multiple processes (virtual machines) which may interact through their choices. Whether or when it halts is less significant than with an a-machine.
  3. o-machine. “o” for oracle. Similar to a c-machine, but the choice is made by an entity which is not a Turing-style machine. This could be a human operator or user, or a machine such as an analog computer or a sensor.
  4. u-machine. “u” for unorganized. Intending to permit modeling of human intelligence and evolutionary computation. See the Evolutionary Turing in the Context of Evolutionary Machines paper by Burgin and Eberbach.

Analog?

Horrendous mountains of code

Database operations

  1. Compute-intensive sequential scanning and sequential processing of an entire data stream.
  2. Query-intensive selective processing, using complex Boolean expressions and optimizing access using indices.
  1. Faster processing.
  2. More efficient forms of indexing.
  3. More efficient forms of queries.
  4. More efficient forms of storing and organizing data.

Time-series data operations

Taylor series expansion

Challenges of algorithms

Data modeling

Achieving statistical stability from probabilistic computation

PL/Q — Need for a programming language to match the full potential of a universal quantum computer

Great barriers to architectural progress: qubit count, coherence time, and connectivity

  1. Greater qubit count. A handful or even a few dozen qubits are not even table stakes to get started. We need hundreds of qubits, with the promise of thousands just to get the juices flowing.
  2. Greater qubit coherence time. There is no clarity about what the threshold should be, but one ten-thousandth of a second is again not even enough for table stakes. Hours and minutes may be too much to ask for at this stage, but a healthier fraction of a second (quarter of a second? Tenth of a second?) is needed before we can get serious, with serious algorithms and serious hybrids of quantum and classical operations. This also includes error correction to assure coherence.
  3. Greater qubit connectivity. It must be possible to connect any qubit with any other qubit before we can enable wide-open algorithms. Current systems have so many restrictions and special rules that algorithms are seriously constrained — we need unconstrained algorithms.

What can a classical computer do?

What should we expect a quantum computer to do?

Criteria for judging progress

How soon before we see the first real universal quantum computers?

No, a Noisy Intermediate-Scale Quantum (NISQ) computer is not a universal quantum computer

Simulate a universal quantum computer

My definition

  1. universal quantum computation. Subject to practical capacity limitations, the ability of a quantum computer to do anything a classical computer can do, in addition to anything any quantum computer can do beyond the capabilities of a classical computer, in particular, supporting a universal quantum logic gate set. It must be able to compute all mathematically computable functions as well as able to simulate any real physical quantum system, subject to practical capacity limits. By definition, this includes all classical computation, including any function which is computable by a classical Turing machine. In theory, universal quantum computation is any computation possible by a universal quantum Turing machine. Even if a quantum computer is universal, it may not be able to practically do everything which a classical computer can do — it may have too few qubits, too short a coherence, or lack sufficient quantum error correction. See the classic Quantum theory, the Church-Turing principle and the universal quantum computer paper by David Deutsch. Alternatively, in practice, the ability to compute the lion-share of computations which have practical application in the real world. Alternatively, the computations possible using a universal quantum logic gate set, in contrast to the limited set of functions supported by a special-purpose or fixed-function quantum computer, and in contrast to the full functions of a classical Turing machine.
  2. universal quantum computer. A quantum computer capable of universal quantum computation. A quantum computer which can be applied to all classes of problems and capable of computing whatever a classical computer can compute, in addition to anything a quantum computer can compute, including simulation of real physical quantum systems, in contrast to a fixed-function quantum computer which is tailored to only one relatively narrow niche class of problems. Note that universal refers to each of the discrete operations which can be performed, not necessarily the amount of data which can be processed or its structure. Alternatively, a quantum computer which supports a universal quantum logic gate set, in contrast to a special-purpose or fixed-function quantum computer, and in contrast to a computer supporting the full functions of a classical Turing machine. Alternatively, a vague marketing term asserting that a quantum computer or some purported future quantum computer is somehow all-powerful, or at least much more impressive than current and envisioned classical computers. Alternatively, again as a vague marketing term, simply a crude synonym for a general purpose quantum computer, in contrast to a fixed-function quantum computer. Note that a universal quantum computer may not have the resources and capabilities to make it suitable as a general purpose computer.
  3. universal quantum Turing machine. A hypothetical equivalent of the concept of a universal Turing machine of classical computing applied to quantum computing. This is the ultimate, ideal conception of a universal quantum computer, in theory even if not in practice. Such a conception has been neither formalized in theory nor realized in the lab in any current quantum computer or near-term quantum computer as of July 2018. See the Wikipedia Quantum Turing machine article. See the Quantum Turing Machines Computations and Measurements paper by Guerrini, Martini, and Masini. See the classic Quantum theory, the Church-Turing principle and the universal quantum computer paper by David Deutsch. Shortened as QTM. See also: quantum Turing machine.

What’s next?

--

--

--

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

Review: Black Opal’s “Control” by Q-CTRL

Which Quantum Modality is Best?

The Quantum Computing Elevator Pitch

Looking at a Bomb Without Looking: A Quantum Paradox