Saltar al contenido ForoHackers

A quantum computer is not a machine that tries every answer at once

Algoritmos cuánticosComputación cuánticaInformación cuántica
#1080 · quantum_tunnel_rat · · Denunciar

The most repeated sentence about quantum computing is also the most misleading: "it tries all the possibilities at the same time". Let me give a more careful picture.

A register of n qubits is described by 2^n complex amplitudes. That is the "all possibilities" part: the state is a superposition over every bit string. But when you measure, you get just one n-bit string, chosen at random with probability equal to the squared magnitude of its amplitude. You do not get to read the whole list of amplitudes.

So a quantum algorithm is not "compute everything, then pick the best". It is a trick to arrange the amplitudes so that the wrong answers cancel out (destructive interference) and the right ones add up, so that measuring gives the right answer with high probability. That is hard to do, and it works only for problems that have the right structure.

Two consequences:

  • There is no general speedup for "try all the candidates". For unstructured search the best you can get is a quadratic improvement, not an exponential one.
  • The information you can extract is limited: n qubits can carry at most n classical bits out, however large the state space is.

If a description makes it sound easy, it left out the interference.

#1667 · bitflip_betty · · Denunciar

Coming from the hardware side: the other half of "it is hard" is that the amplitudes are fragile. Every stray interaction with the environment acts like a measurement and the interference pattern is gone. Error correction costs many physical qubits per logical one. The maths is elegant, the engineering is a battle against noise.

#1668 · off_by_two · · Denunciar

Puzzle for the thread: if n qubits hold 2^n amplitudes and measuring gives only n bits, where is the "extra" information, and can anything use it before measurement?

#1669 · quantum_tunnel_rat · · Denunciar

That is the right question. It is used during the computation: gates act on all amplitudes at once, and interference lets them influence each other. After measurement it is gone. A good algorithm makes sure that what survives the final measurement is the answer you wanted.

Inicia sesión o únete para responder.