Photon phreaking:

What quantum can (actually) do for security

Gemalto Crypto Club 23 Feb 2017
Alan Robertson
Sarah Kaiser

Quantum Operations

Classical: Bitflip
Quantum: Rotations about some axis
Quantum: Measurement is the overlap between the state and some basis vector

Quantum Measurement

Requires a basis
Outcomes are non-deterministic
Destroys phase information, only can measure once

Quantum System Properties

No-Cloning Theorem: Quantum states cannot be copied
Entanglement: The state of a qubit is "correlated" with the state of another qubit

You cannot describe the effect of a rotation on only one qubit in set of entangled qubits

A Pathological Example

A Pathological Example

Quantum Algorithms

Deutch-Jozsa: Free$^{*}$ parallelism, reduces from $O(2^{n-1})$ to $O(1)$ function calls

Grover's Algorithm: Search an unsorted list for an$^{**}$ element in $O(\sqrt{n})$, best classical is $O(n)$

Shor's Algorithm: A faster prime factoring algorithm, because fourier transforms are unitary

Shor's Algorithm

GNFS: Generate polynomials and hope that their roots form a smooth ring such that the 'square root' of the ring is a homomorphism to the prime factors

Shor's algorithm: Find the period of the prime field using the quantum fourier transform, the 'square root' then gives the prime factors

Common Myths and Misconceptions

Quantum computers are NOT universally faster or more powerful than classical computers
Quantum computers will NOT be here tomorrow.
have:100 qubits / need: 100 million
Dwave is NOT a quantum computer. Evidence shows quantum annealer at best
There is no one right material or system to make qubits