Saltar al contenido ForoHackers

Quantum algorithms: start here

Algoritmos cuánticos
#723 · Ophuscado · · Denunciar

A quantum algorithm is a recipe of gates that uses interference to find an answer with fewer steps than any known classical method, for certain problems. The gain is rarely universal: some algorithms are exponentially faster, others only quadratically, and many problems gain nothing. Knowing which is the skill.

Key concepts

  • Oracle problems: Deutsch-Jozsa, Bernstein-Vazirani and Simon show speed-ups in a clean model where a black box is queried.
  • Quantum Fourier transform: a fast change of basis that exposes periodicity; it is the heart of Shor's algorithm.
  • Shor's algorithm: finds the period behind integer factoring and discrete logarithms, which threatens some public-key cryptography.
  • Grover's search: a quadratic speed-up for unstructured search, by repeatedly amplifying the marked item.
  • Variational and simulation methods: quantum simulation of physical systems, and hybrid loops that tune circuit parameters classically.

Vocabulary

  • Query complexity: the number of calls to an oracle an algorithm needs.
  • Amplitude amplification: the generalisation of Grover's idea to raise the probability of good outcomes.
  • BQP: the problems a quantum computer solves in polynomial time with small error.
  • Post-quantum cryptography: classical schemes designed to resist known quantum attacks.

What to study, in order

  1. Quantum circuits and measurement, and the linear algebra they use.
  2. Implement Deutsch-Jozsa and Bernstein-Vazirani in a simulator and see why interference gives the answer.
  3. Work through Grover's search on four and eight items, and count the iterations.
  4. Learn the quantum Fourier transform, then phase estimation.
  5. Follow Shor's algorithm: the classical reduction to period finding, then the quantum step.

Related tags

#quantum-computing #complexity #cryptography #algorithms #linear-algebra

Inicia sesión o únete para responder.