Existe um equivalente à derandomização para algoritmos quânticos?

Com alguns algoritmos aleatórios, você pode des randomizar o algoritmo, removendo (a um possível custo em tempo de execução) o uso de bits aleatórios e maximizando um limite inferior ao objetivo (geralmente calculado usando o fato de que os teoremas têm o desempenho esperado do algoritmo aleatório). algoritmo). Existe um equivalente para algoritmos quânticos? Existem resultados bem conhecidos de "desquantização"? Ou o espaço de estado subjacente é muito grande para esse tipo de técnica?

Houve uma postagem no blog da Fortnow sobre esse tópico. Acredita-se que não há esperança de um programa de "desquantização", semelhante ao programa de des randomização.

Por outro lado, para alguns resultados não quânticos específicos que foram obtidos usando métodos quânticos, foi possível remover a quantumidade na prova. Por exemplo, Kerenidis e de Wolf (2002) provaram o primeiro limite inferior exponencial para o comprimento de códigos decodificáveis ​​localmente não lineares de 2 consultas usando argumentos quânticos. Mais tarde, Ben-Aroya, Regev e de Wolf (2007) puderam remover a quantumidade da prova (embora a linha de argumentação ainda modelasse a quantum). Situações semelhantes também surgiram na comprovação de limites inferiores para rigidez das matrizes de Hadamard e na demonstração de que o PP está fechado sob interseção (embora em ordem cronológica inversa :)). Veja esta pesquisa de Drucker e de Wolf para referências e discussão.

Existem certas classes de portas quânticas que podem ser simuladas eficientemente com um computador clássico. Se nenhum emaranhado estiver presente, uma computação com estados puros (isto é, sem estados aleatórios) pode ser simulada com eficiência. Portões clássicos portões reversíveis são um subconjunto de portões quânticos e, portanto, podem obviamente ser simulados com eficiência. Esses dois exemplos são bastante triviais, no entanto, existem vários conjuntos de portas não triviais conhecidos.

1. Portões valentes, como mencionado na resposta de Josué
2. Portões do grupo Clifford (consulte arXiv: quant-ph / 0406196 )
3. Portões de fósforo (ver arXiv: 0804.4050 )
4. Portões pendulares, etc.

Basicamente, a maioria dos conjuntos de operadores que geram apenas um pequeno subespaço de tendem a ser simuláveis, enquanto os que geram são tão difíceis quanto a simulação quântica geral de N qubits.$SU(2^N)$$SU(2^N)$

Parece muito improvável que a mecânica quântica seja eficientemente simulável e, portanto, esse programa de desquantização provavelmente será impossível em geral. No entanto, existe um regime em que isso funcionou, que é com provas interativas. Foi demonstrado que vários tipos diferentes de sistemas de prova interativos com verificadores quânticos têm o mesmo poder se o verificador quântico for substituído por um verificador puramente clássico. Para um exemplo disso, consulte a prova de Jain, Ji, Upadhyay e Watrous de que QIP = PSPACE ( arXiv: 0907.4737 ).

Uma configuração interessante para estudar a "desquantização" é a complexidade da comunicação. Aqui, uma questão interessante é se um limite superior pode ser colocado na quantidade de emaranhado que Alice e Bob precisam compartilhar para alcançar um protocolo quântico eficiente para resolver algum problema. Este seria um análogo quântico do Teorema de Newman a partir da complexidade clássica da comunicação. Gavinsky deu um problema relacional para o qual isso não pode ser feito, mas até onde eu sei, isso ainda está aberto para problemas funcionais (totais).

Além disso, um adendo ao comentário de Joe sobre os portões pendulares: Bremner, Jozsa e Shepherd mostraram recentemente (arXiv: 1005.1407) que é improvável que uma noção específica de circuitos pendulares seja simulável, pois isso derrubaria a hierarquia polinomial para o terceiro nível.

Embora, em geral, a "desquantização" seja improvável, acredito que esse tipo de idéia tenha ajudado a inspirar os algoritmos holográficos de Valiant. Ou, pelo menos, você pode ver o trabalho dele como alguns resultados de desquantização parcial em classes restritas de circuitos quânticos. Veja, por exemplo: L. Valiant. Circuitos quânticos que podem ser simulados classicamente em tempo polinomial. SIAM J. Comput. 31 (4) 1229-1254 (2002).