Qual é a classe de complexidade para sub-rotinas quânticas que recebem estados quânticos arbitrários como insumos?

15

A classe de complexidade BQP corresponde a sub-rotinas quânticas de tempo polinomial, recebendo entradas clássicas e emitindo uma saída clássica probabilística. O aconselhamento quântico modifica isso para incluir cópias de alguns estados pré-determinados de aconselhamento quântico, mas com informações clássicas, como de costume. Qual é a classe de complexidade para sub-rotinas quânticas de tempo polinomial, que recebem estados quânticos arbitrários como entradas, com apenas uma cópia devido à ausência de clonagem e expõem estados quânticos como saída?

Timmy
fonte
Você poderia especificar o quão arbitrário seu estado pode ser? 'qualquer coisa no espaço de Hilbert', 'algo gerado por uma determinada família de canais quânticos realistas', etc
Juan Bermejo Vega

Respostas:

13

Eu acho que o que você quer saber são análogos quânticos de classes de problemas de função. (Agradecemos a Peter Shor por apontar esta descrição concisa em um comentário.)

Um processo abstrato que toma um estado quântico de tamanho fixo como entrada e produz um estado quântico de tamanho fixo quando a saída é chamada de canal quântico . Na sua situação, não queremos fixar o tamanho da entrada ou o tamanho da saída e, portanto, consideramos naturalmente uma família de canais quânticos como o análogo quântico de funções, de cordas clássicas a cordas clássicas.

É claramente possível definir a classe de famílias de canais quânticos que podem ser implementados / aproximados por famílias de circuitos quânticos eficientes (com noções adequadas de eficiência, uniformidade e aproximação). Não sei se essa classe tem algum nome padrão (mas consulte o comentário de Peter Shor para obter uma sugestão).

Na minha especulação, classes de canais quânticos geralmente não são estudadas porque uma das razões para considerar classes de complexidade é comparar os poderes de diferentes modelos computacionais, e classes de canais quânticos não podem ser usadas para comparar modelos computacionais clássicos e quânticos. No entanto, é perfeitamente bom definir e falar sobre essas classes se algo interessante puder ser provado sobre elas.

Tsuyoshi Ito
fonte
7
Estes são análogos quânticos de classes de função. Você nomeia classes de função prefixando um F no nome; por exemplo, NP é a classe de decisão e FNP é a classe de função correspondente. Presumivelmente, você deve nomear classes de funções quânticas prefixando um QF para o nome, produzindo QFBQP para a classe que você deseja (que seria distinta de FBQP, a classe de funções clássicas que você pode calcular em tempo polinomial com erro limitado em um computador quântico) .
Peter Shor
@ Peter: Obrigado pelo comentário. “Análogos quânticos de classes de função” é uma maneira muito boa de resumir o que estou falando nesta resposta e atualizei a resposta usando essa descrição. Espero que você não se importe.
Tsuyoshi Ito
Eu não me importo.
Peter Shor
7

Algo em que você pode estar interessado é a noção de oráculo quântico introduzida por Aaronson e Kuperberg no arXiv: quant-ph / 0604056 . Citando seu artigo:

Assim como um oráculo clássico modela uma sub-rotina à qual um algoritmo tem acesso à caixa preta, um oráculo quântico modela uma sub-rotina quântica, que pode receber entrada quântica e produzir saída quântica.

Isso não responde diretamente à sua pergunta sobre a definição de uma classe de complexidade que representa o modelo que você descreve. Ainda assim, a noção de oráculo quântico tem relevância na teoria da complexidade: em seu trabalho, Aaronson e Kuperberg usam um oráculo quântico para separar QMA e QCMA .

Alessandro Cosentino
fonte
5

Eu acho que uma classe de complexidade para problemas de decisão , tendo estados quânticos como entrada, provavelmente terá uma definição frágil. Para problemas de promessa, ou a definição será sensível a escolhas numéricas ou essencialmente resolverá problemas clássicos de decisão / promessa codificados em alguma base decodificável de forma eficiente de estados quânticos.

A resposta de Tsuyoshi descreve o que eu consideraria a generalização correta dos problemas de função. Se o que você deseja é uma generalização dos problemas de decisão, você pode se especializar em famílias de canais de nΦn:eu(H2n)eu(H2)estados de qubit para estados de qubit único. Obviamente, um circuito quântico é um canal perfeitamente bom; se vamos falar sobre a execução de canais específicos que são limitados computacionalmente, também podemos falar de famílias uniformes de circuitos quânticos (ou, nesse caso, de qualquer maneira uniforme de implementar um mapa CPTP). Para uma boa medida, o circuito deve terminar com uma medida de base padrão, se quisermos manter a semântica de decidir algo com probabilidade limitada.

euρρeuρρeu

Além disso, parece provável - porque o teorema da não-clonagem o impede de fazer cópias do seu estado de entrada - que você não pode amplificar a probabilidade de sucesso. Portanto, qualquer definição deeueu(1), essa é uma probabilidade mais próxima da certeza à medida que o tamanho da entrada aumenta - e da mesma forma, a probabilidade de rejeição de qualquer estado que a rotina de decisão seja capaz de rejeitar também deve convergir para zero.

Os problemas de promessa quântica que um circuito QBQP (para entradas do tamanho n ) seriam capazes de distinguir seriam então

  • H2n
  • Para casos de NO, misturas de estados puros ortogonais a esse subespaço (ou pelo menos todos os estados ortocomplementares permitidos pela promessa).

eueu problema de decisão ou promessa, codificado em estados quânticos, com erro convergindo para zero.

Niel de Beaudrap
fonte
1
Eu usaria a formulação do problema da promessa para definir os análogos quânticos das classes de problemas de decisão devido ao problema de erro delimitado que você apontou nesta resposta.
Tsuyoshi Ito
@ TsuyoshiIto: bom ponto, o conceito é essencialmente uma restrição de problema de promessa. Eu editei a resposta para acomodar esse conceito.
Niel de Beaudrap 28/11
Caso não esteja claro, não concordo com o primeiro parágrafo da sua resposta se considerarmos problemas promissores.
Tsuyoshi Ito
@ TsuyoshiIto: você está certo ao apontar que não mencionei problemas prometidos no primeiro parágrafo; quanto à questão de saber se o original ainda estava correto para problemas prometidos, suponho que isso dependa de você interpretar 'frágil' como sensível a escolhas numéricas. De qualquer forma, revisei esse parágrafo para refletir melhor a resposta (incluindo uma descrição da sensibilidade que persiste por problemas de promessa).
Niel de Beaudrap 29/11
4

Corrija-me se estiver errado, mas parece-me que você está interessado na classe BQP / qpoly . Definição do Complexity Zoo: "A classe de problemas solucionáveis ​​por uma máquina BQP que recebe um estado quântico ψn como orientação, que depende apenas do comprimento de entrada n".

Se for esse o caso, no site você poderá encontrar relacionamentos dessa classe com outras classes de complexidade. Caso contrário, este site também contém informações sobre o que acontece com o BQP quando você usa diferentes tipos de aconselhamento.

Há também um trabalho relativamente recente sobre a " caracterização de conselhos quânticos ", onde você pode encontrar a seguinte hierarquia:

Classes de complexidade relacionadas a provas e conselhos quânticos

Não sei quanto dessas informações já estão no Complexity Zoo. Se você estiver interessado no artigo, os autores também deram uma palestra sobre o assunto.

Editar Eu me pergunto se por "arbitrária" você quer dizer um estado gerado por um processo quântico mais geral que 'evolução unitária agindo em estados da base computacional' como evolução dissipação. Nesse último caso específico, você não possui mais poder computacional que o BQP, conforme mostrado neste artigo .

Juan Bermejo Vega
fonte
3
Penso que o autor da questão mencionou conselhos quânticos na pergunta para esclarecer que o que ele quer saber é diferente dos conselhos quânticos.
Tsuyoshi Ito
Sim, é por isso que eu tinha dúvidas. Não está claro para mim o quanto "arbitrário" o estado pode estar em questão. > Qual é a classe de complexidade para sub-rotinas quânticas de tempo polinomial, que recebem estados quânticos arbitrários como entradas. Entendo aqui que o estado inicial "arbitrário" precisa ser dado a você por alguém, mas talvez o solicitante esteja interessado em configurações mais realistas.
Juan Bermejo Vega
3

Aqui estão algumas referências sobre linguagens quânticas, isto é, problemas de decisão com entradas quânticas. Provavelmente há muito mais.

  1. NP quântico e uma hierarquia quântica - Tomoyuki Yamakami
  2. Sobre a complexidade das línguas quânticas Elham Kashefi, Carolina Moura Alves
  3. Um teste eficiente para estados de produtos, com aplicações para jogos quânticos de Merlin-Arthur -Aram Harrow, Ashley Montanaro, DOI: 10.1109 / FOCS.2010.66, Resumo: arxiv.org/abs/1001.0017v3
Anônimo
fonte