Forgiare dati quantistici: sconfiggere in modo classico un test quantistico basato su IQP

Forgiare dati quantistici: sconfiggere in modo classico un test quantistico basato su IQP

Timestamp: 11 settembre 2023 8:46

Gregory D. Kahanamoku-Meyer

Dipartimento di Fisica, Università della California a Berkeley, Berkeley, CA 94720

Trovi questo documento interessante o vuoi discuterne? Scrivi o lascia un commento su SciRate.

Astratto

Recentemente, gli esperimenti di calcolo quantistico hanno per la prima volta superato la capacità dei computer classici di eseguire determinati calcoli – una pietra miliare chiamata “vantaggio computazionale quantistico”. Tuttavia, verificare l’output del dispositivo quantistico in questi esperimenti ha richiesto calcoli classici estremamente grandi. Un entusiasmante passo successivo per dimostrare la capacità quantistica sarebbe quello di implementare test di vantaggio computazionale quantistico con un’efficiente verifica classica, in modo tale da poter testare e verificare sistemi di dimensioni più grandi. Una delle prime proposte per un test di quantistica efficientemente verificabile consiste nel nascondere una stringa di bit classica segreta all'interno di un circuito della classe IQP, in modo tale che i campioni della distribuzione di uscita del circuito siano correlati con il segreto. La durezza classica di questo protocollo è stata supportata dall’evidenza che simulare direttamente i circuiti IQP è difficile, ma la sicurezza del protocollo contro altri attacchi classici (non simulanti) è rimasta una questione aperta. In questo lavoro dimostriamo che il protocollo non è sicuro contro la falsificazione classica. Descriviamo un algoritmo classico che non solo può convincere il verificatore che il dimostratore (classico) è quantistico, ma può effettivamente estrarre la chiave segreta alla base di una determinata istanza di protocollo. Inoltre, mostriamo che l'algoritmo di estrazione della chiave è efficiente nella pratica per problemi di dimensioni di centinaia di qubit. Infine, forniamo un’implementazione dell’algoritmo e forniamo il vettore segreto alla base della “sfida da $ 25” pubblicata online dagli autori dell’articolo originale.

Forgiare dati quantistici: sconfiggere in modo classico un test quantistico basato su IQP PlatoBlockchain Data Intelligence. Ricerca verticale. Ai.

Immagine in primo piano: In questo lavoro, mostriamo come un computer classico imbroglione (a sinistra) può mascherarsi da computer quantistico nelle sue interazioni con un computer "verificatore" classico (a destra), nel contesto di uno specifico protocollo di prova della quanticità.

Riepilogo popolare

Recenti esperimenti di campionamento quantistico hanno dimostrato un vantaggio computazionale quantistico eseguendo calcoli che non è possibile riprodurre in modo classico. Tuttavia, il controllo classico dei risultati è almeno altrettanto difficile, rendendo la verifica diretta impossibile per gli esperimenti più grandi. Un candidato per superare questa sfida era un protocollo di campionamento proposto nel 2008, che prometteva un'efficiente verifica classica pur mantenendo la classica durezza di riprodurre il comportamento del dispositivo quantistico. In questo lavoro forniamo un efficiente algoritmo classico che supera i controlli di verifica estraendo la chiave segreta sottostante, che dovrebbe essere nascosta anche a un dispositivo quantistico reale. Il nostro algoritmo invalida l’affermazione secondo cui solo un dispositivo quantistico potrebbe superare i controlli, vanificando l’utilità del test come dimostrazione della capacità quantistica.

► dati BibTeX

► Riferimenti

, Frank Arute et al. "Supremazia quantistica utilizzando un processore superconduttore programmabile". Natura 574, 505–510 (2019).
https:/​/​doi.org/​10.1038/​s41586-019-1666-5

, Han-Sen Zhong et al. “Vantaggio computazionale quantistico utilizzando i fotoni”. Scienza 370, 1460–1463 (2020).
https: / / doi.org/ 10.1126 / science.abe8770

, Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han , Linyin Hong, He-Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang, Dachao Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao , Youwei Zhao, Liang Zhou, Qingling Zhu, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu e Jian-Wei Pan. "Forte vantaggio computazionale quantistico utilizzando un processore quantistico superconduttore". Lettere di revisione fisica 127, 180501 (2021).
https: / / doi.org/ 10.1103 / PhysRevLett.127.180501

, Qingling Zhu, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He -Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang , Dachao Wu, Yulin Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao, Youwei Zhao, Liang Zhou, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu e Jian-Wei Pan. "Vantaggio computazionale quantistico tramite campionamento di circuiti casuali a 60 cicli da 24 qubit". Bollettino scientifico 67, 240–245 (2022).
https: / / doi.org/ 10.1016 / j.scib.2021.10.017

, Scott Aaronson e Alex Arkhipov. “La complessità computazionale dell’ottica lineare”. In Atti del quarantatreesimo simposio annuale ACM sulla teoria dell'informatica. Pagine 333–342. STOC '11New York, NY, Stati Uniti (2011). Associazione per le macchine informatiche.
https: / / doi.org/ 10.1145 / 1993636.1993682 mila

, Edward Farhi e Aram W. Harrow. “Supremazia quantistica attraverso l’algoritmo di ottimizzazione approssimata quantistica” (2019). arXiv:1602.07674.
arXiv: 1602.07674

, AP Lund, Michael J. Bremner e TC Ralph. “Problemi di campionamento quantistico, BosonSampling e supremazia quantistica”. npj Informazioni quantistiche 3, 1–8 (2017).
https:/​/​doi.org/​10.1038/​s41534-017-0018-2

, Aram W. Harrow e Ashley Montanaro. “Supremazia computazionale quantistica”. Natura 549, 203–209 (2017).
https: / / doi.org/ 10.1038 / nature23458

, Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J. Bremner, John M. Martinis e Hartmut Neven. "Caratterizzazione della supremazia quantistica nei dispositivi a breve termine". Fisica della natura 14, 595–600 (2018).
https: / / doi.org/ 10.1038 / s41567-018-0124-x

, Barbara M. Terhal. “Supremazia quantistica, arriviamo”. Fisica della natura 14, 530–531 (2018).
https: / / doi.org/ 10.1038 / s41567-018-0131-y

, C. Neill, P. Roushan, K. Kechedzhi, S. Boixo, SV Isakov, V. Smelyanskiy, A. Megrant, B. Chiaro, A. Dunsworth, K. Arya, R. Barends, B. Burkett, Y. Chen , Z. Chen, et al. "Un progetto per dimostrare la supremazia quantistica con qubit superconduttori". Scienza 360, 195–199 (2018).
https: / / doi.org/ 10.1126 / science.aao4309

, Sergey Bravyi, David Gosset e Robert Konig. "Vantaggio quantistico con circuiti superficiali". Scienza 362, 308–311 (2018).
https: / / doi.org/ 10.1126 / science.aar3106

, Sergey Bravyi, David Gosset, Robert König e Marco Tomamichel. "Vantaggio quantistico con circuiti poco profondi e rumorosi". Fisica della natura 16, 1040–1045 (2020).
https: / / doi.org/ 10.1038 / s41567-020-0948-z

, Adam Bouland, Bill Fefferman, Chinmay Nirkhe e Umesh Vazirani. "Sulla complessità e verifica del campionamento circuitale quantistico casuale". Fisica della natura 15, 159–163 (2019).
https:/​/​doi.org/​10.1038/​s41567-018-0318-2

, Scott Aaronson e Sam Gunn. "Sulla classica durezza dello spoofing del benchmarking lineare di entropia incrociata". Teoria dell'informatica 16, 1–8 (2020).
https: / / doi.org/ 10.4086 / toc.2020.v016a011

, Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani e Thomas Vidick. "Un test crittografico di quanticità e casualità certificabile da un singolo dispositivo quantistico". Giornale dell'ACM (JACM) (2021).
https: / / doi.org/ 10.1145 / 3441309 mila

, Zvika Brakerski, Venkata Koppula, Umesh Vazirani e Thomas Vidick. "Prove più semplici della quantistica". In Steven T. Flammia, curatore, 15a Conferenza sulla teoria del calcolo quantistico, della comunicazione e della crittografia (TQC 2020). Volume 158 di Leibniz International Proceedings in Informatics (LIPIcs), pagine 8:1–8:14. Dagstuhl, Germania (2020). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
https: / / doi.org/ 10.4230 / LIPIcs.TQC.2020.8

, Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani e Norman Y. Yao. "Vantaggio quantistico classicamente verificabile da un test computazionale della campana". Fisica della natura 18, 918–924 (2022).
https:/​/​doi.org/​10.1038/​s41567-022-01643-7

, Dan Shepherd e Michael J. Bremner. “Calcolo quantistico temporalmente non strutturato”. Atti della Royal Society A: Scienze matematiche, fisiche e ingegneristiche 465, 1413–1439 (2009).
https: / / doi.org/ 10.1098 / rspa.2008.0443

, Michael J. Bremner et al. "La simulazione classica dei calcoli quantistici di pendolarismo implica il collasso della gerarchia polinomiale". Atti della Royal Society A: Scienze matematiche, fisiche e ingegneristiche 467, 459–472 (2011).
https: / / doi.org/ 10.1098 / rspa.2010.0301

, Michael J. Bremner et al. "Complessità del caso medio rispetto alla simulazione approssimativa dei calcoli quantistici pendolari". Lettere di revisione fisica 117, 080501 (2016).
https: / / doi.org/ 10.1103 / PhysRevLett.117.080501

, Gregory D Kahanamoku-Meyer (2023). codice: https://​/​doi.org/​10.5281/​zenodo.7545881.
https: / / doi.org/ 10.5281 / zenodo.7545881

, Yusuf Alnawakhtha, Atul Mantri, Carl A. Miller e Daochen Wang. "Vantaggio quantistico basato su reticolo derivante da misurazioni ruotate" (2022). arXiv:2210.10143.
arXiv: 2210.10143

, Takashi Yamakawa e Mark Zhandry. “Vantaggio quantico verificabile senza struttura”. Nel 2022 si terrà il 63° Simposio annuale dell'IEEE sui fondamenti dell'informatica (FOCS). Pagine 69–74. (2022).
https://​/​doi.org/​10.1109/​FOCS54457.2022.00014

, Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan e Lisa Yang. "Vantaggio quantistico da qualsiasi gioco non locale". Negli Atti del 55° Simposio annuale ACM sulla teoria dell'informatica. Pagine 1617–1628. STOC 2023New York, NY, Stati Uniti (2023). Associazione per le macchine informatiche.
https: / / doi.org/ 10.1145 / 3564246.3585164 mila

, Alexandru Gheorghiu e Thomas Vidick. “Preparazione dello stato remoto computazionalmente sicuro e componibile”. Nel 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). Pagine 1024–1033. (2019).
https: / / doi.org/ 10.1109 / FOCS.2019.00066

, Urmila Mahadev. "Verifica classica dei calcoli quantistici". Nel 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). Pagine 259–267. (2018).
https: / / doi.org/ 10.1109 / FOCS.2018.00033

Citato da

[1] Sergey Bravyi, David Gosset, Robert König e Marco Tomamichel, "Vantaggio quantistico con circuiti poco profondi e rumorosi", Fisica della natura 16 10, 1040 (2020).

[2] Dominik Hangleiter e Jens Eisert, "Vantaggio computazionale del campionamento casuale quantistico", Recensioni di Modern Physics 95 3, 035001 (2023).

[3] Zhenning Liu e Alexandru Gheorghiu, "Prove di quantistica efficienti in profondità", Quantico 6, 807 (2022).

[4] Martin Kliesch e Ingo Roth, “Teoria della certificazione del sistema quantistico: un tutorial”, arXiv: 2010.05925, (2020).

[5] Ulysse Chabaud, Frédéric Grosshans, Elham Kashefi e Damian Markham, "Verifica efficiente del campionamento dei bosoni", Quantico 5, 578 (2021).

[6] Michael J. Bremner, Bin Cheng e Zhengfeng Ji, "Campionamento IQP e vantaggio quantico verificabile: schema di stabilizzazione e sicurezza classica", arXiv: 2308.07152, (2023).

[7] Sergey Bravyi, David Gosset, Daniel Grier e Luke Schaeffer, "Algoritmi classici per Forrelation", arXiv: 2102.06963, (2021).

[8] Dominik Hangleiter, "Il campionamento e la complessità della natura", arXiv: 2012.07905, (2020).

[9] Xi Chen, Bin Cheng, Zhaokai Li, Xinfang Nie, Nengkun Yu, Man-Hong Yung e Xinhua Peng, "Verifica crittografica sperimentale per il cloud computing quantistico a breve termine", Bollettino scientifico 66 1, 23 (2021).

[10] Sritam Kumar Satpathy, Vallabh Vibhu, Sudev Pradhan, Bikash K. Behera e Prasanta K. Panigrahi, "Verifica efficiente del campionamento dei bosoni utilizzando un computer quantistico", arXiv: 2108.03954, (2021).

Le citazioni sopra sono di ANNUNCI SAO / NASA (ultimo aggiornamento riuscito 2023-09-12 13:11:52). L'elenco potrebbe essere incompleto poiché non tutti gli editori forniscono dati di citazione adeguati e completi.

On Il servizio citato da Crossref non sono stati trovati dati su citazioni (ultimo tentativo 2023-09-12 13:11:50).

Questo documento è pubblicato in Quantum sotto il Creative Commons Attribuzione 4.0 Internazionale (CC BY 4.0) licenza. Il copyright rimane dei detentori del copyright originali come gli autori o le loro istituzioni.

Timestamp:

Di più da Diario quantistico