Quantum computing#

Short notes on what quantum computers could do, why amplitudes matter, Maxwell's demon, and quantum probability.

About this chapter

The note starts from a question about the limits of computation: could physics let us beat a Turing machine running in polynomial time? It lists some physical “computers” that don’t, then gets to quantum computing. An \(n\)-qubit state is \(2^n\) complex amplitudes whose squared magnitudes sum to 1, updated by unitary matrices.

The central idea is that amplitudes can be negative, so paths to a wrong answer can cancel. The rest covers what that might buy (factoring, Grover’s square-root speedup, simulation) and what gets in the way (decoherence), then two side topics: Maxwell’s demon and a matrix view of joint probability distributions.

  • what does physics tell us about the limits of computers?

  • NP - can check soln in polynomial time

  • NP-hard - if solved, solves every NP

  • NP-complete - NP hard and in NP

  • church-turing thesis \(\implies\) turing machine polynomial time should be best possible in the universe

    • physics could allow us to do better than a turing machine

  • examples

    • glass plates with soapy water - forms minimum steiner tree

    • can get stuck in local optimum

    • ex. protein folding

    • ex. relativity computer

      • leave computer on earth, travel at speed of light for a while, come back and should be done

      • if you want exponential speedup, need to get exponentially close to speed of light (requires exponential energy)

    • ex. zeno’s computer - run clock faster (exponentially more cooling = energy)

Basics#

An \(n\)-bit computer is in one of \(2^n\) states and its operations are stochastic matrices. An \(n\)-qubit computer is described by \(2^n\) complex coefficients whose squares sum to 1, and its operations are unitary matrices, which keep that sum at 1.

  • An n-bit computer has 2^n states and is in one of them with probability 1. You can think of it as having 2^n coefficients, one of which is 0 and the rest of which are 1. Operations on it are multiplying these coefficients by stochastic matrices. Only produces n bits of info.

  • an n-qubit quantum computer is described by 2^n complex coefficients. The sum of their squares sums to 1. It’s 2^n complex coefficients must be multiplied by unitary matrices (they preserve that the sum of the squares add up to 1.)

  • Problem: Decoherence – results from interaction with the outside world

  • Properties:

    • Superposition – an object is in more than one state at once

      • Has a percentage of being in both states

    • Entanglement – 2 particles behave exactly the opposite – instantly

Storing qubits#

  • Fullerenes – naturally found in Precambrian rock, reasonable for storing qubits – can store

    • not developed, but some experiments have shown ability to store qubits for milliseconds

Intro#

Probabilities are computed from amplitudes: add the amplitudes of every path to an outcome, then square the magnitude of the sum. Because amplitudes can have opposite signs, two ways of reaching the same place can cancel.

Interactive 1. Each slit contributes an amplitude at every point of the screen, drawn as an arrow on the right. Move the screen position to a dark fringe: the arrows point in opposite directions and their sum is near 0, even though each slit alone would send the photon there. Turn on "measure which slit" and the probabilities add instead, which wipes out the fringes.
  • probability with minus signs

  • amplitudes - used to calculate probabilites, but can be negative / complex

Photons pass two slits and land on a screen in bands. A dark patch has probability $|a_1 + a_2|^2 = 0$, since the amplitudes through the two slits cancel, yet with one slit closed the photon can land

Fig. 2 Figure 1. Photons pass two slits and land on a screen in bands. A dark patch has probability \(|a_1 + a_2|^2 = 0\), since the amplitudes through the two slits cancel, yet with one slit closed the photon can land there.#

  • applications

    • quantum simulation

    • also could factor integers in polynomial time (shor 1994)

    • scaling up is hard because of decoherence= interaction between cubits and outside world

    • error-correcting codes can make it so we can still work with some decoherence

  • algorithms

    • paths that lead to wrong answer - quantum amplitudes cancel each other out

    • for right answer, quantum amplitudes in phase (all positive or all negative)

    • prime factorization is NP but not NP complete

    • unclear that quantum can solve all NP problems

    • Grover’s algorithm - with quantum computers, something like you can only use sqrt of number of steps

    • adiabatic optimization - like quantum simulated annealing, maybe can solve NP-complete problems

  • dwave - company made ~2000 cubit machine

    • don’t maintain coherence well

    • algorithms for NP-complete problems may not work

    • hope: quantum tunneling can get past local maximum in polynomial time maybe

      • empircally unclear if this is true

  • quantum supremacy - getting quantum speedup for something, maybe not something useful

Maxwell’s demon#

A thought experiment that seems to break the second law of thermodynamics by sorting fast and slow molecules into separate sides. The catch is that the demon has to track every particle, which generates heat.

  • second law of thermodynamics: entropy is always increasing

  • hot things transfer heat to cold things

    • temperature is avg kinetic energy - particles follow a diistribution of temperature

  • separate 2 samples (one hot, one cold) with insulator

    • idea: demon makes all fast particles go to hot side, all slow particles go to slow side - this is against entropy

    • demon controls door between the samples

    • Maxwell's demon works the door between two gas chambers, letting fast molecules into one side and slow ones into the other. One side heats up and the other cools, which would lower entropy and break t

      Fig. 3 Figure 2. Maxwell’s demon works the door between two gas chambers, letting fast molecules into one side and slow ones into the other. One side heats up and the other cools, which would lower entropy and break the second law.#

      • demon opens door whenever high temperature particle comes from cold sample, then closes

      • demon opens door for slow particles from hot sample, then closes

  • problem: demon has to track all the particles (which would generate a lot of heat)

Quantum probability#

A side topic from a blog post: write a joint distribution of X and Y as a matrix \(M\) of square roots of the probabilities. The marginals, which usually throw information away, then appear on the diagonals of \(M^T M\) and \(M M^T\), and the eigenvectors of those matrices keep the conditional distributions.

  • based on this blog post

    • marginal prob. loses information but we don’t need to

  • we then observed that the matrix M^T M contains the marginal probability distribution of Y along its diagonal. Moreover its eigenvectors define conditional probability distributions on Y. Likewise, M M^T contains marginals on X along its diagonal, and its eigenvectors define conditional probability distributions on X

    A joint distribution of X and Y written as a matrix M of square roots of the probabilities. The diagonal of $M^T M$ is the marginal on Y and the diagonal of $M M^T$ is the marginal on X; their eigenve

    Fig. 4 Figure 3. A joint distribution of X and Y written as a matrix M of square roots of the probabilities. The diagonal of \(M^T M\) is the marginal on Y and the diagonal of \(M M^T\) is the marginal on X; their eigenvectors give conditional distributions.#

Key ideas

  • The church-turing thesis suggests a polynomial-time Turing machine is the best computer possible, and most physical shortcuts (soap films, relativity, faster clocks) fail by getting stuck or costing exponential energy.

  • An \(n\)-qubit state is \(2^n\) complex amplitudes whose squared magnitudes sum to 1, changed only by unitary matrices.

  • Amplitudes can be negative, so paths to a wrong answer can cancel while paths to the right answer add up in phase.

  • Quantum computers could factor integers in polynomial time and give Grover’s square-root speedup, but it is unclear that they can solve NP-complete problems.

  • Decoherence, interaction with the outside world, is what makes scaling up hard, and error-correcting codes are the way around it.