Estou interessado em exemplos de problemas em que um teorema que aparentemente não tem nada a ver com mecânica / informação quântica (por exemplo, afirma algo sobre objetos puramente clássicos) pode, no entanto, ser provado usando ferramentas quânticas. Uma pesquisa Quantum Proofs for The Classems Classical (A. Drucker, R. Wolf) fornece uma boa lista de tais problemas, mas certamente há muitos mais.
Particularmente interessantes seriam exemplos em que uma prova quântica não é apenas possível, mas também "mais esclarecedora", em analogia com análises reais e complexas, onde colocar um problema real em um cenário complexo geralmente o torna mais natural (por exemplo, a geometria é mais simples, pois é fechado algebricamente etc.); em outras palavras, problemas clássicos para os quais o mundo quântico é seu "habitat natural".
(Não estou definindo "quantumness" aqui em um sentido preciso, e pode-se argumentar que todos esses argumentos acabam se resumindo à álgebra linear; bem, também é possível traduzir qualquer argumento usando números complexos para usar apenas pares de reais - mas e daí ?)
fonte
Respostas:
Há um artigo recente de Scott Aaronson, que fornece uma nova prova de que a permanente é difícil. Essa prova é baseada no modelo de computação quântica linear-óptica e é mais intuitiva do que a de Leslie Valiant.
fonte
Na minha opinião, gosto do seguinte artigo:
Katalin Friedl, Gabor Ivanyos, Miklos Santha. Teste eficiente de grupos. Em STOC'05.
Aqui eles definem um testador "clássico" para grupos abelianos. No entanto, primeiro eles começam fornecendo um testador quântico e depois eliminam todas as partes quânticas.
O que eu gosto neste artigo é que eles usam o testador quântico para obter intuição e o usam para abordar o problema. Pode parecer uma abordagem mais difícil (a partir do quantum e do clássico), mas os autores são pesquisadores bem conhecidos na computação quântica. Talvez para eles seja mais fácil começar com isso.
Eu diria que sua principal contribuição técnica é um testador de homomorfismo, que eles usam para eliminar as partes quânticas.
fonte
Dois resultados muito recentes e interessantes:
Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary e Ronald de Wolf provaram que "não existe um programa linear de tamanho polinomial (LP) cujo polítopo associado seja projetado no polítopo do vendedor ambulante, mesmo que não seja necessário que o LP seja simétrico. "(citado no resumo).
Eles usam a complexidade da comunicação quântica como uma ferramenta. Veja o artigo deles e a publicação de Gil Kalai no blog . Observe também o comentário de Dave no post de Gil Kalai. Ainda não li o jornal, então não posso comentar sobre onde e como as coisas quânticas são usadas.
Andrew M. Childs, Shelby Kimmel e Robin Kothari usaram a complexidade da consulta quântica para provar limites mais baixos para uma medida muito clássica, que é a contagem de portas de fórmula de funções como PARITY. Veja o jornal deles .
fonte
Como os permanentes fornecem as amplitudes de probabilidade dos resultados de medição dos bósons após interferirem em um interferômetro linear, Scheel obteve uma simples prova "quântica" de que o valor absoluto da permanente de qualquer matriz unitária é 1 ( http://arxiv.org/abs / quant-ph / 0406127 ).
fonte
Um limite quântico inferior para distinguir funções aleatórias de permutações aleatórias Henry Yuen
fonte