Tempos de acerto quântico de um tiro

No artigo Passeios aleatórios quânticos atingidos exponencialmente mais rápido ( arXiv: quant-ph / 0205083 ) Kempe fornece uma noção de tempo de acerto para caminhadas quânticas (no hipercubo) que não é muito popular na literatura sobre caminhadas quânticas. É definido da seguinte forma:

One-Shot Quantum Bater Time: Um passeio de tempo discreto quantum tem uma $(T,p)$ one-shot $(|\Psi_0\rangle,|\Psi^f\rangle)$ -hitting tempo se $|\langle\Psi^f|U^T|\Psi_0\rangle|^2 \geq p$ onde $|\Psi_0\rangle$ é o estado inicial, $|\Psi^f\rangle$ é o estado de destino, e $p>0$ é a probabilidade de acerto.

Normalmente você gostaria de saber o mínimo $T$ tal que $p>0$ . Não é possível (corrija-me se estiver errado) definir uma noção de tempo médio de acerto, porque você precisará fazer medições durante a caminhada, o que a reduziria a uma caminhada clássica. É por isso que temos a noção de um tiro. No mesmo trabalho, há uma aplicação ao roteamento quântico (consulte a seção 5 ).

Para saber que a caminhada chegou ao vértice de destino, você precisa fazer uma medição apenas nesse nó. Por exemplo, no hipercubo dimensional com $n$ nós, se você iniciar no nó e têm como nó de destino , as mostras de papel que com uma probabilidade de erro limitado, ou seja, como $2^n$ $|\Psi_0\rangle=|00\dots00\rangle$ $|\Psi^f\rangle=|11\dots11\rangle$ $T=O(n)$ $p\to 1$ $n$ torna-se muito grande. Então, para detectar que a caminhada chegou a você faz uma medição após etapas. Essa é uma aceleração exponencial. $|11\dots11\rangle$ $\Omega(n)$

Questões:

Para usar essa noção de tempo de acerto para a pesquisa, você precisa saber pelo menos a distância do vértice alvo da origem, porque é assim que você sabe quando aplicar sua medida. Digamos que você tenha um gráfico e defina como vértice inicial e deseja alcançar . Considere-se também que e . Bem, $G$ $v_0$ $v^f$ $T=O(dist(v_0,v^f))$ $p\geq 1/2$ $T$ é óbvio porque você precisa de pelo menos muitos passos para alcançá-lo. Faz algum sentido usar esse tempo de busca para a pesquisa? Se você sabe onde o nó está, não há sentido em pesquisar, mas ter uma informação como "distância do vértice inicial", mas não saber exatamente onde está o alvo, essa noção de tempo de acerto dá alguma coisa interessante (vale a pena estudar ) algoritmo de pesquisa?
A aplicação ao roteamento quântico faz algum sentido? No artigo, ele diz que pode ser usado para rotear pacotes, mas parece-me que você só pode enviar 1 bit, por exemplo, chegou ao destino ou não? Você pode realmente enviar um estado quântico nessa estrutura? No artigo, esta questão não está sendo abordada.
Talvez essa seja uma pergunta boba, mas aqui vai. Você pode usar essa noção de tempo de execução para construir um "Interferômetro Generalizado Mach-Zender"?

Estou ciente das outras noções de tempos de acerto para caminhadas quânticas (como as de Szegedy ou Ambainis ). Estou particularmente interessado nesse tempo específico de chegada.

Atualização (24/09/2010): Graças a Joe Fitzsimons, as perguntas 2 e 3 foram completamente respondidas. Embora a pergunta número 1 ainda permaneça. Primeiro, vou repetir a pergunta 2 em termos mais específicos, agora que terminei de ler o artigo que Joe me recomendou e mais algumas (por exemplo, consulte arXiv: 0802.1224 ), e depois darei um exemplo concreto do que tenho em mente para a pergunta 1.

2 '. Se você estiver enviando uma mensagem concreta (como uma sequência de bits clássicos), poderá usar uma unidade mais complicada que copiará essas informações durante as etapas da caminhada. Para enviar estados quânticos, você precisa de algo mais. O canal de cadeias de spin usa uma matriz linear de qubits com um acoplamento fixo. Você pode colocar o estado (estado puro, não sei se funciona para estados mistos) que deseja transmitir em uma extremidade e ela vai para a outra extremidade com alta fidelidade, de acordo com os resultados numéricos. Ainda tenho que pensar mais, mas tenho duas idéias: i) coloque uma corrente em cada elo do gráfico ou ii) faça a caminhada, encontre o estado alvo, faça o canal entre o estado inicial e o alvo e envie o Estado. Alguma dessas abordagens é plausível? Funciona com estados mistos?

1 '. Considere uma caminhada em uma grade bidimensional centrada na origem com nós com cada lado com comprimento $n$ . Defina o estado inicial eme o estado de destino em $\sqrt{n}$ $v_0=(0,0)$ onde $v^f=(\sqrt{n}-1,a)$ . Como a caminhada é simétrica, temos que o mesmo tempo e probabilidades de acerto valem para qualquer alvo em algum lugar na borda da grade, como mostrado abaixo. $a=0,\dots,\sqrt{n}-1$

texto alternativo

$dist(v_0,v^f)=\Omega(\sqrt{n})$ $\Omega(\sqrt{n})$ $O(\sqrt{n\log n})$ $\sqrt{n\log n}$

quantum-computing random-walks markov-chains quantum-walk Marcos Villagra
fonte

Respostas:

Não estou tão familiarizado com este documento, mas tentarei dar uma resposta aproximada a cada uma das suas perguntas após uma breve análise.

$O(\mbox{dist}(v_0, v^f))$ $O(\sqrt{n})$ $T=O(\mbox{dist}(v_0, v^f))$
Presumo que o autor esteja levando um pacote inteiro para fazer a caminhada aleatória. Obviamente, isso requer uma unidade unitária um pouco mais complicada, mas realmente não vejo um problema. Como alternativa, Burgarth e Bose têm um esquema muito bom para codificar informações em gráficos idênticos, o que também funcionaria se você simplesmente substituísse suas cadeias 1d pela rede de escolha ( quant-ph / 0406112 ).
Bem, você não precisa dessa noção de tempo de jogo. Os hipercubos têm transferência de estado perfeita (consulte, por exemplo, quant-ph / 0309131 e quant-ph / 0411020 ), para que você possa ver o transporte em um hipercubo como um interferômetro com o interferômetro Mach-Zender correspondente ao caso 2d.

UPDATE: (Para responder à pergunta atualizada sobre passeios aleatórios em uma grade ou outra rede)

$v_t$ $v^f$

Joe Fitzsimons
fonte

n

$n$

Ω (n^{1 / d})

$\Omega(n^{1/d})$

∣ v_{0} - v^{f} ∣^{- \frac{1}{2}}

$\mid v_0 - v^f \mid^{-\frac{1}{2}}$

O (t^{- 1})

$O(t^{-1})$

Sim, exatamente. A figura que eu dei é apenas para um sistema específico. Eu simplesmente queria destacar que nem sempre é possível obter uma probabilidade de acerto constante independente do número de vértices.

Joe Fitzsimons

Mas voltando à pergunta sobre pesquisa, dei o exemplo em grades porque estava pensando em "pesquisa espacial em grades" (quant-ph / 0303041). Ainda assim, parece-me que, para fazer uma medição para ver se você atinge o alvo, é necessário fazê-lo no subespaço que contém o alvo. Como eu imagino, você precisa de um dispositivo nesse subespaço para verificar constantemente se a caminhada chegou ou não. Meu problema é que parece que você sempre precisa saber mais ou menos onde está o seu objetivo. (continuar)

Marcos Villagra

Com relação à pergunta 1, conhecer a distância entre o vértice alvo desconhecido e algum vértice de origem conhecido no hipercubo pode ajudar o processo de pesquisa. No entanto, o valor da distância em si determina o quanto essas informações são úteis.

Os algoritmos típicos de caminhada quântica são geralmente variações / aproximações da pesquisa de Grover: envolvem uma rotação aproximada do vetor de estado em um subespaço 2-d do espaço total de Hilbert.

Você pode usar esses algoritmos para preparar com eficiência uma superposição aproximadamente uniforme de todos os vértices a uma determinada distância da origem. Em seguida, você pode pesquisar seu vértice alvo dentro dessa superposição usando a pesquisa quântica ou clássica (Monte Carlo): Para pesquisa clássica, apenas prepare a superposição e meça-a na base do vértice e repita até encontrar o alvo. Para pesquisa quântica, o procedimento de preparação de superposições (e seu inverso) se torna uma sub-rotina que substitui a transformação Hadamard na iteração Grover.

$n$ $d$ $\binom{n}{d}$ $\approx \frac{2^n}{\sqrt{\frac{\pi}{2}n}}$ $\approx n/2$

Antonio Valério Miceli-Barone
fonte