CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>BQP - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"6e05884e-c159-48d7-b5db-1ee7827dfcfa","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"BQP","wgTitle":"BQP","wgCurRevisionId":1230041542,"wgRevisionId":1230041542,"wgArticleId":4080,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["CS1 maint: location missing publisher","CS1 maint: multiple names: authors list","Articles with short description","Short description is different from Wikidata","Webarchive template wayback links","Probabilistic complexity classes","Quantum complexity theory","Quantum computing"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"BQP","wgRelevantArticleId":4080,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit": [],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":20000,"wgRelatedArticlesCompat":[],"wgCentralAuthMobileDomain":false,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q601325","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false, "wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups", "ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.4"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Randomised_Complexity_Classes_2.svg/1200px-Randomised_Complexity_Classes_2.svg.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="1200"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Randomised_Complexity_Classes_2.svg/800px-Randomised_Complexity_Classes_2.svg.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="800"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Randomised_Complexity_Classes_2.svg/640px-Randomised_Complexity_Classes_2.svg.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="640"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="BQP - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/BQP"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=BQP&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/BQP"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-BQP rootpage-BQP skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=BQP" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=BQP" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=BQP" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=BQP" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Definition" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Definition"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Definition</span> </div> </a> <ul id="toc-Definition-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Relationship_to_other_complexity_classes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Relationship_to_other_complexity_classes"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Relationship to other complexity classes</span> </div> </a> <button aria-controls="toc-Relationship_to_other_complexity_classes-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Relationship to other complexity classes subsection</span> </button> <ul id="toc-Relationship_to_other_complexity_classes-sublist" class="vector-toc-list"> <li id="toc-A_complete_problem_for_Promise-BQP" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#A_complete_problem_for_Promise-BQP"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>A complete problem for Promise-BQP</span> </div> </a> <ul id="toc-A_complete_problem_for_Promise-BQP-sublist" class="vector-toc-list"> <li id="toc-APPROX-QCIRCUIT-PROB" class="vector-toc-list-item vector-toc-level-3"> <a class="vector-toc-link" href="#APPROX-QCIRCUIT-PROB"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1.1</span> <span>APPROX-QCIRCUIT-PROB</span> </div> </a> <ul id="toc-APPROX-QCIRCUIT-PROB-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-BQP_and_EXP" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#BQP_and_EXP"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.2</span> <span>BQP and EXP</span> </div> </a> <ul id="toc-BQP_and_EXP-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-BQP_and_PSPACE" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#BQP_and_PSPACE"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.3</span> <span>BQP and PSPACE</span> </div> </a> <ul id="toc-BQP_and_PSPACE-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-BQP_and_PP" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#BQP_and_PP"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.4</span> <span>BQP and PP</span> </div> </a> <ul id="toc-BQP_and_PP-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-P_and_BQP" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#P_and_BQP"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.5</span> <span>P and BQP</span> </div> </a> <ul id="toc-P_and_BQP-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">BQP</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 11 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-11" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">11 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ca mw-list-item"><a href="https://ca.wikipedia.org/wiki/BQP_(complexitat)" title="BQP (complexitat) – Catalan" lang="ca" hreflang="ca" data-title="BQP (complexitat)" data-language-autonym="Català" data-language-local-name="Catalan" class="interlanguage-link-target"><span>Català</span></a></li><li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/BQP" title="BQP – German" lang="de" hreflang="de" data-title="BQP" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/BQP" title="BQP – Spanish" lang="es" hreflang="es" data-title="BQP" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/BQP" title="BQP – French" lang="fr" hreflang="fr" data-title="BQP" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/BQP" title="BQP – Korean" lang="ko" hreflang="ko" data-title="BQP" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/BQP_(complessit%C3%A0)" title="BQP (complessità) – Italian" lang="it" hreflang="it" data-title="BQP (complessità)" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/BQP" title="BQP – Hebrew" lang="he" hreflang="he" data-title="BQP" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/BQP" title="BQP – Japanese" lang="ja" hreflang="ja" data-title="BQP" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/BQP" title="BQP – Portuguese" lang="pt" hreflang="pt" data-title="BQP" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_BQP" title="Класс BQP – Russian" lang="ru" hreflang="ru" data-title="Класс BQP" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/BQP_(%E8%A4%87%E9%9B%9C%E5%BA%A6)" title="BQP (複雜度) – Chinese" lang="zh" hreflang="zh" data-title="BQP (複雜度)" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q601325#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/BQP" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:BQP" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/BQP"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=BQP&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=BQP&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/BQP"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=BQP&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=BQP&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/BQP" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/BQP" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=BQP&oldid=1230041542" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=BQP&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=BQP&id=1230041542&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FBQP"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FBQP"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=BQP&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=BQP&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q601325" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Computational complexity class of problems</div><style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">This article is about the computational complexity class. For other uses, see <a href="/wiki/BQP_(disambiguation)" class="mw-disambig" title="BQP (disambiguation)">BQP (disambiguation)</a>.</div><figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Randomised_Complexity_Classes_2.svg" class="mw-file-description"><img alt="Diagram of randomised complexity classes" src="//upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Randomised_Complexity_Classes_2.svg/280px-Randomised_Complexity_Classes_2.svg.png" decoding="async" width="280" height="280" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Randomised_Complexity_Classes_2.svg/420px-Randomised_Complexity_Classes_2.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Randomised_Complexity_Classes_2.svg/560px-Randomised_Complexity_Classes_2.svg.png 2x" data-file-width="640" data-file-height="640" /></a><figcaption>BQP in relation to other probabilistic complexity classes (<a href="/wiki/ZPP_(complexity)" title="ZPP (complexity)">ZPP</a>, <a href="/wiki/RP_(complexity)" title="RP (complexity)">RP</a>, co-RP, <a href="/wiki/BPP_(complexity)" title="BPP (complexity)">BPP</a>, <a href="/wiki/PP_(complexity)" title="PP (complexity)">PP</a>), which generalise <a href="/wiki/P_(complexity)" title="P (complexity)">P</a> within <a href="/wiki/PSPACE" title="PSPACE">PSPACE</a>. It is unknown if any of these containments are strict.</figcaption></figure> <p>In <a href="/wiki/Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a>, <b>bounded-error quantum polynomial time</b> (<b>BQP</b>) is the class of <a href="/wiki/Decision_problems" class="mw-redirect" title="Decision problems">decision problems</a> solvable by a <a href="/wiki/Quantum_computer" class="mw-redirect" title="Quantum computer">quantum computer</a> in <a href="/wiki/Polynomial_time" class="mw-redirect" title="Polynomial time">polynomial time</a>, with an error probability of at most 1/3 for all instances.<sup id="cite_ref-Chuang2000_1-0" class="reference"><a href="#cite_note-Chuang2000-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> It is the quantum analogue to the <a href="/wiki/Complexity_class" title="Complexity class">complexity class</a> <b><a href="/wiki/BPP_(complexity)" title="BPP (complexity)">BPP</a></b>. </p><p>A decision problem is a member of <b>BQP</b> if there exists a <a href="/wiki/Quantum_algorithm" title="Quantum algorithm">quantum algorithm</a> (an <a href="/wiki/Algorithm" title="Algorithm">algorithm</a> that runs on a quantum computer) that solves the decision problem <a href="/wiki/With_high_probability" title="With high probability">with high probability</a> and is guaranteed to run in polynomial time. A run of the algorithm will correctly solve the decision problem with a probability of at least 2/3. </p> <table class="wikitable" style="float:right; clear:right; text-align:center; margin-left:1em;"> <tbody><tr> <th colspan="3">BQP algorithm (1 run) </th></tr> <tr> <th style="background:#EAECF0;background:linear-gradient(to top right,#EAECF0 49%,#AAA 49.5%,#AAA 50.5%,#EAECF0 51%);line-height:1.2;padding:0.1em 0.4em;"><div style="margin-left:2em;text-align:right">Answer<div style="padding-left:4em;">produced</div></div><div style="margin-right:2em;text-align:left">Correct<br />answer</div> </th> <th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </th> <th style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No </th></tr> <tr> <th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </th> <td>≥ 2/3 </td> <td>≤ 1/3 </td></tr> <tr> <th style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No </th> <td>≤ 1/3 </td> <td>≥ 2/3 </td></tr> <tr> <th colspan="3">BQP algorithm (<i>k</i> runs) </th></tr> <tr> <th style="background:#EAECF0;background:linear-gradient(to top right,#EAECF0 49%,#AAA 49.5%,#AAA 50.5%,#EAECF0 51%);line-height:1.2;padding:0.1em 0.4em;"><div style="margin-left:2em;text-align:right"><div style="padding-left:4em;">Answer</div>produced</div><div style="margin-right:2em;text-align:left">Correct<br />answer</div> </th> <th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </th> <th style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No </th></tr> <tr> <th style="background:#9EFF9E;color:black;vertical-align:middle;text-align:center;" class="table-yes">Yes </th> <td>> 1 − 2<sup>−<i>ck</i></sup> </td> <td>< 2<sup>−<i>ck</i></sup> </td></tr> <tr> <th style="background:#FFC7C7;color:black;vertical-align:middle;text-align:center;" class="table-no">No </th> <td>< 2<sup>−<i>ck</i></sup> </td> <td>> 1 − 2<sup>−<i>ck</i></sup> </td></tr> <tr> <td colspan="3" style="font-size:85%">for some constant <i>c</i> > 0 </td></tr></tbody></table> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=BQP&action=edit&section=1" title="Edit section: Definition"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><b>BQP</b> can be viewed as the <a href="/wiki/Language_(computability)" class="mw-redirect" title="Language (computability)">languages</a> associated with certain bounded-error uniform families of <a href="/wiki/Quantum_circuit" title="Quantum circuit">quantum circuits</a>.<sup id="cite_ref-Chuang2000_1-1" class="reference"><a href="#cite_note-Chuang2000-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> A language <i>L</i> is in <b>BQP</b> if and only if there exists a <a href="/wiki/Circuit_complexity#Polynomial-time_uniform" title="Circuit complexity">polynomial-time uniform</a> family of quantum circuits <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{Q_{n}\colon n\in \mathbb {N} \}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <msub> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>:</mo> <mi>n</mi> <mo>∈</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">N</mi> </mrow> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{Q_{n}\colon n\in \mathbb {N} \}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8d8a4404e5abe854d183dde5481e831afbc40fae" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.329ex; height:2.843ex;" alt="{\displaystyle \{Q_{n}\colon n\in \mathbb {N} \}}"></span>, such that </p> <ul><li>For all <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in \mathbb {N} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>∈</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">N</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\in \mathbb {N} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d059936e77a2d707e9ee0a1d9575a1d693ce5d0b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.913ex; height:2.176ex;" alt="{\displaystyle n\in \mathbb {N} }"></span>, <i>Q<sub>n</sub></i> takes <i>n</i> qubits as input and outputs 1 bit</li> <li>For all <i>x</i> in <i>L</i>, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">P</mi> <mi mathvariant="normal">r</mi> </mrow> <mo stretchy="false">(</mo> <msub> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>≥</mo> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mn>2</mn> <mn>3</mn> </mfrac> </mstyle> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/23047688ee7831c1bc24c03bc85f50018c62240e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:20.386ex; height:3.676ex;" alt="{\displaystyle \mathrm {Pr} (Q_{|x|}(x)=1)\geq {\tfrac {2}{3}}}"></span></li> <li>For all <i>x</i> not in <i>L</i>, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">P</mi> <mi mathvariant="normal">r</mi> </mrow> <mo stretchy="false">(</mo> <msub> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mrow> </msub> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>≥</mo> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mfrac> <mn>2</mn> <mn>3</mn> </mfrac> </mstyle> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f5a5b78570450c48c24b5d3d2cbc54a91639b897" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:20.386ex; height:3.676ex;" alt="{\displaystyle \mathrm {Pr} (Q_{|x|}(x)=0)\geq {\tfrac {2}{3}}}"></span></li></ul> <p>Alternatively, one can define <b>BQP</b> in terms of <a href="/wiki/Quantum_Turing_machine" title="Quantum Turing machine">quantum Turing machines</a>. A language <i>L</i> is in <b>BQP</b> if and only if there exists a polynomial quantum Turing machine that accepts <i>L</i> with an error probability of at most 1/3 for all instances.<sup id="cite_ref-BernVazi_2-0" class="reference"><a href="#cite_note-BernVazi-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p><p>Similarly to other "bounded error" probabilistic classes, the choice of 1/3 in the definition is arbitrary. We can run the algorithm a constant number of times and take a majority vote to achieve any desired probability of correctness less than 1, using the <a href="/wiki/Chernoff_bound" title="Chernoff bound">Chernoff bound</a>. The complexity class is unchanged by allowing error as high as 1/2 − <i>n</i><sup>−<i>c</i></sup> on the one hand, or requiring error as small as 2<sup>−<i>n<sup>c</sup></i></sup> on the other hand, where <i>c</i> is any positive constant, and <i>n</i> is the length of input.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Relationship_to_other_complexity_classes">Relationship to other complexity classes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=BQP&action=edit&section=2" title="Edit section: Relationship to other complexity classes"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1233989161">.mw-parser-output .unsolved{margin:0.5em 0 1em 1em;border:#ccc solid;padding:0.35em 0.35em 0.35em 2.2em;background-color:var(--background-color-interactive-subtle);background-image:url("https://upload.wikimedia.org/wikipedia/commons/2/26/Question%2C_Web_Fundamentals.svg");background-position:top 50%left 0.35em;background-size:1.5em;background-repeat:no-repeat}@media(min-width:720px){.mw-parser-output .unsolved{clear:right;float:right;max-width:25%}}.mw-parser-output .unsolved-label{font-weight:bold}.mw-parser-output .unsolved-body{margin:0.35em;font-style:italic}.mw-parser-output .unsolved-more{font-size:smaller}</style> <div role="note" aria-labelledby="unsolved-label-computer_science" class="unsolved"> <div><span class="unsolved-label" id="unsolved-label-computer_science">Unsolved problem in computer science</span>:</div> <div class="unsolved-body">What is the relationship between <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathsf {BQP}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">B</mi> <mi mathvariant="sans-serif">Q</mi> <mi mathvariant="sans-serif">P</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {BQP}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ae713975de21d756f407c4df40432172a09f0004" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:4.746ex; height:2.343ex;" alt="{\displaystyle {\mathsf {BQP}}}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathsf {NP}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">N</mi> <mi mathvariant="sans-serif">P</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {NP}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/92f22868abb72c8ddd8bd336e87252ce73226086" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.131ex; height:2.176ex;" alt="{\displaystyle {\mathsf {NP}}}"></span>?</div> <div class="unsolved-more"><a href="/wiki/List_of_unsolved_problems_in_computer_science" title="List of unsolved problems in computer science">(more unsolved problems in computer science)</a></div> </div> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:BQP_complexity_class_diagram.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/1/1d/BQP_complexity_class_diagram.svg/220px-BQP_complexity_class_diagram.svg.png" decoding="async" width="220" height="176" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/1d/BQP_complexity_class_diagram.svg/330px-BQP_complexity_class_diagram.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/1d/BQP_complexity_class_diagram.svg/440px-BQP_complexity_class_diagram.svg.png 2x" data-file-width="518" data-file-height="414" /></a><figcaption>The suspected relationship of <b>BQP</b> to other problem spaces<sup id="cite_ref-Chuang2000_1-2" class="reference"><a href="#cite_note-Chuang2000-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></figcaption></figure> <p>BQP is defined for quantum computers; the corresponding complexity class for classical computers (or more formally for <a href="/wiki/Probabilistic_Turing_machine" title="Probabilistic Turing machine">probabilistic Turing machines</a>) is <b><a href="/wiki/Bounded-error_probabilistic_polynomial" class="mw-redirect" title="Bounded-error probabilistic polynomial">BPP</a></b>. Just like <b>P</b> and <b>BPP</b>, <b>BQP</b> is <a href="/wiki/Low_(complexity)" title="Low (complexity)">low</a> for itself, which means <span class="texhtml"><span style="font-family:sans-serif;">BQP<sup>BQP</sup> = BQP</span></span>.<sup id="cite_ref-BernVazi_2-1" class="reference"><a href="#cite_note-BernVazi-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Informally, this is true because polynomial time algorithms are closed under composition. If a polynomial time algorithm calls polynomial time algorithms as subroutines, the resulting algorithm is still polynomial time. </p><p><b>BQP</b> contains <b><a href="/wiki/P_(complexity)" title="P (complexity)">P</a></b> and <b><a href="/wiki/Bounded-error_probabilistic_polynomial" class="mw-redirect" title="Bounded-error probabilistic polynomial">BPP</a></b> and is contained in <b><a href="/wiki/Almost_Wide_Probabilistic_Polynomial-Time" class="mw-redirect" title="Almost Wide Probabilistic Polynomial-Time">AWPP</a></b>,<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> <b><a href="/wiki/PP_(complexity)" title="PP (complexity)">PP</a></b><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> and <b><a href="/wiki/PSPACE" title="PSPACE">PSPACE</a></b>.<sup id="cite_ref-BernVazi_2-2" class="reference"><a href="#cite_note-BernVazi-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> In fact, <b>BQP</b> is <a href="/wiki/Low_(complexity)" title="Low (complexity)">low</a> for <b>PP</b>, meaning that a <b>PP</b> machine achieves no benefit from being able to solve <b>BQP</b> problems instantly, an indication of the possible difference in power between these similar classes. The known relationships with classic complexity classes are: </p> <dl><dd><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathsf {P\subseteq BPP\subseteq BQP\subseteq AWPP\subseteq PP\subseteq PSPACE\subseteq EXP}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">P</mi> <mo>⊆</mo> <mi mathvariant="sans-serif">B</mi> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">P</mi> <mo>⊆</mo> <mi mathvariant="sans-serif">B</mi> <mi mathvariant="sans-serif">Q</mi> <mi mathvariant="sans-serif">P</mi> <mo>⊆</mo> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">W</mi> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">P</mi> <mo>⊆</mo> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">P</mi> <mo>⊆</mo> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">S</mi> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">C</mi> <mi mathvariant="sans-serif">E</mi> <mo>⊆</mo> <mi mathvariant="sans-serif">E</mi> <mi mathvariant="sans-serif">X</mi> <mi mathvariant="sans-serif">P</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {P\subseteq BPP\subseteq BQP\subseteq AWPP\subseteq PP\subseteq PSPACE\subseteq EXP}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5270409da34a463e608c0ad097eec84cf68f45c1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:52.138ex; height:2.343ex;" alt="{\displaystyle {\mathsf {P\subseteq BPP\subseteq BQP\subseteq AWPP\subseteq PP\subseteq PSPACE\subseteq EXP}}}"></span></dd></dl> <p>As the problem of <span class="nowrap">⁠<span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathsf {P}}\ {\stackrel {?}{=}}\ {\mathsf {PSPACE}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">P</mi> </mrow> </mrow> <mtext> </mtext> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-REL"> <mover> <mrow class="MJX-TeXAtom-OP MJX-fixedlimits"> <mo>=</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>?</mo> </mrow> </mover> </mrow> </mrow> <mtext> </mtext> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">S</mi> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">C</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {P}}\ {\stackrel {?}{=}}\ {\mathsf {PSPACE}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4709c088b0e8f91d6a9fe85c834e08fb13674a19" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:13.141ex; height:3.343ex;" alt="{\displaystyle {\mathsf {P}}\ {\stackrel {?}{=}}\ {\mathsf {PSPACE}}}"></span>⁠</span> has not yet been solved, the proof of inequality between <b>BQP</b> and classes mentioned above is supposed to be difficult.<sup id="cite_ref-BernVazi_2-3" class="reference"><a href="#cite_note-BernVazi-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> The relation between <b>BQP</b> and <b><a href="/wiki/NP_(complexity)" title="NP (complexity)">NP</a></b> is not known. In May 2018, computer scientists <a href="/wiki/Ran_Raz" title="Ran Raz">Ran Raz</a> of <a href="/wiki/Princeton_University" title="Princeton University">Princeton University</a> and Avishay Tal of <a href="/wiki/Stanford_University" title="Stanford University">Stanford University</a> published a paper<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> which showed that, relative to an <a href="/wiki/Oracle_machine" title="Oracle machine">oracle</a>, BQP was not contained in <a href="/wiki/Polynomial_hierarchy" title="Polynomial hierarchy">PH</a>. It can be proven that there exists an oracle A such that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathsf {BQP}}^{\mathrm {A} }\nsubseteq {\mathsf {PH}}^{\mathrm {A} }}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">B</mi> <mi mathvariant="sans-serif">Q</mi> <mi mathvariant="sans-serif">P</mi> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">A</mi> </mrow> </mrow> </msup> <mo>⊈</mo> <msup> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">H</mi> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="normal">A</mi> </mrow> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {BQP}}^{\mathrm {A} }\nsubseteq {\mathsf {PH}}^{\mathrm {A} }}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2a18fea7ed649e45c20220a8c05308697ece879d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.905ex; height:3.509ex;" alt="{\displaystyle {\mathsf {BQP}}^{\mathrm {A} }\nsubseteq {\mathsf {PH}}^{\mathrm {A} }}"></span>.<sup id="cite_ref-:0_7-0" class="reference"><a href="#cite_note-:0-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> In an extremely informal sense, this can be thought of as giving PH and BQP an identical, but additional, capability and verifying that BQP with the oracle (BQP<sup>A</sup>) can do things PH<sup>A</sup> cannot. While an oracle separation has been proven, the fact that BQP is not contained in PH has not been proven. An oracle separation does not prove whether or not complexity classes are the same. The oracle separation gives intuition that BQP may not be contained in PH. </p><p>It has been suspected for many years that Fourier Sampling is a problem that exists within BQP, but not within the polynomial hierarchy. Recent conjectures have provided evidence that a similar problem, Fourier Checking, also exists in the class BQP without being contained in the <a href="/wiki/Polynomial_hierarchy" title="Polynomial hierarchy">polynomial hierarchy</a>. This conjecture is especially notable because it suggests that problems existing in BQP could be classified as harder than <a href="/wiki/NP-completeness" title="NP-completeness">NP-Complete</a> problems. Paired with the fact that many practical BQP problems are suspected to exist outside of <a href="/wiki/P_(complexity)" title="P (complexity)">P</a> (it is suspected and not verified because there is no proof that <a href="/wiki/P_versus_NP_problem" title="P versus NP problem">P ≠ NP</a>), this illustrates the potential power of quantum computing in relation to classical computing.<sup id="cite_ref-:0_7-1" class="reference"><a href="#cite_note-:0-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> </p><p>Adding <a href="/wiki/Postselection" title="Postselection">postselection</a> to <b>BQP</b> results in the complexity class <b><a href="/wiki/PostBQP" title="PostBQP">PostBQP</a></b> which is equal to <b><a href="/wiki/PP_(complexity)" title="PP (complexity)">PP</a></b>.<sup id="cite_ref-PostBQP=PP_8-0" class="reference"><a href="#cite_note-PostBQP=PP-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="A_complete_problem_for_Promise-BQP">A complete problem for Promise-BQP</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=BQP&action=edit&section=3" title="Edit section: A complete problem for Promise-BQP"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Promise-BQP is the class of <a href="/wiki/Promise_problem" title="Promise problem">promise problems</a> that can be solved by a uniform family of quantum circuits (i.e., within BQP).<sup id="cite_ref-janzing-wocjan_10-0" class="reference"><a href="#cite_note-janzing-wocjan-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> Completeness proofs focus on this version of BQP. Similar to the notion of <a href="/wiki/NP-completeness" title="NP-completeness">NP-completeness</a> and other <a href="/wiki/Complete_(complexity)" title="Complete (complexity)">complete</a> problems, we can define a complete problem as a problem that is in Promise-BQP and that every other problem in Promise-BQP reduces to it in polynomial time. </p> <div class="mw-heading mw-heading4"><h4 id="APPROX-QCIRCUIT-PROB">APPROX-QCIRCUIT-PROB</h4><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=BQP&action=edit&section=4" title="Edit section: APPROX-QCIRCUIT-PROB"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The APPROX-QCIRCUIT-PROB problem is complete for efficient quantum computation, and the version presented below is complete for the Promise-BQP complexity class (and not for the total BQP complexity class, for which no complete problems are known). APPROX-QCIRCUIT-PROB's completeness makes it useful for proofs showing the relationships between other complexity classes and BQP. </p><p>Given a description of a quantum circuit <span class="texhtml mvar" style="font-style:italic;">C</span> acting on <span class="texhtml mvar" style="font-style:italic;">n</span> qubits with <span class="texhtml mvar" style="font-style:italic;">m</span> gates, where <span class="texhtml mvar" style="font-style:italic;">m</span> is a polynomial in <span class="texhtml mvar" style="font-style:italic;">n</span> and each gate acts on one or two qubits, and two numbers <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha ,\beta \in [0,1],\alpha >\beta }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>α</mi> <mo>,</mo> <mi>β</mi> <mo>∈</mo> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> <mo>,</mo> <mi>α</mi> <mo>></mo> <mi>β</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \alpha ,\beta \in [0,1],\alpha >\beta }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d6ddbd97dc5d10ff466db7a269aa64663cfd86e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.299ex; height:2.843ex;" alt="{\displaystyle \alpha ,\beta \in [0,1],\alpha >\beta }"></span>, distinguish between the following two cases: </p> <ul><li>measuring the first qubit of the state <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C|0\rangle ^{\otimes n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <msup> <mo fence="false" stretchy="false">⟩</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>⊗</mo> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C|0\rangle ^{\otimes n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aa07028abf627a5d67d103c89360c41728ee6b18" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.977ex; height:3.009ex;" alt="{\displaystyle C|0\rangle ^{\otimes n}}"></span> yields <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |1\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |1\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f53021ca18e77477ee5bd3c1523e5830189ec5c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.714ex; height:2.843ex;" alt="{\displaystyle |1\rangle }"></span> with probability <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \geq \alpha }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>≥</mo> <mi>α</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \geq \alpha }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/28bb8812f0aa342b814f97d009787661659f2718" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:3.941ex; height:2.176ex;" alt="{\displaystyle \geq \alpha }"></span></li> <li>measuring the first qubit of the state <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C|0\rangle ^{\otimes n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <msup> <mo fence="false" stretchy="false">⟩</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>⊗</mo> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C|0\rangle ^{\otimes n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aa07028abf627a5d67d103c89360c41728ee6b18" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.977ex; height:3.009ex;" alt="{\displaystyle C|0\rangle ^{\otimes n}}"></span> yields <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |1\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |1\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f53021ca18e77477ee5bd3c1523e5830189ec5c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.714ex; height:2.843ex;" alt="{\displaystyle |1\rangle }"></span> with probability <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \leq \beta }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>≤</mo> <mi>β</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \leq \beta }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6d787170f0a4872351f57ad3a59214650a7a7e3f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.785ex; height:2.509ex;" alt="{\displaystyle \leq \beta }"></span></li></ul> <p>Here, there is a promise on the inputs as the problem does not specify the behavior if an instance is not covered by these two cases. </p><p><b>Claim.</b> Any BQP problem reduces to APPROX-QCIRCUIT-PROB. </p><p><b>Proof.</b> Suppose we have an algorithm <span class="texhtml mvar" style="font-style:italic;">A</span> that solves APPROX-QCIRCUIT-PROB, i.e., given a quantum circuit <span class="texhtml mvar" style="font-style:italic;">C</span> acting on <span class="texhtml mvar" style="font-style:italic;">n</span> qubits, and two numbers <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha ,\beta \in [0,1],\alpha >\beta }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>α</mi> <mo>,</mo> <mi>β</mi> <mo>∈</mo> <mo stretchy="false">[</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">]</mo> <mo>,</mo> <mi>α</mi> <mo>></mo> <mi>β</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \alpha ,\beta \in [0,1],\alpha >\beta }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9d6ddbd97dc5d10ff466db7a269aa64663cfd86e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.299ex; height:2.843ex;" alt="{\displaystyle \alpha ,\beta \in [0,1],\alpha >\beta }"></span>, <span class="texhtml mvar" style="font-style:italic;">A</span> distinguishes between the above two cases. We can solve any problem in BQP with this oracle, by setting <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha =2/3,\beta =1/3}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>α</mi> <mo>=</mo> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>3</mn> <mo>,</mo> <mi>β</mi> <mo>=</mo> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>3</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \alpha =2/3,\beta =1/3}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6be9a1a60ecb7c7eeb49270d7c8faec9a297e57e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.025ex; height:2.843ex;" alt="{\displaystyle \alpha =2/3,\beta =1/3}"></span>. </p><p>For any <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L\in {\mathsf {BQP}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>L</mi> <mo>∈</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">B</mi> <mi mathvariant="sans-serif">Q</mi> <mi mathvariant="sans-serif">P</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L\in {\mathsf {BQP}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cc2dc5ad2fd77568a7ed4b01c3096218c46a61e6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.17ex; height:2.343ex;" alt="{\displaystyle L\in {\mathsf {BQP}}}"></span>, there exists family of quantum circuits <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{Q_{n}\colon n\in \mathbb {N} \}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">{</mo> <msub> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>:</mo> <mi>n</mi> <mo>∈</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">N</mi> </mrow> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \{Q_{n}\colon n\in \mathbb {N} \}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8d8a4404e5abe854d183dde5481e831afbc40fae" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.329ex; height:2.843ex;" alt="{\displaystyle \{Q_{n}\colon n\in \mathbb {N} \}}"></span> such that for all <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in \mathbb {N} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>∈</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">N</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\in \mathbb {N} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d059936e77a2d707e9ee0a1d9575a1d693ce5d0b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.913ex; height:2.176ex;" alt="{\displaystyle n\in \mathbb {N} }"></span>, a state <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |x\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |x\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/48004887d8f9dfc489bd2bc793780b7f1d8039ad" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.881ex; height:2.843ex;" alt="{\displaystyle |x\rangle }"></span> of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> qubits, if <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>∈</mo> <mi>L</mi> <mo>,</mo> <mi>P</mi> <mi>r</mi> <mo stretchy="false">(</mo> <msub> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">)</mo> <mo>=</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>≥</mo> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>3</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fc875439c08003ba4ecf6290758913ee2844247e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.985ex; height:2.843ex;" alt="{\displaystyle x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3}"></span>; else if <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\notin L,Pr(Q_{n}(|x\rangle )=0)\geq 2/3}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>∉</mo> <mi>L</mi> <mo>,</mo> <mi>P</mi> <mi>r</mi> <mo stretchy="false">(</mo> <msub> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">)</mo> <mo>=</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>≥</mo> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>3</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x\notin L,Pr(Q_{n}(|x\rangle )=0)\geq 2/3}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5eda7687047590704ebb807f62b478365a535fbc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.985ex; height:2.843ex;" alt="{\displaystyle x\notin L,Pr(Q_{n}(|x\rangle )=0)\geq 2/3}"></span>. Fix an input <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |x\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |x\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/48004887d8f9dfc489bd2bc793780b7f1d8039ad" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.881ex; height:2.843ex;" alt="{\displaystyle |x\rangle }"></span> of <span class="texhtml mvar" style="font-style:italic;">n</span> qubits, and the corresponding quantum circuit <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q_{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/503d0af3998f76cd4eaf8b3cc5e8834e254cb71b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.057ex; height:2.509ex;" alt="{\displaystyle Q_{n}}"></span>. We can first construct a circuit <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{x}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{x}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/46c7c57eb7d5bafc9dbb07668033f00118f5e48e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.834ex; height:2.509ex;" alt="{\displaystyle C_{x}}"></span> such that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{x}|0\rangle ^{\otimes n}=|x\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <msup> <mo fence="false" stretchy="false">⟩</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>⊗</mo> <mi>n</mi> </mrow> </msup> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C_{x}|0\rangle ^{\otimes n}=|x\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ed5473258592024c08a7108da3208e0596b3e598" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.025ex; height:3.009ex;" alt="{\displaystyle C_{x}|0\rangle ^{\otimes n}=|x\rangle }"></span>. This can be done easily by hardwiring <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |x\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |x\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/48004887d8f9dfc489bd2bc793780b7f1d8039ad" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.881ex; height:2.843ex;" alt="{\displaystyle |x\rangle }"></span> and apply a sequence of <a href="/wiki/Controlled_NOT_gate" title="Controlled NOT gate">CNOT</a> gates to flip the qubits. Then we can combine two circuits to get <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C'=Q_{n}C_{x}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>C</mi> <mo>′</mo> </msup> <mo>=</mo> <msub> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C'=Q_{n}C_{x}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b07f29c8411642e863521df7d274557a9305051c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.472ex; height:2.843ex;" alt="{\displaystyle C'=Q_{n}C_{x}}"></span>, and now <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>C</mi> <mo>′</mo> </msup> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <msup> <mo fence="false" stretchy="false">⟩</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>⊗</mo> <mi>n</mi> </mrow> </msup> <mo>=</mo> <msub> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/04072e65485b09446ed805455c15c0ed31e9af27" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.73ex; height:3.009ex;" alt="{\displaystyle C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle }"></span>. And finally, necessarily the results of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Q_{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/503d0af3998f76cd4eaf8b3cc5e8834e254cb71b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.057ex; height:2.509ex;" alt="{\displaystyle Q_{n}}"></span> is obtained by measuring several qubits and apply some (classical) logic gates to them. We can always <a href="/wiki/Deferred_Measurement_Principle" class="mw-redirect" title="Deferred Measurement Principle">defer the measurement</a><sup id="cite_ref-NielsenChuang2010_11-0" class="reference"><a href="#cite_note-NielsenChuang2010-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Cross2012_12-0" class="reference"><a href="#cite_note-Cross2012-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> and reroute the circuits so that by measuring the first qubit of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>C</mi> <mo>′</mo> </msup> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <msup> <mo fence="false" stretchy="false">⟩</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>⊗</mo> <mi>n</mi> </mrow> </msup> <mo>=</mo> <msub> <mi>Q</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/04072e65485b09446ed805455c15c0ed31e9af27" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.73ex; height:3.009ex;" alt="{\displaystyle C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle }"></span>, we get the output. This will be our circuit <span class="texhtml mvar" style="font-style:italic;">C</span>, and we decide the membership of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in L}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>∈</mo> <mi>L</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x\in L}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/97fca945ad424639c27ec8dccaf96c0bda408d3d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.753ex; height:2.176ex;" alt="{\displaystyle x\in L}"></span> by running <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A(C)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>A</mi> <mo stretchy="false">(</mo> <mi>C</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle A(C)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6fccdefed22adca8e71ef35ea54f288ec050c955" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.319ex; height:2.843ex;" alt="{\displaystyle A(C)}"></span> with <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha =2/3,\beta =1/3}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>α</mi> <mo>=</mo> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>3</mn> <mo>,</mo> <mi>β</mi> <mo>=</mo> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>3</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \alpha =2/3,\beta =1/3}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6be9a1a60ecb7c7eeb49270d7c8faec9a297e57e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.025ex; height:2.843ex;" alt="{\displaystyle \alpha =2/3,\beta =1/3}"></span>. By definition of BQP, we will either fall into the first case (acceptance), or the second case (rejection), so <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L\in {\mathsf {BQP}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>L</mi> <mo>∈</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">B</mi> <mi mathvariant="sans-serif">Q</mi> <mi mathvariant="sans-serif">P</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle L\in {\mathsf {BQP}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cc2dc5ad2fd77568a7ed4b01c3096218c46a61e6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.17ex; height:2.343ex;" alt="{\displaystyle L\in {\mathsf {BQP}}}"></span> reduces to APPROX-QCIRCUIT-PROB. </p> <div class="mw-heading mw-heading3"><h3 id="BQP_and_EXP">BQP and EXP</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=BQP&action=edit&section=5" title="Edit section: BQP and EXP"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>We begin with an easier containment. To show that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {EXP}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">B</mi> <mi mathvariant="sans-serif">Q</mi> <mi mathvariant="sans-serif">P</mi> </mrow> </mrow> <mo>⊆</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">E</mi> <mi mathvariant="sans-serif">X</mi> <mi mathvariant="sans-serif">P</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {EXP}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5ed327e10a44b809e63b8bd3ef392b27e6312285" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:12.268ex; height:2.343ex;" alt="{\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {EXP}}}"></span>, it suffices to show that APPROX-QCIRCUIT-PROB is in EXP since APPROX-QCIRCUIT-PROB is BQP-complete. </p> <style data-mw-deduplicate="TemplateStyles:r1110004140">.mw-parser-output .math_theorem{margin:1em 2em;padding:0.5em 1em 0.4em;border:1px solid #aaa;overflow:hidden}@media(max-width:500px){.mw-parser-output .math_theorem{margin:1em 0em;padding:0.5em 0.5em 0.4em}}</style><div class="math_theorem" style=""> <p><strong class="theorem-name">Claim</strong><span class="theoreme-tiret"> — </span><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtext>APPROX-QCIRCUIT-PROB</mtext> </mrow> <mo>∈</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">E</mi> <mi mathvariant="sans-serif">X</mi> <mi mathvariant="sans-serif">P</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f807abda372c5119a69959ef91268907f66d101c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:37.706ex; height:2.509ex;" alt="{\displaystyle {\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}}"></span> </p> </div> <style data-mw-deduplicate="TemplateStyles:r1174254338">.mw-parser-output .math_proof{border:thin solid #aaa;margin:1em 2em;padding:0.5em 1em 0.4em}@media(max-width:500px){.mw-parser-output .math_proof{margin:1em 0;padding:0.5em 0.5em 0.4em}}</style><div class="math_proof" style=""><strong>Proof</strong> <p>The idea is simple. Since we have exponential power, given a quantum circuit <span class="texhtml mvar" style="font-style:italic;">C</span>, we can use classical computer to stimulate each gate in <span class="texhtml mvar" style="font-style:italic;">C</span> to get the final state. </p><p>More formally, let <span class="texhtml mvar" style="font-style:italic;">C</span> be a polynomial sized quantum circuit on <span class="texhtml mvar" style="font-style:italic;">n</span> qubits and <span class="texhtml mvar" style="font-style:italic;">m</span> gates, where m is polynomial in n. Let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\psi _{0}\rangle =|0\rangle ^{\otimes n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>ψ</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo fence="false" stretchy="false">⟩</mo> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <msup> <mo fence="false" stretchy="false">⟩</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>⊗</mo> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\psi _{0}\rangle =|0\rangle ^{\otimes n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2455089ebe35afd2249848bffc6fc6413e12d368" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.428ex; height:3.009ex;" alt="{\displaystyle |\psi _{0}\rangle =|0\rangle ^{\otimes n}}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\psi _{i}\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>ψ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\psi _{i}\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1284d734d01861923334d7ebfe1ddc855f25a66a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.864ex; height:2.843ex;" alt="{\displaystyle |\psi _{i}\rangle }"></span> be the state after the <span class="texhtml mvar" style="font-style:italic;">i</span>-th gate in the circuit is applied to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\psi _{i-1}\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>ψ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\psi _{i-1}\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a018d67d661c1fa0252cc6789398f7c9f9c004cc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.965ex; height:2.843ex;" alt="{\displaystyle |\psi _{i-1}\rangle }"></span>. Each state <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\psi _{i}\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>ψ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\psi _{i}\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1284d734d01861923334d7ebfe1ddc855f25a66a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.864ex; height:2.843ex;" alt="{\displaystyle |\psi _{i}\rangle }"></span> can be represented in a classical computer as a unit vector in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {C} ^{2^{n}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {C} ^{2^{n}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/529d92e88844b6880aa6a7abf4a8281af6920231" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.697ex; height:2.843ex;" alt="{\displaystyle \mathbb {C} ^{2^{n}}}"></span>. Furthermore, each gate can be represented by a matrix in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {C} ^{2^{n}\times 2^{n}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>×</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {C} ^{2^{n}\times 2^{n}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8ac4dfd7dae7d96deec80ee80c989d177cb55541" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.763ex; height:2.843ex;" alt="{\displaystyle \mathbb {C} ^{2^{n}\times 2^{n}}}"></span>. Hence, the final state <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\psi _{m}\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>ψ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msub> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\psi _{m}\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/58df80b27bb0252fe36d8489583b3af6cf2d1dc8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.74ex; height:2.843ex;" alt="{\displaystyle |\psi _{m}\rangle }"></span> can be computed in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(m\cdot 2^{2n})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>m</mi> <mo>⋅</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> <mi>n</mi> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(m\cdot 2^{2n})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c5ee9c5cca0bfc3b6429f9664a8bdee29838fe29" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.505ex; height:3.176ex;" alt="{\displaystyle O(m\cdot 2^{2n})}"></span> time, and therefore all together, we have an <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{O(n)}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{O(n)}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/69a16bd3fa1209d0c3a221916283c9c3a4006d33" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.914ex; height:2.843ex;" alt="{\displaystyle 2^{O(n)}}"></span> time algorithm for calculating the final state, and thus the probability that the first qubit is measured to be one. This implies that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtext>APPROX-QCIRCUIT-PROB</mtext> </mrow> <mo>∈</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">E</mi> <mi mathvariant="sans-serif">X</mi> <mi mathvariant="sans-serif">P</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f807abda372c5119a69959ef91268907f66d101c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:37.706ex; height:2.509ex;" alt="{\displaystyle {\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}}"></span>. </p> </div> <p>Note that this algorithm also requires <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{O(n)}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{O(n)}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/69a16bd3fa1209d0c3a221916283c9c3a4006d33" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.914ex; height:2.843ex;" alt="{\displaystyle 2^{O(n)}}"></span> space to store the vectors and the matrices. We will show in the following section that we can improve upon the space complexity. </p> <div class="mw-heading mw-heading3"><h3 id="BQP_and_PSPACE">BQP and PSPACE</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=BQP&action=edit&section=6" title="Edit section: BQP and PSPACE"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Sum of histories is a technique introduced by physicist <a href="/wiki/Richard_Feynman" title="Richard Feynman">Richard Feynman</a> for <a href="/wiki/Path_integral_formulation" title="Path integral formulation">path integral formulation</a>. APPROX-QCIRCUIT-PROB can be formulated in the sum of histories technique to show that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {PSPACE}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">B</mi> <mi mathvariant="sans-serif">Q</mi> <mi mathvariant="sans-serif">P</mi> </mrow> </mrow> <mo>⊆</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">S</mi> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">C</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {PSPACE}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8f0a54d494e6aa332b9986d25b9d23bde3a3a388" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:16.531ex; height:2.343ex;" alt="{\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {PSPACE}}}"></span>.<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> </p> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Sum_of_histories_tree.png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/f/f9/Sum_of_histories_tree.png/220px-Sum_of_histories_tree.png" decoding="async" width="220" height="187" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/f/f9/Sum_of_histories_tree.png/330px-Sum_of_histories_tree.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/f/f9/Sum_of_histories_tree.png/440px-Sum_of_histories_tree.png 2x" data-file-width="1784" data-file-height="1518" /></a><figcaption>Sum of Histories Tree</figcaption></figure> <p>Consider a quantum circuit <span class="texhtml mvar" style="font-style:italic;">C</span>, which consists of <span class="texhtml mvar" style="font-style:italic;">t</span> gates, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{1},g_{2},\cdots ,g_{m}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g_{1},g_{2},\cdots ,g_{m}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3c8ebeb89525202bfde82bbd50398bac201f4850" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.323ex; height:2.009ex;" alt="{\displaystyle g_{1},g_{2},\cdots ,g_{m}}"></span>, where each <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{j}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g_{j}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ccc0c1f707e4786c1121db1ba0a608fe85a94e2d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.019ex; height:2.343ex;" alt="{\displaystyle g_{j}}"></span> comes from a <a href="/wiki/Quantum_logic_gate#Universal_quantum_gates" title="Quantum logic gate">universal gate set</a> and acts on at most two qubits. To understand what the sum of histories is, we visualize the evolution of a quantum state given a quantum circuit as a tree. The root is the input <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |0\rangle ^{\otimes n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <msup> <mo fence="false" stretchy="false">⟩</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>⊗</mo> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |0\rangle ^{\otimes n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/de7fb7c35a405ed7bb9376e84754d039f3030998" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.211ex; height:3.009ex;" alt="{\displaystyle |0\rangle ^{\otimes n}}"></span>, and each node in the tree has <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8226f30650ee4fe4e640c6d2798127e80e9c160d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}"></span> children, each representing a state in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {C} ^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">C</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {C} ^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a53b4e76242764d1bca004168353c380fef25258" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.897ex; height:2.343ex;" alt="{\displaystyle \mathbb {C} ^{n}}"></span>. The weight on a tree edge from a node in <span class="texhtml mvar" style="font-style:italic;">j</span>-th level representing a state <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |x\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |x\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/48004887d8f9dfc489bd2bc793780b7f1d8039ad" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.881ex; height:2.843ex;" alt="{\displaystyle |x\rangle }"></span> to a node in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j+1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>j</mi> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle j+1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5baf2ec9e436e9309065133555e3cb2ecd88f87e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:4.988ex; height:2.509ex;" alt="{\displaystyle j+1}"></span>-th level representing a state <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |y\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>y</mi> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |y\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/643420d48e63477f6a3252e36c924ca689f91ef9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.707ex; height:2.843ex;" alt="{\displaystyle |y\rangle }"></span> is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \langle y|g_{j+1}|x\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟨</mo> <mi>y</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \langle y|g_{j+1}|x\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8ac9a3a11935c99b2544bd013843a74f2d49cd83" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.707ex; height:3.009ex;" alt="{\displaystyle \langle y|g_{j+1}|x\rangle }"></span>, the amplitude of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |y\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>y</mi> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |y\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/643420d48e63477f6a3252e36c924ca689f91ef9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.707ex; height:2.843ex;" alt="{\displaystyle |y\rangle }"></span> after applying <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{j+1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> <mo>+</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g_{j+1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d889b057e7e432d7b9eb5d132b1ec51140a42648" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.119ex; height:2.343ex;" alt="{\displaystyle g_{j+1}}"></span> on <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |x\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |x\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/48004887d8f9dfc489bd2bc793780b7f1d8039ad" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.881ex; height:2.843ex;" alt="{\displaystyle |x\rangle }"></span>. The transition amplitude of a root-to-leaf path is the product of all the weights on the edges along the path. To get the probability of the final state being <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\psi \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>ψ</mi> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\psi \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cc27f1893b769a08cd6b296e115a29e61cab675e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.065ex; height:2.843ex;" alt="{\displaystyle |\psi \rangle }"></span>, we sum up the amplitudes of all root-to-leave paths that ends at a node representing <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\psi \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>ψ</mi> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\psi \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cc27f1893b769a08cd6b296e115a29e61cab675e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.065ex; height:2.843ex;" alt="{\displaystyle |\psi \rangle }"></span>. </p><p>More formally, for the quantum circuit <span class="texhtml mvar" style="font-style:italic;">C</span>, its sum over histories tree is a tree of depth <span class="texhtml mvar" style="font-style:italic;">m</span>, with one level for each gate <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2ce36142a0a1c6660e82bdf3ef3f1551317efe0c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.909ex; height:2.009ex;" alt="{\displaystyle g_{i}}"></span> in addition to the root, and with branching factor <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8226f30650ee4fe4e640c6d2798127e80e9c160d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}"></span>. </p> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1110004140"><div class="math_theorem" style=""> <p><strong class="theorem-name">Define</strong><span class="theoreme-tiret"> — </span>A history is a path in the sum of histories tree. We will denote a history by a sequence <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (u_{0}=|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m}=x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <msup> <mo fence="false" stretchy="false">⟩</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>⊗</mo> <mi>n</mi> </mrow> </msup> <mo stretchy="false">→</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo stretchy="false">→</mo> <mo>⋯</mo> <mo stretchy="false">→</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo stretchy="false">→</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msub> <mo>=</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (u_{0}=|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m}=x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a22423075112ec51e28cda9a1293f614116bac17" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:44.604ex; height:3.009ex;" alt="{\displaystyle (u_{0}=|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m}=x)}"></span> for some final state <span class="texhtml mvar" style="font-style:italic;">x</span>. </p> </div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1110004140"><div class="math_theorem" style=""> <p><strong class="theorem-name">Define</strong><span class="theoreme-tiret"> — </span>Let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle u,v\in \{0,1\}^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>u</mi> <mo>,</mo> <mi>v</mi> <mo>∈</mo> <mo fence="false" stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <msup> <mo fence="false" stretchy="false">}</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle u,v\in \{0,1\}^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ac51d9d04cd37aae42fa9b8f8d9da038b8a1f6f2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.234ex; height:2.843ex;" alt="{\displaystyle u,v\in \{0,1\}^{n}}"></span>. Let amplitude of the edge <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (|u\rangle ,|v\rangle )}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>u</mi> <mo fence="false" stretchy="false">⟩</mo> <mo>,</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>v</mi> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (|u\rangle ,|v\rangle )}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7c1f32af6249eb78434c3a51e504c7e9c54002f1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.404ex; height:2.843ex;" alt="{\displaystyle (|u\rangle ,|v\rangle )}"></span> in the <span class="texhtml mvar" style="font-style:italic;">j</span>-th level of the sum over histories tree be <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{j}(u\rightarrow v)=\langle v|g_{j}|u\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>α</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>u</mi> <mo stretchy="false">→</mo> <mi>v</mi> <mo stretchy="false">)</mo> <mo>=</mo> <mo fence="false" stretchy="false">⟨</mo> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>u</mi> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \alpha _{j}(u\rightarrow v)=\langle v|g_{j}|u\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b1b2a33d1442ebec6f407dd603fe0928cf0d49fc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:20.955ex; height:3.009ex;" alt="{\displaystyle \alpha _{j}(u\rightarrow v)=\langle v|g_{j}|u\rangle }"></span>. For any history <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h=(u_{0}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>h</mi> <mo>=</mo> <mo stretchy="false">(</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo stretchy="false">→</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo stretchy="false">→</mo> <mo>⋯</mo> <mo stretchy="false">→</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo stretchy="false">→</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle h=(u_{0}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3bc06318f94f1418d9652c4c6796bcf58635b164" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:36.304ex; height:2.843ex;" alt="{\displaystyle h=(u_{0}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m})}"></span>, the transition amplitude of the history is the product <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{h}=\alpha _{1}(|0\rangle ^{\otimes n}\rightarrow u_{1})\alpha _{2}(u_{1}\rightarrow u_{2})\cdots \alpha _{m}(u_{m-1}\rightarrow x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>α</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>h</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>α</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <msup> <mo fence="false" stretchy="false">⟩</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>⊗</mo> <mi>n</mi> </mrow> </msup> <mo stretchy="false">→</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo stretchy="false">)</mo> <msub> <mi>α</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo stretchy="false">(</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo stretchy="false">→</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo stretchy="false">)</mo> <mo>⋯</mo> <msub> <mi>α</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msub> <mo stretchy="false">(</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo stretchy="false">→</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \alpha _{h}=\alpha _{1}(|0\rangle ^{\otimes n}\rightarrow u_{1})\alpha _{2}(u_{1}\rightarrow u_{2})\cdots \alpha _{m}(u_{m-1}\rightarrow x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4b4f18d81c82622e492d9efaa34967c06a2ebddc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:52.577ex; height:3.009ex;" alt="{\displaystyle \alpha _{h}=\alpha _{1}(|0\rangle ^{\otimes n}\rightarrow u_{1})\alpha _{2}(u_{1}\rightarrow u_{2})\cdots \alpha _{m}(u_{m-1}\rightarrow x)}"></span>. </p> </div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1110004140"><div class="math_theorem" style=""> <p><strong class="theorem-name">Claim</strong><span class="theoreme-tiret"> — </span>For a history <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (u_{0}\rightarrow \cdots \rightarrow u_{m})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo stretchy="false">→</mo> <mo>⋯</mo> <mo stretchy="false">→</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msub> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (u_{0}\rightarrow \cdots \rightarrow u_{m})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bb8b0fcb225d60a42711afcf5bd62589d15f7e1c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.149ex; height:2.843ex;" alt="{\displaystyle (u_{0}\rightarrow \cdots \rightarrow u_{m})}"></span> . The transition amplitude of the history is computable in polynomial time. </p> </div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1174254338"><div class="math_proof" style=""><strong>Proof</strong> <p>Each gate <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{j}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g_{j}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ccc0c1f707e4786c1121db1ba0a608fe85a94e2d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.019ex; height:2.343ex;" alt="{\displaystyle g_{j}}"></span> can be decomposed into <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{j}=I\otimes {\tilde {g}}_{j}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mo>=</mo> <mi>I</mi> <mo>⊗</mo> <msub> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>g</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g_{j}=I\otimes {\tilde {g}}_{j}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/84df430d51749d0f68bde4d257510bf5a2e4b47e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:11.271ex; height:3.009ex;" alt="{\displaystyle g_{j}=I\otimes {\tilde {g}}_{j}}"></span> for some unitary operator <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tilde {g}}_{j}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>g</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\tilde {g}}_{j}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/23e1670dac52394155872fd544f5751b0cf37b03" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:2.141ex; height:3.009ex;" alt="{\displaystyle {\tilde {g}}_{j}}"></span> acting on two qubits, which without loss of generality can be taken to be the first two. Hence, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⟨</mo> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>u</mi> <mo fence="false" stretchy="false">⟩</mo> <mo>=</mo> <mo fence="false" stretchy="false">⟨</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>g</mi> <mo stretchy="false">~</mo> </mover> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo fence="false" stretchy="false">⟩</mo> <mo fence="false" stretchy="false">⟨</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>v</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> <mo>,</mo> <mo>⋯</mo> <mo>,</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dad14da0af7f63352d2a4ebd5dc8a136e141c6a5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:49.394ex; height:3.176ex;" alt="{\displaystyle \langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle }"></span> which can be computed in polynomial time in <span class="texhtml mvar" style="font-style:italic;">n</span>. Since <span class="texhtml mvar" style="font-style:italic;">m</span> is polynomial in <span class="texhtml mvar" style="font-style:italic;">n</span>, the transition amplitude of the history can be computed in polynomial time. </p> </div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1110004140"><div class="math_theorem" style=""> <p><strong class="theorem-name">Claim</strong><span class="theoreme-tiret"> — </span>Let <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <msup> <mo fence="false" stretchy="false">⟩</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>⊗</mo> <mi>n</mi> </mrow> </msup> <mo>=</mo> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> <mo>∈</mo> <mo fence="false" stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <msup> <mo fence="false" stretchy="false">}</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mrow> </munder> <msub> <mi>α</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/10c190672a26bfbdc8de851c556ddb029c816ee4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.671ex; width:22.751ex; height:6.176ex;" alt="{\displaystyle C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle }"></span> be the final state of the quantum circuit. For some <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \{0,1\}^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>∈</mo> <mo fence="false" stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <msup> <mo fence="false" stretchy="false">}</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x\in \{0,1\}^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a2fe5fa2f2f1720e40e59457a01bb8bf14e0e4fc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.073ex; height:2.843ex;" alt="{\displaystyle x\in \{0,1\}^{n}}"></span>, the amplitude <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{x}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>α</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \alpha _{x}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6a6aea4f482cc815dc367ff2686b84188beb9ea0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.66ex; height:2.009ex;" alt="{\displaystyle \alpha _{x}}"></span> can be computed by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>α</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> </mrow> </msub> <mo>=</mo> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>h</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <msup> <mo fence="false" stretchy="false">⟩</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>⊗</mo> <mi>n</mi> </mrow> </msup> <mo stretchy="false">→</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo stretchy="false">→</mo> <mo>⋯</mo> <mo stretchy="false">→</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo stretchy="false">→</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">)</mo> </mrow> </munder> <msub> <mi>α</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>h</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/07c3d0c8bcd5f582df2644cc65d7590643e1c14c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.838ex; width:31.838ex; height:6.343ex;" alt="{\displaystyle \alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}}"></span>. </p> </div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1174254338"><div class="math_proof" style=""><strong>Proof</strong> <p>We have <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>α</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> </mrow> </msub> <mo>=</mo> <mo fence="false" stretchy="false">⟨</mo> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <msup> <mo fence="false" stretchy="false">⟩</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>⊗</mo> <mi>n</mi> </mrow> </msup> <mo>=</mo> <mo fence="false" stretchy="false">⟨</mo> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> </mrow> </msub> <msub> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo>⋯</mo> <msub> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>C</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <msup> <mo fence="false" stretchy="false">⟩</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>⊗</mo> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6d46b582f4764dc69a05a535982a3daa3cd5dc7a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:40.852ex; height:3.009ex;" alt="{\displaystyle \alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}}"></span>. The result comes directly by inserting <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle I=\sum _{x\in \{0,1\}^{n}}|x\rangle \langle x|}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>I</mi> <mo>=</mo> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> <mo>∈</mo> <mo fence="false" stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <msup> <mo fence="false" stretchy="false">}</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mrow> </munder> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mo fence="false" stretchy="false">⟩</mo> <mo fence="false" stretchy="false">⟨</mo> <mi>x</mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle I=\sum _{x\in \{0,1\}^{n}}|x\rangle \langle x|}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e05b9e53166c2dd0d6d789b8eb21cee641cf8c87" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.671ex; width:17.166ex; height:6.176ex;" alt="{\displaystyle I=\sum _{x\in \{0,1\}^{n}}|x\rangle \langle x|}"></span> between <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{1},g_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g_{1},g_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/85e39b0b718144602bbf108d7ee37c3c65b1de72" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.36ex; height:2.009ex;" alt="{\displaystyle g_{1},g_{2}}"></span>, and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g_{2},g_{3}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>,</mo> <msub> <mi>g</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle g_{2},g_{3}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8b93bd08c229189afed60922347240293f9c903b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.36ex; height:2.009ex;" alt="{\displaystyle g_{2},g_{3}}"></span>, and so on, and then expand out the equation. Then each term corresponds to a <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{h}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>α</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>h</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \alpha _{h}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/beed7cd911d8bb76ecc6aa86918bd52c426f9e00" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.667ex; height:2.009ex;" alt="{\displaystyle \alpha _{h}}"></span>, where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>h</mi> <mo>=</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <msup> <mo fence="false" stretchy="false">⟩</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>⊗</mo> <mi>n</mi> </mrow> </msup> <mo stretchy="false">→</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo stretchy="false">→</mo> <mo>⋯</mo> <mo stretchy="false">→</mo> <msub> <mi>u</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>t</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <mo stretchy="false">→</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3b414a17fad84cbe6d8edcc571cae9e9bb7e8bf3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:38.158ex; height:3.009ex;" alt="{\displaystyle h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}"></span> </p> </div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1110004140"><div class="math_theorem" style=""> <p><strong class="theorem-name">Claim</strong><span class="theoreme-tiret"> — </span><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {PSPACE}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtext>APPROX-QCIRCUIT-PROB</mtext> </mrow> <mo>∈</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">S</mi> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">A</mi> <mi mathvariant="sans-serif">C</mi> <mi mathvariant="sans-serif">E</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {PSPACE}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f791a34c96c594143c43bf8c7c3e65b769e402a1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:41.969ex; height:2.509ex;" alt="{\displaystyle {\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {PSPACE}}}"></span> </p> </div> <p>Notice in the sum over histories algorithm to compute some amplitude <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{x}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>α</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \alpha _{x}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6a6aea4f482cc815dc367ff2686b84188beb9ea0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.66ex; height:2.009ex;" alt="{\displaystyle \alpha _{x}}"></span>, only one history is stored at any point in the computation. Hence, the sum over histories algorithm uses <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(nm)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>m</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(nm)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/051245e657739f572fe7902c817ea9103c687fb7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.018ex; height:2.843ex;" alt="{\displaystyle O(nm)}"></span> space to compute <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \alpha _{x}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>α</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \alpha _{x}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6a6aea4f482cc815dc367ff2686b84188beb9ea0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.66ex; height:2.009ex;" alt="{\displaystyle \alpha _{x}}"></span> for any <span class="texhtml mvar" style="font-style:italic;">x</span> since <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(nm)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>n</mi> <mi>m</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(nm)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/051245e657739f572fe7902c817ea9103c687fb7" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.018ex; height:2.843ex;" alt="{\displaystyle O(nm)}"></span> bits are needed to store the histories in addition to some workspace variables. </p><p>Therefore, in polynomial space, we may compute <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sum _{x}|\alpha _{x}|^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> </mrow> </munder> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <msub> <mi>α</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> </mrow> </msub> <msup> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \sum _{x}|\alpha _{x}|^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8e7d6436f3a527009e30d7cbcda27edd4178d8fc" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:8.75ex; height:5.509ex;" alt="{\displaystyle \sum _{x}|\alpha _{x}|^{2}}"></span> over all <span class="texhtml mvar" style="font-style:italic;">x</span> with the first qubit being <span class="nowrap"><span data-sort-value="7000100000000000000♠"></span>1</span>, which is the probability that the first qubit is measured to be 1 by the end of the circuit. </p><p>Notice that compared with the simulation given for the proof that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {EXP}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">B</mi> <mi mathvariant="sans-serif">Q</mi> <mi mathvariant="sans-serif">P</mi> </mrow> </mrow> <mo>⊆</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">E</mi> <mi mathvariant="sans-serif">X</mi> <mi mathvariant="sans-serif">P</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {EXP}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5ed327e10a44b809e63b8bd3ef392b27e6312285" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:12.268ex; height:2.343ex;" alt="{\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {EXP}}}"></span>, our algorithm here takes far less space but far more time instead. In fact it takes <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(m\cdot 2^{mn})}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>m</mi> <mo>⋅</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mi>n</mi> </mrow> </msup> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(m\cdot 2^{mn})}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a3ddc36a4315f6255d8c0976a21d52d7fd096f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.126ex; height:2.843ex;" alt="{\displaystyle O(m\cdot 2^{mn})}"></span> time to calculate a single amplitude! </p> <div class="mw-heading mw-heading3"><h3 id="BQP_and_PP">BQP and PP</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=BQP&action=edit&section=7" title="Edit section: BQP and PP"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A similar sum-over-histories argument can be used to show that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {PP}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">B</mi> <mi mathvariant="sans-serif">Q</mi> <mi mathvariant="sans-serif">P</mi> </mrow> </mrow> <mo>⊆</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">P</mi> <mi mathvariant="sans-serif">P</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {PP}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f629f3ff84729a116e376cc2e2975fbd9c962743" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.815ex; height:2.343ex;" alt="{\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {PP}}}"></span>. <sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="P_and_BQP">P and BQP <span class="anchor" id="BQP,_P,_and_NP"></span></h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=BQP&action=edit&section=8" title="Edit section: P and BQP"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>We know <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathsf {P}}\subseteq {\mathsf {BQP}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">P</mi> </mrow> </mrow> <mo>⊆</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="sans-serif">B</mi> <mi mathvariant="sans-serif">Q</mi> <mi mathvariant="sans-serif">P</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathsf {P}}\subseteq {\mathsf {BQP}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bf51a8b1b66a9079ea02cfbca041b945823fba79" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.33ex; height:2.343ex;" alt="{\displaystyle {\mathsf {P}}\subseteq {\mathsf {BQP}}}"></span>, since every classical circuit can be simulated by a quantum circuit. <sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> </p><p>It is conjectured that BQP solves hard problems outside of P, specifically, problems in NP. The claim is indefinite because we don't know if P=NP, so we don't know if those problems are actually in P. Below are some evidence of the conjecture: </p> <ul><li><a href="/wiki/Integer_factorization" title="Integer factorization">Integer factorization</a> (see <a href="/wiki/Shor%27s_algorithm" title="Shor's algorithm">Shor's algorithm</a>)<sup id="cite_ref-Shor_16-0" class="reference"><a href="#cite_note-Shor-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup></li> <li><a href="/wiki/Discrete_logarithm" title="Discrete logarithm">Discrete logarithm</a><sup id="cite_ref-Shor_16-1" class="reference"><a href="#cite_note-Shor-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup></li> <li>Simulation of quantum systems (see <a href="/wiki/Universal_quantum_simulator" class="mw-redirect" title="Universal quantum simulator">universal quantum simulator</a>)</li> <li>Approximating the <a href="/wiki/Jones_polynomial" title="Jones polynomial">Jones polynomial</a> at certain roots of unity</li> <li><a href="/wiki/HHL_algorithm" title="HHL algorithm">Harrow-Hassidim-Lloyd (HHL) algorithm</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=BQP&action=edit&section=9" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Hidden_subgroup_problem" title="Hidden subgroup problem">Hidden subgroup problem</a></li> <li><a href="/wiki/Polynomial_hierarchy" title="Polynomial hierarchy">Polynomial hierarchy</a> (PH)</li> <li><a href="/wiki/Quantum_complexity_theory" title="Quantum complexity theory">Quantum complexity theory</a></li> <li><b><a href="/wiki/QMA" title="QMA">QMA</a></b>, the quantum equivalent to <b><a href="/wiki/NP_(complexity)" title="NP (complexity)">NP</a></b>.</li> <li><a href="/wiki/QIP_(complexity)" title="QIP (complexity)">QIP</a>, the quantum equivalent to <a href="/wiki/IP_(complexity)" title="IP (complexity)">IP.</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=BQP&action=edit&section=10" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap mw-references-columns"><ol class="references"> <li id="cite_note-Chuang2000-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-Chuang2000_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Chuang2000_1-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-Chuang2000_1-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text">Michael Nielsen and Isaac Chuang (2000). <i>Quantum Computation and Quantum Information</i>. Cambridge: Cambridge University Press. <style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-521-63503-9" title="Special:BookSources/0-521-63503-9">0-521-63503-9</a>.</span> </li> <li id="cite_note-BernVazi-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-BernVazi_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-BernVazi_2-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-BernVazi_2-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-BernVazi_2-3"><sup><i><b>d</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="BernVazi" class="citation journal cs1">Bernstein, Ethan; Vazirani, Umesh (October 1997). "Quantum Complexity Theory". <i>SIAM Journal on Computing</i>. <b>26</b> (5): 1411–1473. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.655.1186">10.1.1.655.1186</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0097539796300921">10.1137/S0097539796300921</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=Quantum+Complexity+Theory&rft.volume=26&rft.issue=5&rft.pages=1411-1473&rft.date=1997-10&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.655.1186%23id-name%3DCiteSeerX&rft_id=info%3Adoi%2F10.1137%2FS0097539796300921&rft.aulast=Bernstein&rft.aufirst=Ethan&rft.au=Vazirani%2C+Umesh&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABQP" class="Z3988"></span></span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBarak2009" class="citation book cs1">Barak, Sanjeev Arora, Boaz (2009). <a rel="nofollow" class="external text" href="https://www.cs.princeton.edu/theory/complexity/"><i>Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak</i></a>. Cambridge. p. 122<span class="reference-accessdate">. Retrieved <span class="nowrap">24 July</span> 2018</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Computational+Complexity%3A+A+Modern+Approach+%2F+Sanjeev+Arora+and+Boaz+Barak&rft.place=Cambridge&rft.pages=122&rft.date=2009&rft.aulast=Barak&rft.aufirst=Sanjeev+Arora%2C+Boaz&rft_id=https%3A%2F%2Fwww.cs.princeton.edu%2Ftheory%2Fcomplexity%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABQP" class="Z3988"></span><span class="cs1-maint citation-comment"><code class="cs1-code">{{<a href="/wiki/Template:Cite_book" title="Template:Cite book">cite book</a>}}</code>: CS1 maint: location missing publisher (<a href="/wiki/Category:CS1_maint:_location_missing_publisher" title="Category:CS1 maint: location missing publisher">link</a>) CS1 maint: multiple names: authors list (<a href="/wiki/Category:CS1_maint:_multiple_names:_authors_list" title="Category:CS1 maint: multiple names: authors list">link</a>)</span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFortnowRogers1999" class="citation journal cs1">Fortnow, Lance; Rogers, John (1999). <a rel="nofollow" class="external text" href="http://people.cs.uchicago.edu/~fortnow/papers/quantum.pdf">"Complexity limitations on Quantum computation"</a> <span class="cs1-format">(PDF)</span>. <i>J. Comput. Syst. Sci</i>. <b>59</b> (2): 240–252. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs/9811023">cs/9811023</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fjcss.1999.1651">10.1006/jcss.1999.1651</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0022-0000">0022-0000</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:42516312">42516312</a>. <a rel="nofollow" class="external text" href="https://ghostarchive.org/archive/20221009/http://people.cs.uchicago.edu/~fortnow/papers/quantum.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2022-10-09.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=J.+Comput.+Syst.+Sci.&rft.atitle=Complexity+limitations+on+Quantum+computation&rft.volume=59&rft.issue=2&rft.pages=240-252&rft.date=1999&rft_id=info%3Aarxiv%2Fcs%2F9811023&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A42516312%23id-name%3DS2CID&rft.issn=0022-0000&rft_id=info%3Adoi%2F10.1006%2Fjcss.1999.1651&rft.aulast=Fortnow&rft.aufirst=Lance&rft.au=Rogers%2C+John&rft_id=http%3A%2F%2Fpeople.cs.uchicago.edu%2F~fortnow%2Fpapers%2Fquantum.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABQP" class="Z3988"></span></span> </li> <li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text">L. Adleman, J. DeMarrais, and M.-D. Huang. Quantum computability. SIAM J. Comput., 26(5):1524–1540, 1997.</span> </li> <li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGeorge" class="citation web cs1">George, Michael Goderbauer, Stefan. <a rel="nofollow" class="external text" href="https://eccc.weizmann.ac.il/report/2018/107/">"ECCC - TR18-107"</a>. <i>eccc.weizmann.ac.il</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2018-08-03</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=eccc.weizmann.ac.il&rft.atitle=ECCC+-+TR18-107&rft.aulast=George&rft.aufirst=Michael+Goderbauer%2C+Stefan&rft_id=https%3A%2F%2Feccc.weizmann.ac.il%2Freport%2F2018%2F107%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABQP" class="Z3988"></span><span class="cs1-maint citation-comment"><code class="cs1-code">{{<a href="/wiki/Template:Cite_web" title="Template:Cite web">cite web</a>}}</code>: CS1 maint: multiple names: authors list (<a href="/wiki/Category:CS1_maint:_multiple_names:_authors_list" title="Category:CS1 maint: multiple names: authors list">link</a>)</span></span> </li> <li id="cite_note-:0-7"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_7-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_7-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAaronson2010" class="citation journal cs1">Aaronson, Scott (2010). <a rel="nofollow" class="external text" href="https://www.scottaaronson.com/papers/bqpph.pdf">"BQP and the Polynomial Hierarchy"</a> <span class="cs1-format">(PDF)</span>. <i>Proceedings of ACM STOC 2010</i>. <a rel="nofollow" class="external text" href="https://ghostarchive.org/archive/20221009/https://www.scottaaronson.com/papers/bqpph.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2022-10-09.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Proceedings+of+ACM+STOC+2010&rft.atitle=BQP+and+the+Polynomial+Hierarchy&rft.date=2010&rft.aulast=Aaronson&rft.aufirst=Scott&rft_id=https%3A%2F%2Fwww.scottaaronson.com%2Fpapers%2Fbqpph.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABQP" class="Z3988"></span></span> </li> <li id="cite_note-PostBQP=PP-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-PostBQP=PP_8-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAaronson2005" class="citation journal cs1">Aaronson, Scott (2005). "Quantum computing, postselection, and probabilistic polynomial-time". <i>Proceedings of the Royal Society A</i>. <b>461</b> (2063): 3473–3482. <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/0412187">quant-ph/0412187</a></span>. <a href="/wiki/Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2005RSPSA.461.3473A">2005RSPSA.461.3473A</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1098%2Frspa.2005.1546">10.1098/rspa.2005.1546</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1770389">1770389</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Proceedings+of+the+Royal+Society+A&rft.atitle=Quantum+computing%2C+postselection%2C+and+probabilistic+polynomial-time&rft.volume=461&rft.issue=2063&rft.pages=3473-3482&rft.date=2005&rft_id=info%3Aarxiv%2Fquant-ph%2F0412187&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A1770389%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1098%2Frspa.2005.1546&rft_id=info%3Abibcode%2F2005RSPSA.461.3473A&rft.aulast=Aaronson&rft.aufirst=Scott&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABQP" class="Z3988"></span>. Preprint available at <a rel="nofollow" class="external autonumber" href="https://arxiv.org/abs/quant-ph/0412187">[1]</a></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAaronson2004" class="citation web cs1">Aaronson, Scott (2004-01-11). <a rel="nofollow" class="external text" href="http://weblog.fortnow.com/2004/01/complexity-class-of-week-pp-by-guest.html">"Complexity Class of the Week: PP"</a>. <i>Computational Complexity Weblog</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2008-05-02</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=Computational+Complexity+Weblog&rft.atitle=Complexity+Class+of+the+Week%3A+PP&rft.date=2004-01-11&rft.aulast=Aaronson&rft.aufirst=Scott&rft_id=http%3A%2F%2Fweblog.fortnow.com%2F2004%2F01%2Fcomplexity-class-of-week-pp-by-guest.html&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABQP" class="Z3988"></span></span> </li> <li id="cite_note-janzing-wocjan-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-janzing-wocjan_10-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFJanzingWocjan2007" class="citation journal cs1">Janzing, Dominik; Wocjan, Pawel (2007-03-30). <a rel="nofollow" class="external text" href="https://theoryofcomputing.org/articles/v003a004/v003a004.pdf">"A Simple PromiseBQP-complete Matrix Problem"</a> <span class="cs1-format">(PDF)</span>. <i>Theory of Computing</i>. <b>3</b> (4): 61–79. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4086%2Ftoc.2007.v003a004">10.4086/toc.2007.v003a004</a><span class="reference-accessdate">. Retrieved <span class="nowrap">2024-04-18</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Theory+of+Computing&rft.atitle=A+Simple+PromiseBQP-complete+Matrix+Problem&rft.volume=3&rft.issue=4&rft.pages=61-79&rft.date=2007-03-30&rft_id=info%3Adoi%2F10.4086%2Ftoc.2007.v003a004&rft.aulast=Janzing&rft.aufirst=Dominik&rft.au=Wocjan%2C+Pawel&rft_id=https%3A%2F%2Ftheoryofcomputing.org%2Farticles%2Fv003a004%2Fv003a004.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABQP" class="Z3988"></span></span> </li> <li id="cite_note-NielsenChuang2010-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-NielsenChuang2010_11-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMichael_A._NielsenIsaac_L._Chuang2010" class="citation book cs1">Michael A. Nielsen; Isaac L. Chuang (9 December 2010). "4.4 Measurement". <a rel="nofollow" class="external text" href="https://books.google.com/books?id=-s4DEy7o-a0C"><i>Quantum Computation and Quantum Information: 10th Anniversary Edition</i></a>. Cambridge University Press. p. 186. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-139-49548-6" title="Special:BookSources/978-1-139-49548-6"><bdi>978-1-139-49548-6</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=4.4+Measurement&rft.btitle=Quantum+Computation+and+Quantum+Information%3A+10th+Anniversary+Edition&rft.pages=186&rft.pub=Cambridge+University+Press&rft.date=2010-12-09&rft.isbn=978-1-139-49548-6&rft.au=Michael+A.+Nielsen&rft.au=Isaac+L.+Chuang&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3D-s4DEy7o-a0C&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABQP" class="Z3988"></span></span> </li> <li id="cite_note-Cross2012-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-Cross2012_12-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFOdel_A._Cross2012" class="citation book cs1">Odel A. Cross (5 November 2012). "5.2.2 Deferred Measurement". <a rel="nofollow" class="external text" href="https://books.google.com/books?id=b_D9flK2h8QC&pg=PA348"><i>Topics in Quantum Computing</i></a>. O. A. Cross. p. 348. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4800-2749-7" title="Special:BookSources/978-1-4800-2749-7"><bdi>978-1-4800-2749-7</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=5.2.2+Deferred+Measurement&rft.btitle=Topics+in+Quantum+Computing&rft.pages=348&rft.pub=O.+A.+Cross&rft.date=2012-11-05&rft.isbn=978-1-4800-2749-7&rft.au=Odel+A.+Cross&rft_id=https%3A%2F%2Fbooks.google.com%2Fbooks%3Fid%3Db_D9flK2h8QC%26pg%3DPA348&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABQP" class="Z3988"></span></span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text">E. Bernstein and U. Vazirani. Quantum complexity theory, SIAM Journal on Computing, 26(5):1411-1473, 1997.</span> </li> <li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"> L. Adleman, J. DeMarrais, and M. Huang. Quantum computability, SIAM Journal on Comput- ing 26:1524-1540, 1997.</span> </li> <li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"> Nielsen, Michael A.; Chuang, Isaac L. (2000), Quantum Computation and Quantum Information, Cambridge: Cambridge University Press, ISBN 0-521-63235-8, MR 1796805.</span> </li> <li id="cite_note-Shor-16"><span class="mw-cite-backlink">^ <a href="#cite_ref-Shor_16-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Shor_16-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://www.arxiv.org/abs/quant-ph/9508027">arXiv:quant-ph/9508027v2 <i>Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer</i>, Peter W. Shor</a></span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=BQP&action=edit&section=11" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bqp">Complexity Zoo link to BQP</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20130603134129/https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#bqp">Archived</a> 2013-06-03 at the <a href="/wiki/Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Quantum_information_science" style="padding:3px"><table class="nowraplinks hlist mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Quantum_information" title="Template:Quantum information"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Quantum_information" title="Template talk:Quantum information"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Quantum_information" title="Special:EditPage/Template:Quantum information"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Quantum_information_science" style="font-size:114%;margin:0 4em"><a href="/wiki/Quantum_information_science" title="Quantum information science">Quantum information science</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/DiVincenzo%27s_criteria" title="DiVincenzo's criteria">DiVincenzo's criteria</a></li> <li><a href="/wiki/Noisy_intermediate-scale_quantum_era" title="Noisy intermediate-scale quantum era">NISQ era</a></li> <li><a href="/wiki/Quantum_computing" title="Quantum computing">Quantum computing</a> <ul><li><a href="/wiki/Timeline_of_quantum_computing_and_communication" title="Timeline of quantum computing and communication">timeline</a></li></ul></li> <li><a href="/wiki/Quantum_information" title="Quantum information">Quantum information</a></li> <li><a href="/wiki/Quantum_programming" title="Quantum programming">Quantum programming</a></li> <li><a href="/wiki/Quantum_simulator" title="Quantum simulator">Quantum simulation</a></li> <li><a href="/wiki/Qubit" title="Qubit">Qubit</a> <ul><li><a href="/wiki/Physical_and_logical_qubits" title="Physical and logical qubits">physical vs. logical</a></li></ul></li> <li><a href="/wiki/List_of_quantum_processors" title="List of quantum processors">Quantum processors</a> <ul><li><a href="/wiki/Cloud-based_quantum_computing" title="Cloud-based quantum computing">cloud-based</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theorems</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Bell%27s_theorem" title="Bell's theorem">Bell's</a></li> <li><a href="/wiki/Eastin%E2%80%93Knill_theorem" title="Eastin–Knill theorem">Eastin–Knill</a></li> <li><a href="/wiki/Gleason%27s_theorem" title="Gleason's theorem">Gleason's</a></li> <li><a href="/wiki/Gottesman%E2%80%93Knill_theorem" title="Gottesman–Knill theorem">Gottesman–Knill</a></li> <li><a href="/wiki/Holevo%27s_theorem" title="Holevo's theorem">Holevo's</a></li> <li><a href="/wiki/No-broadcasting_theorem" title="No-broadcasting theorem">No-broadcasting</a></li> <li><a href="/wiki/No-cloning_theorem" title="No-cloning theorem">No-cloning</a></li> <li><a href="/wiki/No-communication_theorem" title="No-communication theorem">No-communication</a></li> <li><a href="/wiki/No-deleting_theorem" title="No-deleting theorem">No-deleting</a></li> <li><a href="/wiki/No-hiding_theorem" title="No-hiding theorem">No-hiding</a></li> <li><a href="/wiki/No-teleportation_theorem" title="No-teleportation theorem">No-teleportation</a></li> <li><a href="/wiki/PBR_theorem" class="mw-redirect" title="PBR theorem">PBR</a></li> <li><a href="/wiki/Quantum_speed_limit_theorems" class="mw-redirect" title="Quantum speed limit theorems">Quantum speed limit</a></li> <li><a href="/wiki/Threshold_theorem" title="Threshold theorem">Threshold</a></li> <li><a href="/wiki/Solovay%E2%80%93Kitaev_theorem" title="Solovay–Kitaev theorem">Solovay–Kitaev</a></li> <li><a href="/wiki/Schr%C3%B6dinger%E2%80%93HJW_theorem" title="Schrödinger–HJW theorem">Purification</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Quantum<br />communication</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Classical_capacity" title="Classical capacity">Classical capacity</a> <ul><li><a href="/wiki/Entanglement-assisted_classical_capacity" title="Entanglement-assisted classical capacity">entanglement-assisted</a></li> <li><a href="/wiki/Quantum_capacity" title="Quantum capacity">quantum capacity</a></li></ul></li> <li><a href="/wiki/Entanglement_distillation" title="Entanglement distillation">Entanglement distillation</a></li> <li><a href="/wiki/Monogamy_of_entanglement" title="Monogamy of entanglement">Monogamy of entanglement</a></li> <li><a href="/wiki/LOCC" title="LOCC">LOCC</a></li> <li><a href="/wiki/Quantum_channel" title="Quantum channel">Quantum channel</a> <ul><li><a href="/wiki/Quantum_network" title="Quantum network">quantum network</a></li></ul></li> <li><a href="/wiki/Quantum_teleportation" title="Quantum teleportation">Quantum teleportation</a> <ul><li><a href="/wiki/Quantum_gate_teleportation" title="Quantum gate teleportation">quantum gate teleportation</a></li></ul></li> <li><a href="/wiki/Superdense_coding" title="Superdense coding">Superdense coding</a></li></ul> </div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Quantum_cryptography" scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Quantum_cryptography" title="Quantum cryptography">Quantum cryptography</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Post-quantum_cryptography" title="Post-quantum cryptography">Post-quantum cryptography</a></li> <li><a href="/wiki/Quantum_coin_flipping" title="Quantum coin flipping">Quantum coin flipping</a></li> <li><a href="/wiki/Quantum_money" title="Quantum money">Quantum money</a></li> <li><a href="/wiki/Quantum_key_distribution" title="Quantum key distribution">Quantum key distribution</a> <ul><li><a href="/wiki/BB84" title="BB84">BB84</a></li> <li><a href="/wiki/SARG04" title="SARG04">SARG04</a></li> <li><a href="/wiki/List_of_quantum_key_distribution_protocols" title="List of quantum key distribution protocols">other protocols</a></li></ul></li> <li><a href="/wiki/Quantum_secret_sharing" title="Quantum secret sharing">Quantum secret sharing</a></li></ul> </div></td></tr></tbody></table><div> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Quantum_algorithm" title="Quantum algorithm">Quantum algorithms</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Amplitude_amplification" title="Amplitude amplification">Amplitude amplification</a></li> <li><a href="/wiki/Bernstein%E2%80%93Vazirani_algorithm" title="Bernstein–Vazirani algorithm">Bernstein–Vazirani</a></li> <li><a href="/wiki/BHT_algorithm" title="BHT algorithm">BHT</a></li> <li><a href="/wiki/Boson_sampling" title="Boson sampling">Boson sampling</a></li> <li><a href="/wiki/Deutsch%E2%80%93Jozsa_algorithm" title="Deutsch–Jozsa algorithm">Deutsch–Jozsa</a></li> <li><a href="/wiki/Grover%27s_algorithm" title="Grover's algorithm">Grover's</a></li> <li><a href="/wiki/HHL_algorithm" title="HHL algorithm">HHL</a></li> <li><a href="/wiki/Hidden_subgroup_problem" title="Hidden subgroup problem">Hidden subgroup</a></li> <li><a href="/wiki/Quantum_annealing" title="Quantum annealing">Quantum annealing</a></li> <li><a href="/wiki/Quantum_counting_algorithm" title="Quantum counting algorithm">Quantum counting</a></li> <li><a href="/wiki/Quantum_Fourier_transform" title="Quantum Fourier transform">Quantum Fourier transform</a></li> <li><a href="/wiki/Quantum_optimization_algorithms" title="Quantum optimization algorithms">Quantum optimization</a></li> <li><a href="/wiki/Quantum_phase_estimation_algorithm" title="Quantum phase estimation algorithm">Quantum phase estimation</a></li> <li><a href="/wiki/Shor%27s_algorithm" title="Shor's algorithm">Shor's</a></li> <li><a href="/wiki/Simon%27s_problem" title="Simon's problem">Simon's</a></li> <li><a href="/wiki/Variational_quantum_eigensolver" title="Variational quantum eigensolver">VQE</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Quantum_complexity_theory" title="Quantum complexity theory">Quantum<br />complexity theory</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a class="mw-selflink selflink">BQP</a></li> <li><a href="/wiki/Exact_quantum_polynomial_time" title="Exact quantum polynomial time">EQP</a></li> <li><a href="/wiki/QIP_(complexity)" title="QIP (complexity)">QIP</a></li> <li><a href="/wiki/QMA" title="QMA">QMA</a></li> <li><a href="/wiki/PostBQP" title="PostBQP">PostBQP</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Quantum <br /> processor benchmarks</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Quantum_supremacy" title="Quantum supremacy">Quantum supremacy</a></li> <li><a href="/wiki/Quantum_volume" title="Quantum volume">Quantum volume</a></li> <li><a href="/wiki/Randomized_benchmarking" title="Randomized benchmarking">Randomized benchmarking</a> <ul><li><a href="/wiki/Cross-entropy_benchmarking" title="Cross-entropy benchmarking">XEB</a></li></ul></li> <li><a href="/wiki/Relaxation_(NMR)" title="Relaxation (NMR)">Relaxation times</a> <ul><li><a href="/wiki/Spin%E2%80%93lattice_relaxation" title="Spin–lattice relaxation"><i>T</i><sub>1</sub></a></li> <li><a href="/wiki/Spin%E2%80%93spin_relaxation" title="Spin–spin relaxation"><i>T</i><sub>2</sub></a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Quantum<br /><a href="/wiki/Model_of_computation" title="Model of computation">computing models</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Adiabatic_quantum_computation" title="Adiabatic quantum computation">Adiabatic quantum computation</a></li> <li><a href="/wiki/Continuous-variable_quantum_information" title="Continuous-variable quantum information">Continuous-variable quantum information</a></li> <li><a href="/wiki/One-way_quantum_computer" title="One-way quantum computer">One-way quantum computer</a> <ul><li><a href="/wiki/Cluster_state" title="Cluster state">cluster state</a></li></ul></li> <li><a href="/wiki/Quantum_circuit" title="Quantum circuit">Quantum circuit</a> <ul><li><a href="/wiki/Quantum_logic_gate" title="Quantum logic gate">quantum logic gate</a></li></ul></li> <li><a href="/wiki/Quantum_machine_learning" title="Quantum machine learning">Quantum machine learning</a> <ul><li><a href="/wiki/Quantum_neural_network" title="Quantum neural network">quantum neural network</a></li></ul></li> <li><a href="/wiki/Quantum_Turing_machine" title="Quantum Turing machine">Quantum Turing machine</a></li> <li><a href="/wiki/Topological_quantum_computer" title="Topological quantum computer">Topological quantum computer</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Quantum_error_correction" title="Quantum error correction">Quantum<br />error correction</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li>Codes <ul><li><a href="/wiki/CSS_code" title="CSS code">CSS</a></li> <li><a href="/wiki/Quantum_convolutional_code" title="Quantum convolutional code">quantum convolutional</a></li> <li><a href="/wiki/Stabilizer_code" title="Stabilizer code">stabilizer</a></li> <li><a href="/wiki/Shor_code" class="mw-redirect" title="Shor code">Shor</a></li> <li><a href="/wiki/Bacon%E2%80%93Shor_code" title="Bacon–Shor code">Bacon–Shor</a></li> <li><a href="/wiki/Steane_code" title="Steane code">Steane</a></li> <li><a href="/wiki/Toric_code" title="Toric code">Toric</a></li> <li><a href="/wiki/Gnu_code" title="Gnu code"><i>gnu</i></a></li></ul></li> <li><a href="/wiki/Entanglement-assisted_stabilizer_formalism" title="Entanglement-assisted stabilizer formalism">Entanglement-assisted</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Physical<br />implementations</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Quantum_optics" title="Quantum optics">Quantum optics</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Cavity_quantum_electrodynamics" title="Cavity quantum electrodynamics">Cavity QED</a></li> <li><a href="/wiki/Circuit_quantum_electrodynamics" title="Circuit quantum electrodynamics">Circuit QED</a></li> <li><a href="/wiki/Linear_optical_quantum_computing" title="Linear optical quantum computing">Linear optical QC</a></li> <li><a href="/wiki/KLM_protocol" title="KLM protocol">KLM protocol</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Ultracold_atom" title="Ultracold atom">Ultracold atoms</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Neutral_atom_quantum_computer" title="Neutral atom quantum computer">Neutral atom QC</a></li> <li><a href="/wiki/Trapped-ion_quantum_computer" title="Trapped-ion quantum computer">Trapped-ion QC</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Spin_(physics)" title="Spin (physics)">Spin</a>-based</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Kane_quantum_computer" title="Kane quantum computer">Kane QC</a></li> <li><a href="/wiki/Spin_qubit_quantum_computer" title="Spin qubit quantum computer">Spin qubit QC</a></li> <li><a href="/wiki/Nitrogen-vacancy_center" title="Nitrogen-vacancy center">NV center</a></li> <li><a href="/wiki/Nuclear_magnetic_resonance_quantum_computer" title="Nuclear magnetic resonance quantum computer">NMR QC</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Superconducting_quantum_computing" title="Superconducting quantum computing">Superconducting</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Charge_qubit" title="Charge qubit">Charge qubit</a></li> <li><a href="/wiki/Flux_qubit" title="Flux qubit">Flux qubit</a></li> <li><a href="/wiki/Phase_qubit" title="Phase qubit">Phase qubit</a></li> <li><a href="/wiki/Transmon" title="Transmon">Transmon</a></li></ul> </div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Quantum_programming" title="Quantum programming">Quantum<br />programming</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/OpenQASM" title="OpenQASM">OpenQASM</a>–<a href="/wiki/Qiskit" title="Qiskit">Qiskit</a>–<a href="/wiki/IBM_Quantum_Experience" class="mw-redirect" title="IBM Quantum Experience">IBM QX</a></li> <li><a href="/wiki/Quil_(instruction_set_architecture)" title="Quil (instruction set architecture)">Quil</a>–<a href="/wiki/Rigetti_Computing" title="Rigetti Computing">Forest/Rigetti QCS</a></li> <li><a href="/wiki/Cirq" title="Cirq">Cirq</a></li> <li><a href="/wiki/Q_Sharp" title="Q Sharp">Q#</a></li> <li><a href="/wiki/Libquantum" title="Libquantum">libquantum</a></li> <li><a href="/wiki/Quantum_programming" title="Quantum programming">many others...</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div> <ul><li><span class="noviewer" typeof="mw:File"><span title="Category"><img alt="" src="//upload.wikimedia.org/wikipedia/en/thumb/9/96/Symbol_category_class.svg/16px-Symbol_category_class.svg.png" decoding="async" width="16" height="16" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/9/96/Symbol_category_class.svg/23px-Symbol_category_class.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/9/96/Symbol_category_class.svg/31px-Symbol_category_class.svg.png 2x" data-file-width="180" data-file-height="185" /></span></span> <a href="/wiki/Category:Quantum_information_science" title="Category:Quantum information science">Quantum information science</a></li> <li><span class="noviewer" typeof="mw:File"><span title="Template"><img alt="" src="//upload.wikimedia.org/wikipedia/commons/thumb/8/83/Symbol_template_class_pink.svg/16px-Symbol_template_class_pink.svg.png" decoding="async" width="16" height="16" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/8/83/Symbol_template_class_pink.svg/23px-Symbol_template_class_pink.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/8/83/Symbol_template_class_pink.svg/31px-Symbol_template_class_pink.svg.png 2x" data-file-width="180" data-file-height="185" /></span></span> <a href="/wiki/Template:Quantum_mechanics_topics" title="Template:Quantum mechanics topics">Quantum mechanics topics</a></li></ul> </div></td></tr></tbody></table></div> <div class="navbox-styles"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236075235"></div><div role="navigation" class="navbox" aria-labelledby="Complexity_classes" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239400231"><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Complexity_classes" title="Template:Complexity classes"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Complexity_classes" title="Template talk:Complexity classes"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Complexity_classes" title="Special:EditPage/Template:Complexity classes"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Complexity_classes" style="font-size:114%;margin:0 4em"><a href="/wiki/Complexity_class" title="Complexity class">Complexity classes</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Considered feasible</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/DLOGTIME" title="DLOGTIME">DLOGTIME</a></li> <li><a href="/wiki/AC0" title="AC0">AC<sup>0</sup></a></li> <li><a href="/wiki/ACC0" title="ACC0">ACC<sup>0</sup></a></li> <li><a href="/wiki/TC0" title="TC0">TC<sup>0</sup></a></li> <li><a href="/wiki/L_(complexity)" title="L (complexity)">L</a></li> <li><a href="/wiki/SL_(complexity)" title="SL (complexity)">SL</a></li> <li><a href="/wiki/RL_(complexity)" title="RL (complexity)">RL</a></li> <li><a href="/wiki/FL_(complexity)" title="FL (complexity)">FL</a></li> <li><a href="/wiki/NL_(complexity)" title="NL (complexity)">NL</a> <ul><li><a href="/wiki/NL-complete" title="NL-complete">NL-complete</a></li></ul></li> <li><a href="/wiki/NC_(complexity)" title="NC (complexity)">NC</a></li> <li><a href="/wiki/SC_(complexity)" title="SC (complexity)">SC</a></li> <li><a href="/wiki/CC_(complexity)" title="CC (complexity)">CC</a></li> <li><a href="/wiki/P_(complexity)" title="P (complexity)">P</a> <ul><li><a href="/wiki/P-complete" title="P-complete">P-complete</a></li></ul></li> <li><a href="/wiki/ZPP_(complexity)" title="ZPP (complexity)">ZPP</a></li> <li><a href="/wiki/RP_(complexity)" title="RP (complexity)">RP</a></li> <li><a href="/wiki/BPP_(complexity)" title="BPP (complexity)">BPP</a></li> <li><a class="mw-selflink selflink">BQP</a></li> <li><a href="/wiki/APX" title="APX">APX</a></li> <li><a href="/wiki/FP_(complexity)" title="FP (complexity)">FP</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Suspected infeasible</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/UP_(complexity)" title="UP (complexity)">UP</a></li> <li><a href="/wiki/NP_(complexity)" title="NP (complexity)">NP</a> <ul><li><a href="/wiki/NP-completeness" title="NP-completeness">NP-complete</a></li> <li><a href="/wiki/NP-hardness" title="NP-hardness">NP-hard</a></li> <li><a href="/wiki/Co-NP" title="Co-NP">co-NP</a></li> <li><a href="/wiki/Co-NP-complete" title="Co-NP-complete">co-NP-complete</a></li></ul></li> <li><a href="/wiki/TFNP" title="TFNP">TFNP</a></li> <li><a href="/wiki/FNP_(complexity)" title="FNP (complexity)">FNP</a></li> <li><a href="/wiki/Arthur%E2%80%93Merlin_protocol" title="Arthur–Merlin protocol">AM</a></li> <li><a href="/wiki/QMA" title="QMA">QMA</a></li> <li><a href="/wiki/PH_(complexity)" title="PH (complexity)">PH</a></li> <li><a href="/wiki/Parity_P" title="Parity P">⊕P</a></li> <li><a href="/wiki/PP_(complexity)" title="PP (complexity)">PP</a></li> <li><a href="/wiki/%E2%99%AFP" title="♯P">#P</a> <ul><li><a href="/wiki/%E2%99%AFP-complete" title="♯P-complete">#P-complete</a></li></ul></li> <li><a href="/wiki/IP_(complexity)" title="IP (complexity)">IP</a></li> <li><a href="/wiki/PSPACE" title="PSPACE">PSPACE</a> <ul><li><a href="/wiki/PSPACE-complete" title="PSPACE-complete">PSPACE-complete</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Considered infeasible</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/EXPTIME" title="EXPTIME">EXPTIME</a></li> <li><a href="/wiki/NEXPTIME" title="NEXPTIME">NEXPTIME</a></li> <li><a href="/wiki/EXPSPACE" title="EXPSPACE">EXPSPACE</a></li> <li><a href="/wiki/2-EXPTIME" title="2-EXPTIME">2-EXPTIME</a></li> <li><a href="/wiki/ELEMENTARY" title="ELEMENTARY">ELEMENTARY</a></li> <li><a href="/wiki/PR_(complexity)" title="PR (complexity)">PR</a></li> <li><a href="/wiki/R_(complexity)" title="R (complexity)">R</a></li> <li><a href="/wiki/RE_(complexity)" title="RE (complexity)">RE</a></li> <li><a href="/wiki/ALL_(complexity)" title="ALL (complexity)">ALL</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Class hierarchies</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Polynomial_hierarchy" title="Polynomial hierarchy">Polynomial hierarchy</a></li> <li><a href="/wiki/Exponential_hierarchy" title="Exponential hierarchy">Exponential hierarchy</a></li> <li><a href="/wiki/Grzegorczyk_hierarchy" title="Grzegorczyk hierarchy">Grzegorczyk hierarchy</a></li> <li><a href="/wiki/Arithmetical_hierarchy" title="Arithmetical hierarchy">Arithmetical hierarchy</a></li> <li><a href="/wiki/Boolean_hierarchy" title="Boolean hierarchy">Boolean hierarchy</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Families of classes</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/DTIME" title="DTIME">DTIME</a></li> <li><a href="/wiki/NTIME" title="NTIME">NTIME</a></li> <li><a href="/wiki/DSPACE" title="DSPACE">DSPACE</a></li> <li><a href="/wiki/NSPACE" title="NSPACE">NSPACE</a></li> <li><a href="/wiki/Probabilistically_checkable_proof" title="Probabilistically checkable proof">Probabilistically checkable proof</a></li> <li><a href="/wiki/Interactive_proof_system" title="Interactive proof system">Interactive proof system</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div><a href="/wiki/List_of_complexity_classes" title="List of complexity classes">List of complexity classes</a></div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=BQP&oldid=1230041542">https://en.wikipedia.org/w/index.php?title=BQP&oldid=1230041542</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Probabilistic_complexity_classes" title="Category:Probabilistic complexity classes">Probabilistic complexity classes</a></li><li><a href="/wiki/Category:Quantum_complexity_theory" title="Category:Quantum complexity theory">Quantum complexity theory</a></li><li><a href="/wiki/Category:Quantum_computing" title="Category:Quantum computing">Quantum computing</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:CS1_maint:_location_missing_publisher" title="Category:CS1 maint: location missing publisher">CS1 maint: location missing publisher</a></li><li><a href="/wiki/Category:CS1_maint:_multiple_names:_authors_list" title="Category:CS1 maint: multiple names: authors list">CS1 maint: multiple names: authors list</a></li><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Webarchive_template_wayback_links" title="Category:Webarchive template wayback links">Webarchive template wayback links</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 20 June 2024, at 07:19<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=BQP&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-f69cdc8f6-nv2q5","wgBackendResponseTime":159,"wgPageParseReport":{"limitreport":{"cputime":"0.508","walltime":"0.686","ppvisitednodes":{"value":2351,"limit":1000000},"postexpandincludesize":{"value":81581,"limit":2097152},"templateargumentsize":{"value":7987,"limit":2097152},"expansiondepth":{"value":16,"limit":100},"expensivefunctioncount":{"value":2,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":68848,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 418.402 1 -total"," 35.16% 147.093 1 Template:Reflist"," 22.32% 93.367 4 Template:Navbox"," 21.78% 91.148 1 Template:Quantum_computing"," 15.99% 66.909 5 Template:Cite_journal"," 15.55% 65.070 1 Template:Short_description"," 10.06% 42.100 2 Template:Pagetype"," 8.14% 34.073 1 Template:Isbn"," 6.57% 27.502 1 Template:Catalog_lookup_link"," 6.44% 26.947 1 Template:Val"]},"scribunto":{"limitreport-timeusage":{"value":"0.240","limit":"10.000"},"limitreport-memusage":{"value":7349854,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-f69cdc8f6-v4897","timestamp":"20241122150028","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"BQP","url":"https:\/\/en.wikipedia.org\/wiki\/BQP","sameAs":"http:\/\/www.wikidata.org\/entity\/Q601325","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q601325","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2001-08-27T03:26:43Z","dateModified":"2024-06-20T07:19:10Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/9\/9e\/Randomised_Complexity_Classes_2.svg","headline":"complexity class"}</script> </body> </html>