Skip to content

Instantly share code, notes, and snippets.

@cgranade
Created August 4, 2020 17:55
Show Gist options
  • Save cgranade/c2f447cc130574e9f7e5f33728b2566f to your computer and use it in GitHub Desktop.
Save cgranade/c2f447cc130574e9f7e5f33728b2566f to your computer and use it in GitHub Desktop.

DISCLAIMER: This post is still in a draft!

Falsehoods programmers believe about quantum computing

Preamble

Quantum computing has captured broad attention and fascination over the past few years, but with that interest has come a large number of well-intentioned misunderstandings. In this post, I'll lay out a few of these falsehoods in the tradition of other wonderful falsehood lists, and in the hopes of spurring more exploration into this new and fascinating way of solving hard problems.

As a brief housekeeping note, these falsehoods are ordered by theme and topic, not in order of complexity, so don't worry if some of these points seem a bit intimidating. If you're looking to learn more about quantum computing in the first place, check out Learn Quantum Computing with Python and Q# (Manning Publications, October 2020) by Sarah Kaiser and myself.

Special thanks to everyone that made suggestions on falsehoods to include in this list:

QF1000: Falsehoods about what quantum computing is

  • QF1000: quantum computers will totally replace classical computers
    We believe that quantum computers likely can solve a lot of really neat problems faster than any classical computer. For other problems, though, you won't get any advantage from quantum computing. This makes quantum computers a little bit like GPUs, FPGAs, TPUs, or other specialized hardware that we use together with conventional CPUs to solve problems.

  • QF1001: quantum computers can certainly solve NP-complete problems efficiently
    There's some very good evidence to suggest that many kinds of problems, such as NP-complete problems will remain hard for quantum computers and classical computers alike. While quantum computing offers to significantly expand what problems we can solve, there's always a harder problem out there.

  • QF1002: qubits can be in two places at once
    Quantum mechanics is a bit different than the everyday classical mechanics we're used to, such that sometimes it takes a little while for our intuition to catch up. To help out, there's a number of analogies that get used to help fill the gap. For example, superposition is sometimes described as objects being "in two places at once." Like all analogies, this way of explaining superposition can help, but it also has its limitations we need to be aware of. When a qubit or register of qubits is in superposition, it's definitely in a particular state; just that state is a combination of states in a preferred basis.

    To offer another analogy to help bridge intuition in a different way, the states of qubits and quantum registers are like directions on a map. Just as northwest is a combination of north and west, we can make up those directions by combining directions on a compass. If I'm walking northwest, I'm definitely not walking only north or only west, but some combination of the two, just like superposition in quantum mechanics.

  • QF1003: qubits can hold more information than classical bits
    Sometimes you may see a claim that qubits can hold two bits of classsical data (often, a nod to a concept called superdense coding), or that qubits can hold infinite amounts of classical data (a reference to that describing the state of an 𝑛-qubit quantum register requires writing down a vector of 2 × 2𝑛 real numbers). As it turns out, though, when we measure 𝑛 qubits, we always get at most 𝑛 classical bits back. A wonderful bit of math called Holevo's theorem tells us that if I give you an 𝑛-qubit register, you can learn at most 𝑛 classical bits from that.

    If it seems like that contradicts what you've learned about superdense coding, the resolution is that in superdense coding, I not only give you a qubit, but I share half of an entangled pair of qubits with you from the start. Thus, you measure two qubits at the end, allowing you to get two classical bits back.

  • QF1004: quantum mechanics lets us send information faster than light
    Early criticisms of quantum mechanics such as "Schrödinger's cat" or "spooky action at a distance" survive on to this day in popular attention, even as we've understood quantum mechanics well enough to address these arguments. As a result, early misconceptions such as that quantum mechanics allows for violating the speed of light can stick around long after we've come to realize that entanglement is much more subtle than we first believed nearly a century ago. Indeed, the no-signalling theorem tells us that while entanglement can help us communicate, you cannot send information using entanglement on its own. That means that you need some form of communication that obeys the speed of light to make use of entanglement, such that there's no inherent contradiction between quantum mechanics and the speed of light.

  • QF1005: randomness is what makes quantum computing powerful
    It's definitely the case that quantum mechanics lets us generate truly random numbers, but that alone isn't enough to explain why quantum computers are powerful. After all, classical random numbers are good enough for us to make some truly neat algorithms like Monte Carlo integration. To explain the power of quantum algorithms, you need more than randomness alone, but also another effect known as interference. For more, check out Greg Kuperberg's 2012 article on Slate.

  • QF1006: quantum algorithms are always random
    Some of the best quantum algorithms we know of are random, in that the return the right answer most of the time but aren't guaranteed to do so. Shor's algorithm and Grover's algorithm are both great examples of this, in that it may take several runs of each to guarantee that you get the right answer with a high enough probability to meet your needs. In a practical sense, this isn't really important, since the number of times you need to run each is a constant (we say that both are examples of problems in BQP, but it may suggest that quantum algorithms are always random. Especially since randomness is a key part of quantum mechanics, and since noise in near-term quantum devices means that measurement results are subject to still further randomness, this falsehood is an especially common one.

    As it turns out, many quantum algorithms (e.g. the Deutsch–Jozsa algorithm), are deterministic when run on fault-tolerant quantum devices. Just like classical algorithms, randomness can be a useful tool, but it isn't the only tool that we have access to when we design quantum algorithms.

QF2000: Falsehoods about learning quantum computing

  • QF2000: no one understands anything about quantum mechanics
    Like anything in science, we still have much to learn about quantum physics. That doesn't erase, though, that we've learned a whole hell of a lot about quantum physics over the past century. That understanding has provided us with a consistent and coherent formalism for describing quantum effects, known as quantum mechanics. The formalism of quantum mechanics is understood very well by now, giving us a great platform to describe, simulate, and reason about quantum computers built using those effects.

  • QF2001: you have to be a physicist to understand quantum computing
    Physics tells us which effects we need to simulate and when, but once we have the right description from a physical theory, we can deal with it entirely using the formalism of quantum mechanics. In that way, quantum computing is much like classical computing: we may need physics to describe how a transistor works and why, but once we have that description, we can abstract the physics away into the truth tables and logic gates that we use to build our computers.

  • QF2002: you need special hardware or hardware access to get started learning
    Quantum hardware is cool, no doubt about that. On the other hand, you don't need hardware to start learning, exploring, and building new quantum applications. Up to about 30 qubits, you can simulate anything a noiseless quantum computer would do using a moderately powerful laptop or desktop, giving you lots of room to learn and explore.

  • QF2003: quantum programming is too hard for me to learn
    Learning new things can be challenging, and can force us to rethink our assumptions in new and interesting ways. As technology as progressed, everything from multicore CPUs through to the web and cloud computing has presented both new challenges and new opportunities. Quantum computing continues in that history, and in the same way that we learned and grew through each previous paradigm shift, you can learn quantum computing too.

  • QF2004: quantum programming takes too much math for me to learn
    It's true that math can be helpful, just like in graphics programming or machine learning. That said, math isn't the end-all of quantum computing either. There's a lot of useful skills that can help you suceed as you learn quantum computing, such that you can find your own way to make the community better with the skills that you have. Even when it comes to the math, there's a lot of useful tools and libraries to help make that math easier to work with — classical computers are great tools for doing the math for us, and that works wonderfully when it comes to quantum computing as well.

QF3000: Falsehoods about quantum programming and development in general

  • QF3000: quantum programming is nothing like classical programing
    It's tempting to look at the notation and terminology used in quantum mechanics and to conclude that everything is so completely different that you can't use anything that you've already learned. On the contrary, though, even if the notation can be a bit different, many of the underlying concepts are the same, or build on the skills you already have (e.g.: the linear algebra used in quantum is very similar to that used both in graphics and in machine learning).

  • QF3001: quantum programming is just like classical programing
    On the other hand, there are some differences that are worth keeping in mind! Quantum computing does bring along with it is own concepts and techniques that can be helpful to keep in mind. For instance, the no-cloning theorem tells us that if we want to avoid turning a quantum computer into an expensive and slow classical computer, we need to be careful about how we represent and manipulate the information stored in quantum registers. That in turn motivates some features in quantum programming languages that may look a little different than the classical languages you're used to.

  • QF3002: you can just run classical libraries and applications on a quantum computer
    To take advantage of the power of quantum computers, we do need some new techniques, such as quantum simulation, phase estimation, amplitude amplification, and phase kickback. We can learn from existing approaches and applications, and while we can use existing classical libraries alongside quantum computers, but new libraries built around quantum concepts and techniques help make it easy to apply them to new problems and new domains.

QF4000: Falsehoods about quantum platforms, tools, and technologies

  • QF4000: quantum programming tools don't exist yet, it's all just theory
    There's a lot out there to help you get started with quantum programming. Q# and the Quantum Development Kit are near and dear to my heart, of course, as a member of the Microsoft Quantum team. The community around Q# is a great place to start if you want to learn more about how to get started with quantum computing. If that's not your cup of tea, though, check out the Quantum Open Source Foundation's list of quantum platforms to learn more.

  • QF4001: you can't use Python for quantum programming
    Python works great with many quantum programming languages; it's easy to use Q# and Python together, for instance. Many other quantum programming frameworks are embedded or implemented in Python, making it a great tool to use in getting going with quantum computing.

  • QF4002: you have to use Python for quantum programming
    Of course, you also don't have to use Python to be a quantum developer. For example, Q# works great on its own, or with .NET. If you're a Haskell developer, you may find Quipper of interest, while if you're a Julia developer, JuliaQuantum and Yao.jl may be to your liking. Other standalone options like Scaffold are another good place to get started.

  • QF4003: there's no way for me to use my favorite technolgy to help the quantum computing community
    No matter what your preferred languages, platforms, or toolchains are, there's a way to apply what you know to help make the quantum computing community better. Tools like JavaScript and TypeScript can be used to offer better visualizations for quantum programs on the front end, to power IDE tooling, or even to offer interactive services for exploring quantum computing. Systems languages like C, C++, and Rust can be used to write quantum simulators that help us predict, model, and understand quantum computers. Data science languages like Python can be used to interact with quantum programs and to connect them to a broader ecosystem of scientific tools. The .NET platform provides a great infrastructure for quantum compilers and runtimes.

  • QF4004: you have to work at the level of assembly instructions to write quantum programs
    Working at the level of individual quantum instructions, like H and X, can be a great way to understand how quantum computers work, or to optimize small parts of larger quantum programs. Just like it can be helpful to drop into __asmblocks in C, or to call AVX2 intrinsics directly in high-level languages, there's nothing wrong with calling H or X yourself. That said, you also don't have to. As you explore larger and larger quantum programs, it gets more and more difficult to see the structure in those programs by only using low-level instructions. Learning from the history of classical programming, we know that writing modular code using concepts like functions, methods, libraries, and packages can help us to understand and make sense even of very large programs. Similarly, we can use the same concepts to help us focus on high-level quantum algorithms rather than getting stuck on their low-level implementations.

  • QF4005: none of this stuff is open source
    Most quantum platforms currently available are either mostly or completely open source, so that it's easy to get involved, as well as to hack on platforms and make them better. Open source advocacy groups like Unitary Fund and QOSF help to support open source in quantum computing through grants and mentorships as well, so go on and check them out!

QF5000: Quantum and security

DISCLAIMER: Security is a really subtle topic to get right. Before taking any of the points here too seriously, it helps to also do your own research and due dilligence to make sure that your approach to security meets your needs, capabilities, and your threat model.

  • QF5000: Quantum key distribution is a kind of cryptography
    There's no question that QKD is useful to cryptography. Most symmetric-key algorithms in current use don't fare too badly against quantum algorithms, so if you and your communication partner have a way to generate small amounts of shared randomness using quantum mechanics, then you can use that instead of public-key algorithms like RSA. Moreover, if you generate a large enough key with QKD, you can even apply the one-time pad encryption scheme, which is guaranteed to be unbreakable if implemented correctly. In both cases, QKD is an incredibly useful tool for use with cryptography, even if it in and of itself isn't an encryption algorithm per se.

  • QF5001: Quantum key distribution is completely unbreakable
    This is almost true, but the word "almost" carries an immense amount of weight here. As with anything, QKD only works if you do it right, and it can be difficult to do right in practice. Commercial and practical QKD systems can be subject to side-channel attacks that let you extract keys or even implant your own keys without violating the no-cloning theorem, using flaws in physical implementations. By contrast, many comparable classical systems can't be proven to be secure even if they work correctly; we only have really good evidence built up from years and years of trying to break them. Thus, while quantum mechanics really helps out in providing security for your key exchange, it doesn't save you from having to make sure you don't leak that key in other, more mundane ways.

  • QF5002: You need to be afraid of quantum computing right now
    Algorithms that power much of the technology that keeps you and your privacy safe against adversaries as wide ranging as your telecom provider to your government (e.g.: RSA) are put at risk by quantum algorithms like Shor's algorithm. Thus, it might seem like it's a really important thing to panic right now about the impending death of privacy at the hands of quantum computing. Thankfully, however, lots of good work has gone into post-quantum cryptography to try and find replacements for RSA that will continue to work well even once quantum computers have reached the scale needed to run Shor's algorithm for real-world key sizes. Thus, for many use cases, we have the time to do the due dilligence to test these new algorithms and make sure they work right, without having to panic.

@thormighti
Copy link

Wow. Thanks for this

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment