L'algorisme de recompte quàntic és un algorisme quàntic per comptar de manera eficient el nombre de solucions per a un problema de cerca determinat. L'algorisme es basa en l'algorisme d'estimació de fase quàntica i en l'algorisme de cerca de Grover.
Els problemes de recompte són comuns en diversos camps com l'estimació estadística, la física estadística, les xarxes, etc. Pel que fa a la computació quàntica, la capacitat de realitzar un recompte quàntic de manera eficient és necessària per utilitzar l'algorisme de cerca de Grover (perquè executar l'algorisme de cerca de Grover requereix saber quantes solucions existeixen). A més, aquest algorisme resol el problema de l'existència quàntica (és a dir, decidir si existeix alguna solució) com un cas especial.
L'algorisme va ser ideat per Gilles Brassard, Peter Høyer i Alain Tapp el 1998.
El problema Considereu un conjunt finit de mida i un conjunt de "solucions" (és a dir, un subconjunt de ). Defineix:
En altres paraules, és la funció indicadora de .
Calcula el nombre de solucions
Solució clàssica Sense coneixements previs sobre el conjunt de solucions (o l'estructura de la funció ), una solució determinista clàssica no pot funcionar millor que , perquè tots els elements de s'ha d'inspeccionar (considereu un cas en què l'últim element a inspeccionar és una solució).
L'algorisme miniatura|500x500px|Circuit de recompte quàntic
Configuració L'entrada consta de dos registres (és a dir, dues parts): la part superior Els qubits formen el primer registre i el registre inferior Els qubits són el segon registre.
Crea superposició L'estat inicial del sistema és Després d'aplicar l'operació de porta Hadamard de diversos bits a cadascun dels registres per separat, l'estat del primer registre és
i l'estat del segon registre és
un estat de superposició igual en la base computacional.
Operador de Grover Perquè la mida de l'espai és i el nombre de solucions és , podem definir els estats normalitzats:
Tingueu en compte que
que és l'estat del segon registre després de la transformada d'Hadamard.
La visualització geomètrica de l'algorisme de Grover mostra que a l'espai bidimensional que cobreix i , l'operador de Grover és una rotació en sentit antihorari; per tant, es pot expressar com
en la base ortonormal .
De les propietats de les matrius de rotació sabem que és una matriu unitària amb els dos valors propis .
Estimació del valor de θ A partir d'aquí, seguim l'esquema de l'algorisme d'estimació de fase quàntica : apliquem operacions controlades de Grover seguides de la transformada quàntica inversa de Fourier; i segons l'anàlisi, trobarem el millor aproximació de bits al nombre real (pertanyent als valors propis de l'operador Grover) amb probabilitat superior a .
Cal tenir en compte que el segon registre es troba en realitat en una superposició dels vectors propis de l'operador de Grover (mentre que en l'algorisme original d'estimació de fase quàntica, el segon registre és el vector propi requerit). Això significa que, amb certa probabilitat, aproximem , i amb certa probabilitat, aproximem ; aquestes dues aproximacions són equivalents.
Anàlisi Suposant que la mida de l'espai és com a mínim el doble del nombre de solucions (és a dir, suposant que ), un resultat de l'anàlisi de l'algorisme de Grover és:
Així, si trobem , també podem trobar el valor de (perquè es coneix).
L'error
està determinat per l'error dins de l'estimació del valor de L'algorisme d'estimació de fase quàntica troba, amb alta probabilitat, el millor aproximació de bits de ; això vol dir que si és prou gran, tindrem , per tant .
Usos L'algorisme de cerca de Grover per a un nombre inicialment desconegut de solucions En l'algorisme de cerca de Grover, el nombre d'iteracions que s'han de fer és .
Així, si és conegut i es calcula mitjançant l'algorisme de recompte quàntic, el nombre d'iteracions de l'algorisme de Grover es calcula fàcilment.
Acceleració de problemes NP-complets L'algorisme de recompte quàntic es pot utilitzar per accelerar la solució de problemes NP-complets.
Un exemple d'un problema NP-complet és el problema del cicle hamiltonià, que és el problema de determinar si un graf té un cicle hamiltonià.
Una solució senzilla al problema del cicle hamiltonià és comprovar, per a cada ordre dels vèrtexs de , tant si es tracta d'un cicle hamiltonià com si no. La cerca a través de totes les possibles ordenacions dels vèrtexs del graf es pot fer amb el recompte quàntic seguit de l'algorisme de Grover, aconseguint una acceleració de l'arrel quadrada, similar a l'algorisme de Grover.Aquest mètode troba un cicle hamiltonià (si existeix); per determinar si existeix un cicle hamiltonià, l'algorisme de recompte quàntic és suficient (i fins i tot l'algorisme d'existència quàntica, descrit a continuació, és suficient).
Problema d'existència quàntica El problema de l'existència quàntica és un cas especial de recompte quàntic en què no volem calcular el valor de , però només volem saber si o no.
Una solució trivial a aquest problema és utilitzar directament l'algorisme de recompte quàntic: l'algorisme dóna com a resultat , així comprovant si obtenim la resposta al problema d'existència. Aquest enfocament implica informació general perquè no ens interessa el valor de L'estimació de fase quàntica es pot optimitzar per eliminar aquesta sobrecàrrega.
Si no us interessa el control de la probabilitat d'error, utilitzar una configuració amb un nombre petit de qubits al registre superior no produirà una estimació precisa del valor de , però serà suficient per determinar si és igual a zero o no.
Problema de prova de relacions quàntiques Proves de relacions quàntiques . és una extensió de les proves d'existència quàntica, decideix si es pot trobar almenys una entrada a la base de dades que compleixi la relació amb un cert valor de referència. P. ex. retorna YES si la base de dades conté qualsevol valor superior a 5, altrament retorna NO. Les proves de relacions quàntiques combinades amb la cerca logarítmica clàssica formen un algorisme eficient de cerca quàntica de mínims/màxims.
Referències
Categoria:Algorismes Categoria:Mecànica quàntica