Prova de segurança rigorosa para o dinheiro quântico de Wiesner?

50

Em seu célebre artigo "Conjugate Coding" (escrito por volta de 1970), Stephen Wiesner propôs um esquema de dinheiro quântico que é incondicionalmente impossível de falsificar, assumindo que o banco emissor tenha acesso a uma tabela gigante de números aleatórios e que as notas possam ser trazidas de volta ao banco para verificação. No esquema de Wiesner, cada nota consiste em um "número de série" clássica , juntamente com um estado quântico dinheiro consistindo de qubits não enredado, cada um quer| ψ sns|ψsn

|0, |1, |+=(|0+|1)/2, or |=(|0|1)/2.

O banco se lembra de uma descrição clássica de para cada . E, portanto, quando é trazido de volta ao banco para verificação, o banco pode medir cada qubit de na base correta ( ou ) e verifique se obtém os resultados corretos.s | ψ s| ψ s{ | 0 , | 1 } | + , | - |ψss|ψs|ψs{|0,|1}|+,|

Por outro lado, devido à relação de incerteza (ou, alternativamente, o Teorema da Não-Clonagem), é "intuitivamente óbvio" que, se um falsificador que não conhece as bases corretas tenta copiar , então o A probabilidade de os dois estados de saída do falsificador passarem no teste de verificação do banco pode ser no máximo , para alguma constante . Além disso, isso deve ser verdade, independentemente da estratégia usada pelo falsificador, consistente com a mecânica quântica (por exemplo, mesmo que o falsificador use medições entrelaçadas sofisticadas em ).c n c < 1 | ψ s|ψscnc<1|ψs

Entretanto, enquanto escrevia um artigo sobre outros esquemas de quantum money, meu co-autor e eu percebemos que nunca vimos uma prova rigorosa da reivindicação acima em nenhum lugar ou um limite superior explícito em : nem no artigo original de Wiesner nem em nenhum outro posterior. .c

Então, tem essa prova um (com um limite superior de ) foi publicado? Caso contrário, pode-se derivar essa prova de maneira mais ou menos direta de (digamos) versões aproximadas do Teorema Sem Clonagem, ou resultados sobre a segurança do esquema de distribuição de chaves quânticas BB84?c

Atualização: À luz da discussão com Joe Fitzsimons abaixo, devo esclarecer que estou procurando mais do que apenas uma redução da segurança do BB84. Em vez disso, estou procurando um limite superior explícito à probabilidade de uma contrafação bem-sucedida (ou seja, na ) --- e, idealmente, também um pouco de compreensão de como é a estratégia ideal de falsificação. Ou seja, a estratégia ideal simplesmente mede cada qubit de independentemente, digamos na base| ψ sc|ψs

{cos(π/8)|0+sin(π/8)|1,sin(π/8)|0cos(π/8)|1}?

Ou existe uma estratégia de falsificação emaranhada que se sai melhor?

Atualização 2: No momento, as melhores estratégias de falsificação que conheço são (a) a estratégia acima e (b) a estratégia que simplesmente mede cada qubit na base e " espera o melhor. " Curiosamente, essas duas estratégias resultam em uma probabilidade de sucesso de (5/8) n . Então, minha conjectura do momento é que (5/8) n pode ser a resposta certa. De qualquer forma, o fato de 5/8 ser um limite inferior em c exclui qualquer argumento de segurança para o esquema de Wiesner que seja "muito" simples (por exemplo, qualquer argumento no sentido de que não há nada não trivial que um falsificador possa fazer e, portanto, a resposta certa é c = 1/2).{|0,|1}

Atualização 3: Não, a resposta certa é (3/4) n ! Veja o tópico de discussão abaixo da resposta de Abel Molina.

Scott Aaronson
fonte
3
Bem-vindo ao TP.SE Scott! Bom ver você aqui.
Joe Fitzsimons
1
Parece que o esquema de Wiesner corresponde exatamente ao BB84, no qual você seleciona o Bob após ter escolhido exatamente as mesmas bases de medição que Alice tem para a preparação (já que o banco é Alice e Bob). Claramente, o banco poderia escolher a base de medição aleatoriamente e simular o BB84, o que renderia uma segurança estritamente mais fraca (já que você consideraria exatamente as mesmas medidas, mas apenas em um subconjunto de qubits), para que você possa certamente usar uma prova do BB84 para reduzir limitava a segurança do esquema quântico de dinheiro. Talvez eu esteja perdendo alguma coisa.
Joe Fitzsimons
Obrigado pela recepção e pela resposta, Joe! FWIW, compartilho sua intuição de que uma prova de segurança para o esquema de Wiesner deveria ser "estritamente mais fácil" do que uma prova de segurança para BB84. No entanto, com esse argumento (como todos os outros), continuo voltando à mesma pergunta: "então qual é o limite superior de c?"
23811 Scott
Certamente, ele é limitado pela probabilidade de determinar a chave no BB84.
Joe Fitzsimons
Além disso, embora seja correto deduzir a segurança do esquema de Wiesner da segurança do BB84, se essa é a única / melhor alternativa, tenho a esperança de que exista uma prova mais direta e informativa. Além disso, parece plausível que uma prova direta seja necessária para obter um limite superior explícito em c ou para obter um limite "razoável" (mais parecido com 0,9 do que com 0,99999).
22811 Scott Schaffner (

Respostas:

33

Parece que essa interação pode ser modelada da seguinte maneira:

  1. Alice prepara um dos estados , , , , de acordo com uma certa distribuição de probabilidade, e envia o primeiro qubit para Bob.| 101 ( | 0 + | 1 ) | 10 / |000|101 (|0-|1)| 11/(|0+|1)|10/2(|0|1)|11/2
  2. Bob executa um canal quântico arbitrário que envia seu qubit a dois qubits, que são devolvidos a Alice.
  3. Alice realiza uma medição projetiva dos quatro qubit em sua posse.

Se não estou errado sobre isso (e desculpe se estou), isso se enquadra no formalismo de Gutoski e Watrous apresentado aqui e aqui , o que implica que:

  1. No Teorema 4.9 do segundo, é ideal que Bob atue de maneira independente quando Alice repete esse processo com vários qubits de maneira independente, se o objetivo de Bob é sempre enganar Alice.
  2. É possível obter o valor de c em um pequeno programa semidefinido. Você pode encontrar mais detalhes sobre como obter este programa na Seção 3 aqui . Veja os comentários para o código cvx do programa e seu valor.
Abel Molina
fonte
10
Seguindo a sugestão de Abel, parece que o valor ótimo é c = 3/4.
3
Acabei de obter o mesmo valor de 3/4. Seu poder explicativo é pequeno, mas o código do computador está em cs.uwaterloo.ca/~amolinap/scriptWeisner.m e cs.uwaterloo.ca/~amolinap/prtrace.m .
Abel Molina
4
A estratégia é dada por um canal quântico cuja representação de Choi-Jamielkowski é uma solução ótima para o programa semidefinido. Veja cs.uwaterloo.ca/~amolinap/optSolution.txt para obter um link para essa solução (o qubit menos significativo é o recebido por Bob e os outros dois são os que ele envia para Alice). Se meus cálculos estiverem corretos, o canal correspondente envia | 0> para (| 01> + | 10>) / √2 com probabilidade 1/6 e para (3 | 00> + | 11>) / √10 com probabilidade 5 / 6 | 1> é enviado para (| 01> + | 10>) / √2 com probabilidade 1/6 e para (| 00> +3 | 11>) / √10 com probabilidade 5/6
Abel Molina
4
Da mesma forma, (| 0> + | 1>) / √2 é enviado para (| 11> - | 00>) / √2 com probabilidade 1/6 e para (| 00> +1/2 | 01> +1 / 2 | 10> + | 11>) / √ (5/2) com probabilidade 5/6. Da mesma forma, (| 0> - | 1>) / √2 é enviado para (| 11> - | 00>) / √2 com probabilidade 1/6 e para (| 00> -1/2 | 01> -1 / 2 | 10> + | 11>) / √ (5/2) com probabilidade 5/6.
Abel Molina
3
Como a resposta da @ AbelMolina também foi convertida em um artigo do arXiv, arxiv.org/abs/1202.4010 , adiciono o link para futuros leitores.
Frédéric Grosshans
19

α|0+β|1αβR

(12+18)2n.72855n
n(58)n

i=12AiρAi

A1=(12+18001801812180)    A2=(01218180180012+18).

i=12AiρAi

A1=112(30010110)    A2=112(01101003).

Elas claramente provêm da mesma família de transformações, mas foram otimizadas para satisfazer diferentes funções objetivas. Essa família de transformações covariantes parece ser dada por

A1=12x2+4y2(x+y00y0yxy0)    A2=12x2+4y2(0xyy0y00x+y).
Peter Shor
fonte
Obrigado Peter! Seria ótimo mostrar otimização ou até quase otimização do clonador. Por isso, acho que o primeiro passo seria mostrar que o ataque ideal é individual e não coletivo.
26811 Scott Aronson
Se a abordagem de Abel Molina funcionar, ela deve demonstrar isso. Caso contrário, você poderá usar as técnicas nos documentos de clonagem ideais para obter um limite superior, mas não sei imediatamente o que seria.
Peter Shor
(|0+i|1)/2(|0i|1)/2c=2/3x=y=1
x=y=1
16

Não conheço uma prova de segurança publicada. Eu pensaria que a maneira mais simples e o limite mais forte viriam da não clonagem aproximada, mas acho que você precisaria de uma versão especializada para os estados do BB84. Mesmo uma redução do BB84 não é óbvia, pois a condição de segurança do BB84 é diferente.

Eu acho que você pode obter uma prova direta como consequência da prova de segurança da criptografia não clonável ( quant-ph / 0210062 ). Isso não terá um limite superior apertado na probabilidade de trapaça, mas pelo menos fornece segurança.

ρk

Isso pode ser usado para criar um esquema de quantum money: O banco A usa criptografia não clonável para criptografar uma sequência aleatória da "mensagem". Existe um esquema de criptografia não clonável que é basicamente o BB84, portanto, isso poderia dar o esquema de Weisner. Eve intercepta o dinheiro, interage com ele e envia o original modificado para o Banco B. Ela também tenta fazer uma cópia, que vai para o Banco C. Os bancos B e C aceitam se o estado fornecido a eles passa no teste de escuta de criptografia não clonável e se eles decodificarem a sequência "mensagem" aleatória correta. A propriedade de criptografia não clonável b diz que, com alta probabilidade, a cópia de B falha no teste de espionagem ou a cópia de C quase não contém informações sobre a mensagem. Isso é mais forte do que o necessário, mas suficiente para provar a segurança.

Para melhor ataque assintótico, eu imaginaria, devido ao quantum de Finetti, que o melhor ataque coletivo é o mesmo que o melhor ataque individual.


fonte
Muito obrigado, Daniel! Continuarei procurando um argumento que dê um limite explícito em c, mas, enquanto isso, isso é extremamente útil. Fui em frente e marquei sua resposta como "aceita".
Scott Aaronson