Os circuitos de Clifford podem ser adequadamente aprendidos por PAC se e somente se $textsf{RP}=textsf{NP}$

Os circuitos de Clifford podem ser adequadamente aprendidos por PAC se e somente se $textsf{RP}=textsf{NP}$

Carimbo de data / hora: 7 de junho de 2023 6h07
Nó Fonte: 2706854

Daniel Liang

Departamento de Ciência da Computação, Universidade do Texas em Austin

Acha este artigo interessante ou deseja discutir? Scite ou deixe um comentário no SciRate.

Sumário

Dado um conjunto de dados de estados de entrada, medições e probabilidades, é possível prever com eficiência as probabilidades de medição associadas a um circuito quântico? Trabalho recente de Caro e Datta [19] estudou o problema de PAC aprendendo circuitos quânticos em um sentido teórico da informação, deixando em aberto questões de eficiência computacional. Em particular, uma classe candidata de circuitos para os quais um aprendiz eficiente poderia ter sido possível era a dos circuitos de Clifford, uma vez que o conjunto correspondente de estados gerados por tais circuitos, chamados de estados estabilizadores, são conhecidos por serem eficientemente aprendidos pelo PAC [44]. Aqui fornecemos um resultado negativo, mostrando que o aprendizado adequado de circuitos CNOT com erro 1/ poly($n$) é difícil para alunos clássicos, a menos que $textsf{RP = NP}$, descartando a possibilidade de alunos fortes sob a teoria da complexidade padrão premissas. Como o análogo clássico e subconjunto dos circuitos de Clifford, isso naturalmente leva a um resultado de dureza também para os circuitos de Clifford. Além disso, mostramos que se $textsf{RP = NP}$ então existiriam algoritmos de aprendizado adequados e eficientes para os circuitos CNOT e Clifford. Por argumentos semelhantes, também descobrimos que um aprendiz quântico adequado e eficiente para tais circuitos existe se e somente se $textsf{NP ⊆ RQP}$. Deixamos em aberto o problema de dificuldade para aprendizado impróprio ou erro $mathcal{O(1)}$ para trabalho futuro.

► dados BibTeX

► Referências

[1] Scott Aaronson. A capacidade de aprendizado de estados quânticos. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 463 (2088): 3089–3114, 2007. 10.1098/​rspa.2007.0113.
https: / / doi.org/ 10.1098 / rspa.2007.0113

[2] Scott Aaronson. Tomografia de sombra de estados quânticos. Em Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, página 325–338, Nova York, NY, EUA, 2018. Association for Computing Machinery. ISBN 9781450355599. 10.1145/​3188745.3188802.
https: / / doi.org/ 10.1145 / 3188745.3188802

[3] Scott Aaronson e Daniel Gottesman. Simulação aprimorada de circuitos estabilizadores. Physical Review A, 70 (5): 052328, 2004. 10.1103/​physreva.70.052328.
https: / / doi.org/ 10.1103 / physreva.70.052328

[4] JB Altepeter, D. Branning, E. Jeffrey, TC Wei, PG Kwiat, RT Thew, JL O'Brien, MA Nielsen e AG White. Tomografia de processo quântico assistida por Ancilla. Física. Rev. Lett., 90: 193601, maio de 2003. 10.1103/​PhysRevLett.90.193601.
https: / / doi.org/ 10.1103 / PhysRevLett.90.193601

[5] Martin Anthony e Peter L. Bartlett. Aprendizagem de funções por interpolação. Combinatorics, Probability and Computing, 9 (3): 213–225, 2000. 10.1017/​S0963548300004247.
https: / / doi.org/ 10.1017 / S0963548300004247

[6] Srinivasan Arunachalam e Ronald de Wolf. Coluna de convidados: Uma pesquisa sobre a teoria da aprendizagem quântica. ACM SIGACT News, 48 ​​(2): 41–67, 2017. 10.1145/​3106700.3106710.
https: / / doi.org/ 10.1145 / 3106700.3106710

[7] Srinivasan Arunachalam e Ronald de Wolf. Complexidade ideal de amostra quântica de algoritmos de aprendizagem. Em Ryan O'Donnell, editor, 32ª Conferência de Complexidade Computacional (CCC 2017), volume 79 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 25:1–25:31, Dagstuhl, Alemanha, 2017. Schloss Dagstuhl–Leibniz-Zentrum mais informática. ISBN 978-3-95977-040-8. 10.4230/​LIPIcs.CCC.2017.25.
https: / / doi.org/ 10.4230 / LIPIcs.CCC.2017.25

[8] Srinivasan Arunachalam, Alex B Grilo e Henry Yuen. Aprendizagem de consulta estatística quântica. arXiv preprint arXiv:2002.08240, 2020. https:/​/​doi.org/​10.48550/​arXiv.2002.08240.
https://​/​doi.org/​10.48550/​arXiv.2002.08240
arXiv: 2002.08240

[9] Srinivasan Arunachalam, Alex Bredariol Grilo e Aarthi Sundaram. Dureza quântica de aprendizagem de circuitos clássicos rasos. SIAM Journal on Computing, 50 (3): 972–1013, 2021. 10.1137/​20M1344202.
https: / / doi.org/ 10.1137 / 20M1344202

[10] Charles H. Bennett e Gilles Brassard. Criptografia quântica: distribuição de chave pública e lançamento de moeda. Theoretical Computer Science, 560: 7–11, dezembro de 2014. ISSN 0304-3975. 10.1016/​j.tcs.2014.05.025.
https: / / doi.org/ 10.1016 / j.tcs.2014.05.025

[11] Charles H. Bennett e Stephen J. Wiesner. Comunicação via operadores de uma e duas partículas nos estados de einstein-podolsky-rosen. Física Rev. Lett., 69: 2881–2884, novembro de 1992. 10.1103/PhysRevLett.69.2881.
https: / / doi.org/ 10.1103 / PhysRevLett.69.2881

[12] Charles H. Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres e William K. Wootters. Teletransportando um estado quântico desconhecido via canais duplos clássicos e einstein-podolsky-rosen. Física Rev. Lett., 70: 1895–1899, março de 1993. 10.1103/PhysRevLett.70.1895.
https: / / doi.org/ 10.1103 / PhysRevLett.70.1895

[13] Ethan Bernstein e Umesh Vazirani. Teoria da complexidade quântica. SIAM Journal on Computing, 26 (5): 1411–1473, 1997. 10.1137 / S0097539796300921.
https: / / doi.org/ 10.1137 / S0097539796300921

[14] Avrim Blum. Dificuldade Computacional de Aprendizagem. http:/​/​www.cs.cmu.edu/​ avrim/​ML07/​lect1007.pdf, 2015. URL http:/​/​www.cs.cmu.edu/​ avrim/​ML07/​lect1007 .pdf. Notas de aula para CS 10-806 Foundations of Machine Learning and Data Science.
http://www.cs.cmu.edu/~avrim/ML07/lect1007.pdf

[15] Avrim L. Blum e Ronald L. Rivest. O treinamento de uma rede neural de 3 nós é np-completo. Neural Networks, 5 (1): 117–127, 1992. ISSN 0893-6080. https:/​/​doi.org/​10.1016/​S0893-6080(05)80010-3.
https:/​/​doi.org/​10.1016/​S0893-6080(05)80010-3

[16] Anselm Blumer, A. Ehrenfeucht, David Haussler e Manfred K. Warmuth. Aprendizagem e a dimensão vapnik-chervonenkis. J. ACM, 36 (4): 929–965, outubro de 1989. ISSN 0004-5411. 10.1145/76359.76371.
https: / / doi.org/ 10.1145 / 76359.76371

[17] Jonathan F Buss, Gudmund S Frandsen e Jeffrey O Shallit. A complexidade computacional de alguns problemas de álgebra linear. Journal of Computer and System Sciences, 58 (3): 572–596, 1999. ISSN 0022-0000. https:/​/​doi.org/​10.1006/​jcss.1998.1608.
https: / / doi.org/ 10.1006 / jcss.1998.1608

[18] Matthias C. Caro. Classificação binária com instâncias clássicas e rótulos quânticos. Quantum Machine Intelligence, 3 (1), maio de 2021. 10.1007/​s42484-021-00043-z.
https: / / doi.org/ 10.1007 / s42484-021-00043-z

[19] Matthias C. Caro e Ishaun Datta. Pseudo-dimensão de circuitos quânticos. Quantum Machine Intelligence, 2 (2), novembro de 2020. ISSN 2524-4914. 10.1007/​s42484-020-00027-5.
https:/​/​doi.org/​10.1007/​s42484-020-00027-5

[20] Hao-Chung Cheng, Min-Hsiu Hsieh e Ping-Cheng Yeh. A capacidade de aprendizado de medições quânticas desconhecidas. Informações Quânticas. Comput., 16 (7–8): 615–656, maio de 2016. ISSN 1533-7146. 10.26421/​QIC16.7-8-4.
https: / / doi.org/ 10.26421 / QIC16.7-8-4

[21] Isaac L. Chuang e MA Nielsen. Prescrição para determinação experimental da dinâmica de uma caixa preta quântica. Journal of Modern Optics, 44 (11-12): 2455–2467, 1997. 10.1080/09500349708231894.
https: / / doi.org/ 10.1080 / 09500349708231894

[22] Kai-Min Chung e Han-Hsuan Lin. Algoritmos Eficientes de Amostra para Aprender Canais Quânticos no Modelo PAC e o Problema de Discriminação de Estado Aproximado. Em Min-Hsiu Hsieh, editor, 16ª Conferência sobre a Teoria da Computação Quântica, Comunicação e Criptografia (TQC 2021), volume 197 de Leibniz International Proceedings in Informatics (LIPIcs), páginas 3:1–3:22, Dagstuhl, Alemanha, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-198-6. 10.4230/​LIPIcs.TQC.2021.3.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2021.3

[23] Amit Daniely e Shai Shalev-Shwartz. Limitações teóricas da complexidade na aprendizagem de DNF's. Em Vitaly Feldman, Alexander Rakhlin e Ohad Shamir, editores, 29th Annual Conference on Learning Theory, volume 49 de Proceedings of Machine Learning Research, páginas 815–830, Columbia University, Nova York, Nova York, EUA, 23–26 de junho de 2016 .PMLR. URL https://​/​proceedings.mlr.press/​v49/​daniely16.html.
https://​/​proceedings.mlr.press/​v49/​daniely16.html

[24] Steven T Flammia, David Gross, Yi-Kai Liu e Jens Eisert. Tomografia quântica via sensoriamento comprimido: limites de erro, complexidade amostral e estimadores eficientes. New Journal of Physics, 14 (9): 095022, set 2012. 10.1088/​1367-2630/​14/​9/​095022.
https:/​/​doi.org/​10.1088/​1367-2630/​14/​9/​095022

[25] Paul W. Goldberg e Mark R. Jerrum. Limitando a dimensão vapnik-chervonenkis de classes de conceito parametrizadas por números reais. Machine Learning, 18: 131–148, 1995. 10.1007/​BF00993408.
https: / / doi.org/ 10.1007 / BF00993408

[26] Daniel Gotesman. Códigos estabilizadores e correção de erros quânticos, 1997.

[27] Daniel Gotesman. A representação de Heisenberg de computadores quânticos, 1998.

[28] Venkatesan Guruswami e Prasad Raghavendra. Dificuldade de aprender semi-espaços com ruído. SIAM Journal on Computing, 39 (2): 742–765, 2009. 10.1137/070685798.
https: / / doi.org/ 10.1137 / 070685798

[29] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu e Nengkun Yu. Tomografia de amostras ótimas de estados quânticos. IEEE Transactions on Information Theory, páginas 1–1, 2017. ISSN 1557-9654. 10.1109/​tit.2017.2719044.
https: / / doi.org/ 10.1109 / tit.2017.2719044

[30] Nika Haghtalab. Aula 9: Dificuldade de Aprendizagem. https:/​/​www.cs.cornell.edu/​courses/​cs6781/​2020sp/​lectures/​09-hardness1.pdf, 2020. URL https:/​/​www.cs.cornell.edu/ ​cursos/​cs6781/​2020sp/​palestras/​09-dureza1.pdf. Notas de aula para CS6781 - Fundamentos Teóricos do Aprendizado de Máquina.
https://www.cs.cornell.edu/courses/cs6781/2020sp/lectures/09-hardness1.pdf

[31] Hsin-Yuan Huang, Richard Kueng e John Preskill. Prevendo muitas propriedades de um sistema quântico a partir de poucas medições. Nature Physics, outubro de 2020. 10.1038/​s41567-020-0932-7.
https:/​/​doi.org/​10.1038/​s41567-020-0932-7

[32] Jonathan Katz. Notas sobre a Teoria da Complexidade Aula 3. https:/​/​www.cs.umd.edu/​ jkatz/​complexity/​f11/​lecture3.pdf, 2011. URL https:/​/​www.cs.umd. edu/​ jkatz/​complexity/​f11/​lecture3.pdf. Notas de aula para CS 652 — Teoria da Complexidade.
https://www.cs.umd.edu/​~jkatz/​complexity/​f11/​lecture3.pdf

[33] Michael Kharitonov. Dureza criptográfica do aprendizado específico da distribuição. Em Anais do Vigésimo Quinto Simpósio Anual ACM sobre Teoria da Computação, STOC '93, páginas 372–381, Nova York, NY, EUA, 1993. Association for Computing Machinery. ISBN 0897915917/​10.1145.
https: / / doi.org/ 10.1145 / 167088.167197

[34] J. Kleinberg e E. Tardos. Projeto de Algoritmo. Pearson Education, 2022. ISBN 9780132131087. URL https:/​/​books.google.com/​books?id=GORecgAACAAJ.
https://​/​books.google.com/​books?id=GORecgAACAAJ

[35] Adam Klivans. O Modelo de Aprendizagem PAC. https:/​/​www.cs.utexas.edu/​ klivans/​f06lec2.pdf, 2005. URL https:/​/​www.cs.utexas.edu/​ klivans/​f06lec2.pdf. Notas de aula para Teoria de Aprendizagem Computacional CS 395T.
https://www.cs.utexas.edu/​~klivans/​f06lec2.pdf

[36] Robert Koenig e John A. Smolin. Como selecionar com eficiência um elemento de grupo clifford arbitrário. Journal of Mathematical Physics, 55 (12): 122202, dezembro de 2014. ISSN 1089-7658. 10.1063/​1.4903507.
https: / / doi.org/ 10.1063 / 1.4903507

[37] Richard Kueng e David Gross. Os estados do estabilizador Qubit são 3 designs projetivos complexos, 2015.

[38] Ching-Yi Lai e Hao-Chung Cheng. Aprendendo circuitos quânticos de algumas portas t. IEEE Transactions on Information Theory, páginas 1–1, 2022. 10.1109/​TIT.2022.3151760.
https: / / doi.org/ 10.1109 / TIT.2022.3151760

[39] Richard A. Baixo. Algoritmos de aprendizado e teste para o grupo clifford. Física Rev. A, 80: 052314, novembro de 2009. 10.1103/​PhysRevA.80.052314.
https: / / doi.org/ 10.1103 / PhysRevA.80.052314

[40] Ashley Montanaro. Aprendendo estados do estabilizador por amostragem de Bell, 2017.

[41] Ryan O'Donnell e John Wright. Tomografia quântica eficiente. Em Anais do Quadragésimo Oitavo Simpósio Anual ACM sobre Teoria da Computação, STOC '16, páginas 899–912, Nova York, NY, EUA, 2016. Association for Computing Machinery. ISBN 9781450341325/​10.1145.
https: / / doi.org/ 10.1145 / 2897518.2897544

[42] Ryan O'Donnell e John Wright. Tomografia quântica eficiente ii. Em Anais do 49º Simpósio Anual ACM SIGACT sobre Teoria da Computação, STOC 2017, páginas 962–974, Nova York, NY, EUA, 2017. Association for Computing Machinery. ISBN 9781450345286/​10.1145.
https: / / doi.org/ 10.1145 / 3055399.3055454

[43] Yihui Quek, Srinivasan Arunachalam e John A Smolin. A aprendizagem privada implica estabilidade quântica. Em M. Ranzato, A. Beygelzimer, Y. Dauphin, PS Liang e J. Wortman Vaughan, editores, Advances in Neural Information Processing Systems, volume 34, páginas 20503–20515. Curran Associates, Inc., 2021. URL https:/​/​proceedings.neurips.cc/​paper/​2021/​file/​abdbeb4d8dbe30df8430a8394b7218ef-Paper.pdf.
https:/​/​proceedings.neurips.cc/​paper/​2021/​file/​abdbeb4d8dbe30df8430a8394b7218ef-Paper.pdf

[44] Andréa Rochetto. Os estados do estabilizador podem ser aprendidos com eficiência pelo PAC. Quantum Information & Computation, 18 (7-8): 541–552, 2018. 10.26421/qic18.7-8-1.
https: / / doi.org/ 10.26421 / qic18.7-8-1

[45] Peter W. Shor. Algoritmos de tempo polinomial para fatoração primária e logaritmos discretos em um computador quântico. SIAM Review, 41 (2): 303–332, 1999. 10.1137/​S0036144598347011.
https: / / doi.org/ 10.1137 / S0036144598347011

[46] Daniel R. Simon. Sobre o poder da computação quântica. SIAM Journal on Computing, 26 (5): 1474–1483, 1997. 10.1137/​S0097539796298637.
https: / / doi.org/ 10.1137 / S0097539796298637

[47] Leslie G Valiant. A teoria da aprendizagem. Communications of the ACM, 27 (11): 1134–1142, 1984. 10.1145/​1968.1972.
https: / / doi.org/ 10.1145 / 1968.1972

[48] Ewout Van Den Berg. Um método simples para amostragem de operadores aleatórios de Clifford. Em 2021 IEEE International Conference on Quantum Computing and Engineering (QCE), páginas 54–59, 2021. 10.1109/​QCE52317.2021.00021.
https: / / doi.org/ 10.1109 / QCE52317.2021.00021

[49] Mithuna Yoganathan. Uma condição sob a qual a simulabilidade clássica implica capacidade de aprendizado de estado eficiente, 2019.

[50] Huangjun Zhu. Grupos clifford multiqubit são 3 designs unitários. Física Rev. A, 96: 062336, dez 2017. 10.1103/​PhysRevA.96.062336.
https: / / doi.org/ 10.1103 / PhysRevA.96.062336

Citado por

[1] Lorenzo Leone, Salvatore FE Oliviero, Seth Lloyd e Alioscia Hamma, "Aprendendo decodificadores eficientes para embaralhadores quânticos quase caóticos", arXiv: 2212.11338, (2022).

[2] Srinivasan Arunachalam, Sergey Bravyi, Arkopal Dutt e Theodore J. Yoder, "Algoritmos ideais para aprender estados de fase quântica", arXiv: 2208.07851, (2022).

[3] Anurag Anshu e Srinivasan Arunachalam, "Uma pesquisa sobre a complexidade da aprendizagem de estados quânticos", arXiv: 2305.20069, (2023).

As citações acima são de SAO / NASA ADS (última atualização com êxito 2023-06-07 22:21:42). A lista pode estar incompleta, pois nem todos os editores fornecem dados de citação adequados e completos.

On Serviço citado por Crossref nenhum dado sobre a citação de trabalhos foi encontrado (última tentativa 2023-06-07 22:21:40).

Este artigo é publicado na Quantum sob o Atribuição 4.0 do Creative Commons Internacional (CC BY 4.0) licença. Os direitos autorais permanecem com os detentores originais, como os autores ou suas instituições.

Carimbo de hora:

Mais de Diário Quântico