Quantum Computing

While quantum computers will probably never replace the laptops and desktops that we use daily, they have to potential to revolutionize high-intensity computation by making possible calculations that we could never conceive of doing on a classical computer.

Problem Complexity

  • Classical computing problems are commonly divided into P, NP complete, and NP problems. We can solve P problems efficiently (in polynomial time) with classical computers, but not other NP problems.

  • Quantum computing creates a new class of problems, called BQP, which we may be able to solve in reasonable time with quantum computers. This may include problems in the NP category, which means we can solve new problems with quantum computers efficiently!

  • Such problems could include

    • Modeling physical / biological systems (account for quantum behavior)

      • Drug discovery

      • Improving batteries

      • Weather forecasting / climate change

    • Cryptography

The Qubit

  • Qubits are in superposition until the final measurement (output of a computational task)

  • Pro: Qubits essentially take on a bunch of probabilities at once (superposition)

  • Con: May have to run a circuit multiple times to know the result; nothing is deterministic

Logic Gates

  • Similar to classical gates: allow actions on and interactions between qubits

  • Essential for making any quantum computer program

  • Useful when they take advantage of quantum properties (especially superposition & entanglement)

  • Example: X gate, which acts analogously to the NOT gate

  • Another example: H gate, which converts a bit into a superposition

Quantum Cryptography

  • Alice and Bob are trying to share a private message

  • Alice tries to send a “one-time pad” (key) online so Bob can decrypt the encrypted information she’ll send

  • Not 100% secure w/ classical computing

BB84 Protocol


Alice

  • Alice would generate a private string of random bits

    • Could do this with a Quantum computer (H gate)

  • Then, for each bit she randomly chooses whether to code it in the 0,1 basis or the +,- basis (remember that the + and - are superpositions)

    • Can easily do this with H and X gates

    • H gate makes + and -, X gate makes 1 and 0

  • Alice then sends the resulting qubits to Bob (through quantum channel)

Bob

  • Whenever bob receives a qubit, he randomly decides whether to measure it in 0, 1 basis or +, - basis (I'm being lazy, when I type 0, 1, + or - it should technically have $\vert 0 \rangle$ around it

  • He does this by choosing whether or not to apply the H gate

  • Then he writes down the results:

    • If used 0,1, write what he gets

    • If used +, - write 0 if gets +, 1 if gets -

Alice and Bob on the phone

  • Now, Alice and Bob talk on classical channel

  • Bob announces bases he used for measurements and Alice announces basis she used to code the bits

    • Bob does not announce the result of the bits

  • For bits that Bob measured with the same basis Alice intended for coding, he got the correct bit

    • Discard the rest (about half are kept)

What happens if Eve tries to intercept??

  • Imagine Eve has access to qubits that Alice sends to Bob

  • Eve could try to measure and resend the bit to Bob

  • It is impossible for Eve to distinguish the four possibilities 0, 1, +, - because she doesn't know which basis Alice selects

  • If Eve chooses a basis at random, she will make an error half the time, which Alice and Bob may detect (they can share a few bits to check that they are equal)

  • Eve cannot copy the qubits and wait to check the basis (no cloning theorem)

  • Other complex attacks possible, but shown to fail


Quantum advantage over classical?


  • If Eve tries to intercept (capture the qubit and then resend them), she won’t know which basis Alice sent them in – gets it wrong half the time

  • Alice and Bob can easily verify a few of the qubits, so they will detect this discrepancy!


Result: Secure, uncrackable key exchanged without meeting in person