Deutsch–Jozsa algorithm

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-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-sticky-header-enabled vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Deutsch–Jozsa algorithm - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-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-sticky-header-enabled 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":"8d0da8c4-4ada-48dd-a343-71a286c09673","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Deutsch–Jozsa_algorithm","wgTitle":"Deutsch–Jozsa algorithm","wgCurRevisionId":1280319525,"wgRevisionId":1280319525,"wgArticleId":475310,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description is different from Wikidata","Quantum algorithms"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Deutsch–Jozsa_algorithm","wgRelevantArticleId":475310,"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":10000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1028209","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"};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"];</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.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.20"> <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 name="viewport" content="width=1120"> <meta property="og:title" content="Deutsch–Jozsa algorithm - 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/Deutsch%E2%80%93Jozsa_algorithm"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Deutsch%E2%80%93Jozsa_algorithm&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/Deutsch%E2%80%93Jozsa_algorithm"> <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-Deutsch–Jozsa_algorithm rootpage-Deutsch–Jozsa_algorithm 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" title="Main menu" > <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><li id="n-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages"><span>Special pages</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/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=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=Deutsch%E2%80%93Jozsa+algorithm" 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=Deutsch%E2%80%93Jozsa+algorithm" 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/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=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=Deutsch%E2%80%93Jozsa+algorithm" 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=Deutsch%E2%80%93Jozsa+algorithm" 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-Problem_statement" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Problem_statement"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Problem statement</span> </div> </a> <ul id="toc-Problem_statement-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Classical_solution" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Classical_solution"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Classical solution</span> </div> </a> <ul id="toc-Classical_solution-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-History" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#History"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>History</span> </div> </a> <ul id="toc-History-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Algorithm" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Algorithm"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Algorithm</span> </div> </a> <ul id="toc-Algorithm-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Deutsch's_algorithm" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Deutsch's_algorithm"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Deutsch's algorithm</span> </div> </a> <ul id="toc-Deutsch's_algorithm-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Deutsch–Jozsa_algorithm_Qiskit_implementation" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Deutsch–Jozsa_algorithm_Qiskit_implementation"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Deutsch–Jozsa algorithm Qiskit implementation</span> </div> </a> <ul id="toc-Deutsch–Jozsa_algorithm_Qiskit_implementation-sublist" class="vector-toc-list"> </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">7</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">8</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">9</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" title="Table of Contents" > <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">Deutsch–Jozsa algorithm</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 17 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-17" 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">17 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/Algorisme_Deutsch%E2%80%93Jozsa" title="Algorisme Deutsch–Jozsa – Catalan" lang="ca" hreflang="ca" data-title="Algorisme Deutsch–Jozsa" 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/Deutsch-Jozsa-Algorithmus" title="Deutsch-Jozsa-Algorithmus – German" lang="de" hreflang="de" data-title="Deutsch-Jozsa-Algorithmus" 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/Algoritmo_de_Deutsch-Jozsa" title="Algoritmo de Deutsch-Jozsa – Spanish" lang="es" hreflang="es" data-title="Algoritmo de Deutsch-Jozsa" 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-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D8%AF%D9%88%DB%8C%DA%86" title="الگوریتم دویچ – Persian" lang="fa" hreflang="fa" data-title="الگوریتم دویچ" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Algorithme_de_Deutsch-Jozsa" title="Algorithme de Deutsch-Jozsa – French" lang="fr" hreflang="fr" data-title="Algorithme de Deutsch-Jozsa" 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/%EB%8F%84%EC%9D%B4%EC%B9%98%E2%80%93%EC%A1%B0%EC%82%AC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EB%93%AC" title="도이치–조사 알고리듬 – Korean" lang="ko" hreflang="ko" data-title="도이치–조사 알고리듬" 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/Algoritmo_di_Deutsch-Jozsa" title="Algoritmo di Deutsch-Jozsa – Italian" lang="it" hreflang="it" data-title="Algoritmo di Deutsch-Jozsa" 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/%D7%90%D7%9C%D7%92%D7%95%D7%A8%D7%99%D7%AA%D7%9D_%D7%93%D7%95%D7%99%D7%98%D7%A9-%D7%92%27%D7%95%D7%96%D7%94" title="אלגוריתם דויטש-ג'וזה – Hebrew" lang="he" hreflang="he" data-title="אלגוריתם דויטש-ג'וזה" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-lt mw-list-item"><a href="https://lt.wikipedia.org/wiki/Doi%C4%8Do-D%C5%BEozo_algoritmas" title="Doičo-Džozo algoritmas – Lithuanian" lang="lt" hreflang="lt" data-title="Doičo-Džozo algoritmas" data-language-autonym="Lietuvių" data-language-local-name="Lithuanian" class="interlanguage-link-target"><span>Lietuvių</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E3%83%89%E3%82%A4%E3%83%83%E3%83%81%E3%83%A5%E3%83%BB%E3%82%B8%E3%83%A7%E3%82%B5%E3%81%AE%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0" title="ドイッチュ・ジョサのアルゴリズム – Japanese" lang="ja" hreflang="ja" data-title="ドイッチュ・ジョサのアルゴリズム" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Algorytm_Deutscha-Jozsy" title="Algorytm Deutscha-Jozsy – Polish" lang="pl" hreflang="pl" data-title="Algorytm Deutscha-Jozsy" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Algoritmo_de_Deutsch-Jozsa" title="Algoritmo de Deutsch-Jozsa – Portuguese" lang="pt" hreflang="pt" data-title="Algoritmo de Deutsch-Jozsa" 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%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%BE%D0%B9%D1%87%D0%B0_%E2%80%94_%D0%99%D0%BE%D0%B6%D0%B8" title="Алгоритм Дойча — Йожи – Russian" lang="ru" hreflang="ru" data-title="Алгоритм Дойча — Йожи" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-fi mw-list-item"><a href="https://fi.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa-algoritmi" title="Deutsch–Jozsa-algoritmi – Finnish" lang="fi" hreflang="fi" data-title="Deutsch–Jozsa-algoritmi" data-language-autonym="Suomi" data-language-local-name="Finnish" class="interlanguage-link-target"><span>Suomi</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%BE%D0%B9%D1%87%D0%B0_%E2%80%94_%D0%99%D0%BE%D0%B6%D0%B8" title="Алгоритм Дойча — Йожи – Ukrainian" lang="uk" hreflang="uk" data-title="Алгоритм Дойча — Йожи" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-vi mw-list-item"><a href="https://vi.wikipedia.org/wiki/Thu%E1%BA%ADt_to%C3%A1n_Deutsch-Jozsa" title="Thuật toán Deutsch-Jozsa – Vietnamese" lang="vi" hreflang="vi" data-title="Thuật toán Deutsch-Jozsa" data-language-autonym="Tiếng Việt" data-language-local-name="Vietnamese" class="interlanguage-link-target"><span>Tiếng Việt</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E5%A4%9A%E4%BC%8A%E5%A5%87-%E4%B9%94%E8%90%A8%E7%AE%97%E6%B3%95" title="多伊奇-乔萨算法 – Chinese" lang="zh" hreflang="zh" data-title="多伊奇-乔萨算法" 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/Q1028209#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/Deutsch%E2%80%93Jozsa_algorithm" 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:Deutsch%E2%80%93Jozsa_algorithm" 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/Deutsch%E2%80%93Jozsa_algorithm"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Deutsch%E2%80%93Jozsa_algorithm&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=Deutsch%E2%80%93Jozsa_algorithm&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/Deutsch%E2%80%93Jozsa_algorithm"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Deutsch%E2%80%93Jozsa_algorithm&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=Deutsch%E2%80%93Jozsa_algorithm&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/Deutsch%E2%80%93Jozsa_algorithm" 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/Deutsch%E2%80%93Jozsa_algorithm" 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="//en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Deutsch%E2%80%93Jozsa_algorithm&oldid=1280319525" 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=Deutsch%E2%80%93Jozsa_algorithm&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=Deutsch%E2%80%93Jozsa_algorithm&id=1280319525&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%2FDeutsch%25E2%2580%2593Jozsa_algorithm"><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%2FDeutsch%25E2%2580%2593Jozsa_algorithm"><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=Deutsch%E2%80%93Jozsa_algorithm&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=Deutsch%E2%80%93Jozsa_algorithm&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/Q1028209" 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">Deterministic quantum algorithm</div> <p>The <b>Deutsch–Jozsa algorithm</b> is a <a href="/wiki/Deterministic_algorithm" title="Deterministic algorithm">deterministic</a> <a href="/wiki/Quantum_algorithm" title="Quantum algorithm">quantum algorithm</a> proposed by <a href="/wiki/David_Deutsch" title="David Deutsch">David Deutsch</a> and <a href="/wiki/Richard_Jozsa" title="Richard Jozsa">Richard Jozsa</a> in 1992 with improvements by <a href="/wiki/Richard_Cleve" title="Richard Cleve">Richard Cleve</a>, <a href="/wiki/Artur_Ekert" title="Artur Ekert">Artur Ekert</a>, Chiara Macchiavello, and <a href="/wiki/Michele_Mosca" title="Michele Mosca">Michele Mosca</a> in 1998.<sup id="cite_ref-DJ92_1-0" class="reference"><a href="#cite_note-DJ92-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-CEMM98_2-0" class="reference"><a href="#cite_note-CEMM98-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Although of little practical use, it is one of the first examples of a quantum algorithm that is <a href="/wiki/Time_complexity" title="Time complexity">exponentially faster</a> than any possible deterministic classical algorithm.<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><p>The Deutsch–Jozsa problem is specifically designed to be easy for a quantum algorithm and hard for any deterministic classical algorithm. It is a <a href="/wiki/Black_box" title="Black box">black box</a> problem that can be solved efficiently by a quantum computer with no error, whereas a deterministic classical computer would need an exponential number of queries to the black box to solve the problem. More formally, it yields an oracle relative to which <b><a href="/wiki/EQP_(complexity)" class="mw-redirect" title="EQP (complexity)">EQP</a></b>, the class of problems that can be solved exactly in polynomial time on a quantum computer, and <b><a href="/wiki/P_(complexity)" title="P (complexity)">P</a></b> are different.<sup id="cite_ref-Johansson2017_4-0" class="reference"><a href="#cite_note-Johansson2017-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> </p><p>Since the problem is easy to solve on a probabilistic classical computer, it does not yield an oracle separation with <b><a href="/wiki/BPP_(complexity)" title="BPP (complexity)">BPP</a></b>, the class of problems that can be solved with bounded error in polynomial time on a probabilistic classical computer. <a href="/wiki/Simon%27s_problem" title="Simon's problem">Simon's problem</a> is an example of a problem that yields an oracle separation between <b><a href="/wiki/BQP" title="BQP">BQP</a></b> and <b>BPP</b>. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Problem_statement">Problem statement</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Deutsch%E2%80%93Jozsa_algorithm&action=edit&section=1" title="Edit section: Problem statement"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In the Deutsch–Jozsa problem, we are given a black box quantum computer known as an <a href="/wiki/Oracle_machine" title="Oracle machine">oracle</a> that implements some function: </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</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> <mo stretchy="false">→</mo> <mo fence="false" stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/45f03afcbbd1be0a0fff8fb2a502a61d1642cd94" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.513ex; height:2.843ex;" alt="{\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}}" /></span> </p><p>The function takes n-bit binary values as input and produces either a 0 or a 1 as output for each such value. We are <a href="/wiki/Promise_problem" title="Promise problem">promised</a> that the function is either <a href="/wiki/Constant_function" title="Constant function">constant</a> (0 on all inputs or 1 on all inputs) or <i>balanced</i> (1 for exactly half of the input <a href="/wiki/Function_domain" class="mw-redirect" title="Function domain">domain</a> and 0 for the other half).<sup id="cite_ref-DJ92_1-1" class="reference"><a href="#cite_note-DJ92-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> The task then is to determine 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 f}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" /></span> is constant or balanced by using the oracle. </p> <div class="mw-heading mw-heading2"><h2 id="Classical_solution">Classical solution</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Deutsch%E2%80%93Jozsa_algorithm&action=edit&section=2" title="Edit section: Classical solution"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>For a conventional <a href="/wiki/Deterministic" class="mw-redirect" title="Deterministic">deterministic</a> algorithm 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 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> is the number of bits, <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-1}+1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{n-1}+1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/63c360467bd69c84245273b9dbf52230e11fde24" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.484ex; height:2.843ex;" alt="{\displaystyle 2^{n-1}+1}" /></span> evaluations 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 f}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" /></span> will be required in the worst case. To prove 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 f}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" /></span> is constant, just over half the set of inputs must be evaluated and their outputs found to be identical (because the function is guaranteed to be either balanced or constant, not somewhere in between). The best case occurs where the function is balanced and the first two output values are different. For a conventional <a href="/wiki/Randomized_algorithm" title="Randomized algorithm">randomized algorithm</a>, a constant <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 k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" /></span> evaluations of the function suffices to produce the correct answer with a high probability (failing 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 \epsilon \leq 1/2^{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>ϵ</mi> <mo>≤</mo> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \epsilon \leq 1/2^{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3bb698c931dd2653fd77c77d5855c49635676d27" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.619ex; height:3.176ex;" alt="{\displaystyle \epsilon \leq 1/2^{k}}" /></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 k\geq 1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> <mo>≥</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k\geq 1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d30d7dcf305b7bce39d36df72fe3985b47aa9961" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.472ex; height:2.343ex;" alt="{\displaystyle k\geq 1}" /></span>). However, <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 k=2^{n-1}+1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> <mo>=</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k=2^{n-1}+1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/05fa2f22fc26840563ee59f5c21a231183a32a75" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:12.794ex; height:2.843ex;" alt="{\displaystyle k=2^{n-1}+1}" /></span> evaluations are still required if we want an answer that has no possibility of error. The Deutsch-Jozsa quantum algorithm produces an answer that is always correct with a single evaluation 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 f}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" /></span>. </p> <div class="mw-heading mw-heading2"><h2 id="History">History</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Deutsch%E2%80%93Jozsa_algorithm&action=edit&section=3" title="Edit section: History"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The Deutsch–Jozsa algorithm generalizes earlier (1985) work by David Deutsch, which provided a solution for the simple case 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 n=1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>=</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n=1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d9ec7e1edc2e6d98f5aec2a39ae5f1c99d1e1425" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;" alt="{\displaystyle n=1}" /></span>. <br />Specifically, finding out if a given <a href="/wiki/Boolean_function" title="Boolean function">Boolean function</a> whose input is one bit, <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 f:\{0,1\}\to \{0,1\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo>:</mo> <mo fence="false" stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo fence="false" stretchy="false">}</mo> <mo stretchy="false">→</mo> <mo fence="false" stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f:\{0,1\}\to \{0,1\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c2eb63fbadc9aeee78180ffafd2407e25d2ce4bf" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.197ex; height:2.843ex;" alt="{\displaystyle f:\{0,1\}\to \{0,1\}}" /></span>, is constant.<sup id="cite_ref-Deu85_5-0" class="reference"><a href="#cite_note-Deu85-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> </p><p>The algorithm, as Deutsch had originally proposed it, was not deterministic. The algorithm was successful with a probability of one half. In 1992, Deutsch and Jozsa produced a deterministic algorithm which was generalized to a function which 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 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> bits for its input. Unlike Deutsch's algorithm, this algorithm required two function evaluations instead of only one. </p><p>Further improvements to the Deutsch–Jozsa algorithm were made by Cleve et al.,<sup id="cite_ref-CEMM98_2-1" class="reference"><a href="#cite_note-CEMM98-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> resulting in an algorithm that is both deterministic and requires only a single query 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 f}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" /></span>. This algorithm is still referred to as Deutsch–Jozsa algorithm in honour of the groundbreaking techniques they employed.<sup id="cite_ref-CEMM98_2-2" class="reference"><a href="#cite_note-CEMM98-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Deutsch%E2%80%93Jozsa_algorithm&action=edit&section=4" title="Edit section: Algorithm"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>For the Deutsch–Jozsa algorithm to work, the oracle computing <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 f(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/202945cce41ecebb6f643f31d119c514bec7a074" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" /></span> from <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}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" /></span> must be a quantum oracle which does not <a href="/wiki/Quantum_decoherence" title="Quantum decoherence">decohere</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 x}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" /></span>. In its computation, it cannot make a copy 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}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" /></span>, because that would violate the <a href="/wiki/No_cloning_theorem" class="mw-redirect" title="No cloning theorem">no cloning theorem</a>. The point of view of the Deutsch-Jozsa algorithm 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 f}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" /></span> as an oracle means that it does not matter what the oracle does, since it just has to perform its promised transformation. </p> <figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/File:Deutsch-Jozsa-algorithm-quantum-circuit.png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/b/b5/Deutsch-Jozsa-algorithm-quantum-circuit.png/400px-Deutsch-Jozsa-algorithm-quantum-circuit.png" decoding="async" width="400" height="195" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/b/b5/Deutsch-Jozsa-algorithm-quantum-circuit.png/600px-Deutsch-Jozsa-algorithm-quantum-circuit.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/b/b5/Deutsch-Jozsa-algorithm-quantum-circuit.png/800px-Deutsch-Jozsa-algorithm-quantum-circuit.png 2x" data-file-width="947" data-file-height="462" /></a><figcaption>Deutsch-Jozsa algorithm <a href="/wiki/Quantum_circuit" title="Quantum circuit">quantum circuit</a></figcaption></figure> <p>The algorithm begins with the <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+1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n+1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2a135e65a42f2d73cccbfc4569523996ca0036f1" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n+1}" /></span> bit 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 |0\rangle ^{\otimes n}|1\rangle }"> <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> <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 |0\rangle ^{\otimes n}|1\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/74ebbf3426ea5460233805b0f3a86675fa4e915f" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.925ex; height:3.009ex;" alt="{\displaystyle |0\rangle ^{\otimes n}|1\rangle }" /></span>. That is, the first n bits are each in 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 |0\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |0\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ed066a3ad158da0ad6d6a421a606b1c8a35eb95b" 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 |0\rangle }" /></span> and the final bit 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 |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>. A <a href="/wiki/Quantum_logic_gate#Hadamard_gate" title="Quantum logic gate">Hadamard gate</a> is applied to each bit to obtain the state </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\rangle -|1\rangle ),}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msqrt> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msup> </msqrt> </mfrac> </mrow> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">)</mo> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\rangle -|1\rangle ),}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/edcdf3f910316b5d357a0d263a5bedf5983e73b8" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:25.909ex; height:7.509ex;" alt="{\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\rangle -|1\rangle ),}" /></span> </p><p>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 x}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" /></span> runs over 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}"> <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>-bit strings, which each may be represented by a number from <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}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" /></span> 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 2^{n}-1}"> <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> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{n}-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/51e4bd4ef2f9549d026cbf643a91c0d12a8c6794" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.384ex; height:2.509ex;" alt="{\displaystyle 2^{n}-1}" /></span>. We have the function <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 f}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" /></span> implemented as a quantum oracle. The oracle maps its input 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 |y\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> <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 |x\rangle |y\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/117efc81558a975a62aa4444733440ad5f65b980" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.588ex; height:2.843ex;" alt="{\displaystyle |x\rangle |y\rangle }" /></span> 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 |x\rangle |y\oplus f(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> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>y</mi> <mo>⊕</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |x\rangle |y\oplus f(x)\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6280bad32d01da9eaf2066b19764f8c3ab812ad6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.846ex; height:2.843ex;" alt="{\displaystyle |x\rangle |y\oplus f(x)\rangle }" /></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 \oplus }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>⊕</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \oplus }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8b16e2bdaefee9eed86d866e6eba3ac47c710f60" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \oplus }" /></span> denotes addition modulo 2. Applying the quantum oracle gives; </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\oplus f(x)\rangle -|1\oplus f(x)\rangle ).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msqrt> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msup> </msqrt> </mfrac> </mrow> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <mo>⊕</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo fence="false" stretchy="false">⟩</mo> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo>⊕</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">)</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\oplus f(x)\rangle -|1\oplus f(x)\rangle ).}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0f2134450863e8efaa88e8705cc5566e360e78b7" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:40.424ex; height:7.509ex;" alt="{\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}|x\rangle (|0\oplus f(x)\rangle -|1\oplus f(x)\rangle ).}" /></span> </p><p>For 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 x,f(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>x</mi> <mo>,</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle x,f(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/089191d6fcec60fb5a5a77b39600faf7038a4a51" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.781ex; height:2.843ex;" alt="{\displaystyle x,f(x)}" /></span> is either 0 or 1. Testing these two possibilities, we see the above state is equal to </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle (|0\rangle -|1\rangle ).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msqrt> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>+</mo> <mn>1</mn> </mrow> </msup> </msqrt> </mfrac> </mrow> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">)</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle (|0\rangle -|1\rangle ).}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ae27989c9108304afdc7c638981a94f4c1cad837" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:33.657ex; height:7.509ex;" alt="{\displaystyle {\frac {1}{\sqrt {2^{n+1}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle (|0\rangle -|1\rangle ).}" /></span> </p><p>At this point the last qubit <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 {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> </mrow> <msqrt> <mn>2</mn> </msqrt> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4e428aaf74b13b0709992efede12bfa92e06247c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:9.104ex; height:6.676ex;" alt="{\displaystyle {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}}" /></span> may be ignored and the following remains: </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle .}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msqrt> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </msqrt> </mfrac> </mrow> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>x</mi> <mo fence="false" stretchy="false">⟩</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle .}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bff660e62e6a060c9f1a275fc8bc8c34a12264fe" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:21.091ex; height:7.343ex;" alt="{\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle .}" /></span> </p><p>Next, we will have each qubit go through a <a href="/wiki/Quantum_logic_gate#Hadamard_gate" title="Quantum logic gate">Hadamard gate</a>. The total transformation over 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}"> <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 can be expressed with the following identity: </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H^{\otimes n}|k\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{k\cdot j}|j\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>⊗</mo> <mi>n</mi> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>k</mi> <mo fence="false" stretchy="false">⟩</mo> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msqrt> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </msqrt> </mfrac> </mrow> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>⋅</mo> <mi>j</mi> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>j</mi> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle H^{\otimes n}|k\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{k\cdot j}|j\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0817994eb7191dae88c2dc09b61b8c55f63aa74a" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:29.402ex; height:7.676ex;" alt="{\displaystyle H^{\otimes n}|k\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}(-1)^{k\cdot j}|j\rangle }" /></span> </p><p>(<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\cdot k=j_{0}k_{0}\oplus j_{1}k_{1}\oplus \cdots \oplus j_{n-1}k_{n-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>j</mi> <mo>⋅</mo> <mi>k</mi> <mo>=</mo> <msub> <mi>j</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> <mo>⊕</mo> <msub> <mi>j</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>⊕</mo> <mo>⋯</mo> <mo>⊕</mo> <msub> <mi>j</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle j\cdot k=j_{0}k_{0}\oplus j_{1}k_{1}\oplus \cdots \oplus j_{n-1}k_{n-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/776db953370c5aa97c27730f392eb6cff6cf39b0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:35.581ex; height:2.509ex;" alt="{\displaystyle j\cdot k=j_{0}k_{0}\oplus j_{1}k_{1}\oplus \cdots \oplus j_{n-1}k_{n-1}}" /></span> is the sum of the bitwise product). This results in </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{y=0}^{2^{n}-1}{\left(-1\right)}^{x\cdot y}|y\rangle \right]=\sum _{y=0}^{2^{n}-1}\left[{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot y}\right]|y\rangle .}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msqrt> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </msqrt> </mfrac> </mrow> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> </msup> <mrow> <mo>[</mo> <mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msqrt> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </msqrt> </mfrac> </mrow> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>y</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <msup> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mrow> <mo>−</mo> <mn>1</mn> </mrow> <mo>)</mo> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> <mo>⋅</mo> <mi>y</mi> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>y</mi> <mo fence="false" stretchy="false">⟩</mo> </mrow> <mo>]</mo> </mrow> <mo>=</mo> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>y</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <mrow> <mo>[</mo> <mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mfrac> </mrow> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> </msup> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> <mo>⋅</mo> <mi>y</mi> </mrow> </msup> </mrow> <mo>]</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>y</mi> <mo fence="false" stretchy="false">⟩</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{y=0}^{2^{n}-1}{\left(-1\right)}^{x\cdot y}|y\rangle \right]=\sum _{y=0}^{2^{n}-1}\left[{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot y}\right]|y\rangle .}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7e615c5a10969bf3c4fa017a6fe9b27057f5765a" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:77.088ex; height:7.676ex;" alt="{\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}\left[{\frac {1}{\sqrt {2^{n}}}}\sum _{y=0}^{2^{n}-1}{\left(-1\right)}^{x\cdot y}|y\rangle \right]=\sum _{y=0}^{2^{n}-1}\left[{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}(-1)^{x\cdot y}\right]|y\rangle .}" /></span> </p><p>From this, we can see that the probability for 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 k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" /></span> to be measured is </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left|{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}{\left(-1\right)}^{f(x)}{\left(-1\right)}^{x\cdot k}\right|^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mrow> <mo>|</mo> <mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mfrac> </mrow> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <msup> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mrow> <mo>−</mo> <mn>1</mn> </mrow> <mo>)</mo> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> </msup> <msup> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mrow> <mo>−</mo> <mn>1</mn> </mrow> <mo>)</mo> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> <mo>⋅</mo> <mi>k</mi> </mrow> </msup> </mrow> <mo>|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left|{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}{\left(-1\right)}^{f(x)}{\left(-1\right)}^{x\cdot k}\right|^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/14a37deaa8df361c179697b6509f717cdf41e0ad" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.171ex; width:25.629ex; height:8.009ex;" alt="{\displaystyle \left|{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}{\left(-1\right)}^{f(x)}{\left(-1\right)}^{x\cdot k}\right|^{2}}" /></span> </p><p>The probability of measuring <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 k=0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k=0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6307c8a99dad7d0bcb712352ae0a748bd99a038b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle k=0}" /></span>, corresponding 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 |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>, is </p><p><span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\bigg |}{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}{\bigg |}^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo maxsize="2.047em" minsize="2.047em">|</mo> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mfrac> </mrow> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>x</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mrow> </msup> <msup> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo maxsize="2.047em" minsize="2.047em">|</mo> </mrow> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\bigg |}{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}{\bigg |}^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d63bcf95178860da9a399485674f72ffbfb8620e" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:17.975ex; height:7.343ex;" alt="{\displaystyle {\bigg |}{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}{\bigg |}^{2}}" /></span> </p><p>which evaluates to 1 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 f(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/202945cce41ecebb6f643f31d119c514bec7a074" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" /></span> is constant (<a href="/wiki/Constructive_interference" class="mw-redirect" title="Constructive interference">constructive interference</a>) and 0 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 f(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/202945cce41ecebb6f643f31d119c514bec7a074" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" /></span> is balanced (<a href="/wiki/Destructive_interference" class="mw-redirect" title="Destructive interference">destructive interference</a>). In other words, the final measurement will 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 |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> (all zeros) if and only 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 f(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/202945cce41ecebb6f643f31d119c514bec7a074" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" /></span> is constant and will yield some other state 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 f(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/202945cce41ecebb6f643f31d119c514bec7a074" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" /></span> is balanced. </p> <div class="mw-heading mw-heading2"><h2 id="Deutsch's_algorithm"><span id="Deutsch.27s_algorithm"></span>Deutsch's algorithm</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Deutsch%E2%80%93Jozsa_algorithm&action=edit&section=5" title="Edit section: Deutsch's algorithm"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Deutsch's algorithm is a special case of the general Deutsch–Jozsa algorithm where n = 1 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 f\colon \{0,1\}^{n}\rightarrow \{0,1\}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</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> <mo stretchy="false">→</mo> <mo fence="false" stretchy="false">{</mo> <mn>0</mn> <mo>,</mo> <mn>1</mn> <mo fence="false" stretchy="false">}</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/f713c7fab3c3cb60f59ac3ca1cafddb734b927bd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.513ex; height:2.843ex;" alt="{\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}" /></span>. We need to check the condition <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 f(0)=f(1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(0)=f(1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cc37ee05542c1472c465dd6441c3d3a8a1adfa6d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.599ex; height:2.843ex;" alt="{\displaystyle f(0)=f(1)}" /></span>. It is equivalent to check <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 f(0)\oplus f(1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>⊕</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(0)\oplus f(1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fcc09ccd120f8d7ba4ed1fcb2f976d804fa24b74" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.341ex; height:2.843ex;" alt="{\displaystyle f(0)\oplus f(1)}" /></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 \oplus }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>⊕</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \oplus }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8b16e2bdaefee9eed86d866e6eba3ac47c710f60" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \oplus }" /></span> is addition modulo 2, which can also be viewed as a quantum <a href="/wiki/XOR_gate" title="XOR gate">XOR gate</a> implemented as a <a href="/wiki/Controlled_NOT_gate" title="Controlled NOT gate">Controlled NOT gate</a>), if zero, then <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 f}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" /></span> is constant, otherwise <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 f}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" /></span> is not constant. </p><p>We begin with the two-qubit 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 |0\rangle |1\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> <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 |0\rangle |1\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/68b498aded053bf27955d47e993ece190cd53414" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.428ex; height:2.843ex;" alt="{\displaystyle |0\rangle |1\rangle }" /></span> and apply a <a href="/wiki/Quantum_logic_gate#Hadamard_gate" title="Quantum logic gate">Hadamard gate</a> to each qubit. This yields <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mrow> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">)</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">)</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ).}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ab670e74c7c082f46552e02c079a1cb86ce32955" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:22.801ex; height:5.176ex;" alt="{\displaystyle {\frac {1}{2}}(|0\rangle +|1\rangle )(|0\rangle -|1\rangle ).}" /></span> </p><p>We are given a quantum implementation of the function <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 f}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.279ex; height:2.509ex;" alt="{\displaystyle f}" /></span> that maps <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 |y\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> <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 |x\rangle |y\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/117efc81558a975a62aa4444733440ad5f65b980" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.588ex; height:2.843ex;" alt="{\displaystyle |x\rangle |y\rangle }" /></span> 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 |x\rangle |f(x)\oplus y\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> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> <mo>⊕</mo> <mi>y</mi> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |x\rangle |f(x)\oplus y\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2c4b893c08bc8167c35760f73df73197d9cb8785" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.846ex; height:2.843ex;" alt="{\displaystyle |x\rangle |f(x)\oplus y\rangle }" /></span>. Applying this function to our current state we obtain <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}&{\frac {1}{2}}(|0\rangle (|f(0)\oplus 0\rangle -|f(0)\oplus 1\rangle )+|1\rangle (|f(1)\oplus 0\rangle -|f(1)\oplus 1\rangle ))\\&={\frac {1}{2}}((-1)^{f(0)}|0\rangle (|0\rangle -|1\rangle )+(-1)^{f(1)}|1\rangle (|0\rangle -|1\rangle ))\\&=(-1)^{f(0)}{\frac {1}{2}}\left(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle \right)(|0\rangle -|1\rangle ).\end{aligned}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true"> <mtr> <mtd></mtd> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mrow> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>f</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>⊕</mo> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>f</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>⊕</mo> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">)</mo> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>f</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>⊕</mo> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>f</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>⊕</mo> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mtd> </mtr> <mtr> <mtd></mtd> <mtd> <mi></mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mrow> <mo stretchy="false">(</mo> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>f</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">)</mo> <mo>+</mo> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>f</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mtd> </mtr> <mtr> <mtd></mtd> <mtd> <mi></mi> <mo>=</mo> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>f</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mrow> <mrow> <mo>(</mo> <mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> <mo>+</mo> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>f</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>⊕</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> </mrow> <mo>)</mo> </mrow> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">)</mo> <mo>.</mo> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&{\frac {1}{2}}(|0\rangle (|f(0)\oplus 0\rangle -|f(0)\oplus 1\rangle )+|1\rangle (|f(1)\oplus 0\rangle -|f(1)\oplus 1\rangle ))\\&={\frac {1}{2}}((-1)^{f(0)}|0\rangle (|0\rangle -|1\rangle )+(-1)^{f(1)}|1\rangle (|0\rangle -|1\rangle ))\\&=(-1)^{f(0)}{\frac {1}{2}}\left(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle \right)(|0\rangle -|1\rangle ).\end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c30d2d8e3a6cbbf5f2482088c0d41aa09a75efbd" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -7.192ex; margin-bottom: -0.313ex; width:61.346ex; height:16.176ex;" alt="{\displaystyle {\begin{aligned}&{\frac {1}{2}}(|0\rangle (|f(0)\oplus 0\rangle -|f(0)\oplus 1\rangle )+|1\rangle (|f(1)\oplus 0\rangle -|f(1)\oplus 1\rangle ))\\&={\frac {1}{2}}((-1)^{f(0)}|0\rangle (|0\rangle -|1\rangle )+(-1)^{f(1)}|1\rangle (|0\rangle -|1\rangle ))\\&=(-1)^{f(0)}{\frac {1}{2}}\left(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle \right)(|0\rangle -|1\rangle ).\end{aligned}}}" /></span> </p><p>We ignore the last bit and the global phase and therefore have the state <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{\sqrt {2}}}(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle ).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msqrt> <mn>2</mn> </msqrt> </mfrac> </mrow> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> <mo>+</mo> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>f</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>⊕</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">)</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\frac {1}{\sqrt {2}}}(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle ).}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ee4757749be23898b87f233a1d1ad9eee21f8e7e" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:26.96ex; height:6.176ex;" alt="{\displaystyle {\frac {1}{\sqrt {2}}}(|0\rangle +(-1)^{f(0)\oplus f(1)}|1\rangle ).}" /></span> </p><p>Applying a Hadamard gate to this state we have <span class="mwe-math-element"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{aligned}&{\frac {1}{2}}(|0\rangle +|1\rangle +(-1)^{f(0)\oplus f(1)}|0\rangle -(-1)^{f(0)\oplus f(1)}|1\rangle )\\&={\frac {1}{2}}((1+(-1)^{f(0)\oplus f(1)})|0\rangle +(1-(-1)^{f(0)\oplus f(1)})|1\rangle ).\end{aligned}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right left right left right left right left right left right left" rowspacing="3pt" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true"> <mtr> <mtd></mtd> <mtd> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mrow> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> <mo>+</mo> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>f</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>⊕</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> <mo>−</mo> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>f</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>⊕</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">)</mo> </mtd> </mtr> <mtr> <mtd></mtd> <mtd> <mi></mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mrow> <mo stretchy="false">(</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>f</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>⊕</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> <mo>+</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>−</mo> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>f</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>⊕</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> </msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">)</mo> <mo>.</mo> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}&{\frac {1}{2}}(|0\rangle +|1\rangle +(-1)^{f(0)\oplus f(1)}|0\rangle -(-1)^{f(0)\oplus f(1)}|1\rangle )\\&={\frac {1}{2}}((1+(-1)^{f(0)\oplus f(1)})|0\rangle +(1-(-1)^{f(0)\oplus f(1)})|1\rangle ).\end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7e222b27ed580ba3adee399a229753cb7a58ef1a" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.485ex; margin-bottom: -0.187ex; width:52.8ex; height:10.509ex;" alt="{\displaystyle {\begin{aligned}&{\frac {1}{2}}(|0\rangle +|1\rangle +(-1)^{f(0)\oplus f(1)}|0\rangle -(-1)^{f(0)\oplus f(1)}|1\rangle )\\&={\frac {1}{2}}((1+(-1)^{f(0)\oplus f(1)})|0\rangle +(1-(-1)^{f(0)\oplus f(1)})|1\rangle ).\end{aligned}}}" /></span> </p><p><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 f(0)\oplus f(1)=0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>⊕</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(0)\oplus f(1)=0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e77de7f3d5926f533dfc63870b15bbcfefc16247" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.602ex; height:2.843ex;" alt="{\displaystyle f(0)\oplus f(1)=0}" /></span> if and only if we measure <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 }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |0\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ed066a3ad158da0ad6d6a421a606b1c8a35eb95b" 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 |0\rangle }" /></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 f(0)\oplus f(1)=1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mn>0</mn> <mo stretchy="false">)</mo> <mo>⊕</mo> <mi>f</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>=</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(0)\oplus f(1)=1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/89a4b71e7a1a13c49f935af2c5be87f469f8948b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.602ex; height:2.843ex;" alt="{\displaystyle f(0)\oplus f(1)=1}" /></span> if and only if we measure <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>. So with certainty we know whether <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 f(x)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo stretchy="false">(</mo> <mi>x</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f(x)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/202945cce41ecebb6f643f31d119c514bec7a074" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.418ex; height:2.843ex;" alt="{\displaystyle f(x)}" /></span> is constant or balanced. </p> <div class="mw-heading mw-heading2"><h2 id="Deutsch–Jozsa_algorithm_Qiskit_implementation"><span id="Deutsch.E2.80.93Jozsa_algorithm_Qiskit_implementation"></span>Deutsch–Jozsa algorithm Qiskit implementation</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Deutsch%E2%80%93Jozsa_algorithm&action=edit&section=6" title="Edit section: Deutsch–Jozsa algorithm Qiskit implementation"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The quantum circuit shown here is from <a rel="nofollow" class="external text" href="https://learning.quantum.ibm.com/course/fundamentals-of-quantum-algorithms/quantum-query-algorithms#the-deutsch-jozsa-algorithm">a simple example of how the Deutsch–Jozsa algorithm can be implemented in Python</a> using <a href="/wiki/Qiskit" title="Qiskit">Qiskit</a>, an open-source quantum computing software development framework by IBM. </p> <figure class="mw-default-size" typeof="mw:File/Thumb"><a href="/wiki/File:Deutsch-Jozsa_balanced_quantum_circuit.png" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/1/12/Deutsch-Jozsa_balanced_quantum_circuit.png/220px-Deutsch-Jozsa_balanced_quantum_circuit.png" decoding="async" width="220" height="56" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/12/Deutsch-Jozsa_balanced_quantum_circuit.png/330px-Deutsch-Jozsa_balanced_quantum_circuit.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/12/Deutsch-Jozsa_balanced_quantum_circuit.png/440px-Deutsch-Jozsa_balanced_quantum_circuit.png 2x" data-file-width="1746" data-file-height="444" /></a><figcaption>Deutsch-Jozsa balanced quantum circuit</figcaption></figure> <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=Deutsch%E2%80%93Jozsa_algorithm&action=edit&section=7" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Bernstein%E2%80%93Vazirani_algorithm" title="Bernstein–Vazirani algorithm">Bernstein–Vazirani algorithm</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=Deutsch%E2%80%93Jozsa_algorithm&action=edit&section=8" 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"><ol class="references"> <li id="cite_note-DJ92-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-DJ92_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-DJ92_1-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><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><cite id="CITEREFDavid_DeutschRichard_Jozsa1992" class="citation journal cs1"><a href="/wiki/David_Deutsch" title="David Deutsch">David Deutsch</a> & <a href="/wiki/Richard_Jozsa" title="Richard Jozsa">Richard Jozsa</a> (1992). "Rapid solutions of problems by quantum computation". <i>Proceedings of the Royal Society of London A</i>. <b>439</b> (1907): <span class="nowrap">553–</span>558. <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/1992RSPSA.439..553D">1992RSPSA.439..553D</a>. <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.5997">10.1.1.655.5997</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.1098%2Frspa.1992.0167">10.1098/rspa.1992.0167</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:121702767">121702767</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+of+London+A&rft.atitle=Rapid+solutions+of+problems+by+quantum+computation&rft.volume=439&rft.issue=1907&rft.pages=%3Cspan+class%3D%22nowrap%22%3E553-%3C%2Fspan%3E558&rft.date=1992&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.655.5997%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A121702767%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1098%2Frspa.1992.0167&rft_id=info%3Abibcode%2F1992RSPSA.439..553D&rft.au=David+Deutsch&rft.au=Richard+Jozsa&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADeutsch%E2%80%93Jozsa+algorithm" class="Z3988"></span></span> </li> <li id="cite_note-CEMM98-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-CEMM98_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-CEMM98_2-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-CEMM98_2-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFR._CleveA._EkertC._MacchiavelloM._Mosca1998" class="citation journal cs1">R. Cleve; A. Ekert; C. Macchiavello; M. Mosca (1998). "Quantum algorithms revisited". <i>Proceedings of the Royal Society of London A</i>. <b>454</b> (1969): <span class="nowrap">339–</span>354. <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/9708016">quant-ph/9708016</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/1998RSPSA.454..339C">1998RSPSA.454..339C</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.1998.0164">10.1098/rspa.1998.0164</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:16128238">16128238</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+of+London+A&rft.atitle=Quantum+algorithms+revisited&rft.volume=454&rft.issue=1969&rft.pages=%3Cspan+class%3D%22nowrap%22%3E339-%3C%2Fspan%3E354&rft.date=1998&rft_id=info%3Aarxiv%2Fquant-ph%2F9708016&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A16128238%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1098%2Frspa.1998.0164&rft_id=info%3Abibcode%2F1998RSPSA.454..339C&rft.au=R.+Cleve&rft.au=A.+Ekert&rft.au=C.+Macchiavello&rft.au=M.+Mosca&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADeutsch%E2%80%93Jozsa+algorithm" 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="CITEREFSimon1994" class="citation book cs1">Simon, Daniel (November 1994). <a rel="nofollow" class="external text" href="http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.51.5477&rep=rep1&type=pdf">"On the power of quantum computation"</a>. <i>Proceedings 35th Annual Symposium on Foundations of Computer Science</i>. pp. <span class="nowrap">116–</span>123. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.1994.365701">10.1109/SFCS.1994.365701</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-8186-6580-7" title="Special:BookSources/0-8186-6580-7"><bdi>0-8186-6580-7</bdi></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:7457814">7457814</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=On+the+power+of+quantum+computation&rft.btitle=Proceedings+35th+Annual+Symposium+on+Foundations+of+Computer+Science&rft.pages=%3Cspan+class%3D%22nowrap%22%3E116-%3C%2Fspan%3E123&rft.date=1994-11&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A7457814%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1109%2FSFCS.1994.365701&rft.isbn=0-8186-6580-7&rft.aulast=Simon&rft.aufirst=Daniel&rft_id=http%3A%2F%2Fciteseer.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.51.5477%26rep%3Drep1%26type%3Dpdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADeutsch%E2%80%93Jozsa+algorithm" class="Z3988"></span></span> </li> <li id="cite_note-Johansson2017-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-Johansson2017_4-0">^</a></b></span> <span class="reference-text"> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFJohansson,_N.Larsson,_JÅ.2017" class="citation journal cs1">Johansson, N.; Larsson, JÅ. (2017). "Efficient classical simulation of the Deutsch–Jozsa and Simon's algorithms". <i>Quantum Inf Process (2017)</i>. <b>16</b> (9): 233. <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/1508.05027">1508.05027</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/2017QuIP...16..233J">2017QuIP...16..233J</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.1007%2Fs11128-017-1679-7">10.1007/s11128-017-1679-7</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:28670540">28670540</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Quantum+Inf+Process+%282017%29&rft.atitle=Efficient+classical+simulation+of+the+Deutsch%E2%80%93Jozsa+and+Simon%27s+algorithms&rft.volume=16&rft.issue=9&rft.pages=233&rft.date=2017&rft_id=info%3Aarxiv%2F1508.05027&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A28670540%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1007%2Fs11128-017-1679-7&rft_id=info%3Abibcode%2F2017QuIP...16..233J&rft.au=Johansson%2C+N.&rft.au=Larsson%2C+J%C3%85.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADeutsch%E2%80%93Jozsa+algorithm" class="Z3988"></span></span> </li> <li id="cite_note-Deu85-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-Deu85_5-0">^</a></b></span> <span class="reference-text"> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFDavid_Deutsch1985" class="citation journal cs1"><a href="/wiki/David_Deutsch" title="David Deutsch">David Deutsch</a> (1985). "Quantum Theory, the Church-Turing Principle and the Universal Quantum Computer". <i>Proceedings of the Royal Society of London A</i>. <b>400</b> (1818): <span class="nowrap">97–</span>117. <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/1985RSPSA.400...97D">1985RSPSA.400...97D</a>. <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.41.2382">10.1.1.41.2382</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.1098%2Frspa.1985.0070">10.1098/rspa.1985.0070</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:1438116">1438116</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+of+London+A&rft.atitle=Quantum+Theory%2C+the+Church-Turing+Principle+and+the+Universal+Quantum+Computer&rft.volume=400&rft.issue=1818&rft.pages=%3Cspan+class%3D%22nowrap%22%3E97-%3C%2Fspan%3E117&rft.date=1985&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.41.2382%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A1438116%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1098%2Frspa.1985.0070&rft_id=info%3Abibcode%2F1985RSPSA.400...97D&rft.au=David+Deutsch&rfr_id=info%3Asid%2Fen.wikipedia.org%3ADeutsch%E2%80%93Jozsa+algorithm" class="Z3988"></span></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=Deutsch%E2%80%93Jozsa_algorithm&action=edit&section=9" 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="http://www.quiprocone.org/Protected/Lecture_5.htm">Deutsch's lecture about the Deutsch-Jozsa algorithm</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_science667" 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_science667" 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/Entanglement_swapping" title="Entanglement swapping">Entanglement swapping</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_cryptography24" 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 class="mw-selflink selflink">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 href="/wiki/BQP" title="BQP">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> <li><a href="/wiki/Hamiltonian_quantum_computation" title="Hamiltonian quantum computation">Hamiltonian quantum computation</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><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" 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=Deutsch–Jozsa_algorithm&oldid=1280319525">https://en.wikipedia.org/w/index.php?title=Deutsch–Jozsa_algorithm&oldid=1280319525</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">Category</a>: <ul><li><a href="/wiki/Category:Quantum_algorithms" title="Category:Quantum algorithms">Quantum algorithms</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: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></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 13 March 2025, at 22: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=Deutsch%E2%80%93Jozsa_algorithm&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"><picture><source media="(min-width: 500px)" srcset="/static/images/footer/wikimedia-button.svg" width="84" height="29"><img src="/static/images/footer/wikimedia.svg" width="25" height="25" alt="Wikimedia Foundation" lang="en" loading="lazy"></picture></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"><picture><source media="(min-width: 500px)" srcset="/w/resources/assets/poweredby_mediawiki.svg" width="88" height="31"><img src="/w/resources/assets/mediawiki_compact.svg" alt="Powered by MediaWiki" lang="en" width="25" height="25" loading="lazy"></picture></a></li> </ul> </footer> </div> </div> </div> <div class="vector-header-container vector-sticky-header-container"> <div id="vector-sticky-header" class="vector-sticky-header"> <div class="vector-sticky-header-start"> <div class="vector-sticky-header-icon-start vector-button-flush-left vector-button-flush-right" aria-hidden="true"> <button class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-sticky-header-search-toggle" tabindex="-1" data-event-name="ui.vector-sticky-search-form.icon"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </button> </div> <div role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box"> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail"> <form action="/w/index.php" id="vector-sticky-search-form" class="cdx-search-input cdx-search-input--has-end-button"> <div 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"> <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> <div class="vector-sticky-header-context-bar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-sticky-header-toc" class="vector-dropdown mw-portlet mw-portlet-sticky-header-toc vector-sticky-header-toc vector-button-flush-left" > <input type="checkbox" id="vector-sticky-header-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-sticky-header-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-sticky-header-toc-label" for="vector-sticky-header-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-sticky-header-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div class="vector-sticky-header-context-bar-primary" aria-hidden="true" ><span class="mw-page-title-main">Deutsch–Jozsa algorithm</span></div> </div> </div> <div class="vector-sticky-header-end" aria-hidden="true"> <div class="vector-sticky-header-icons"> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-talk-sticky-header" tabindex="-1" data-event-name="talk-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbles mw-ui-icon-wikimedia-speechBubbles"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-subject-sticky-header" tabindex="-1" data-event-name="subject-sticky-header"><span class="vector-icon mw-ui-icon-article mw-ui-icon-wikimedia-article"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-history-sticky-header" tabindex="-1" data-event-name="history-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-history mw-ui-icon-wikimedia-wikimedia-history"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-watchlink" id="ca-watchstar-sticky-header" tabindex="-1" data-event-name="watch-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-star mw-ui-icon-wikimedia-wikimedia-star"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-edit-sticky-header" tabindex="-1" data-event-name="wikitext-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-wikiText mw-ui-icon-wikimedia-wikimedia-wikiText"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-ve-edit-sticky-header" tabindex="-1" data-event-name="ve-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-edit mw-ui-icon-wikimedia-wikimedia-edit"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-viewsource-sticky-header" tabindex="-1" data-event-name="ve-edit-protected-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-editLock mw-ui-icon-wikimedia-wikimedia-editLock"></span> <span></span> </a> </div> <div class="vector-sticky-header-buttons"> <button class="cdx-button cdx-button--weight-quiet mw-interlanguage-selector" id="p-lang-btn-sticky-header" tabindex="-1" data-event-name="ui.dropdown-p-lang-btn-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-language mw-ui-icon-wikimedia-wikimedia-language"></span> <span>17 languages</span> </button> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive" id="ca-addsection-sticky-header" tabindex="-1" data-event-name="addsection-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbleAdd-progressive mw-ui-icon-wikimedia-speechBubbleAdd-progressive"></span> <span>Add topic</span> </a> </div> <div class="vector-sticky-header-icon-end"> <div class="vector-user-links"> </div> </div> </div> </div> </div> <div class="mw-portlet mw-portlet-dock-bottom emptyPortlet" id="p-dock-bottom"> <ul> </ul> </div> <script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-5886496d-7xwtc","wgBackendResponseTime":172,"wgPageParseReport":{"limitreport":{"cputime":"0.332","walltime":"0.556","ppvisitednodes":{"value":1074,"limit":1000000},"postexpandincludesize":{"value":48021,"limit":2097152},"templateargumentsize":{"value":494,"limit":2097152},"expansiondepth":{"value":8,"limit":100},"expensivefunctioncount":{"value":1,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":33577,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 305.199 1 -total"," 37.55% 114.614 1 Template:Reflist"," 30.55% 93.250 1 Template:Quantum_computing"," 30.28% 92.412 3 Template:Navbox"," 29.80% 90.964 1 Template:Short_description"," 29.54% 90.152 4 Template:Cite_journal"," 15.74% 48.036 2 Template:Pagetype"," 10.52% 32.112 3 Template:Main_other"," 4.69% 14.307 1 Template:SDcat"," 2.46% 7.496 2 Template:Icon"]},"scribunto":{"limitreport-timeusage":{"value":"0.178","limit":"10.000"},"limitreport-memusage":{"value":4832393,"limit":52428800}},"cachereport":{"origin":"mw-api-int.codfw.main-6c84f9f8cc-lgdxt","timestamp":"20250313221940","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Deutsch\u2013Jozsa algorithm","url":"https:\/\/en.wikipedia.org\/wiki\/Deutsch%E2%80%93Jozsa_algorithm","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1028209","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1028209","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":"2004-02-18T19:29:10Z","dateModified":"2025-03-13T22:19:32Z","headline":"quantum algorithm"}</script> </body> </html>

CINXE.COM

Deutsch–Jozsa algorithm - Wikipedia