Conférences (Rapports L3) 1er Septembre

Quantum Computing

It all begins with Feynman. Why don’t you try to build a machine underlied by quantum mechanics ?

Extraordinary progress made :

  • Tomography
  • Foundation
  • Cryprotgraphy

Why laws of macro don’t “apply” to micro ?

This computational tools has completely opened new doors -> not only for physicists anymore

Questions : What do/can we do with QC ?

Buzz words : superposition, etc…

  1. Deterministic : step by step
  2. Probabilistic : randomized, proba trees, etc…
  3. Quantum : proba + ℂ numbers ⟹ THERE IS NEGATIVE proba ⟹ there is interference of quantum, can cancel out each other

Deutsch and Jozca : first quantum thinking paradigm

Input : x ∈ {0,1}^n, $f$ a function : how many tries to determine if f is constant ? ⟹ 2^n tries (we overdue) VS Q : only 1 try There exists a witness to say if a function is constant or not

Simon’s pb

How to determine the period of a periodic function ? In Q : only 1 try ⟹ Ouput in 1 go THEN check the property

Shor’s Period finding pb

Given a n-bit int, find the prime factorisation. Breaks the RSA cryptosystem !

Q algorithms

The Zoo - Stephen Jordan

  1. Algebraic and Number Theoretic Algo ⟶ All crypto will be broken

  2. Oraculr Algo ⟶ ex: sqrt speed-up for search algo

  3. Approximation and Simulation Algo ⟶ original idea of Feynman : simulation (perfect for physicists, e.g)

    • optimization
  • Refuting the strong Church-Turing Thesis because in QC ∃ simulators NOT equivalent with TM Computability revamped

Why does it jeopardize classical cryptography ? QC relies on the laws of QMechanics

Classical Cryptgraphers VS Q Crypto ⟹ fight

Q Principles :

very simple :

  1. Measure perturbs the system
  2. Uncertainty Principle
  3. No cloning

    How is it secure ? Knowing that sb has tried to tamper with the lock doesn’t necessarily protect the content that is to be protected

TODO : Because of Pauli principle ?

Quantum Money

How to create a quantum money ?

Serial numbers to copyable because of QM

Quantum Key Distribution

China has launched a satellite to enable QKD over 2000kms

  • 10 qubits : max
  • 14 ions isolated

BUT : we need to have 40 qubits to be done (2^40)

  • 30 qubit machine by Google ? (buyed by Google)

⟹ quastion of engineering/Money

We’re going to build a device that is not classically


Bra, Ket ⟶ Linear algebra We work (to simplify) in a closed system

Represent, Evolve, Measure,

Basis : if the vectors that I’m trying to determine are not ortho, they can’t be distinguished

Entanglement :

Leave a Comment