Two Guys, One Quantum Computer

Who we are

Caarn

  • Self taught
  • Cycling enjoyer
  • Free beer enthusiast

Eugene

  • Self taught
  • Dog person
  • Retro gamer

Who we are not

So why are we doing this?

"We didn't do it because it was easy, but because we thought it would be easy"

- Unknown developer

What the hell is quantum computing?

Disclaimer

Quantum Mechanics vs Quantum Computing

A Common Misconception

Bits vs Qubits

superposition

entanglement

superposition + entanglement = 

quantum parallelism

NP problems

Sudoku

Coloring a map

Travelling salesman problem

Certain types of encryption

Quantum algorithms and operations

Grover's algorithm

Shor's algorithm

Bernstein-Vazirani algorithm

Hadamard transformation

...and many others!

Grover's coming for your nudes!

Grover's Search Algorithm

Useful for searching unstructured data

The Oracle

A mysterious "black box" that can reveal if an answer is true or not

?

Value

Return 1 for true, 0 for false

The problem

(1, 2, 3, 4, 5, 6... N - 1)
5
1 (true)
if x == 5
  return true;
else
  return false;

?

Grover's algorithm, step 1

Val
⎥1〉

⎥2〉

⎥3〉
⎥4〉
⎥5〉
⎥6〉

Prob
0,16

0,16

0,16
0,16
0,16
0,16

Val
⎥1〉

⎥2〉

⎥3〉
⎥4〉
⎥5〉
⎥6〉

Prob
0,16

0,16

0,16
0,16
-0,16
0,16

Grover's algorithm, step 2

Val
⎥1〉

⎥2〉

⎥3〉
⎥4〉
⎥5〉
⎥6〉

Prob
0,10

0,10

0,10
0,10
0,48
0,10

Val
⎥1〉

⎥2〉

⎥3〉
⎥4〉
⎥5〉
⎥6〉

Prob
0,16

0,16

0,16
0,16
-0,16
0,16

Vector

transformation

Initial state

Source: Youtube 3Blue1Brown https://www.youtube.com/watch?v=RQWpF2Gb-gU

Source: Youtube 3Blue1Brown https://www.youtube.com/watch?v=RQWpF2Gb-gU

After Oracle transformation

Source: Youtube 3Blue1Brown https://www.youtube.com/watch?v=RQWpF2Gb-gU

Vector transformation (axis flip)

Source: Youtube 3Blue1Brown https://www.youtube.com/watch?v=RQWpF2Gb-gU

After vector transformation

Source: Youtube 3Blue1Brown https://www.youtube.com/watch?v=RQWpF2Gb-gU

Rinse and repeat

Doesn't the oracle know the answer?

The oracle does not know

⎥1〉

⎥2〉

⎥3〉
⎥4〉
⎥5〉
⎥6〉
...

⎥N-1〉
⎥5〉= seems legit

Does not know the answer, but knows what rules a correct answer satisfies

Back to superposition

Collapsing a qubit

If you collapse it too early, you get randomness!

If you collapse it too late, you get randomness!

But if you collapse it after exactly (𝜋/4)√N repetitions...

Very high chance of getting the correct answer!

Is it that fast?

Classical computing = O(1/2N)

Quantum computing = O(√N)

N = 1,000,000 → ~500,000 steps

N = 1,000,000 → ~1,000 steps

Moar fast!

Bernstein–Vazirani algorithm demo

BV Oracle Function

Did we learn anything?

Is it faster than classical computing?

Yes, but no. And only for some things.

Will quantum computers replace classical?

No.

Are my nudes safe?

Maybe. But delete them to be safe.

Can it run DOOM?

Yes and no.

Should you drop everything and become a quantum engineer?

No.

Learn more:

Grover's Algorithm: https://www.youtube.com/watch?v=RQWpF2Gb-gU

Learn Q#: https://quantum.microsoft.com/en-us/tools/quantum-coding

Detailed intro to quantum: https://quantum.country/

Slides: https://slides.com/eugene-romero/quantum