Idéias de projetos de computação quântica

14

Sou estudante de graduação em ciência da computação e atualmente estou planejando meu projeto de graduação. Eu preciso de algumas idéias no campo da computação quântica. qualquer ajuda?

Deyaa
fonte
Seria bom se você desse um exemplo do tipo de projeto que consideraria apropriado, dado o tempo que você tem para esse projeto e a dificuldade pretendida. Como ler um artigo em detalhes é aceitável como projeto?
Robin Kothari
Exemplo: combinando (ou inventando novas) técnicas de aprendizado de máquina com computação quântica para resolver um problema difícil O Google usou algoritmos de aprendizado de máquina e computador quântico de onda D para fazer uma pesquisa de imagens muito mais rápida. Tempo, eu tenho: 11 meses dificuldade: médio (Graduação)
Deyaa 28/08
3
Eu acho que esse deve ser um wiki da comunidade, assumindo que ele esteja no escopo.
Lev Reyzin
2
@ Ross: Eu diminuí a votação, simplesmente porque a pergunta não era clara, muito aberta, subjetiva e certamente não era algo com uma clara "resposta correta" (consulte também cstheory.stackexchange.com/faq ). Com explicações mais cuidadosas e no modo "wiki da comunidade", provavelmente teria evitado meu voto negativo. Desculpas se isso parecer desnecessariamente duro, mas acho que as pessoas devem prestar mais atenção à formulação de suas perguntas (e usar o sinalizador CW corretamente, especialmente porque ninguém mais pode corrigi-lo atualmente).
Jukka Suomela 28/08/10
3
@Deyaa, acho que tentar responder às perguntas de Joe Fitzsimmons e Jukka Suomela ajudará você a criar uma pergunta melhor.
Suresh Venkat

Respostas:

27

Publiquei algumas idéias de projetos da teoria da complexidade quântica em http://scottaaronson.com/blog/?p=471

(Mas cuidado, muitos destes problemas estão abertos há anos! Minha sugestão para um projeto de graduação seria interromper um pedaço de um dos problemas.)

Scott Aaronson
fonte
17

Um projeto que eu sugeriria é o seguinte: tente desenvolver um algoritmo quântico baseado na caminhada aleatória quântica para programação linear. Para o projeto, você deve primeiro aprender alguns fatos básicos sobre passeios aleatórios quânticos e como eles são úteis algoritmicamente, segundo sobre algoritmos aleatórios do tipo simplex e terceiro tentando combinar os dois. A parte 3 é muito ambiciosa e eu não sei se alguma coisa proveitosa pode ser dita, mas as partes 1 e 2 já são boas para um projeto de graduação.

Gil Kalai
fonte
1
Essa é uma sugestão muito legal. De fato, há um bom número de algoritmos que podem se beneficiar de passeios aleatórios especializados. Os códigos de correção de erros do LT / Raptor são baseados em uma caminhada aleatória, por exemplo. Voto de mim. E é bom ver você aqui, Gil. :-)
Ross Snider
Eu não sabia que havia coisas como caminhadas aleatórias quânticas! boa ideia !
Suresh Venkat
2
Suresh: Sim, existem. Eles se mostram uma abordagem bastante importante para os algoritmos quânticos. O problema dos projetos de algoritmos, porém, é que é trivial obter uma aceleração da raiz quadrada e muito muito difícil obter algo melhor. Talvez outra idéia seria tentar tentar obter algoritmos de tempo polinomial para logar, como no algoritmo recente para resolver sistemas lineares de equações.
Joe Fitzsimons
11

Os resultados do DWaves com a pesquisa de imagens são um pouco estranhos. Atualmente, não há fortes evidências de que os dispositivos da DWave não possam ser simulados com eficiência. Isso foi discutido detalhadamente em vários blogs (para Scott Aaronson e Dave Bacon já cobriram a DWave várias vezes).

Agora, deixando isso de lado, há um grande número de projetos em potencial, dependendo de qual aspecto da computação quântica você está interessado. Também depende do nível de seu conhecimento sobre mecânica e física quântica. As questões do tipo arquitetura geralmente se tornam bastante físicas, pois as limitações experimentais desempenham um papel importante na determinação de quais problemas vale a pena examinar. Algoritmos e complexidade das comunicações são muito mais áreas orientadas para o CS.

Existem vários modelos diferentes de computação quântica e existem barreiras mais acentuadas à entrada de alguns do que de outros. A computação quântica adiabática e topológica tende a ser um pouco mais difícil de entrar do que o modelo de circuito e o modelo de computação baseado em medição.

Um problema em que tive sucesso com um aluno de verão trabalhando foi aproximar os limites de tolerância a falhas para vários códigos de correção de erros por simulação. Isso é algo que tem uma barreira relativamente baixa à entrada. Outra idéia é examinar esquemas de autômatos celulares quânticos para tarefas de finalidade especial (codificação, medição, preparação de estados).

Você mencionou o aprendizado de máquina; portanto, talvez você queira usar a programação evolutiva para desenvolver circuitos quânticos para vários problemas simples. Eu brinquei com isso algumas vezes e parece que você pode ter um comportamento bastante agradável (por exemplo, regras de pesquisa em evolução).

Eu poderia continuar listando idéias aleatórias que podem fazer um projeto adequado, mas se você puder dar uma idéia maior sobre a área em que está interessado, acho que obterá respostas melhores. Uma pergunta fundamental pode ser simplesmente: você está interessado em um projeto de codificação, um sobre design de hardware, outro sobre teoria pura, etc.? Dependendo do caminho que você deseja seguir, haverá várias possibilidades.

Joe Fitzsimons
fonte
4

Sugiro algo como fornecer as ferramentas atuais de desenvolvimento da computação quântica (como a libquantum) com a capacidade de tirar proveito das GPUs habilitadas para CUDA para acelerar as simulações. A computação quântica trata mais ou menos de álgebra linear, isto é, operações matriciais e vetoriais, para as quais as GPUs foram projetadas em primeiro lugar.

M. Alaggan
fonte
simulações como o que?
Deyaa 29/08/10
As ferramentas de desenvolvimento da computação quântica permitem simular algoritmos e protocolos quânticos, incluindo o algoritmo de Shor, a pesquisa de Grover, o teletransporte quântico, os códigos de correção de erros e os algoritmos que você criou e deseja testar por si mesmo.
M. Alaggan
3

Linguagens temáticas de computação quântica, como QCL, foram criadas para projetos de tese. De fato, todas as linguagens baseadas em computação quântica que eu já vi implementadas na Web foram feitas para projetos de tese. Você também pode tentar codificar um emulador quântico. No livro "Computação quântica para cientistas da computação", eles fornecem exercícios de programação que, coletivamente, se somam a esse emulador.

Vincent Russo
fonte
2

Não sei como isso será útil, mas talvez ele ofereça alguma orientação.

Na primavera de 2009, Sasha Razborov ministrou um curso sobre computação quântica. O site do curso contém algumas idéias de "projeto", bem como referências a alguns documentos quânticos seminais.

Os "projetos" na página são realmente apenas "problemas de lição de casa mais envolvidos", portanto, provavelmente não são adequados para uma tese de nível superior, nem levarão 11 meses. No entanto, esses problemas e / ou algumas das referências podem gerar boas idéias para você.

Joshua Grochow
fonte