Notes on Interrogating Random Quantum Circuits

<!DOCTYPE html> <html lang="en-us" xml:lang="en-us"> <head> <meta charset="utf-8" /> <title>Notes on Interrogating Random Quantum Circuits | CSRC</title> <meta http-equiv="content-type" content="text/html; charset=UTF-8" /> <meta http-equiv="content-style-type" content="text/css" /> <meta http-equiv="content-script-type" content="text/javascript" /> <meta name="viewport" content="width=device-width, initial-scale=1.0" /> <meta name="msapplication-config" content="/CSRC/Media/images/favicons/browserconfig.xml" /> <meta name="theme-color" content="#000000" /> <meta name="google-site-verification" content="xbrnrVYDgLD-Bd64xHLCt4XsPXzUhQ-4lGMj4TdUUTA" /> <meta description="Consider a quantum circuit that, when fed a constant input, produces a fixed-length random bit-string in each execution. Executing it many times yields a sample of many bit-strings that contain fresh randomness inherent to the quantum evaluation. When the circuit is freshly selected from a special class, the output distribution of strings cannot be simulated in a short amount of time by a classical (non-quantum) computer. This quantum vs. classical gap of computational efficiency enables ways of inferring that an honest sample contains quantumly generated strings, and therefore fresh randomness. This possibility, initially proposed by Aaronson, has been recently validated in a 'quantum supremacy' experiment by Google, using circuits with 53 qubits. In these notes, we consider the problem of estimating information entropy (a quantitative measure of random-ness), based on the sum of 'probability values' (here called QC-values) of strings output by quantum evaluation. We assume that the sample of strings, claimed to have been produced by repeated evaluation of a quantum circuit, was in fact crafted by an adversary intending to induce us into overestimating entropy. We analyze the case of a 'collisional' adversary that can over-sample and possibly take advantage of observed collisions. For diverse false-positive and false-negative rates, we devise parameters for testing the hypothesis that the sample has at least a certain expected entropy. This enables a client to certify the presence of entropy, after a lengthy computation of the QC-values. We also explore a method for low-budget clients to compute fewer QC-values, at the cost of more computation by a server. We conclude with several questions requiring further exploration." />  <meta name="dcterms.title" content="Notes on Interrogating Random Quantum Circuits" /> <meta name="dcterms.description" content="Consider a quantum circuit that, when fed a constant input, produces a fixed-length random bit-string in each execution. Executing it many times yields a sample of many bit-strings that contain fresh randomness inherent to the quantum evaluation. When the circuit is freshly selected from a special class, the output distribution of strings cannot be simulated in a short amount of time by a classical (non-quantum) computer. This quantum vs. classical gap of computational efficiency enables ways of inferring that an honest sample contains quantumly generated strings, and therefore fresh randomness. This possibility, initially proposed by Aaronson, has been recently validated in a 'quantum supremacy' experiment by Google, using circuits with 53 qubits. In these notes, we consider the problem of estimating information entropy (a quantitative measure of random-ness), based on the sum of 'probability values' (here called QC-values) of strings output by quantum evaluation. We assume that the sample of strings, claimed to have been produced by repeated evaluation of a quantum circuit, was in fact crafted by an adversary intending to induce us into overestimating entropy. We analyze the case of a 'collisional' adversary that can over-sample and possibly take advantage of observed collisions. For diverse false-positive and false-negative rates, we devise parameters for testing the hypothesis that the sample has at least a certain expected entropy. This enables a client to certify the presence of entropy, after a lengthy computation of the QC-values. We also explore a method for low-budget clients to compute fewer QC-values, at the cost of more computation by a server. We conclude with several questions requiring further exploration." />  <meta name="dcterms.creator" content="Author: Luís T. A. N. Brandão (NIST)" /> <meta name="dcterms.creator" content="Author: Rene Peralta (NIST)" />  <meta name="dcterms.date.created" schema="ISO8601" content="2020-05-29" /> <meta name="dcterms.identifier" content="https://csrc.nist.gov/pubs/other/2020/05/29/notes-on-interrogating-random-quantum-circuits/final" /> <meta name="dcterms.language" scheme="DCTERMS.RFC1766" content="EN-US" />  <meta name="citation_title" content="Notes on Interrogating Random Quantum Circuits" /> <meta name="citation_publication_date" content="2020/05/29" /> <meta name="citation_doi" content="https://doi.org/10.13140/RG.2.2.24562.94400" /> <meta name="citation_keywords" content="certifiable randomness,distinguishability,entropy estimation,gamma distribution,public randomness,quantum randomness" /> <meta name="citation_language" content="en" /> <meta name="citation_pdf_url" content="https://doi.org/10.13140/RG.2.2.24562.94400" /> <meta name="citation_abstract_html_url" content="https://csrc.nist.gov/pubs/other/2020/05/29/notes-on-interrogating-random-quantum-circuits/final" />  <meta name="citation_author" content="Brandão, Luís T. A. N." /> <meta name="citation_author" content="Peralta, Rene" />  <meta name="og:site_name" content="CSRC | NIST" /> <meta name="og:type" content="article" /> <meta name="og:url" content="https://csrc.nist.gov/pubs/other/2020/05/29/notes-on-interrogating-random-quantum-circuits/final" /> <meta name="og:title" content="Notes on Interrogating Random Quantum Circuits" /> <meta name="og:description" content="Consider a quantum circuit that, when fed a constant input, produces a fixed-length random bit-string in each execution. Executing it many times yields a sample of many bit-strings that contain fresh randomness inherent to the quantum evaluation. When the circuit is freshly selected from a special class, the output distribution of strings cannot be simulated in a short amount of time by a classical (non-quantum) computer. This quantum vs. classical gap of computational efficiency enables ways of inferring that an honest sample contains quantumly generated strings, and therefore fresh randomness. This possibility, initially proposed by Aaronson, has been recently validated in a 'quantum supremacy' experiment by Google, using circuits with 53 qubits. In these notes, we consider the problem of estimating information entropy (a quantitative measure of random-ness), based on the sum of 'probability values' (here called QC-values) of strings output by quantum evaluation. We assume that the..." /> <meta name="article:author" content="Brandão, Luís T. A. N." /> <meta name="article:author" content="Peralta, Rene" /> <meta name="article:tag" content="certifiable randomness,distinguishability,entropy estimation,gamma distribution,public randomness,quantum randomness" /> <meta name="article:published_time" content="2020-05-29" /> <link rel="apple-touch-icon" sizes="180x180" href="/images/icons/apple-touch-icon.png" /> <link rel="icon" type="image/png" href="/images/icons/favicon-32x32.png" sizes="32x32" /> <link rel="icon" type="image/png" href="/images/icons/favicon-16x16.png" sizes="16x16" /> <link rel="manifest" href="/images/icons/manifest.json" /> <link rel="mask-icon" href="/images/icons/safari-pinned-tab.svg" color="#000000" /> <link href="/CSRC/Media/images/favicons/favicon.ico" type="image/x-icon" rel="shortcut icon" /> <link href="/CSRC/Media/images/favicons/favicon.ico" type="image/x-icon" rel="icon" /> <link href="/dist/app.css" rel="stylesheet" />  <link href="/dist/highlight-js/github.css" rel="stylesheet" />  <link href="/dist/uswds/css/uswds.css" type="text/css" rel="stylesheet" /> <script type="text/javascript" src="/dist/uswds/js/uswds-init.min.js"></script>  <style> .grecaptcha-badge { visibility: hidden; } </style> <script async type="text/javascript" id="_fed_an_ua_tag" src="https://dap.digitalgov.gov/Universal-Federated-Analytics-Min.js?agency=nist&subagency=csrc&pua=UA-66610693-15&yt=true&exts=xsd,xml,wav,mpg,mpeg,avi,rtf,webm,ogg,ogv,oga,map,otf,eot,svg,ttf,woff"></script> <style id="antiClickjackCss"> body > * { display: none !important; } #antiClickjack { display: block !important; } </style> <noscript> <style id="antiClickjackNoScript"> body > * { display: block !important; } #antiClickjack { display: none !important; } </style> </noscript> <script type="text/javascript" id="antiClickjackScript"> if (self === top) { // no clickjacking var antiClickjack = document.getElementById("antiClickjackCss"); antiClickjack.parentNode.removeChild(antiClickjack); } else { setTimeout(tryForward(), 5000); } function tryForward() { top.location = self.location; } </script>  <script async src="https://www.googletagmanager.com/gtag/js?id=G-TSQ0PLGJZP"></script> <script> 聽聽window.dataLayer = window.dataLayer || []; 聽聽function gtag(){dataLayer.push(arguments);} 聽聽gtag('js', new Date()); 聽聽gtag('config', 'G-TSQ0PLGJZP'); </script>  <script>(function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0],j=d.createElement(s),dl=l!='dataLayer'?'&l='+l:'';j.async=true;j.src='https://www.googletagmanager.com/gtm.js?id='+i+dl;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-MZQC4NCJ');</script>  </head> <body>  <noscript><iframe src="https://www.googletagmanager.com/ns.html?id=GTM-MZQC4NCJ" height="0" width="0" style="display:none;visibility:hidden"></iframe></noscript>  <div id="antiClickjack" style="display: none;"> <strong style="font-size: 1.6rem;">You are viewing this page in an unauthorized frame window.</strong> <p>This is a potential security issue, you are being redirected to <a href="https://csrc.nist.gov">https://csrc.nist.gov</a>.</p> </div> <section class="usa-banner" aria-label="Official website of the United States government"> <div class="usa-accordion"> <header class="usa-banner__header"> <noscript> <p style="font-size: 0.85rem; font-weight: bold;">You have JavaScript disabled. This site requires JavaScript to be enabled for complete site functionality.</p> </noscript> <div class="usa-banner__inner"> <div class="grid-col-auto"> <img aria-hidden="true" class="usa-banner__header-flag" src="/dist/uswds/img/us_flag_small.png" alt=""/> </div> <div class="grid-col-fill tablet:grid-col-auto" aria-hidden="true"> <p class="usa-banner__header-text"> An official website of the United States government </p> <p class="usa-banner__header-action">Here鈥檚 how you know</p> </div> <button type="button" class="usa-accordion__button usa-banner__button" aria-expanded="false" aria-controls="gov-banner-default"> <span class="usa-banner__button-text">Here鈥檚 how you know</span> </button> </div> </header> <div class="usa-banner__content usa-accordion__content" id="gov-banner-default"> <div class="grid-row grid-gap-lg"> <div class="usa-banner__guidance tablet:grid-col-6"> <img class="usa-banner__icon usa-media-block__img" src="/dist/uswds/img/icon-dot-gov.svg" role="img" alt="" aria-hidden="true"/> <div class="usa-media-block__body"> <p> <strong>Official websites use .gov</strong><br/>A <strong>.gov</strong> website belongs to an official government organization in the United States. </p> </div> </div> <div class="usa-banner__guidance tablet:grid-col-6"> <img class="usa-banner__icon usa-media-block__img" src="/dist/uswds/img/icon-https.svg" role="img" alt="" aria-hidden="true"/> <div class="usa-media-block__body"> <p> <strong>Secure .gov websites use HTTPS</strong><br/>A <strong>lock</strong> ( <span class="icon-lock"> <svg xmlns="http://www.w3.org/2000/svg" width="52" height="64" viewBox="0 0 52 64" class="usa-banner__lock-image" role="img" aria-labelledby="banner-lock-description-default" focusable="false"> <title id="banner-lock-title-default">Lock</title> <desc id="banner-lock-description-default">Locked padlock icon</desc> <path fill="#000000" fill-rule="evenodd" d="M26 0c10.493 0 19 8.507 19 19v9h3a4 4 0 0 1 4 4v28a4 4 0 0 1-4 4H4a4 4 0 0 1-4-4V32a4 4 0 0 1 4-4h3v-9C7 8.507 15.507 0 26 0zm0 8c-5.979 0-10.843 4.77-10.996 10.712L15 19v9h22v-9c0-6.075-4.925-11-11-11z"/> </svg> </span >) or <strong>https://</strong> means you鈥檝e safely connected to the .gov website. Share sensitive information only on official, secure websites. </p> </div> </div> </div> </div> </div> </section> <nav id="navbar" class="navbar"> <div id="nist-menu-container" class="container"> <div class="row">  <div class="col-xs-6 col-md-4 navbar-header"> <a class="navbar-brand" href="https://www.nist.gov" target="_blank" id="navbar-brand-image"> <img src="/CSRC/media/images/svg/nist-logo.svg" alt="National Institute of Standards and Technology" width="110" height="30"> </a> </div> <div class="col-xs-6 col-md-8 navbar-nist-logo"> <div class="form-inline hidden-sm hidden-xs"> <form name="site-search" id="site-search-form" action="/search" method="GET"> <label for="search-csrc-query" class="element-invisible">Search</label> <input autocomplete="off" class="form-control" id="search-csrc-query" name="keywords" type="text" size="15" maxlength="128" placeholder="Search CSRC" /> <input type="hidden" name="ipp" value="25" /> <input type="hidden" name="sortBy" value="relevance" /> <input type="hidden" name="showOnly" value="publications,projects,news,events,presentations,glossary,topics" /> <input type="hidden" name="topicsMatch" value="ANY" /> <input type="hidden" name="status" value="Final,Draft" /> <button type="submit" id="search-csrc-submit-btn" class="form-submit"> <span class="element-invisible">Search</span> <i class="fa fa-search"></i> </button> </form> </div> <span id="nvd-menu-button" class="pull-right"> <a href="#" id="nvd-menu-button-link"> <span class="fa fa-bars"></span> <span id="nvd-menu-full-text">CSRC MENU</span> </a> </span> </div> </div> </div> <div class="form-inline hidden-md hidden-lg"> <form name="site-search-mobile" id="site-search-form-mobile" action="/search" method="GET"> <label for="search-csrc-query-mobile" class="element-invisible">Search</label> <input autocomplete="off" class="form-control" id="search-csrc-query-mobile" name="keywords" type="text" size="15" maxlength="128" placeholder="Search CSRC" /> <button type="submit" id="search-csrc-submit-btn-mobile" class="form-submit"> <span class="element-invisible">Search</span> <i class="fa fa-search"></i> </button> </form> </div> <div class="main-menu-row container">  <div id="main-menu-drop" class="col-lg-12" style="display: none;"> <ul> <li><a href="/projects">Projects</a></li> <li> <a href="/publications"> Publications <span class="expander fa fa-plus" id="main-menu-pubs-expander" data-expander-name="publications" data-expanded="false"> <span class="element-invisible">Expand or Collapse</span> </span> </a> <div style="display: none;" class="sub-menu" data-expander-trigger="publications" id="main-menu-pubs-expanded"> <div class="row"> <div class="col-lg-4"> <p><a href="/publications/drafts-open-for-comment">Drafts for Public Comment</a></p> <p><a href="/publications/draft-pubs">All Public Drafts</a></p> <p><a href="/publications/final-pubs">Final Pubs</a></p> <p><a href="/publications/fips">FIPS <small>(standards)</small></a></p> </div> <div class="col-lg-4"> <p><a href="/publications/sp">Special Publications (SP<small>s</small>)</a></p> <p><a href="/publications/ir">IR <small>(interagency/internal reports)</small></a></p> <p><a href="/publications/cswp">CSWP <small>(cybersecurity white papers)</small></a></p> <p><a href="/publications/itl-bulletin">ITL Bulletins</a></p> </div> <div class="col-lg-4"> <p><a href="/publications/project-description">Project Descriptions</a></p> <p><a href="/publications/journal-article">Journal Articles</a></p> <p><a href="/publications/conference-paper">Conference Papers</a></p> <p><a href="/publications/book">Books</a></p> </div> </div> </div> </li> <li> <a href="/topics"> Topics <span class="expander fa fa-plus" id="main-menu-topics-expander" data-expander-name="topics" data-expanded="false"> <span class="element-invisible">Expand or Collapse</span> </span> </a> <div style="display: none;" class="sub-menu" data-expander-trigger="topics" id="main-menu-topics-expanded"> <div class="row"> <div class="col-lg-4"> <p><a href="/Topics/Security-and-Privacy">Security & Privacy</a></p> <p><a href="/Topics/Applications">Applications</a></p> </div> <div class="col-lg-4"> <p><a href="/Topics/Technologies">Technologies</a></p> <p><a href="/Topics/Sectors">Sectors</a></p> </div> <div class="col-lg-4"> <p><a href="/Topics/Laws-and-Regulations">Laws & Regulations</a></p> <p><a href="/Topics/Activities-and-Products">Activities & Products</a></p> </div> </div> </div> </li> <li><a href="/news">News & Updates</a></li> <li><a href="/events">Events</a></li> <li><a href="/glossary">Glossary</a></li> <li> <a href="/about"> About CSRC <span class="expander fa fa-plus" id="main-menu-about-expander" data-expander-name="about" data-expanded="false"> <span class="element-invisible">Expand or Collapse</span> </span> </a> <div style="display: none;" class="sub-menu" data-expander-trigger="about" id="main-menu-about-expanded"> <div class="row"> <div class="col-lg-6"> <p> <strong><a href="/Groups/Computer-Security-Division">Computer Security Division</a></strong><br /> <ul> <li><a href="/Groups/Computer-Security-Division/Cryptographic-Technology">Cryptographic Technology</a></li> <li><a href="/Groups/Computer-Security-Division/Secure-Systems-and-Applications">Secure Systems and Applications</a></li> <li><a href="/Groups/Computer-Security-Division/Security-Components-and-Mechanisms">Security Components and Mechanisms</a></li> <li><a href="/Groups/Computer-Security-Division/Security-Engineering-and-Risk-Management">Security Engineering and Risk Management</a></li> <li><a href="/Groups/Computer-Security-Division/Security-Testing-Validation-and-Measurement">Security Testing, Validation, and Measurement</a></li> </ul> </p> </div> <div class="col-lg-6"> <p> <strong><a href="/Groups/Applied-Cybersecurity-Division">Applied Cybersecurity Division</a></strong><br /> <ul> <li><a href="/Groups/Applied-Cybersecurity-Division/Cybersecurity-and-Privacy-Applications">Cybersecurity and Privacy Applications</a></li> <li><a href="/Groups/Applied-Cybersecurity-Division/National-Cybersecurity-Center-of-Excellence">National Cybersecurity Center of Excellence (NCCoE)</a></li> <li><a href="https://www.nist.gov/nice/">National Initiative for Cybersecurity Education (NICE)</a></li> </ul> </p> <p> <a href="/contact"> Contact Us </a> </p> </div> </div> </div> </li> </ul> </div> </div> </nav> <section id="itl-header" class="has-menu"> <div class="container"> <div class="row"> <div class="col-sm-12 col-md-8"> <div class="hidden-xs hidden-sm" id="itl-header-lg"> <a href="https://www.nist.gov/itl" target="_blank" id="itl-header-link">Information Technology Laboratory</a> </div> <div class="hidden-xs hidden-sm" id="csrc-header-lg"> <a href="/" id="csrc-header-link-lg">Computer Security Resource Center</a> </div> </div> <div class="col-sm-12 col-md-4"> <div class="hidden-xs hidden-sm hidden-md"> <a id="logo-csrc-lg" href="/"><img id="img-logo-csrc-lg" src="/CSRC/Media/images/nist-logo-csrc-white.svg" alt="CSRC Logo" class="csrc-header-logo"></a> </div> <div class="hidden-lg"> <a id="logo-csrc-sm" href="/"><img id="img-logo-csrc-sm" src="/CSRC/Media/images/nist-logo-csrc-white.svg" alt="CSRC Logo" class="csrc-header-logo"></a> </div> </div> </div> </div> </section> <div id="body-section" class="container"> <div class="publications-detail"> <ol class="breadcrumb"> <a href="/publications" class="breadcrumb-link">Publications</a> </ol> <h3 id="pub-header-display-container"> <span id="pub-header-full-display"> Other </span> </h3> <h1 id="pub-title">Notes on Interrogating Random Quantum Circuits</h1> <div class="page-social-buttons" id="page-social-buttons"> <a href="https://www.facebook.com/sharer/sharer.php?u=https%3A%2F%2Fcsrc.nist.gov%2Fpubs%2Fother%2F2020%2F05%2F29%2Fnotes-on-interrogating-random-quantum-circuits%2Ffinal" class="social-facebook"><i class="fa fa-facebook fa-fw" aria-hidden="true"></i><span class="sr-only">Share to Facebook</span></a> <a href="https://twitter.com/share?url=https%3A%2F%2Fcsrc.nist.gov%2Fpubs%2Fother%2F2020%2F05%2F29%2Fnotes-on-interrogating-random-quantum-circuits%2Ffinal" class="social-twitter"><i class="fa fa-twitter fa-fw" aria-hidden="true"></i><span class="sr-only">Share to Twitter</span></a> <a href="https://www.linkedin.com/shareArticle?mini=true&url=https%3A%2F%2Fcsrc.nist.gov%2Fpubs%2Fother%2F2020%2F05%2F29%2Fnotes-on-interrogating-random-quantum-circuits%2Ffinal&source=csrc.nist.gov" class="social-linked-in"><i class="fa fa-linkedin fa-fw" aria-hidden="true"></i><span class="sr-only">Share to LinkedIn</span></a> <a href="mailto:?subject=csrc.nist.gov&body=Check out this site https://csrc.nist.gov/pubs/other/2020/05/29/notes-on-interrogating-random-quantum-circuits/final" class="social-email"><i class="fa fa-envelope fa-fw" aria-hidden="true"></i><span class="sr-only">Share ia Email</span></a> </div> <p class="hidden-lg hidden-md">     <a href="#pubs-documentation" class="btn btn-lg btn-info" id="pub-topics-anchor-sm">Documentation</a>     <a href="#pubs-topics" class="btn btn-lg btn-info" id="pub-topics-anchor-sm">Topics</a> </p> <div class="row"> <div class="col-md-8 col-sm-12 publication-panel"> <p> <strong>Date Published:</strong> <span id="pub-release-date" data-date-type="citation">May 2020</span><br /> </p> <h4>Author(s)</h4> <p id="pub-authors-container" data-total="2"> <span id="pub-author-0">Lu铆s T. A. N. Brand茫o (NIST)</span>, <span id="pub-author-1">Rene Peralta (NIST)</span> </p> <div class="bs-callout bs-callout-success pub-abstract-callout"> <h4 id="pubs-abstract-header">Abstract</h4> <div class="hidden-sm hidden-xs hidden-xxs" id="pub-detail-abstract-info">Consider a quantum circuit that, when fed a constant input, produces a fixed-length random bit-string in each execution. Executing it many times yields a sample of many bit-strings that contain fresh randomness inherent to the quantum evaluation. When the circuit is freshly selected from a special class, the output distribution of strings cannot be simulated in a short amount of time by a classical (non-quantum) computer. This quantum vs. classical gap of computational efficiency enables ways of inferring that an honest sample contains quantumly generated strings, and therefore fresh randomness. This possibility, initially proposed by Aaronson, has been recently validated in a "quantum supremacy" experiment by Google, using circuits with 53 qubits. In these notes, we consider the problem of estimating information entropy (a quantitative measure of random-ness), based on the sum of "probability values" (here called QC-values) of strings output by quantum evaluation. We assume that the sample of strings, claimed to have been produced by repeated evaluation of a quantum circuit, was in fact crafted by an adversary intending to induce us into overestimating entropy. We analyze the case of a "collisional" adversary that can over-sample and possibly take advantage of observed collisions. For diverse false-positive and false-negative rates, we devise parameters for testing the hypothesis that the sample has at least a certain expected entropy. This enables a client to certify the presence of entropy, after a lengthy computation of the QC-values. We also explore a method for low-budget clients to compute fewer QC-values, at the cost of more computation by a server. We conclude with several questions requiring further exploration.</div> <div class="hidden-lg hidden-md"> <div id="pub-detail-abstract-min"> Consider a quantum circuit that, when fed a constant input, produces a fixed-length random bit-string in each execution. Executing it many times yields a sample of many bit-strings that contain fresh randomness inherent to the quantum evaluation. When the circuit is freshly selected from a special... <a href="#pubs-abstract-header" id="pub-detail-abs-show">See full abstract</a> </div> <div id="pub-detail-abstract-all" style="display: none;"> Consider a quantum circuit that, when fed a constant input, produces a fixed-length random bit-string in each execution. Executing it many times yields a sample of many bit-strings that contain fresh randomness inherent to the quantum evaluation. When the circuit is freshly selected from a special class, the output distribution of strings cannot be simulated in a short amount of time by a classical (non-quantum) computer. This quantum vs. classical gap of computational efficiency enables ways of inferring that an honest sample contains quantumly generated strings, and therefore fresh randomness. This possibility, initially proposed by Aaronson, has been recently validated in a "quantum supremacy" experiment by Google, using circuits with 53 qubits. In these notes, we consider the problem of estimating information entropy (a quantitative measure of random-ness), based on the sum of "probability values" (here called QC-values) of strings output by quantum evaluation. We assume that the sample of strings, claimed to have been produced by repeated evaluation of a quantum circuit, was in fact crafted by an adversary intending to induce us into overestimating entropy. We analyze the case of a "collisional" adversary that can over-sample and possibly take advantage of observed collisions. For diverse false-positive and false-negative rates, we devise parameters for testing the hypothesis that the sample has at least a certain expected entropy. This enables a client to certify the presence of entropy, after a lengthy computation of the QC-values. We also explore a method for low-budget clients to compute fewer QC-values, at the cost of more computation by a server. We conclude with several questions requiring further exploration.<br /> <a href="#pubs-abstract-header" id="pub-detail-abs-hide">Hide full abstract</a> </div> </div> <h4>Keywords</h4> <span id='pub-keywords-container' data-total='6'> <span id="pub-keyword-0">certifiable randomness</span>; <span id="pub-keyword-1">distinguishability</span>; <span id="pub-keyword-2">entropy estimation</span>; <span id="pub-keyword-3">gamma distribution</span>; <span id="pub-keyword-4">public randomness</span>; <span id="pub-keyword-5">quantum randomness</span> </span> </div> <h5>Control Families</h5> <p> <span id="pub-control-fam-container" data-total="0">None selected</span> </p> </div> <div class="col-md-4 col-sm-12"> <div class="bs-callout bs-callout-success" id="pubs-documentation"> <h4>Documentation</h4> <p> <strong>Publication:</strong><br /> <a href="https://doi.org/10.13140/RG.2.2.24562.94400" id="pub-doi-link"> <i class="fa fa-external-link" aria-hidden="true"></i> https://doi.org/10.13140/RG.2.2.24562.94400 </a><br /> </p> <p> <strong>Supplemental Material:</strong><br /> <span id="pub-supp-container" data-total="0">None available</span><br /> </p> <p> <strong>Document History:</strong><br /> <span id="pub-history-container" data-total="1"> 05/29/20: <span id="pub-history-link-0" data-current-document='true'>Other (Final)</span><br /> </span> </p> </div> <div class="bs-callout bs-callout-danger" id="topicsCallout-lg"> <h4>Topics</h4> <strong id="pub-cat-0">Security and Privacy</strong> <p> <a id="pub-cat-top-0-0" href="/topics/security-and-privacy/cryptography/random-number-generation">random number generation</a> </p> <strong id="pub-cat-1">Technologies</strong> <p> <a id="pub-cat-top-1-0" href="/topics/technologies/quantum-information-science">quantum information science</a> </p> </div> </div> </div> </div> <div id="footer-pusher"></div> </div> <footer id="footer"> <div class="container"> <div class="row"> <div class="col-sm-6"> <span class="hidden-xs"> <a href="https://www.nist.gov" title="National Institute of Standards and Technology" rel="home" target="_blank" class="footer-nist-logo" id="footer-nist-logo-link"> <img src="/CSRC/Media/images/nist-logo-brand-white.svg" alt="National Institute of Standards and Technology logo" id="footer-nist-logo" /> </a> </span> <div class="row footer-contact-container"> <div class="col-sm-12" id="footer-address"> <strong>HEADQUARTERS</strong><br> 100 Bureau Drive<br> Gaithersburg, MD 20899 </div> </div> </div> <div class="col-sm-6"> <ul class="social-list text-right" style="display: block;"> <li class="field-item service-twitter list-horiz"> <a href="https://twitter.com/NISTCyber" class="social-btn social-btn--large extlink ext" id="footer-social-twitter-link"> <i class="fa fa-twitter fa-fw"><span class="element-invisible">twitter</span></i><span class="ext"><span class="element-invisible"> (link is external)</span></span> </a> </li> <li class="field-item service-facebook list-horiz"> <a href="https://www.facebook.com/NIST" class="social-btn social-btn--large extlink ext" id="footer-social-facebook-link"> <i class="fa fa-facebook fa-fw"><span class="element-invisible">facebook</span></i><span class="ext"><span class="element-invisible"> (link is external)</span></span> </a> </li> <li class="field-item service-linkedin list-horiz"> <a href="https://www.linkedin.com/company/nist" class="social-btn social-btn--large extlink ext" id="footer-social-linkedin-link"> <i class="fa fa-linkedin fa-fw"><span class="element-invisible">linkedin</span></i><span class="ext"><span class="element-invisible"> (link is external)</span></span> </a> </li> <li class="field-item service-instagram list-horiz"> <a href="https://www.instagram.com/usnistgov/" class="social-btn social-btn--large extlink ext" id="footer-social-instagram-link"> <i class="fa fa-instagram fa-fw"><span class="element-invisible">instagram</span></i> <span class="ext"><span class="element-invisible"> (link is external)</span></span> </a> </li> <li class="field-item service-youtube list-horiz"> <a href="https://www.youtube.com/user/USNISTGOV" class="social-btn social-btn--large extlink ext" id="footer-social-youtube-link"> <i class="fa fa-youtube fa-fw"><span class="element-invisible">youtube</span></i><span class="ext"><span class="element-invisible"> (link is external)</span></span> </a> </li> <li class="field-item service-rss list-horiz"> <a href="https://www.nist.gov/news-events/nist-rss-feeds" class="social-btn social-btn--large extlink" id="footer-social-rss-link"> <i class="fa fa-rss fa-fw"><span class="element-invisible">rss</span></i> </a> </li> <li class="field-item service-govdelivery list-horiz last"> <a href="https://public.govdelivery.com/accounts/USNIST/subscriber/new?qsp=USNIST_3" class="social-btn social-btn--large extlink ext" title="Subscribe to CSRC and publication updates, and other NIST cybersecurity news" id="footer-social-govdelivery-link"> <i class="fa fa-envelope fa-fw"><span class="element-invisible">govdelivery</span></i><span class="ext"><span class="element-invisible"> (link is external)</span></span> </a> </li> </ul> <p class="text-right"> Want updates about CSRC and our publications? <a href="https://public.govdelivery.com/accounts/USNIST/subscriber/new?qsp=USNIST_3" class="btn btn-lg btn-primary" style="background-color: #12659c!important; border-color: #12659c!important;" id="footer-subscribe-link">Subscribe</a> </p> </div> </div> <div class="row hidden-sm hidden-md hidden-lg"> <div class="col-sm-12"> <a href="https://www.nist.gov" title="National Institute of Standards and Technology" rel="home" target="_blank" class="footer-nist-logo" id="footer-bottom-nist-logo-link"> <img src="/CSRC/Media/images/logo_rev.png" alt="National Institute of Standards and Technology logo" id="footer-bottom-nist-logo" /> </a> </div> </div> <div class="row"> <div class="col-sm-6"> <p> <a href="/about/contact" id="footer-contact-us-link">Contact Us</a> | <a href="https://www.nist.gov/about-nist/visit" style="display: inline-block;" id="footer-org-link">Our Other Offices</a> </p> </div> <div class="col-sm-6"> <span class="pull-right text-right"> Send inquiries to <a href="mailto:csrc-inquiry@nist.gov?subject=CSRC Inquiry" style="display: inline-block;" id="footer-inquiries-link">csrc-inquiry@nist.gov</a> </span> </div> </div> <div class="row"> <div class="footer-bottom-links-container" id="footer-bottom-links-container"> <ul> <li><a href="https://www.nist.gov/privacy-policy">Site Privacy</a></li> <li><a href="https://www.nist.gov/oism/accessibility">Accessibility</a></li> <li><a href="https://www.nist.gov/privacy">Privacy Program</a></li> <li><a href="https://www.nist.gov/oism/copyrights">Copyrights</a></li> <li><a href="https://www.commerce.gov/vulnerability-disclosure-policy">Vulnerability Disclosure</a></li> <li><a href="https://www.nist.gov/no-fear-act-policy">No Fear Act Policy</a></li> <li><a href="https://www.nist.gov/foia">FOIA</a></li> <li><a href="https://www.nist.gov/environmental-policy-statement">Environmental Policy</a></li> <li><a href="https://www.nist.gov/summary-report-scientific-integrity">Scientific Integrity</a></li> <li><a href="https://www.nist.gov/nist-information-quality-standards">Information Quality Standards</a></li> <li><a href="https://www.commerce.gov/">Commerce.gov</a></li> <li><a href="https://www.science.gov/">Science.gov</a></li> <li><a href="https://www.usa.gov/">USA.gov</a></li> <li><a href="https://vote.gov/">Vote.gov</a></li> </ul> </div> </div> </div> </footer> <script type="text/javascript" src="/dist/js/quick-collapse.js"></script> <script type="text/javascript" src="/dist/app.bundle.js"></script>  <script type="text/javascript" src="/dist/uswds/js/uswds.min.js"></script> </body> </html>

CINXE.COM

Notes on Interrogating Random Quantum Circuits | CSRC