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