Bluff Your Way In Quantum Computing

What is a computer anyway?

Classical Computers

  • State: sequence of classical bits
  • Operations on that state: logic gates

Quantum Computers

  • State: sequence of quantum bits (qubits)
  • Operations on that state: quantum gates

Quantum Theory

\[\begin{aligned} \text{Superposition: } & \alpha|1\rangle + \beta |0\rangle \\ \end{aligned} \]

\[\begin{aligned} \text{Measurement: } & M(\alpha|1\rangle + \beta |0\rangle) \stackrel{\text{Pr} = |\alpha|^2}{\rightarrow} |1\rangle \\ \end{aligned} \]

\[\begin{aligned} \text{Entanglement: } & 0_A 1_B 1_C 0_D \\ \end{aligned} \]

\[\begin{aligned} \text{Entanglement: } & |0\rangle_A |1\rangle_B + |1\rangle_A |0\rangle_B \end{aligned} \]

Origins

The rule of simulation that I would like to have is that the number of computer elements required to simulate a large physical system is only to be proportional to the space-time volume of the physical system. I don't want to have an explosion. That is, if you say I want to explain this much physics, I can do it exactly and I need a certain-sized computer. If doubling the volume of space and time means I'll need an exponentially larger computer, I consider that against the rules (I make up the rules, I'm allowed to do that).

2 Classical bits

\[ 0_A 0_B \]
\[ 0_A 1_B \]
\[ 1_A 0_B \]
\[ 1_A 1_B \]

2 Qubits

\[ |0\rangle |0\rangle \]
\[ |0\rangle |1\rangle \]
\[ |1\rangle |0\rangle \]
\[ |1\rangle |1\rangle \]

\[ \alpha|0\rangle |0\rangle + \beta|0\rangle |1\rangle + \gamma|1\rangle |0\rangle + \delta|1\rangle |1\rangle \]

QCs > CCs?

  • More compact?

    No

  • Easier to build?

    No!

  • Faster?

    It depends

  • More capable?

    No

Faster?

  • QCs are not "universally" faster
  • Depends on the algorithm!
  • Nothing to do with the hardware

More capable?

Are they able to solve problems which CCs cannot?

  1. Classical computers are Turing-complete
  2. Classical computations can be simulated on QCs and vice versa
  3. Therefore, QCs are Turing-complete
  4. Therefore, QCs have no computational advantage over CCs

A Philosophical Mystery

What is the explanation for the power of quantum computing?

  • Superposition?
  • Entanglement?

To Bluff Your Way:

  • Describe at least superposition
  • Use superposition to run the "exponential argument"
  • Describe precisely the sense in which QCs > CCs
  • Highlight limitations of QCs
  • Quantum speed-up is not, fundamentally to do with hardware