Hadamard transform

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Hadamard transform - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"7a92ab22-7804-42ee-ba83-4d150bc27ad6","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Hadamard_transform","wgTitle":"Hadamard transform","wgCurRevisionId":1259857899,"wgRevisionId":1259857899,"wgArticleId":634765,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["CS1: long volume value","Articles with short description","Short description is different from Wikidata","Use American English from January 2019","All Wikipedia articles written in American English","Pages with French IPA","Articles to be expanded from April 2024","Quantum algorithms","Transforms"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Hadamard_transform","wgRelevantArticleId":634765, "wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[],"wgRestrictionMove":[],"wgRedirectedFrom":"Walsh_transform","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":30000,"wgInternalRedirectTargetUrl":"/wiki/Hadamard_transform","wgRelatedArticlesCompat":[],"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q1014065","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","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["mediawiki.action.view.redirect","ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips", "ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%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.5"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/a/aa/1010_0110_Walsh_spectrum_%28single_row%29.svg/1200px-1010_0110_Walsh_spectrum_%28single_row%29.svg.png"> <meta property="og:image:width" content="1200"> <meta property="og:image:height" content="780"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/a/aa/1010_0110_Walsh_spectrum_%28single_row%29.svg/800px-1010_0110_Walsh_spectrum_%28single_row%29.svg.png"> <meta property="og:image:width" content="800"> <meta property="og:image:height" content="520"> <meta property="og:image" content="https://upload.wikimedia.org/wikipedia/commons/thumb/a/aa/1010_0110_Walsh_spectrum_%28single_row%29.svg/640px-1010_0110_Walsh_spectrum_%28single_row%29.svg.png"> <meta property="og:image:width" content="640"> <meta property="og:image:height" content="416"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Hadamard transform - 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/Hadamard_transform"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Hadamard_transform&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/Hadamard_transform"> <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-Hadamard_transform rootpage-Hadamard_transform skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Hadamard+transform" 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=Hadamard+transform" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Hadamard+transform" 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=Hadamard+transform" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Definition" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Definition"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Definition</span> </div> </a> <ul id="toc-Definition-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Advantages_of_the_Walsh–Hadamard_transform" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Advantages_of_the_Walsh–Hadamard_transform"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Advantages of the Walsh–Hadamard transform</span> </div> </a> <button aria-controls="toc-Advantages_of_the_Walsh–Hadamard_transform-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Advantages of the Walsh–Hadamard transform subsection</span> </button> <ul id="toc-Advantages_of_the_Walsh–Hadamard_transform-sublist" class="vector-toc-list"> <li id="toc-Real" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Real"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>Real</span> </div> </a> <ul id="toc-Real-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-No_multiplication_is_required" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#No_multiplication_is_required"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.2</span> <span>No multiplication is required</span> </div> </a> <ul id="toc-No_multiplication_is_required-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Some_properties_are_similar_to_those_of_the_DFT" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Some_properties_are_similar_to_those_of_the_DFT"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.3</span> <span>Some properties are similar to those of the DFT</span> </div> </a> <ul id="toc-Some_properties_are_similar_to_those_of_the_DFT-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Relation_to_Fourier_transform" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Relation_to_Fourier_transform"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Relation to Fourier transform</span> </div> </a> <ul id="toc-Relation_to_Fourier_transform-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Computational_complexity" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Computational_complexity"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Computational complexity</span> </div> </a> <ul id="toc-Computational_complexity-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Quantum_computing_applications" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Quantum_computing_applications"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Quantum computing applications</span> </div> </a> <button aria-controls="toc-Quantum_computing_applications-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Quantum computing applications subsection</span> </button> <ul id="toc-Quantum_computing_applications-sublist" class="vector-toc-list"> <li id="toc-Hadamard_gate" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Hadamard_gate"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.1</span> <span>Hadamard gate</span> </div> </a> <ul id="toc-Hadamard_gate-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Hadamard_gate_operations" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Hadamard_gate_operations"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.2</span> <span>Hadamard gate operations</span> </div> </a> <ul id="toc-Hadamard_gate_operations-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Hadamard_transform_in_quantum_algorithms" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Hadamard_transform_in_quantum_algorithms"> <div class="vector-toc-text"> <span class="vector-toc-numb">5.3</span> <span>Hadamard transform in quantum algorithms</span> </div> </a> <ul id="toc-Hadamard_transform_in_quantum_algorithms-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Molecular_phylogenetics_(evolutionary_biology)_applications" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Molecular_phylogenetics_(evolutionary_biology)_applications"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>Molecular phylogenetics (evolutionary biology) applications</span> </div> </a> <ul id="toc-Molecular_phylogenetics_(evolutionary_biology)_applications-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Other_applications" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Other_applications"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>Other applications</span> </div> </a> <ul id="toc-Other_applications-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">8</span> <span>See also</span> </div> </a> <ul id="toc-See_also-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> <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">10</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Hadamard transform</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 10 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-10" 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">10 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/Transformada_de_Hadamard" title="Transformada de Hadamard – Catalan" lang="ca" hreflang="ca" data-title="Transformada de Hadamard" 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/Hadamard-Transformation" title="Hadamard-Transformation – German" lang="de" hreflang="de" data-title="Hadamard-Transformation" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%AA%D8%A8%D8%AF%DB%8C%D9%84_%D8%A2%D8%AF%D8%A7%D9%85%D8%A7%D8%B1" 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/Transform%C3%A9e_de_Hadamard" title="Transformée de Hadamard – French" lang="fr" hreflang="fr" data-title="Transformée de Hadamard" 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-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Trasformata_di_Hadamard" title="Trasformata di Hadamard – Italian" lang="it" hreflang="it" data-title="Trasformata di Hadamard" 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%A9%D7%A2%D7%A8_%D7%90%D7%93%D7%9E%D7%A8" 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-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E3%82%A2%E3%83%80%E3%83%9E%E3%83%BC%E3%83%AB%E5%A4%89%E6%8F%9B" 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-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D1%82%D0%B2%D0%BE%D1%80%D0%B5%D0%BD%D0%BD%D1%8F_%D0%90%D0%B4%D0%B0%D0%BC%D0%B0%D1%80%D0%B0" 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/Bi%E1%BA%BFn_%C4%91%E1%BB%95i_Hadamard" title="Biến đổi Hadamard – Vietnamese" lang="vi" hreflang="vi" data-title="Biến đổi Hadamard" 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/%E9%98%BF%E8%BE%BE%E9%A9%AC%E5%8F%98%E6%8D%A2" 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/Q1014065#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/Hadamard_transform" 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:Hadamard_transform" 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/Hadamard_transform"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Hadamard_transform&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=Hadamard_transform&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/Hadamard_transform"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Hadamard_transform&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=Hadamard_transform&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/Hadamard_transform" 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/Hadamard_transform" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Hadamard_transform&oldid=1259857899" 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=Hadamard_transform&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=Hadamard_transform&id=1259857899&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%2FHadamard_transform"><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%2FHadamard_transform"><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=Hadamard_transform&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=Hadamard_transform&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/Q1014065" 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"><span class="mw-redirectedfrom">(Redirected from <a href="/w/index.php?title=Walsh_transform&redirect=no" class="mw-redirect" title="Walsh transform">Walsh transform</a>)</span></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">Involutive change of basis in linear algebra</div> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">"Walsh transform" redirects here. Not to be confused with <a href="/wiki/Walsh_matrix" title="Walsh matrix">Walsh matrix</a>.</div> <p class="mw-empty-elt"> </p> <figure typeof="mw:File/Thumb"><a href="/wiki/File:1010_0110_Walsh_spectrum_(single_row).svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/1010_0110_Walsh_spectrum_%28single_row%29.svg/300px-1010_0110_Walsh_spectrum_%28single_row%29.svg.png" decoding="async" width="300" height="195" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/1010_0110_Walsh_spectrum_%28single_row%29.svg/450px-1010_0110_Walsh_spectrum_%28single_row%29.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/aa/1010_0110_Walsh_spectrum_%28single_row%29.svg/600px-1010_0110_Walsh_spectrum_%28single_row%29.svg.png 2x" data-file-width="354" data-file-height="230" /></a><figcaption>The <a href="/wiki/Matrix_multiplication" title="Matrix multiplication">product</a> of a <a href="/wiki/Boolean_function" title="Boolean function">Boolean function</a> and a Hadamard matrix is its <a href="/w/index.php?title=Walsh_spectrum&action=edit&redlink=1" class="new" title="Walsh spectrum (page does not exist)">Walsh spectrum</a>:<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><br />(1, 0, 1, 0, 0, 1, 1, 0) × H(8) = (4, 2, 0, −2, 0, 2, 0, 2)</figcaption></figure> <figure typeof="mw:File/Thumb"><a href="/wiki/File:1010_0110_Walsh_spectrum_(fast_WHT).svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/5/58/1010_0110_Walsh_spectrum_%28fast_WHT%29.svg/300px-1010_0110_Walsh_spectrum_%28fast_WHT%29.svg.png" decoding="async" width="300" height="143" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/5/58/1010_0110_Walsh_spectrum_%28fast_WHT%29.svg/450px-1010_0110_Walsh_spectrum_%28fast_WHT%29.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/5/58/1010_0110_Walsh_spectrum_%28fast_WHT%29.svg/600px-1010_0110_Walsh_spectrum_%28fast_WHT%29.svg.png 2x" data-file-width="1540" data-file-height="736" /></a><figcaption><a href="/wiki/Fast_Walsh%E2%80%93Hadamard_transform" title="Fast Walsh–Hadamard transform">Fast Walsh–Hadamard transform</a>, a faster way to calculate the Walsh spectrum of (1, 0, 1, 0, 0, 1, 1, 0).</figcaption></figure> <figure typeof="mw:File/Thumb"><a href="/wiki/File:1010_0110_Walsh_spectrum_(polynomial).svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/5/5d/1010_0110_Walsh_spectrum_%28polynomial%29.svg/300px-1010_0110_Walsh_spectrum_%28polynomial%29.svg.png" decoding="async" width="300" height="120" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/5/5d/1010_0110_Walsh_spectrum_%28polynomial%29.svg/450px-1010_0110_Walsh_spectrum_%28polynomial%29.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/5/5d/1010_0110_Walsh_spectrum_%28polynomial%29.svg/600px-1010_0110_Walsh_spectrum_%28polynomial%29.svg.png 2x" data-file-width="773" data-file-height="308" /></a><figcaption>The original function can be expressed by means of its Walsh spectrum as an arithmetical polynomial.</figcaption></figure> <p>The <b>Hadamard transform</b> (also known as the <b>Walsh–Hadamard transform</b>, <b>Hadamard–Rademacher–Walsh transform</b>, <b>Walsh transform</b>, or <b>Walsh–Fourier transform</b>) is an example of a generalized class of <a href="/wiki/Fourier_transform" title="Fourier transform">Fourier transforms</a>. It performs an <a href="/wiki/Orthogonal_matrix" title="Orthogonal matrix">orthogonal</a>, <a href="/wiki/Symmetric_matrix" title="Symmetric matrix">symmetric</a>, <a href="/wiki/Involution_(mathematics)" title="Involution (mathematics)">involutive</a>, <a href="/wiki/Linear_operator" class="mw-redirect" title="Linear operator">linear operation</a> on <span class="texhtml">2<sup><i>m</i></sup></span> <a href="/wiki/Real_number" title="Real number">real numbers</a> (or <a href="/wiki/Complex_number" title="Complex number">complex</a>, or <a href="/wiki/Hypercomplex_number" title="Hypercomplex number">hypercomplex numbers</a>, although the Hadamard matrices themselves are purely real). </p><p>The Hadamard transform can be regarded as being built out of size-2 <a href="/wiki/Discrete_Fourier_transform" title="Discrete Fourier transform">discrete Fourier transforms</a> (DFTs), and is in fact equivalent to a multidimensional DFT of size <span class="texhtml">2 × 2 × ⋯ × 2 × 2</span>.<sup id="cite_ref-kunz_2-0" class="reference"><a href="#cite_note-kunz-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> It decomposes an arbitrary input vector into a superposition of <a href="/wiki/Walsh_function" title="Walsh function">Walsh functions</a>. </p><p>The transform is named for the <a href="/wiki/France" title="France">French</a> <a href="/wiki/Mathematician" title="Mathematician">mathematician</a> <a href="/wiki/Jacques_Hadamard" title="Jacques Hadamard">Jacques Hadamard</a> (<style data-mw-deduplicate="TemplateStyles:r1177148991">.mw-parser-output .IPA-label-small{font-size:85%}.mw-parser-output .references .IPA-label-small,.mw-parser-output .infobox .IPA-label-small,.mw-parser-output .navbox .IPA-label-small{font-size:100%}</style><span class="IPA-label IPA-label-small">French:</span> <span class="IPA nowrap" lang="fr-Latn-fonipa"><a href="/wiki/Help:IPA/French" title="Help:IPA/French">[adamaʁ]</a></span>), the German-American mathematician <a href="/wiki/Hans_Rademacher" title="Hans Rademacher">Hans Rademacher</a>, and the American mathematician <a href="/wiki/Joseph_L._Walsh" title="Joseph L. Walsh">Joseph L. Walsh</a>. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Hadamard_transform&action=edit&section=1" title="Edit section: Definition"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The Hadamard transform <i>H</i><sub><i>m</i></sub> is a 2<sup><i>m</i></sup> × 2<sup><i>m</i></sup> matrix, the <a href="/wiki/Hadamard_matrix" title="Hadamard matrix">Hadamard matrix</a> (scaled by a normalization factor), that transforms 2<sup><i>m</i></sup> real numbers <i>x</i><sub><i>n</i></sub> into 2<sup><i>m</i></sup> real numbers <i>X</i><sub><i>k</i></sub>. The Hadamard transform can be defined in two ways: <a href="/wiki/Recursively" class="mw-redirect" title="Recursively">recursively</a>, or by using the <a href="/wiki/Binary_numeral_system" class="mw-redirect" title="Binary numeral system">binary</a> (<a href="/wiki/Base_(exponentiation)" title="Base (exponentiation)">base</a>-2) representation of the indices <i>n</i> and <i>k</i>. </p><p>Recursively, we define the 1 × 1 Hadamard transform <i>H</i><sub>0</sub> by the <a href="/wiki/Identity_matrix" title="Identity matrix">identity</a> <i>H</i><sub>0</sub> = 1, and then define <i>H</i><sub><i>m</i></sub> for <i>m</i> > 0 by: <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_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msub> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msqrt> <mn>2</mn> </msqrt> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mtd> <mtd> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mtd> </mtr> <mtr> <mtd> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mtd> <mtd> <mo>−</mo> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mtd> </mtr> </mtable> <mo>)</mo> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3cb8264a319887b52db7ec2a2ba508659c8b2aad" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:30.356ex; height:6.509ex;" alt="{\displaystyle H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}}"></span> where the 1/<span class="nowrap">√<span style="border-top:1px solid; padding:0 0.1em;">2</span></span> is a normalization that is sometimes omitted. </p><p>For <i>m</i> > 1, we can also define <i>H</i><sub><i>m</i></sub> by: <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_{m}=H_{1}\otimes H_{m-1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msub> <mo>=</mo> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>⊗</mo> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle H_{m}=H_{1}\otimes H_{m-1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/127a9c5b3c0ca6c50d4445435b752b810a537554" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:18.237ex; height:2.509ex;" alt="{\displaystyle H_{m}=H_{1}\otimes H_{m-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 \otimes }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo>⊗</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \otimes }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/de29098f5a34ee296a505681a0d5e875070f2aea" 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 \otimes }"></span> represents the <a href="/wiki/Kronecker_product" title="Kronecker product">Kronecker product</a>. Thus, other than this normalization factor, the Hadamard matrices are made up entirely of 1 and −1. </p><p>Equivalently, we can define the Hadamard matrix by its (<i>k</i>, <i>n</i>)-th entry by writing <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}k&=\sum _{i=0}^{m-1}{k_{i}2^{i}}=k_{m-1}2^{m-1}+k_{m-2}2^{m-2}+\dots +k_{1}2+k_{0}\\n&=\sum _{i=0}^{m-1}{n_{i}2^{i}}=n_{m-1}2^{m-1}+n_{m-2}2^{m-2}+\dots +n_{1}2+n_{0}\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> <mi>k</mi> </mtd> <mtd> <mi></mi> <mo>=</mo> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msup> </mrow> <mo>=</mo> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>+</mo> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mo>−</mo> <mn>2</mn> </mrow> </msub> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mo>−</mo> <mn>2</mn> </mrow> </msup> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mn>2</mn> <mo>+</mo> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mtd> </mtr> <mtr> <mtd> <mi>n</mi> </mtd> <mtd> <mi></mi> <mo>=</mo> <munderover> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>=</mo> <mn>0</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <mrow class="MJX-TeXAtom-ORD"> <msub> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msup> </mrow> <mo>=</mo> <msub> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mo>−</mo> <mn>1</mn> </mrow> </msub> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo>+</mo> <msub> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mo>−</mo> <mn>2</mn> </mrow> </msub> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mo>−</mo> <mn>2</mn> </mrow> </msup> <mo>+</mo> <mo>⋯</mo> <mo>+</mo> <msub> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mn>2</mn> <mo>+</mo> <msub> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}k&=\sum _{i=0}^{m-1}{k_{i}2^{i}}=k_{m-1}2^{m-1}+k_{m-2}2^{m-2}+\dots +k_{1}2+k_{0}\\n&=\sum _{i=0}^{m-1}{n_{i}2^{i}}=n_{m-1}2^{m-1}+n_{m-2}2^{m-2}+\dots +n_{1}2+n_{0}\end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/30777a2be6cc4a65b711524c4738d0c1d8839995" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.838ex; width:56.792ex; height:14.843ex;" alt="{\displaystyle {\begin{aligned}k&=\sum _{i=0}^{m-1}{k_{i}2^{i}}=k_{m-1}2^{m-1}+k_{m-2}2^{m-2}+\dots +k_{1}2+k_{0}\\n&=\sum _{i=0}^{m-1}{n_{i}2^{i}}=n_{m-1}2^{m-1}+n_{m-2}2^{m-2}+\dots +n_{1}2+n_{0}\end{aligned}}}"></span> </p><p>where the <i>k</i><sub><i>j</i></sub> and <i>n</i><sub><i>j</i></sub> are the bit elements (0 or 1) of <i>k</i> and <i>n</i>, respectively. Note that for the element in the top left corner, we define: <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=n=0}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> <mo>=</mo> <mi>n</mi> <mo>=</mo> <mn>0</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k=n=0}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e0492228dd022ba37c1f4f106fe4502cda5030eb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.965ex; height:2.176ex;" alt="{\displaystyle k=n=0}"></span>. In this case, 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 (H_{m})_{k,n}={\frac {1}{2^{m/2}}}(-1)^{\sum _{j}k_{j}n_{j}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msub> <msub> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> <mo>,</mo> <mi>n</mi> </mrow> </msub> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> </mrow> </msup> </mfrac> </mrow> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </munder> <msub> <mi>k</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> <msub> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>j</mi> </mrow> </msub> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (H_{m})_{k,n}={\frac {1}{2^{m/2}}}(-1)^{\sum _{j}k_{j}n_{j}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a2fef01db7195a2a526ac1d253992727f97ac1a2" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:27.484ex; height:5.843ex;" alt="{\displaystyle (H_{m})_{k,n}={\frac {1}{2^{m/2}}}(-1)^{\sum _{j}k_{j}n_{j}}}"></span> </p><p>This is exactly the multidimensional <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="{\textstyle 2\times 2\times \cdots \times 2\times 2}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mn>2</mn> <mo>×</mo> <mn>2</mn> <mo>×</mo> <mo>⋯</mo> <mo>×</mo> <mn>2</mn> <mo>×</mo> <mn>2</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle 2\times 2\times \cdots \times 2\times 2}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8464c1417e447c98669c1e31386fc630f10a3c86" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:18.735ex; height:2.176ex;" alt="{\textstyle 2\times 2\times \cdots \times 2\times 2}"></span> DFT, normalized to be <a href="/wiki/Unitary_operator" title="Unitary operator">unitary</a>, if the inputs and outputs are regarded as multidimensional arrays indexed by the <i>n</i><sub><i>j</i></sub> and <i>k</i><sub><i>j</i></sub>, respectively. </p><p>Some examples of the Hadamard matrices follow. <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}H_{0}&=+{\begin{pmatrix}1\end{pmatrix}}\\[5pt]H_{1}&={\frac {1}{\sqrt {2}}}\left({\begin{array}{rr}1&1\\1&-1\end{array}}\right)\\[5pt]H_{2}&={\frac {1}{2}}\left({\begin{array}{rrrr}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{array}}\right)\\[5pt]H_{3}&={\frac {1}{2^{3/2}}}\left({\begin{array}{rrrrrrrr}1&1&1&1&1&1&1&1\\1&-1&1&-1&1&-1&1&-1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&1&1&1&-1&-1&-1&-1\\1&-1&1&-1&-1&1&-1&1\\1&1&-1&-1&-1&-1&1&1\\1&-1&-1&1&-1&1&1&-1\end{array}}\right)\\[5pt](H_{n})_{i,j}&={\frac {1}{2^{n/2}}}(-1)^{i\cdot j}\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="0.8em 0.8em 0.8em 0.8em 0.3em" columnspacing="0em 2em 0em 2em 0em 2em 0em 2em 0em 2em 0em" displaystyle="true"> <mtr> <mtd> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msub> </mtd> <mtd> <mi></mi> <mo>=</mo> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>1</mn> </mtd> </mtr> </mtable> <mo>)</mo> </mrow> </mrow> </mtd> </mtr> <mtr> <mtd> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mtd> <mtd> <mi></mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msqrt> <mn>2</mn> </msqrt> </mfrac> </mrow> <mrow> <mo>(</mo> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right right" rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> </mtr> </mtable> </mrow> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mtd> <mtd> <mi></mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mrow> <mrow> <mo>(</mo> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right right right right" rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> </mtable> </mrow> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msub> </mtd> <mtd> <mi></mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> </mrow> </msup> </mfrac> </mrow> <mrow> <mo>(</mo> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right right right right right right right right" rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> </mtr> </mtable> </mrow> <mo>)</mo> </mrow> </mtd> </mtr> <mtr> <mtd> <mo stretchy="false">(</mo> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>,</mo> <mi>j</mi> </mrow> </msub> </mtd> <mtd> <mi></mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> </mrow> </msup> </mfrac> </mrow> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>⋅</mo> <mi>j</mi> </mrow> </msup> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}H_{0}&=+{\begin{pmatrix}1\end{pmatrix}}\\[5pt]H_{1}&={\frac {1}{\sqrt {2}}}\left({\begin{array}{rr}1&1\\1&-1\end{array}}\right)\\[5pt]H_{2}&={\frac {1}{2}}\left({\begin{array}{rrrr}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{array}}\right)\\[5pt]H_{3}&={\frac {1}{2^{3/2}}}\left({\begin{array}{rrrrrrrr}1&1&1&1&1&1&1&1\\1&-1&1&-1&1&-1&1&-1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&1&1&1&-1&-1&-1&-1\\1&-1&1&-1&-1&1&-1&1\\1&1&-1&-1&-1&-1&1&1\\1&-1&-1&1&-1&1&1&-1\end{array}}\right)\\[5pt](H_{n})_{i,j}&={\frac {1}{2^{n/2}}}(-1)^{i\cdot j}\end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5ca7686d523e9c65ce1930978cfa1e5bf718196b" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -28.535ex; margin-bottom: -0.303ex; width:58.86ex; height:58.843ex;" alt="{\displaystyle {\begin{aligned}H_{0}&=+{\begin{pmatrix}1\end{pmatrix}}\\[5pt]H_{1}&={\frac {1}{\sqrt {2}}}\left({\begin{array}{rr}1&1\\1&-1\end{array}}\right)\\[5pt]H_{2}&={\frac {1}{2}}\left({\begin{array}{rrrr}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{array}}\right)\\[5pt]H_{3}&={\frac {1}{2^{3/2}}}\left({\begin{array}{rrrrrrrr}1&1&1&1&1&1&1&1\\1&-1&1&-1&1&-1&1&-1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&1&1&1&-1&-1&-1&-1\\1&-1&1&-1&-1&1&-1&1\\1&1&-1&-1&-1&-1&1&1\\1&-1&-1&1&-1&1&1&-1\end{array}}\right)\\[5pt](H_{n})_{i,j}&={\frac {1}{2^{n/2}}}(-1)^{i\cdot j}\end{aligned}}}"></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 i\cdot j}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>i</mi> <mo>⋅</mo> <mi>j</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle i\cdot j}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b58a90cbb07dfff72365437a6790811fe6ca2838" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.44ex; height:2.509ex;" alt="{\displaystyle i\cdot j}"></span> is the bitwise <a href="/wiki/Dot_product" title="Dot product">dot product</a> of the binary representations of the numbers i and j. For example, 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="{\textstyle n\;\geq \;2}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mi>n</mi> <mspace width="thickmathspace" /> <mo>≥</mo> <mspace width="thickmathspace" /> <mn>2</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle n\;\geq \;2}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/98095de3749e58db86a0fb3acb25856f1d7a6b24" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.946ex; height:2.343ex;" alt="{\textstyle n\;\geq \;2}"></span>, then <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_{n})_{3,2}\;=\;(-1)^{3\cdot 2}\;=\;(-1)^{(1,1)\cdot (1,0)}\;=\;(-1)^{1+0}\;=\;(-1)^{1}\;=\;-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> <mo>,</mo> <mn>2</mn> </mrow> </msub> <mspace width="thickmathspace" /> <mo>=</mo> <mspace width="thickmathspace" /> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> <mo>⋅</mo> <mn>2</mn> </mrow> </msup> <mspace width="thickmathspace" /> <mo>=</mo> <mspace width="thickmathspace" /> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">(</mo> <mn>1</mn> <mo>,</mo> <mn>1</mn> <mo stretchy="false">)</mo> <mo>⋅</mo> <mo stretchy="false">(</mo> <mn>1</mn> <mo>,</mo> <mn>0</mn> <mo stretchy="false">)</mo> </mrow> </msup> <mspace width="thickmathspace" /> <mo>=</mo> <mspace width="thickmathspace" /> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> <mo>+</mo> <mn>0</mn> </mrow> </msup> <mspace width="thickmathspace" /> <mo>=</mo> <mspace width="thickmathspace" /> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msup> <mspace width="thickmathspace" /> <mo>=</mo> <mspace width="thickmathspace" /> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (H_{n})_{3,2}\;=\;(-1)^{3\cdot 2}\;=\;(-1)^{(1,1)\cdot (1,0)}\;=\;(-1)^{1+0}\;=\;(-1)^{1}\;=\;-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0dbf19e7a366740c93ca0179c343c5602fb7d8ea" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:65.32ex; height:3.509ex;" alt="{\displaystyle (H_{n})_{3,2}\;=\;(-1)^{3\cdot 2}\;=\;(-1)^{(1,1)\cdot (1,0)}\;=\;(-1)^{1+0}\;=\;(-1)^{1}\;=\;-1}"></span>, agreeing with the above (ignoring the overall constant). Note that the first row, first column element of the matrix is denoted by <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle (H_{n})_{0,0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mo stretchy="false">(</mo> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <msub> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> <mo>,</mo> <mn>0</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle (H_{n})_{0,0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b91c1f4dea8d06d74ba74045535c871972ee8a06" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.293ex; height:3.009ex;" alt="{\textstyle (H_{n})_{0,0}}"></span>. </p><p><i>H</i><sub>1</sub> is precisely the size-2 DFT. It can also be regarded as the <a href="/wiki/Fourier_transform" title="Fourier transform">Fourier transform</a> on the two-element <i>additive</i> group of <b>Z</b>/(2). </p><p>The rows of the Hadamard matrices are the <a href="/wiki/Walsh_function" title="Walsh function">Walsh functions</a>. </p> <style data-mw-deduplicate="TemplateStyles:r1251242444">.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}</style><table class="box-Missing_information plainlinks metadata ambox ambox-content" role="presentation"><tbody><tr><td class="mbox-image"><div class="mbox-image-div"><span typeof="mw:File"><a href="/wiki/File:Wiki_letter_w.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/en/thumb/6/6c/Wiki_letter_w.svg/44px-Wiki_letter_w.svg.png" decoding="async" width="44" height="44" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/en/thumb/6/6c/Wiki_letter_w.svg/66px-Wiki_letter_w.svg.png 1.5x, //upload.wikimedia.org/wikipedia/en/thumb/6/6c/Wiki_letter_w.svg/88px-Wiki_letter_w.svg.png 2x" data-file-width="44" data-file-height="44" /></a></span></div></td><td class="mbox-text"><div class="mbox-text-span">This section <b>is missing information</b> about ordering variants of the Hadamard matrices: sequency (<a href="/wiki/Walsh_matrix" title="Walsh matrix">Walsh matrix</a>), Hadamard, and dyadic.<span class="hide-when-compact"> Please expand the section to include this information. Further details may exist on the <a href="/wiki/Talk:Hadamard_transform" title="Talk:Hadamard transform">talk page</a>.</span> <span class="date-container"><i>(<span class="date">April 2024</span>)</i></span></div></td></tr></tbody></table> <div class="mw-heading mw-heading2"><h2 id="Advantages_of_the_Walsh–Hadamard_transform"><span id="Advantages_of_the_Walsh.E2.80.93Hadamard_transform"></span>Advantages of the Walsh–Hadamard transform</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Hadamard_transform&action=edit&section=2" title="Edit section: Advantages of the Walsh–Hadamard transform"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Real">Real</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Hadamard_transform&action=edit&section=3" title="Edit section: Real"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>According to the above definition of matrix <i>H</i>, here we let <i>H</i> = <i>H</i>[<i>m</i>,<i>n</i>] <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[m,n]={\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>H</mi> <mo stretchy="false">[</mo> <mi>m</mi> <mo>,</mo> <mi>n</mi> <mo stretchy="false">]</mo> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> </mtr> </mtable> <mo>)</mo> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle H[m,n]={\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1495340ecc82d26d794063788bb5b364a53e1963" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:21.553ex; height:6.176ex;" alt="{\displaystyle H[m,n]={\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}"></span> </p><p>In the Walsh transform, only 1 and −1 will appear in the matrix. The numbers 1 and −1 are real numbers so there is no need to perform a <a href="/wiki/Complex_number" title="Complex number">complex number</a> calculation. </p> <div class="mw-heading mw-heading3"><h3 id="No_multiplication_is_required">No multiplication is required</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Hadamard_transform&action=edit&section=4" title="Edit section: No multiplication is required"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The DFT needs irrational multiplication, while the Hadamard transform does not. Even rational multiplication is not needed, since sign flips is all it takes. </p> <div class="mw-heading mw-heading3"><h3 id="Some_properties_are_similar_to_those_of_the_DFT">Some properties are similar to those of the DFT</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Hadamard_transform&action=edit&section=5" title="Edit section: Some properties are similar to those of the DFT"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In the Walsh transform matrix, all entries in the first row (and column) are equal to 1. </p><p>sign change calculated 1st row 0 </p><p>second row=1. </p><p>third row =2. </p><p>. </p><p>. </p><p>. </p><p>eighth row=7.<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[m,n]=\left({\begin{array}{rrrrrrrr}1&1&1&1&1&1&1&1\\1&1&1&1&-1&-1&-1&-1\\1&1&-1&-1&-1&-1&1&1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&-1&-1&1&-1&1&1&-1\\1&-1&1&-1&-1&1&-1&1\\1&-1&1&-1&1&-1&1&-1\end{array}}\right)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>H</mi> <mo stretchy="false">[</mo> <mi>m</mi> <mo>,</mo> <mi>n</mi> <mo stretchy="false">]</mo> <mo>=</mo> <mrow> <mo>(</mo> <mrow class="MJX-TeXAtom-ORD"> <mtable columnalign="right right right right right right right right" rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> </mtr> </mtable> </mrow> <mo>)</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle H[m,n]=\left({\begin{array}{rrrrrrrr}1&1&1&1&1&1&1&1\\1&1&1&1&-1&-1&-1&-1\\1&1&-1&-1&-1&-1&1&1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&-1&-1&1&-1&1&1&-1\\1&-1&1&-1&-1&1&-1&1\\1&-1&1&-1&1&-1&1&-1\end{array}}\right)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4a4444f9dc6ce63ed6ff6f74049037fe8212b277" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -12.171ex; width:53.958ex; height:25.509ex;" alt="{\displaystyle H[m,n]=\left({\begin{array}{rrrrrrrr}1&1&1&1&1&1&1&1\\1&1&1&1&-1&-1&-1&-1\\1&1&-1&-1&-1&-1&1&1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&-1&-1&1&-1&1&1&-1\\1&-1&1&-1&-1&1&-1&1\\1&-1&1&-1&1&-1&1&-1\end{array}}\right)}"></span> </p><p>Discrete Fourier transform： <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 e^{-j2\pi mn/N}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mi>e</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mi>j</mi> <mn>2</mn> <mi>π</mi> <mi>m</mi> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mi>N</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle e^{-j2\pi mn/N}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c96cb30bbfe308d73f54b4a21ff7ab0a9c69ad5a" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.746ex; height:2.843ex;" alt="{\displaystyle e^{-j2\pi mn/N}}"></span> </p><p>In discrete Fourier transform, when m equal to zeros (mean first row), the result of DFT also is 1. At the second row, although it is different from the first row we can observe a characteristic of the matrix that the signal in the first raw matrix is low frequency and it will increase the frequency at second row, increase more frequency until the last row. </p><p>If we calculate zero crossing: </p> <pre>First row = 0 zero crossing Second row = 1 zero crossing Third row = 2 zero crossings ⋮ Eight row = 7 zero crossings </pre> <div class="mw-heading mw-heading2"><h2 id="Relation_to_Fourier_transform">Relation to Fourier transform</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Hadamard_transform&action=edit&section=6" title="Edit section: Relation to Fourier transform"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The Hadamard transform is in fact equivalent to a multidimensional DFT of size <span class="texhtml">2 × 2 × ⋯ × 2 × 2</span>.<sup id="cite_ref-kunz_2-1" class="reference"><a href="#cite_note-kunz-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p><p>Another approach is to view the Hadamard transform as a Fourier transform on the <a href="/wiki/Boolean_group" class="mw-redirect" title="Boolean group">Boolean group</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 (\mathbb {Z} /2\mathbb {Z} )^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5686cb9b950687c6d056088cb2314829751e9ac9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.453ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}"></span>.<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> <sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> Using the <a href="/wiki/Fourier_transform_on_finite_groups" title="Fourier transform on finite groups">Fourier transform on finite (abelian) groups</a>, the Fourier transform of a 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\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>f</mi> <mo>:</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo stretchy="false">→</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">C</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle f\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/87ad971168e93a4fc892f1d36a975c0323a00db8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.058ex; height:2.843ex;" alt="{\displaystyle f\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} }"></span> is 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 {\widehat {f}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>f</mi> <mo>^</mo> </mover> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\widehat {f}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/153a4a4d50ef7099fc5f8804e34dccc539f08743" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-right: -0.019ex; width:1.79ex; height:3.343ex;" alt="{\displaystyle {\widehat {f}}}"></span> defined by <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 {\widehat {f}}(\chi )=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a){\bar {\chi }}(a)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>f</mi> <mo>^</mo> </mover> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>χ</mi> <mo stretchy="false">)</mo> <mo>=</mo> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>a</mi> <mo>∈</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mrow> </munder> <mi>f</mi> <mo stretchy="false">(</mo> <mi>a</mi> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>χ</mi> <mo stretchy="false">¯</mo> </mover> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>a</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\widehat {f}}(\chi )=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a){\bar {\chi }}(a)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e0ae2e468d0b11af319593d787caff24d0005726" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.671ex; width:25.379ex; height:6.343ex;" alt="{\displaystyle {\widehat {f}}(\chi )=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a){\bar {\chi }}(a)}"></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 \chi }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>χ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \chi }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/656111758322ace96d80a9371771aa6d3de25437" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.455ex; height:2.009ex;" alt="{\displaystyle \chi }"></span> is a <a href="/wiki/Character_(mathematics)" title="Character (mathematics)">character</a> 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 (\mathbb {Z} /2\mathbb {Z} )^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5686cb9b950687c6d056088cb2314829751e9ac9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.453ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}"></span>. Each character has the form <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 \chi _{r}(a)=(-1)^{a\cdot r}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>χ</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>r</mi> </mrow> </msub> <mo stretchy="false">(</mo> <mi>a</mi> <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>a</mi> <mo>⋅</mo> <mi>r</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \chi _{r}(a)=(-1)^{a\cdot r}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ed52f6d2f28c049287b365478b9b9e104138dd14" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.647ex; height:2.843ex;" alt="{\displaystyle \chi _{r}(a)=(-1)^{a\cdot r}}"></span> for some <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>r</mi> <mo>∈</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4c3884081220a4fba0294516c9c3989dcc84c1cb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.343ex; height:2.843ex;" alt="{\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}}"></span>, where the multiplication is the boolean dot product on bit strings, so we can identify the input 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 {\widehat {f}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>f</mi> <mo>^</mo> </mover> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\widehat {f}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/153a4a4d50ef7099fc5f8804e34dccc539f08743" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-right: -0.019ex; width:1.79ex; height:3.343ex;" alt="{\displaystyle {\widehat {f}}}"></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 r\in (\mathbb {Z} /2\mathbb {Z} )^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>r</mi> <mo>∈</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4c3884081220a4fba0294516c9c3989dcc84c1cb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.343ex; height:2.843ex;" alt="{\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}}"></span> (<a href="/wiki/Pontryagin_duality" title="Pontryagin duality">Pontryagin duality</a>) and define <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 {\widehat {f}}\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>f</mi> <mo>^</mo> </mover> </mrow> </mrow> <mo>:</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mo stretchy="false">→</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">C</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\widehat {f}}\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4b7a146628e920d517983097b06d88f63772819d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.55ex; height:3.509ex;" alt="{\displaystyle {\widehat {f}}\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} }"></span> by <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 {\widehat {f}}(r)=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a)(-1)^{r\cdot a}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>f</mi> <mo>^</mo> </mover> </mrow> </mrow> <mo stretchy="false">(</mo> <mi>r</mi> <mo stretchy="false">)</mo> <mo>=</mo> <munder> <mo>∑</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>a</mi> <mo>∈</mo> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mrow> </munder> <mi>f</mi> <mo stretchy="false">(</mo> <mi>a</mi> <mo stretchy="false">)</mo> <mo stretchy="false">(</mo> <mo>−</mo> <mn>1</mn> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>r</mi> <mo>⋅</mo> <mi>a</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\widehat {f}}(r)=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a)(-1)^{r\cdot a}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/fb691372c5e3fb5a873b18cfc17b41240a801f41" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.671ex; width:27.559ex; height:6.343ex;" alt="{\displaystyle {\widehat {f}}(r)=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a)(-1)^{r\cdot a}}"></span> </p><p>This is the Hadamard transform 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>, considering the input 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 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> 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 {\widehat {f}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mover> <mi>f</mi> <mo>^</mo> </mover> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\widehat {f}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/153a4a4d50ef7099fc5f8804e34dccc539f08743" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-right: -0.019ex; width:1.79ex; height:3.343ex;" alt="{\displaystyle {\widehat {f}}}"></span> as boolean strings. </p><p>In terms of the above formulation where the Hadamard transform multiplies a vector 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 2^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8226f30650ee4fe4e640c6d2798127e80e9c160d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}"></span> complex numbers <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}"></span> on the left by the Hadamard matrix <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle H_{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e63458b04288bbe116a9a8037dfae0b36b2c639a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.15ex; height:2.509ex;" alt="{\displaystyle H_{n}}"></span> the equivalence is seen by taking <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> to take as input the bit string corresponding to the index of an element 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 v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}"></span>, and having <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> output the corresponding element 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 v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}"></span>. </p><p>Compare this to the usual <a href="/wiki/Discrete_Fourier_transform" title="Discrete Fourier transform">discrete Fourier transform</a> which when applied to a vector <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 v}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>v</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle v}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e07b00e7fc0847fbd16391c778d65bc25c452597" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}"></span> of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8226f30650ee4fe4e640c6d2798127e80e9c160d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}"></span> complex numbers instead uses characters of the <a href="/wiki/Cyclic_group" title="Cyclic group">cyclic group</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 \mathbb {Z} /2^{n}\mathbb {Z} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/28526fdf9d9d5ac32c95d34e9414ef6db8642b31" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.644ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }"></span>. </p> <div class="mw-heading mw-heading2"><h2 id="Computational_complexity">Computational complexity</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Hadamard_transform&action=edit&section=7" title="Edit section: Computational complexity"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In the classical domain, the Hadamard transform can be computed in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\log n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n\log n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/560dfdce0353a330e03e4b3e0b7ca6e484bb40fb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.535ex; height:2.509ex;" alt="{\displaystyle n\log n}"></span> operations (<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=2^{m}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>=</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>m</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n=2^{m}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ab14407b66fdd78b64c1eeec8dff77a7df81b101" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.331ex; height:2.343ex;" alt="{\displaystyle n=2^{m}}"></span>), using the <a href="/wiki/Fast_Hadamard_transform" class="mw-redirect" title="Fast Hadamard transform">fast Hadamard transform</a> algorithm. </p><p>In the quantum domain, the Hadamard transform can be computed in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e66384bc40452c5452f33563fe0e27e803b0cc21" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}"></span> time, as it is a <a href="/wiki/Quantum_logic_gate" title="Quantum logic gate">quantum logic gate</a> that can be <a href="/wiki/Quantum_logic_gate#Parallel_gates" title="Quantum logic gate">parallelized</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Quantum_computing_applications">Quantum computing applications</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Hadamard_transform&action=edit&section=8" title="Edit section: Quantum computing applications"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The Hadamard transform is used extensively in <a href="/wiki/Quantum_computing" title="Quantum computing">quantum computing</a>. The 2 × 2 Hadamard transform <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle H_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/4d4d9a872a55b209f2eb7cc23a71e5e1541bd1f4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.985ex; height:2.509ex;" alt="{\displaystyle H_{1}}"></span> is the <a href="/wiki/Quantum_logic_gate" title="Quantum logic gate">quantum logic gate</a> known as the Hadamard gate, and the application of a Hadamard gate to each qubit of an <span class="nowrap"><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 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>-qubit</span> register in parallel is equivalent to the Hadamard transform <span class="nowrap"><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle H_{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e63458b04288bbe116a9a8037dfae0b36b2c639a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.15ex; height:2.509ex;" alt="{\displaystyle H_{n}}"></span>.</span> </p> <div class="mw-heading mw-heading3"><h3 id="Hadamard_gate">Hadamard gate</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Hadamard_transform&action=edit&section=9" title="Edit section: Hadamard gate"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1236090951"><div role="note" class="hatnote navigation-not-searchable">Further information: <a href="/wiki/Quantum_gate#Hadamard_gate" class="mw-redirect" title="Quantum gate">Quantum gate § Hadamard gate</a></div> <p>In quantum computing, the Hadamard gate is a one-<a href="/wiki/Qubit" title="Qubit">qubit</a> <a href="/wiki/Rotation" title="Rotation">rotation</a>, mapping the qubit-basis states <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 |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> to two superposition states with equal weight of the computational <a href="/wiki/Basis_(linear_algebra)" title="Basis (linear algebra)">basis</a> states <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 |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>. Usually the phases are chosen so that <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={\frac {|0\rangle +|1\rangle }{\sqrt {2}}}\langle 0|+{\frac {|0\rangle -|1\rangle }{\sqrt {2}}}\langle 1|}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>H</mi> <mo>=</mo> <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> <mo fence="false" stretchy="false">⟨</mo> <mn>0</mn> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mo>+</mo> <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> <mo fence="false" stretchy="false">⟨</mo> <mn>1</mn> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle H={\frac {|0\rangle +|1\rangle }{\sqrt {2}}}\langle 0|+{\frac {|0\rangle -|1\rangle }{\sqrt {2}}}\langle 1|}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6a6ed466bf2bc7837cdbd82ef8fedccec3d4afd6" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:31.639ex; height:6.676ex;" alt="{\displaystyle H={\frac {|0\rangle +|1\rangle }{\sqrt {2}}}\langle 0|+{\frac {|0\rangle -|1\rangle }{\sqrt {2}}}\langle 1|}"></span> </p><p>in <a href="/wiki/Dirac_notation" class="mw-redirect" title="Dirac notation">Dirac notation</a>. This corresponds to the <a href="/wiki/Transformation_matrix" title="Transformation matrix">transformation matrix</a> <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_{1}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msqrt> <mn>2</mn> </msqrt> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow> <mo>(</mo> <mtable rowspacing="4pt" columnspacing="1em"> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mn>1</mn> </mtd> </mtr> <mtr> <mtd> <mn>1</mn> </mtd> <mtd> <mo>−</mo> <mn>1</mn> </mtd> </mtr> </mtable> <mo>)</mo> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle H_{1}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ea6351bc21cd91bb3d622fd18b53e49db9ec1ad0" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:20.647ex; height:6.509ex;" alt="{\displaystyle H_{1}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}"></span> in 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 |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> <mo>,</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/49e6ffebc672fad9d9fcde57c8eafc34bd550ced" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.462ex; height:2.843ex;" alt="{\displaystyle |0\rangle ,|1\rangle }"></span> basis, also known as the <a href="/w/index.php?title=Computational_basis&action=edit&redlink=1" class="new" title="Computational basis (page does not exist)">computational basis</a>. The states <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="{\textstyle {\frac {\left|0\right\rangle +\left|1\right\rangle }{\sqrt {2}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mrow> <mo>|</mo> <mn>0</mn> <mo>⟩</mo> </mrow> <mo>+</mo> <mrow> <mo>|</mo> <mn>1</mn> <mo>⟩</mo> </mrow> </mrow> <msqrt> <mn>2</mn> </msqrt> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle {\frac {\left|0\right\rangle +\left|1\right\rangle }{\sqrt {2}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1e5fc8d82c293ca7cd97a3b94e3f0f56d184f5a2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:5.953ex; height:4.843ex;" alt="{\textstyle {\frac {\left|0\right\rangle +\left|1\right\rangle }{\sqrt {2}}}}"></span> and <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\frac {\left|0\right\rangle -\left|1\right\rangle }{\sqrt {2}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mrow> <mo>|</mo> <mn>0</mn> <mo>⟩</mo> </mrow> <mo>−</mo> <mrow> <mo>|</mo> <mn>1</mn> <mo>⟩</mo> </mrow> </mrow> <msqrt> <mn>2</mn> </msqrt> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle {\frac {\left|0\right\rangle -\left|1\right\rangle }{\sqrt {2}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c95f71924fca25ca525334d4f7a94050ec4ccfd0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:5.953ex; height:4.843ex;" alt="{\textstyle {\frac {\left|0\right\rangle -\left|1\right\rangle }{\sqrt {2}}}}"></span> are known as <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 \left|{\boldsymbol {+}}\right\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>|</mo> <mrow class="MJX-TeXAtom-ORD"> <mo mathvariant="bold">+</mo> </mrow> <mo>⟩</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left|{\boldsymbol {+}}\right\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a0bb4e0c8d1ead493d96dcf9d2ada1a1f5736fba" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.629ex; height:2.843ex;" alt="{\displaystyle \left|{\boldsymbol {+}}\right\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 \left|{\boldsymbol {-}}\right\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow> <mo>|</mo> <mrow class="MJX-TeXAtom-ORD"> <mo mathvariant="bold">−</mo> </mrow> <mo>⟩</mo> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \left|{\boldsymbol {-}}\right\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e7649767fc05ed90325a1eea5704e8a84ede1523" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.629ex; height:2.843ex;" alt="{\displaystyle \left|{\boldsymbol {-}}\right\rangle }"></span> respectively, and together constitute the <a href="/w/index.php?title=Polar_basis&action=edit&redlink=1" class="new" title="Polar basis (page does not exist)">polar basis</a> in <a href="/wiki/Quantum_computing" title="Quantum computing">quantum computing</a>. </p> <div class="mw-heading mw-heading3"><h3 id="Hadamard_gate_operations">Hadamard gate operations</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Hadamard_transform&action=edit&section=10" title="Edit section: Hadamard gate operations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <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 {\begin{aligned}H(|0\rangle )&={\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle =:|+\rangle \\H(|1\rangle )&={\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle =:|-\rangle \\H(|+\rangle )&=H\left({\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{2}}{\Big (}|0\rangle +|1\rangle {\Big )}+{\frac {1}{2}}{\Big (}|0\rangle -|1\rangle {\Big )}=|0\rangle \\H(|-\rangle )&=H\left({\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{2}}{\Big (}|0\rangle +|1\rangle {\Big )}-{\frac {1}{2}}{\Big (}|0\rangle -|1\rangle {\Big )}=|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> <mi>H</mi> <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> </mtd> <mtd> <mi></mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msqrt> <mn>2</mn> </msqrt> </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"> <mfrac> <mn>1</mn> <msqrt> <mn>2</mn> </msqrt> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> <mo>=:</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mo>+</mo> <mo fence="false" stretchy="false">⟩</mo> </mtd> </mtr> <mtr> <mtd> <mi>H</mi> <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> </mtd> <mtd> <mi></mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msqrt> <mn>2</mn> </msqrt> </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"> <mfrac> <mn>1</mn> <msqrt> <mn>2</mn> </msqrt> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> <mo>=:</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mo>−</mo> <mo fence="false" stretchy="false">⟩</mo> </mtd> </mtr> <mtr> <mtd> <mi>H</mi> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mo>+</mo> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">)</mo> </mtd> <mtd> <mi></mi> <mo>=</mo> <mi>H</mi> <mrow> <mo>(</mo> <mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msqrt> <mn>2</mn> </msqrt> </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"> <mfrac> <mn>1</mn> <msqrt> <mn>2</mn> </msqrt> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> </mrow> <mo>)</mo> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo maxsize="1.623em" minsize="1.623em">(</mo> </mrow> </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 class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo maxsize="1.623em" minsize="1.623em">)</mo> </mrow> </mrow> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo maxsize="1.623em" minsize="1.623em">(</mo> </mrow> </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 class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo maxsize="1.623em" minsize="1.623em">)</mo> </mrow> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <mo fence="false" stretchy="false">⟩</mo> </mtd> </mtr> <mtr> <mtd> <mi>H</mi> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mo>−</mo> <mo fence="false" stretchy="false">⟩</mo> <mo stretchy="false">)</mo> </mtd> <mtd> <mi></mi> <mo>=</mo> <mi>H</mi> <mrow> <mo>(</mo> <mrow> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msqrt> <mn>2</mn> </msqrt> </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"> <mfrac> <mn>1</mn> <msqrt> <mn>2</mn> </msqrt> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> </mrow> <mo>)</mo> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo maxsize="1.623em" minsize="1.623em">(</mo> </mrow> </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 class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo maxsize="1.623em" minsize="1.623em">)</mo> </mrow> </mrow> <mo>−</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <mn>2</mn> </mfrac> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo maxsize="1.623em" minsize="1.623em">(</mo> </mrow> </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 class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mo maxsize="1.623em" minsize="1.623em">)</mo> </mrow> </mrow> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}H(|0\rangle )&={\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle =:|+\rangle \\H(|1\rangle )&={\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle =:|-\rangle \\H(|+\rangle )&=H\left({\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{2}}{\Big (}|0\rangle +|1\rangle {\Big )}+{\frac {1}{2}}{\Big (}|0\rangle -|1\rangle {\Big )}=|0\rangle \\H(|-\rangle )&=H\left({\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{2}}{\Big (}|0\rangle +|1\rangle {\Big )}-{\frac {1}{2}}{\Big (}|0\rangle -|1\rangle {\Big )}=|1\rangle \end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cb24c1340d0661ce8429ad51c0b1c257a910446b" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -12.171ex; width:70.928ex; height:25.509ex;" alt="{\displaystyle {\begin{aligned}H(|0\rangle )&={\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle =:|+\rangle \\H(|1\rangle )&={\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle =:|-\rangle \\H(|+\rangle )&=H\left({\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{2}}{\Big (}|0\rangle +|1\rangle {\Big )}+{\frac {1}{2}}{\Big (}|0\rangle -|1\rangle {\Big )}=|0\rangle \\H(|-\rangle )&=H\left({\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{2}}{\Big (}|0\rangle +|1\rangle {\Big )}-{\frac {1}{2}}{\Big (}|0\rangle -|1\rangle {\Big )}=|1\rangle \end{aligned}}}"></span> </p><p>One application of the Hadamard gate to either a 0 or 1 qubit will produce a quantum state that, if observed, will be a 0 or 1 with equal probability (as seen in the first two operations). This is exactly like flipping a fair coin in the standard <a href="/wiki/Probabilistic_Turing_machine" title="Probabilistic Turing machine">probabilistic model of computation</a>. However, if the Hadamard gate is applied twice in succession (as is effectively being done in the last two operations), then the final state is always the same as the initial state. </p> <div class="mw-heading mw-heading3"><h3 id="Hadamard_transform_in_quantum_algorithms">Hadamard transform in quantum algorithms</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Hadamard_transform&action=edit&section=11" title="Edit section: Hadamard transform in quantum algorithms"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Computing the quantum Hadamard transform is simply the application of a Hadamard gate to each qubit individually because of the tensor product structure of the Hadamard transform. This simple result means the quantum Hadamard transform requires <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \log _{2}N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ebbb0de63b56848f6d121470d64eb2359472a6e2" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.477ex; height:2.676ex;" alt="{\displaystyle \log _{2}N}"></span> operations, compared to the classical case of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N\log _{2}N}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mi>N</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N\log _{2}N}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a15c2984d04cc0cf262b93fcb00cc9d74c32d7cb" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.927ex; height:2.676ex;" alt="{\displaystyle N\log _{2}N}"></span> operations. </p><p><br /> For an <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 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>-qubit system, <a href="/wiki/Hadamard_gates" class="mw-redirect" title="Hadamard gates">Hadamard gates</a> acting on each of 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}"> <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 (each initialized to 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 |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>) can be used to prepare uniform quantum superposition states when <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/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span> is of the form <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=2^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <mo>=</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N=2^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d47454e9a8a33d7f62a8b689ecda44afd41e51be" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.543ex; height:2.343ex;" alt="{\displaystyle N=2^{n}}"></span>. In this case case 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 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, the combined Hadamard gate <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle H_{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e63458b04288bbe116a9a8037dfae0b36b2c639a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.15ex; height:2.509ex;" alt="{\displaystyle H_{n}}"></span> is expressed as the tensor product of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> Hadamard gates: <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H_{n}=\underbrace {H\otimes H\otimes \ldots \otimes H} _{n{\text{ times}}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mo>=</mo> <munder> <mrow class="MJX-TeXAtom-OP MJX-fixedlimits"> <munder> <mrow> <mi>H</mi> <mo>⊗</mo> <mi>H</mi> <mo>⊗</mo> <mo>…</mo> <mo>⊗</mo> <mi>H</mi> </mrow> <mo>⏟</mo> </munder> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> <mrow class="MJX-TeXAtom-ORD"> <mtext> times</mtext> </mrow> </mrow> </munder> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle H_{n}=\underbrace {H\otimes H\otimes \ldots \otimes H} _{n{\text{ times}}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/186a65eec374e6480c66bf448c04e3eb98fe71dd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.838ex; width:23.683ex; height:5.676ex;" alt="{\displaystyle H_{n}=\underbrace {H\otimes H\otimes \ldots \otimes H} _{n{\text{ times}}}}"></span> </p><p>The resulting uniform quantum superposition state is 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 H_{n}|0\rangle ^{\otimes n}={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}|j\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msub> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mn>0</mn> <msup> <mo fence="false" stretchy="false">⟩</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>⊗</mo> <mi>n</mi> </mrow> </msup> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <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> <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_{n}|0\rangle ^{\otimes n}={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}|j\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0e41d713d85db7885f1fe01880dcbb88f882171b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:23.783ex; height:7.676ex;" alt="{\displaystyle H_{n}|0\rangle ^{\otimes n}={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}|j\rangle }"></span> This generalizes the preparation of uniform quantum states using Hadamard gates for any <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=2^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>N</mi> <mo>=</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle N=2^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d47454e9a8a33d7f62a8b689ecda44afd41e51be" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.543ex; height:2.343ex;" alt="{\displaystyle N=2^{n}}"></span>.<sup id="cite_ref-Nielsen-Chuang_5-0" class="reference"><a href="#cite_note-Nielsen-Chuang-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> </p><p><a href="#Measurement">Measurement</a> of this uniform quantum state results in a <a href="/wiki/Random_number_generation" title="Random number generation">random</a> state between <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |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="nowrap"><span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |N-1\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>N</mi> <mo>−</mo> <mn>1</mn> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |N-1\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6f49a0547e43ba18fa945a73747a78f750fa524e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.618ex; height:2.843ex;" alt="{\displaystyle |N-1\rangle }"></span>.</span> </p><p>Many <a href="/wiki/Quantum_algorithm" title="Quantum algorithm">quantum algorithms</a> use the Hadamard transform as an initial step, since as explained earlier, it maps <i>n</i> qubits initialized 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 |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> to a superposition of all 2<sup><i>n</i></sup> orthogonal states in 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 |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> <mo>,</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/49e6ffebc672fad9d9fcde57c8eafc34bd550ced" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.462ex; height:2.843ex;" alt="{\displaystyle |0\rangle ,|1\rangle }"></span> basis with equal weight. For example, this is used in the <a href="/wiki/Deutsch%E2%80%93Jozsa_algorithm" title="Deutsch–Jozsa algorithm">Deutsch–Jozsa algorithm</a>, <a href="/wiki/Simon%27s_algorithm" class="mw-redirect" title="Simon's algorithm">Simon's algorithm</a>, the <a href="/wiki/Bernstein%E2%80%93Vazirani_algorithm" title="Bernstein–Vazirani algorithm">Bernstein–Vazirani algorithm</a>, and in <a href="/wiki/Grover%27s_algorithm" title="Grover's algorithm">Grover's algorithm</a>. Note that <a href="/wiki/Shor%27s_algorithm" title="Shor's algorithm">Shor's algorithm</a> uses both an initial Hadamard transform, as well as the <a href="/wiki/Quantum_Fourier_transform" title="Quantum Fourier transform">quantum Fourier transform</a>, which are both types of <a href="/wiki/Fourier_transform_on_finite_groups" title="Fourier transform on finite groups">Fourier transforms on finite groups</a>; the first on <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo stretchy="false">(</mo> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <msup> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5686cb9b950687c6d056088cb2314829751e9ac9" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.453ex; height:2.843ex;" alt="{\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}"></span> and the second on <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="double-struck">Z</mi> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/28526fdf9d9d5ac32c95d34e9414ef6db8642b31" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.644ex; height:2.843ex;" alt="{\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }"></span>. </p><p>Preparation of uniform quantum superposition states in the general case, when <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/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span> ≠ <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{n}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>n</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{n}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8226f30650ee4fe4e640c6d2798127e80e9c160d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.381ex; height:2.343ex;" alt="{\displaystyle 2^{n}}"></span> is non-trivial and requires more work. An efficient and deterministic approach for preparing the superposition 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 |\Psi \rangle ={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}|j\rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi mathvariant="normal">Ψ</mi> <mo fence="false" stretchy="false">⟩</mo> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>1</mn> <msqrt> <mi>N</mi> </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"> <mi>N</mi> <mo>−</mo> <mn>1</mn> </mrow> </munderover> <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 |\Psi \rangle ={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}|j\rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/67d1dc6941579e10f848940058259f933f7e6512" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:18.137ex; height:7.676ex;" alt="{\displaystyle |\Psi \rangle ={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}|j\rangle }"></span> with a gate complexity and circuit depth of only <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log _{2}N)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log _{2}N)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/16b70215be77c09f7472854e6c22dda8314b69aa" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.059ex; height:2.843ex;" alt="{\displaystyle O(\log _{2}N)}"></span> for all <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}"> <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/f5e3890c981ae85503089652feb48b191b57aae3" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}"></span> was recently presented.<sup id="cite_ref-shukla2024efficient_6-0" class="reference"><a href="#cite_note-shukla2024efficient-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> This approach requires only <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=\lceil \log _{2}N\rceil }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>=</mo> <mo fence="false" stretchy="false">⌈</mo> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mi>N</mi> <mo fence="false" stretchy="false">⌉</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n=\lceil \log _{2}N\rceil }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/51a072e4dd331b8cd6513935f5de2f3a9f87bc14" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.035ex; height:2.843ex;" alt="{\displaystyle n=\lceil \log _{2}N\rceil }"></span> qubits. Importantly, neither ancilla qubits nor any quantum gates with multiple controls are needed in this approach for creating the uniform superposition state <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\Psi \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi mathvariant="normal">Ψ</mi> <mo fence="false" stretchy="false">⟩</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\Psi \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/6e77f6b1e903837c5765c9683da41dd93199621c" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.36ex; height:2.843ex;" alt="{\displaystyle |\Psi \rangle }"></span>. </p> <div class="mw-heading mw-heading2"><h2 id="Molecular_phylogenetics_(evolutionary_biology)_applications"><span id="Molecular_phylogenetics_.28evolutionary_biology.29_applications"></span>Molecular phylogenetics (evolutionary biology) applications</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Hadamard_transform&action=edit&section=12" title="Edit section: Molecular phylogenetics (evolutionary biology) applications"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The Hadamard transform can be used to estimate <a href="/wiki/Phylogenetic_tree" title="Phylogenetic tree">phylogenetic trees</a> from molecular data.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> <a href="/wiki/Phylogenetics" title="Phylogenetics">Phylogenetics</a> is the subfield of <a href="/wiki/Evolutionary_biology" title="Evolutionary biology">evolutionary biology</a> focused on understanding the relationships among organisms. A Hadamard transform applied to a vector (or matrix) of site pattern frequencies obtained from a DNA <a href="/wiki/Multiple_sequence_alignment" title="Multiple sequence alignment">multiple sequence alignment</a> can be used to generate another vector that carries information about the tree topology. The invertible nature of the phylogenetic Hadamard transform also allows the calculation of site likelihoods from a tree topology vector, allowing one to use the Hadamard transform for <a href="/wiki/Maximum_likelihood_estimation" title="Maximum likelihood estimation">maximum likelihood estimation</a> of phylogenetic trees. However, the latter application is less useful than the transformation from the site pattern vector to the tree vector because there are other ways to calculate site likelihoods<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> that are much more efficient. However, the invertible nature of the phylogenetic Hadamard transform does provide an elegant tool for mathematic phylogenetics.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> </p><p>The mechanics of the phylogenetic Hadamard transform involve the calculation of a vector <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 \gamma (T)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>γ</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \gamma (T)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/179cf17e05ddc78ec20065244a26551778b73a89" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.708ex; height:2.843ex;" alt="{\displaystyle \gamma (T)}"></span> that provides information about the topology and branch lengths for tree <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 T}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>T</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle T}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}"></span> using the site pattern vector or matrix <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 s(T)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>s</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle s(T)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e1da166e4104876bcd8373abbfb7cc5042ee29f8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.536ex; height:2.843ex;" alt="{\displaystyle s(T)}"></span>. </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 \gamma (T)=H^{-1}(\ln(Hs(T)))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>γ</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> <mo>=</mo> <msup> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>ln</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>H</mi> <mi>s</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \gamma (T)=H^{-1}(\ln(Hs(T)))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f90048258c316595e20e6c4f6072ff495d01957" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.4ex; height:3.176ex;" alt="{\displaystyle \gamma (T)=H^{-1}(\ln(Hs(T)))}"></span> where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle H}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>H</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle H}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/75a9edddcca2f782014371f75dca39d7e13a9c1b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle H}"></span> is the Hadamard matrix of the appropriate size. This equation can be rewritten as a series of three equations to simplify its interpretation: </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 {\begin{aligned}r&=Hs(T)\\\rho &=\ln r\\\gamma (T)&=H^{-1}\rho \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> <mi>r</mi> </mtd> <mtd> <mi></mi> <mo>=</mo> <mi>H</mi> <mi>s</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mtd> </mtr> <mtr> <mtd> <mi>ρ</mi> </mtd> <mtd> <mi></mi> <mo>=</mo> <mi>ln</mi> <mo>⁡</mo> <mi>r</mi> </mtd> </mtr> <mtr> <mtd> <mi>γ</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mtd> <mtd> <mi></mi> <mo>=</mo> <msup> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mi>ρ</mi> </mtd> </mtr> </mtable> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}r&=Hs(T)\\\rho &=\ln r\\\gamma (T)&=H^{-1}\rho \end{aligned}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/20ccacfb668617aa2ceff41c5fff97739c1d322d" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.171ex; width:15.157ex; height:9.343ex;" alt="{\displaystyle {\begin{aligned}r&=Hs(T)\\\rho &=\ln r\\\gamma (T)&=H^{-1}\rho \end{aligned}}}"></span> </p><p>The invertible nature of this equation allows one to calculate an expected site pattern vector (or matrix) as follows: </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 s(T)=H^{-1}(\exp(H\gamma (T)))}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>s</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> <mo>=</mo> <msup> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mo stretchy="false">(</mo> <mi>exp</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>H</mi> <mi>γ</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle s(T)=H^{-1}(\exp(H\gamma (T)))}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e3eed460648334b6a9bf1138db6e35b0bbaa97cf" class="mwe-math-fallback-image-display mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.013ex; height:3.176ex;" alt="{\displaystyle s(T)=H^{-1}(\exp(H\gamma (T)))}"></span> </p><p>We can use the Cavender–Farris–<a href="/wiki/Jerzy_Neyman" title="Jerzy Neyman">Neyman</a> (CFN) two-state <a href="/wiki/Substitution_model" title="Substitution model">substitution model</a> for DNA by encoding the <a href="/wiki/Nucleotide" title="Nucleotide">nucleotides</a> as binary characters (the <a href="/wiki/Purine" title="Purine">purines</a> A and G are encoded as R and the <a href="/wiki/Pyrimidine" title="Pyrimidine">pyrimidines</a> C and T are encoded as Y). This makes it possible to encode the multiple sequence alignment as the site pattern vector <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 s(T)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>s</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle s(T)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e1da166e4104876bcd8373abbfb7cc5042ee29f8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.536ex; height:2.843ex;" alt="{\displaystyle s(T)}"></span> that can be converted to a tree vector <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 \gamma (T)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>γ</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \gamma (T)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/179cf17e05ddc78ec20065244a26551778b73a89" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.708ex; height:2.843ex;" alt="{\displaystyle \gamma (T)}"></span>, as shown in the following example: </p> <table class="wikitable"> <caption>Example showing the Hadamard transform for a specific tree (values for worked example adapted from Waddell et al. 1997<sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup>) </caption> <tbody><tr> <th>Index </th> <th>Binary pattern </th> <th>Alignment patterns </th> <th><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 \gamma (T)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>γ</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \gamma (T)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/179cf17e05ddc78ec20065244a26551778b73a89" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.708ex; height:2.843ex;" alt="{\displaystyle \gamma (T)}"></span> </th> <th><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 \rho =H^{-1}\gamma (T)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>ρ</mi> <mo>=</mo> <msup> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mi>γ</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \rho =H^{-1}\gamma (T)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/8d842790109780436428f7a88e24976a2145c1c6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.445ex; height:3.176ex;" alt="{\displaystyle \rho =H^{-1}\gamma (T)}"></span> </th> <th><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 r=\exp(\rho )}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>r</mi> <mo>=</mo> <mi>exp</mi> <mo>⁡</mo> <mo stretchy="false">(</mo> <mi>ρ</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle r=\exp(\rho )}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3cdf1938dc9621d9b9846ad0e58ee9871a183a3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.711ex; height:2.843ex;" alt="{\displaystyle r=\exp(\rho )}"></span> </th> <th><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 s(T)=H^{-1}\rho }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>s</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> <mo>=</mo> <msup> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mi>ρ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle s(T)=H^{-1}\rho }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5d5f1fb9a8685faa576770281169e4c7b54dd25a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.273ex; height:3.176ex;" alt="{\displaystyle s(T)=H^{-1}\rho }"></span> </th></tr> <tr> <td>0 </td> <td>0000 </td> <td>RRRR and YYYY </td> <td>−0.475 </td> <td>0 </td> <td>1 </td> <td>0.6479 </td></tr> <tr> <td>1 </td> <td>0001 </td> <td>RRRY and YYYR </td> <td>0.2 </td> <td>−0.5 </td> <td>0.6065 </td> <td>0.1283 </td></tr> <tr> <td>2 </td> <td>0010 </td> <td>RRYR and YYRY </td> <td>0.025 </td> <td>−0.15 </td> <td>0.8607 </td> <td>0.02 </td></tr> <tr> <td>3* </td> <td>0011 </td> <td>RRYY and YYRR </td> <td>0.025 </td> <td>−0.45 </td> <td>0.6376 </td> <td>0.0226 </td></tr> <tr> <td>4 </td> <td>0100 </td> <td>RYRR and YRYY </td> <td>0.2 </td> <td>−0.45 </td> <td>0.6376 </td> <td>0.1283 </td></tr> <tr> <td>5* </td> <td>0101 </td> <td>RYRY and YRYR </td> <td>0 </td> <td>−0.85 </td> <td>0.4274 </td> <td>0.0258 </td></tr> <tr> <td>6* </td> <td>0110 </td> <td>RYYR and YRRY </td> <td>0 </td> <td>−0.5 </td> <td>0.6065 </td> <td>0.0070 </td></tr> <tr> <td>7 </td> <td>0111 </td> <td>RYYY and YRRR </td> <td>0.025 </td> <td>−0.9 </td> <td>0.4066 </td> <td>0.02 </td></tr></tbody></table> <p>The example shown in this table uses the simplified three equation scheme and it is for a four taxon tree that can be written as ((A,B),(C,D)); in <a href="/wiki/Newick_format" title="Newick format">newick format</a>. The site patterns are written in the order ABCD. This particular tree has two long terminal branches (0.2 <a href="/wiki/Transversion" title="Transversion">transversion</a> substitutions per site), two short terminal branches (0.025 transversion substitutions per site), and a short internal branch (0.025 transversion substitutions per site); thus, it would be written as ((A:0.025,B:0.2):0.025,(C:0.025,D:0.2)); in newick format. This tree will exhibit <a href="/wiki/Long_branch_attraction" title="Long branch attraction">long branch attraction</a> if the data are analyzed using the <a href="/wiki/Maximum_parsimony_(phylogenetics)" title="Maximum parsimony (phylogenetics)">maximum parsimony</a> criterion (assuming the sequence analyzed is long enough for the observed site pattern frequencies to be close to the expected frequencies shown in 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 s(T)=H^{-1}\rho }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>s</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> <mo>=</mo> <msup> <mi>H</mi> <mrow class="MJX-TeXAtom-ORD"> <mo>−</mo> <mn>1</mn> </mrow> </msup> <mi>ρ</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle s(T)=H^{-1}\rho }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5d5f1fb9a8685faa576770281169e4c7b54dd25a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.273ex; height:3.176ex;" alt="{\displaystyle s(T)=H^{-1}\rho }"></span> column). The long branch attraction reflects the fact that the expected number of site patterns with index 6 -- which support the tree ((A,C),(B,D)); -- exceed the expected number of site patterns that support the true tree (index 4). Obviously, the invertible nature of the phylogenetic Hadamard transform means that the tree vector means that the tree vector <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 \gamma (T)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>γ</mi> <mo stretchy="false">(</mo> <mi>T</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \gamma (T)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/179cf17e05ddc78ec20065244a26551778b73a89" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.708ex; height:2.843ex;" alt="{\displaystyle \gamma (T)}"></span> corresponds to the correct tree. Parsimony analysis after the transformation is therefore <a href="/wiki/Consistent_estimator" title="Consistent estimator">statistically consistent</a>,<sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup> as would be a standard maximum likelihood analysis using the correct model (in this case the CFN model). </p><p>Note that the site pattern with 0 corresponds to the sites that have not changed (after encoding the nucleotides as purines or pyrimidines). The indices with asterisks (3, 5, and 6) are "parsimony-informative", and. the remaining indices represent site patterns where a single taxon differs from the other three taxa (so they are the equivalent of terminal branch lengths in a standard maximum likelihood phylogenetic tree). </p><p>If one wishes to use nucleotide data without recoding as R and Y (and ultimately as 0 and 1) it is possible to encode the site patterns as a matrix. If we consider a four-taxon tree there are a total of 256 site patterns (four nucleotides to the 4th power). However, symmetries of the <a href="/wiki/Models_of_DNA_evolution" title="Models of DNA evolution">Kimura three-parameter (or K81) model</a> allow us to reduce the 256 possible site patterns for DNA to 64 patterns, making it possible to encode the nucleotide data for a four-taxon tree as an 8 × 8 matrix<sup id="cite_ref-:0_16-0" class="reference"><a href="#cite_note-:0-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> in a manner similar to the vector of 8 elements used above for transversion (RY) site patterns. This is accomplished by recoding the data using the <a href="/wiki/Klein_four-group" title="Klein four-group">Klein four-group</a>: </p> <table class="wikitable"> <caption>Klein four-group coding for phylogenetic Hadamard transform </caption> <tbody><tr> <th>Nucleotide 1 </th> <th>Nucleotide 2 </th> <th>Nucleotide 3 </th> <th>Nucleotide 4 </th></tr> <tr> <td>A (0,0) </td> <td>G (1,0) </td> <td>C (0,1) </td> <td>T (1,1) </td></tr> <tr> <td>C (0,0) </td> <td>T (1,0) </td> <td>A (0,1) </td> <td>G (1,1) </td></tr> <tr> <td>G (0,0) </td> <td>A (1,0) </td> <td>T (0,1) </td> <td>C (1,1) </td></tr> <tr> <td>T (0,0) </td> <td>C (1,0) </td> <td>G (0,1) </td> <td>A (1,1) </td></tr></tbody></table> <p>As with RY data, site patterns are indexed relative to the base in the arbitrarily chosen first taxon with the bases in the subsequent taxa encoded relative to that first base. Thus, the first taxon receives the bit pair (0,0). Using those bit pairs one can produce two vectors similar to the RY vectors and then populate the matrix using those vectors. This can be illustrated using the example from Hendy et al. (1994),<sup id="cite_ref-:0_16-1" class="reference"><a href="#cite_note-:0-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> which is based on a multiple sequence alignment of four primate hemoglobin pseudogenes: </p> <table class="wikitable"> <caption>Example of encoded sequence alignment (from Hendy et al. 1994<sup id="cite_ref-:0_16-2" class="reference"><a href="#cite_note-:0-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup>) (values are counts out of 9879 sites) </caption> <tbody><tr> <th> </th> <th>0 </th> <th>8 </th> <th>16 </th> <th>24 </th> <th>32 </th> <th>40 </th> <th>48 </th> <th>56 </th></tr> <tr> <td>0 </td> <td>8988 </td> <td>9 </td> <td>10 </td> <td>12 </td> <td>24 </td> <td> </td> <td> </td> <td>90 </td></tr> <tr> <td>1 </td> <td>41 </td> <td>9 </td> <td> </td> <td>** </td> <td> </td> <td> </td> <td> </td> <td> </td></tr> <tr> <td>2 </td> <td>45 </td> <td> </td> <td>13 </td> <td> </td> <td> </td> <td> </td> <td> </td> <td> </td></tr> <tr> <td>3 </td> <td>54* </td> <td> </td> <td> </td> <td>14 </td> <td> </td> <td> </td> <td> </td> <td>3 </td></tr> <tr> <td>4 </td> <td>94 </td> <td> </td> <td> </td> <td> </td> <td>20 </td> <td> </td> <td> </td> <td> </td></tr> <tr> <td>5 </td> <td> </td> <td> </td> <td>1 </td> <td> </td> <td> </td> <td> </td> <td> </td> <td> </td></tr> <tr> <td>6 </td> <td>2 </td> <td> </td> <td> </td> <td> </td> <td>2 </td> <td> </td> <td> </td> <td> </td></tr> <tr> <td>7 </td> <td>356 </td> <td> </td> <td>1 </td> <td> </td> <td>1 </td> <td> </td> <td> </td> <td>75 </td></tr></tbody></table> <p>The much larger number of site patterns in column 0 reflects the fact that column 0 corresponds to <a href="/wiki/Transition_(genetics)" title="Transition (genetics)">transition</a> differences, which accumulate more rapidly than transversion differences in virtually all comparisons of genomic regions (and definitely accumulate more rapidly in the hemoglobin pseudogenes used for this worked example<sup id="cite_ref-17" class="reference"><a href="#cite_note-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup>). If we consider the site pattern AAGG it would to binary pattern 0000 for the second element of the Klein group bit pair and 0011 for the first element. in this case binary pattern based on the first element first element corresponds to index 3 (so row 3 in column 0; indicated with a single asterisk in the table). The site patterns GGAA, CCTT, and TTCC would be encoded in the exact same way. The site pattern AACT would be encoded with binary pattern 0011 based on the second element and 0001 based on the first element; this yields index 1 for the first element and index 3 for the second. The index based on the second Klein group bit pair is multiplied by 8 to yield the column index (in this case it would be column 24) The cell that would include the count of AACT site patterns is indicated with two asterisks; however, the absence of a number in the example indicates that the sequence alignment include no AACT site patterns (likewise, CCAG, GGTC, and TTGA site patterns, which would be encoded in the same way, are absent). </p> <div class="mw-heading mw-heading2"><h2 id="Other_applications">Other applications</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Hadamard_transform&action=edit&section=13" title="Edit section: Other applications"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>The Hadamard transform is also used in <a href="/wiki/Data_encryption" class="mw-redirect" title="Data encryption">data encryption</a>, as well as many <a href="/wiki/Signal_processing" title="Signal processing">signal processing</a> and <a href="/wiki/Data_compression" title="Data compression">data compression</a> <a href="/wiki/Algorithms" class="mw-redirect" title="Algorithms">algorithms</a>, such as <a href="/wiki/JPEG_XR" title="JPEG XR">JPEG XR</a> and <a href="/wiki/H.264/MPEG-4_AVC" class="mw-redirect" title="H.264/MPEG-4 AVC">MPEG-4 AVC</a>. In <a href="/wiki/Video_compression" class="mw-redirect" title="Video compression">video compression</a> applications, it is usually used in the form of the <a href="/wiki/Sum_of_absolute_transformed_differences" title="Sum of absolute transformed differences">sum of absolute transformed differences</a>. It is also a crucial part of significant number of algorithms in quantum computing. The Hadamard transform is also applied in experimental techniques such as <a href="/wiki/NMR" class="mw-redirect" title="NMR">NMR</a>, <a href="/wiki/Mass_spectrometry" title="Mass spectrometry">mass spectrometry</a> and <a href="/wiki/Crystallography" title="Crystallography">crystallography</a>. It is additionally used in some versions of <a href="/wiki/Locality-sensitive_hashing" title="Locality-sensitive hashing">locality-sensitive hashing</a>, to obtain pseudo-random matrix rotations. </p> <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=Hadamard_transform&action=edit&section=14" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Fast_Walsh%E2%80%93Hadamard_transform" title="Fast Walsh–Hadamard transform">Fast Walsh–Hadamard transform</a></li> <li><a href="/wiki/Pseudo-Hadamard_transform" title="Pseudo-Hadamard transform">Pseudo-Hadamard transform</a></li> <li><a href="/wiki/Haar_transform" class="mw-redirect" title="Haar transform">Haar transform</a></li> <li><a href="/wiki/Generalized_distributive_law" title="Generalized distributive law">Generalized distributive law</a></li></ul> <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=Hadamard_transform&action=edit&section=15" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><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="CITEREFRitter1996" class="citation web cs1">Ritter, Terry (August 1996). <a rel="nofollow" class="external text" href="http://www.ciphersbyritter.com/RES/WALHAD.HTM">"Walsh–Hadamard Transforms: A Literature Survey"</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Walsh%E2%80%93Hadamard+Transforms%3A+A+Literature+Survey&rft.date=1996-08&rft.aulast=Ritter&rft.aufirst=Terry&rft_id=http%3A%2F%2Fwww.ciphersbyritter.com%2FRES%2FWALHAD.HTM&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHadamard+transform" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAkansuPoluri2007" class="citation journal cs1"><a href="/wiki/Ali_Akansu" title="Ali Akansu">Akansu</a>, Ali N.; Poluri, R. (July 2007). <a rel="nofollow" class="external text" href="http://web.njit.edu/~akansu/PAPERS/Akansu-Poluri-WALSH-LIKE2007.pdf">"Walsh-Like Nonlinear Phase Orthogonal Codes for Direct Sequence CDMA Communications"</a> <span class="cs1-format">(PDF)</span>. <i>IEEE Transactions on Signal Processing</i>. <b>55</b> (7): 3800–6. <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/2007ITSP...55.3800A">2007ITSP...55.3800A</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.1109%2FTSP.2007.894229">10.1109/TSP.2007.894229</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:6830633">6830633</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=IEEE+Transactions+on+Signal+Processing&rft.atitle=Walsh-Like+Nonlinear+Phase+Orthogonal+Codes+for+Direct+Sequence+CDMA+Communications&rft.volume=55&rft.issue=7&rft.pages=3800-6&rft.date=2007-07&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A6830633%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1109%2FTSP.2007.894229&rft_id=info%3Abibcode%2F2007ITSP...55.3800A&rft.aulast=Akansu&rft.aufirst=Ali+N.&rft.au=Poluri%2C+R.&rft_id=http%3A%2F%2Fweb.njit.edu%2F~akansu%2FPAPERS%2FAkansu-Poluri-WALSH-LIKE2007.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHadamard+transform" class="Z3988"></span></li> <li>Pan, Jeng-shyang <a rel="nofollow" class="external text" href="http://www.freepatentsonline.com/y2009/0136023.html">Data Encryption Method Using Discrete Fractional Hadamard Transformation</a> (May 28, 2009)</li> <li>Lachowicz, Dr. Pawel. <a rel="nofollow" class="external text" href="http://www.quantatrisk.com/2015/04/07/walsh-hadamard-transform-python-tests-for-randomness-of-financial-return-series/">Walsh–Hadamard Transform and Tests for Randomness of Financial Return-Series</a> (April 7, 2015)</li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBeddardYorke2011" class="citation web cs1">Beddard, Godfrey; Yorke, Briony A. (January 2011). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20141018190749/http://www1.chem.leeds.ac.uk/People/GSB/Hadamard_for_web.pdf">"Pump-probe Spectroscopy using Hadamard Transforms"</a> <span class="cs1-format">(PDF)</span>. Archived from <a rel="nofollow" class="external text" href="http://www1.chem.leeds.ac.uk/People/GSB/Hadamard_for_web.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 2014-10-18<span class="reference-accessdate">. Retrieved <span class="nowrap">2012-04-28</span></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=unknown&rft.btitle=Pump-probe+Spectroscopy+using+Hadamard+Transforms&rft.date=2011-01&rft.aulast=Beddard&rft.aufirst=Godfrey&rft.au=Yorke%2C+Briony+A.&rft_id=http%3A%2F%2Fwww1.chem.leeds.ac.uk%2FPeople%2FGSB%2FHadamard_for_web.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHadamard+transform" class="Z3988"></span></li> <li><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFYorkeBeddardOwenPearson2014" class="citation journal cs1">Yorke, Briony A.; Beddard, Godfrey; Owen, Robin L.; Pearson, Arwen R. (September 2014). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4216935">"Time-resolved crystallography using the Hadamard transform"</a>. <i>Nature Methods</i>. <b>11</b> (11): 1131–1134. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1038%2Fnmeth.3139">10.1038/nmeth.3139</a>. <a href="/wiki/PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4216935">4216935</a></span>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/25282611">25282611</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Nature+Methods&rft.atitle=Time-resolved+crystallography+using+the+Hadamard+transform&rft.volume=11&rft.issue=11&rft.pages=1131-1134&rft.date=2014-09&rft_id=https%3A%2F%2Fwww.ncbi.nlm.nih.gov%2Fpmc%2Farticles%2FPMC4216935%23id-name%3DPMC&rft_id=info%3Apmid%2F25282611&rft_id=info%3Adoi%2F10.1038%2Fnmeth.3139&rft.aulast=Yorke&rft.aufirst=Briony+A.&rft.au=Beddard%2C+Godfrey&rft.au=Owen%2C+Robin+L.&rft.au=Pearson%2C+Arwen+R.&rft_id=https%3A%2F%2Fwww.ncbi.nlm.nih.gov%2Fpmc%2Farticles%2FPMC4216935&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHadamard+transform" class="Z3988"></span></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=Hadamard_transform&action=edit&section=16" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist"> <div class="mw-references-wrap mw-references-columns"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">Compare Figure 1 in <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFTownsendThornton" class="citation conference cs1">Townsend, W.J.; Thornton, M.A. "Walsh spectrum computations using Cayley graphs". <i>Proceedings of the 44th IEEE 2001 Midwest Symposium on Circuits and Systems (MWSCAS 2001)</i>. MWSCAS-01. IEEE. <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%2Fmwscas.2001.986127">10.1109/mwscas.2001.986127</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.atitle=Walsh+spectrum+computations+using+Cayley+graphs&rft.btitle=Proceedings+of+the+44th+IEEE+2001+Midwest+Symposium+on+Circuits+and+Systems+%28MWSCAS+2001%29&rft.series=MWSCAS-01&rft.pub=IEEE&rft_id=info%3Adoi%2F10.1109%2Fmwscas.2001.986127&rft.aulast=Townsend&rft.aufirst=W.J.&rft.au=Thornton%2C+M.A.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHadamard+transform" class="Z3988"></span></span> </li> <li id="cite_note-kunz-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-kunz_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-kunz_2-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFKunz1979" class="citation journal cs1">Kunz, H.O. (1979). "On the Equivalence Between One-Dimensional Discrete Walsh–Hadamard and Multidimensional Discrete Fourier Transforms". <i>IEEE Transactions on Computers</i>. <b>28</b> (3): 267–8. <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%2FTC.1979.1675334">10.1109/TC.1979.1675334</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:206621901">206621901</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=IEEE+Transactions+on+Computers&rft.atitle=On+the+Equivalence+Between+One-Dimensional+Discrete+Walsh%E2%80%93Hadamard+and+Multidimensional+Discrete+Fourier+Transforms&rft.volume=28&rft.issue=3&rft.pages=267-8&rft.date=1979&rft_id=info%3Adoi%2F10.1109%2FTC.1979.1675334&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A206621901%23id-name%3DS2CID&rft.aulast=Kunz&rft.aufirst=H.O.&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHadamard+transform" 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"><a rel="nofollow" class="external text" href="https://www.staff.uni-mainz.de/pommeren/Kryptologie/Bitblock/A_Nonlin/Fourier.pdf">Fourier Analysis of Boolean Maps– A Tutorial –, pp. 12–13</a></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://www.cse.iitk.ac.in/users/rmittal/prev_course/s19/reports/5_algo.pdf">Lecture 5: Basic quantum algorithms, Rajat Mittal, pp. 4–5</a></span> </li> <li id="cite_note-Nielsen-Chuang-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-Nielsen-Chuang_5-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFNielsenChuang2010" class="citation book cs1"><a href="/wiki/Michael_Nielsen" title="Michael Nielsen">Nielsen, Michael A.</a>; <a href="/wiki/Isaac_Chuang" title="Isaac Chuang">Chuang, Isaac</a> (2010). <a rel="nofollow" class="external text" href="https://www.cambridge.org/9781107002173"><i>Quantum Computation and Quantum Information</i></a>. Cambridge: <a href="/wiki/Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-10700-217-3" title="Special:BookSources/978-1-10700-217-3"><bdi>978-1-10700-217-3</bdi></a>. <a href="/wiki/OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/43641333">43641333</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Quantum+Computation+and+Quantum+Information&rft.place=Cambridge&rft.pub=Cambridge+University+Press&rft.date=2010&rft_id=info%3Aoclcnum%2F43641333&rft.isbn=978-1-10700-217-3&rft.aulast=Nielsen&rft.aufirst=Michael+A.&rft.au=Chuang%2C+Isaac&rft_id=https%3A%2F%2Fwww.cambridge.org%2F9781107002173&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHadamard+transform" class="Z3988"></span></span> </li> <li id="cite_note-shukla2024efficient-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-shukla2024efficient_6-0">^</a></b></span> <span class="reference-text"> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFAlok_Shukla_and_Prakash_Vedula2024" class="citation journal cs1 cs1-prop-long-vol">Alok Shukla and Prakash Vedula (2024). "An efficient quantum algorithm for preparation of uniform quantum superposition states". <i>Quantum Information Processing</i>. 23:38 (1): 38. <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/2306.11747">2306.11747</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/2024QuIP...23...38S">2024QuIP...23...38S</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-024-04258-4">10.1007/s11128-024-04258-4</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Quantum+Information+Processing&rft.atitle=An+efficient+quantum+algorithm+for+preparation+of+uniform+quantum+superposition+states&rft.volume=23%3A38&rft.issue=1&rft.pages=38&rft.date=2024&rft_id=info%3Aarxiv%2F2306.11747&rft_id=info%3Adoi%2F10.1007%2Fs11128-024-04258-4&rft_id=info%3Abibcode%2F2024QuIP...23...38S&rft.au=Alok+Shukla+and+Prakash+Vedula&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHadamard+transform" class="Z3988"></span></span> </li> <li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHendyPenny1989" class="citation journal cs1">Hendy, Michael D.; Penny, David (December 1989). <a rel="nofollow" class="external text" href="https://academic.oup.com/sysbio/article-lookup/doi/10.2307/2992396">"A Framework for the Quantitative Study of Evolutionary Trees"</a>. <i>Systematic Zoology</i>. <b>38</b> (4): 297. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.2307%2F2992396">10.2307/2992396</a>. <a href="/wiki/JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2992396">2992396</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Systematic+Zoology&rft.atitle=A+Framework+for+the+Quantitative+Study+of+Evolutionary+Trees&rft.volume=38&rft.issue=4&rft.pages=297&rft.date=1989-12&rft_id=info%3Adoi%2F10.2307%2F2992396&rft_id=https%3A%2F%2Fwww.jstor.org%2Fstable%2F2992396%23id-name%3DJSTOR&rft.aulast=Hendy&rft.aufirst=Michael+D.&rft.au=Penny%2C+David&rft_id=https%3A%2F%2Facademic.oup.com%2Fsysbio%2Farticle-lookup%2Fdoi%2F10.2307%2F2992396&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHadamard+transform" class="Z3988"></span></span> </li> <li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHendyPenny1993" class="citation journal cs1">Hendy, Michael D.; Penny, David (January 1993). <a rel="nofollow" class="external text" href="http://link.springer.com/10.1007/BF02638451">"Spectral analysis of phylogenetic data"</a>. <i>Journal of Classification</i>. <b>10</b> (1): 5–24. <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%2FBF02638451">10.1007/BF02638451</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0176-4268">0176-4268</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:122466038">122466038</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Classification&rft.atitle=Spectral+analysis+of+phylogenetic+data&rft.volume=10&rft.issue=1&rft.pages=5-24&rft.date=1993-01&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A122466038%23id-name%3DS2CID&rft.issn=0176-4268&rft_id=info%3Adoi%2F10.1007%2FBF02638451&rft.aulast=Hendy&rft.aufirst=Michael+D.&rft.au=Penny%2C+David&rft_id=http%3A%2F%2Flink.springer.com%2F10.1007%2FBF02638451&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHadamard+transform" class="Z3988"></span></span> </li> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text">Székely, L. A., Erdős, P. L., Steel, M. A., & Penny, D. (1993). A Fourier inversion formula for evolutionary trees. <i>Applied mathematics letters</i>, <i>6</i>(2), 13–16.</span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFelsenstein1981" class="citation journal cs1">Felsenstein, Joseph (November 1981). <a rel="nofollow" class="external text" href="http://link.springer.com/10.1007/BF01734359">"Evolutionary trees from DNA sequences: A maximum likelihood approach"</a>. <i>Journal of Molecular Evolution</i>. <b>17</b> (6): 368–376. <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/1981JMolE..17..368F">1981JMolE..17..368F</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%2FBF01734359">10.1007/BF01734359</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0022-2844">0022-2844</a>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/7288891">7288891</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:8024924">8024924</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Molecular+Evolution&rft.atitle=Evolutionary+trees+from+DNA+sequences%3A+A+maximum+likelihood+approach&rft.volume=17&rft.issue=6&rft.pages=368-376&rft.date=1981-11&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A8024924%23id-name%3DS2CID&rft_id=info%3Abibcode%2F1981JMolE..17..368F&rft.issn=0022-2844&rft_id=info%3Adoi%2F10.1007%2FBF01734359&rft_id=info%3Apmid%2F7288891&rft.aulast=Felsenstein&rft.aufirst=Joseph&rft_id=http%3A%2F%2Flink.springer.com%2F10.1007%2FBF01734359&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHadamard+transform" class="Z3988"></span></span> </li> <li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFStamatakis2019" class="citation cs2">Stamatakis, Alexandros (2019), Warnow, Tandy (ed.), <a rel="nofollow" class="external text" href="http://link.springer.com/10.1007/978-3-030-10837-3_1">"A Review of Approaches for Optimizing Phylogenetic Likelihood Calculations"</a>, <i>Bioinformatics and Phylogenetics</i>, Computational Biology, vol. 29, Cham: Springer International Publishing, pp. 1–19, <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%2F978-3-030-10837-3_1">10.1007/978-3-030-10837-3_1</a>, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-3-030-10836-6" title="Special:BookSources/978-3-030-10836-6"><bdi>978-3-030-10836-6</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:145834168">145834168</a><span class="reference-accessdate">, retrieved <span class="nowrap">2020-10-10</span></span></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Bioinformatics+and+Phylogenetics&rft.atitle=A+Review+of+Approaches+for+Optimizing+Phylogenetic+Likelihood+Calculations&rft.volume=29&rft.pages=1-19&rft.date=2019&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A145834168%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1007%2F978-3-030-10837-3_1&rft.isbn=978-3-030-10836-6&rft.aulast=Stamatakis&rft.aufirst=Alexandros&rft_id=http%3A%2F%2Flink.springer.com%2F10.1007%2F978-3-030-10837-3_1&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHadamard+transform" class="Z3988"></span></span> </li> <li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFChorHendyHollandPenny2000" class="citation journal cs1"><a href="/wiki/Benny_Chor" title="Benny Chor">Chor, Benny</a>; Hendy, Michael D.; Holland, Barbara R.; Penny, David (2000-10-01). <a rel="nofollow" class="external text" href="http://academic.oup.com/mbe/article/17/10/1529/956181">"Multiple Maxima of Likelihood in Phylogenetic Trees: An Analytic Approach"</a>. <i>Molecular Biology and Evolution</i>. <b>17</b> (10): 1529–1541. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Foxfordjournals.molbev.a026252">10.1093/oxfordjournals.molbev.a026252</a></span>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1537-1719">1537-1719</a>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/11018159">11018159</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Molecular+Biology+and+Evolution&rft.atitle=Multiple+Maxima+of+Likelihood+in+Phylogenetic+Trees%3A+An+Analytic+Approach&rft.volume=17&rft.issue=10&rft.pages=1529-1541&rft.date=2000-10-01&rft.issn=1537-1719&rft_id=info%3Apmid%2F11018159&rft_id=info%3Adoi%2F10.1093%2Foxfordjournals.molbev.a026252&rft.aulast=Chor&rft.aufirst=Benny&rft.au=Hendy%2C+Michael+D.&rft.au=Holland%2C+Barbara+R.&rft.au=Penny%2C+David&rft_id=http%3A%2F%2Facademic.oup.com%2Fmbe%2Farticle%2F17%2F10%2F1529%2F956181&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHadamard+transform" class="Z3988"></span></span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMatsenSteel2007" class="citation journal cs1">Matsen, Frederick A.; Steel, Mike (2007-10-01). <a href="/wiki/C%C3%A9cile_An%C3%A9" title="Cécile Ané">Ané, Cécile</a>; Sullivan, Jack (eds.). <a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F10635150701627304">"Phylogenetic Mixtures on a Single Tree Can Mimic a Tree of Another Topology"</a>. <i>Systematic Biology</i>. <b>56</b> (5): 767–775. <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/0704.2260">0704.2260</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F10635150701627304">10.1080/10635150701627304</a></span>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1076-836X">1076-836X</a>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/17886146">17886146</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Systematic+Biology&rft.atitle=Phylogenetic+Mixtures+on+a+Single+Tree+Can+Mimic+a+Tree+of+Another+Topology&rft.volume=56&rft.issue=5&rft.pages=767-775&rft.date=2007-10-01&rft_id=info%3Aarxiv%2F0704.2260&rft.issn=1076-836X&rft_id=info%3Apmid%2F17886146&rft_id=info%3Adoi%2F10.1080%2F10635150701627304&rft.aulast=Matsen&rft.aufirst=Frederick+A.&rft.au=Steel%2C+Mike&rft_id=https%3A%2F%2Fdoi.org%2F10.1080%252F10635150701627304&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHadamard+transform" class="Z3988"></span></span> </li> <li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFWaddellSteel1997" class="citation journal cs1">Waddell, Peter J; Steel, M.A (December 1997). "General Time-Reversible Distances with Unequal Rates across Sites: Mixing Γ and Inverse Gaussian Distributions with Invariant Sites". <i>Molecular Phylogenetics and Evolution</i>. <b>8</b> (3): 398–414. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1006%2Fmpev.1997.0452">10.1006/mpev.1997.0452</a>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/9417897">9417897</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Molecular+Phylogenetics+and+Evolution&rft.atitle=General+Time-Reversible+Distances+with+Unequal+Rates+across+Sites%3A+Mixing+%CE%93+and+Inverse+Gaussian+Distributions+with+Invariant+Sites&rft.volume=8&rft.issue=3&rft.pages=398-414&rft.date=1997-12&rft_id=info%3Adoi%2F10.1006%2Fmpev.1997.0452&rft_id=info%3Apmid%2F9417897&rft.aulast=Waddell&rft.aufirst=Peter+J&rft.au=Steel%2C+M.A&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHadamard+transform" class="Z3988"></span></span> </li> <li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSteelHendyPenny1993" class="citation journal cs1">Steel, M. A.; Hendy, M. D.; Penny, D. (1993-12-01). <a rel="nofollow" class="external text" href="https://academic.oup.com/sysbio/article-lookup/doi/10.1093/sysbio/42.4.581">"Parsimony Can Be Consistent!"</a>. <i>Systematic Biology</i>. <b>42</b> (4): 581–587. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fsysbio%2F42.4.581">10.1093/sysbio/42.4.581</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1063-5157">1063-5157</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Systematic+Biology&rft.atitle=Parsimony+Can+Be+Consistent%21&rft.volume=42&rft.issue=4&rft.pages=581-587&rft.date=1993-12-01&rft_id=info%3Adoi%2F10.1093%2Fsysbio%2F42.4.581&rft.issn=1063-5157&rft.aulast=Steel&rft.aufirst=M.+A.&rft.au=Hendy%2C+M.+D.&rft.au=Penny%2C+D.&rft_id=https%3A%2F%2Facademic.oup.com%2Fsysbio%2Farticle-lookup%2Fdoi%2F10.1093%2Fsysbio%2F42.4.581&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHadamard+transform" class="Z3988"></span></span> </li> <li id="cite_note-:0-16"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_16-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_16-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-:0_16-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="CITEREFHendyPennySteel1994" class="citation journal cs1">Hendy, M. D.; Penny, D.; Steel, M. A. (1994-04-12). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC43572">"A discrete Fourier analysis for evolutionary trees"</a>. <i>Proceedings of the National Academy of Sciences</i>. <b>91</b> (8): 3339–3343. <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/1994PNAS...91.3339H">1994PNAS...91.3339H</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1073%2Fpnas.91.8.3339">10.1073/pnas.91.8.3339</a></span>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0027-8424">0027-8424</a>. <a href="/wiki/PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC43572">43572</a></span>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/8159749">8159749</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+National+Academy+of+Sciences&rft.atitle=A+discrete+Fourier+analysis+for+evolutionary+trees.&rft.volume=91&rft.issue=8&rft.pages=3339-3343&rft.date=1994-04-12&rft_id=https%3A%2F%2Fwww.ncbi.nlm.nih.gov%2Fpmc%2Farticles%2FPMC43572%23id-name%3DPMC&rft_id=info%3Abibcode%2F1994PNAS...91.3339H&rft_id=info%3Apmid%2F8159749&rft_id=info%3Adoi%2F10.1073%2Fpnas.91.8.3339&rft.issn=0027-8424&rft.aulast=Hendy&rft.aufirst=M.+D.&rft.au=Penny%2C+D.&rft.au=Steel%2C+M.+A.&rft_id=https%3A%2F%2Fwww.ncbi.nlm.nih.gov%2Fpmc%2Farticles%2FPMC43572&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHadamard+transform" class="Z3988"></span></span> </li> <li id="cite_note-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-17">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFMiyamotoKoopSlightomGoodman1988" class="citation journal cs1">Miyamoto, M. M.; Koop, B. F.; Slightom, J. L.; Goodman, M.; Tennant, M. R. (1988-10-01). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC282245">"Molecular systematics of higher primates: genealogical relations and classification"</a>. <i>Proceedings of the National Academy of Sciences</i>. <b>85</b> (20): 7627–7631. <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/1988PNAS...85.7627M">1988PNAS...85.7627M</a>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1073%2Fpnas.85.20.7627">10.1073/pnas.85.20.7627</a></span>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0027-8424">0027-8424</a>. <a href="/wiki/PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC282245">282245</a></span>. <a href="/wiki/PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/3174657">3174657</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+National+Academy+of+Sciences&rft.atitle=Molecular+systematics+of+higher+primates%3A+genealogical+relations+and+classification.&rft.volume=85&rft.issue=20&rft.pages=7627-7631&rft.date=1988-10-01&rft_id=https%3A%2F%2Fwww.ncbi.nlm.nih.gov%2Fpmc%2Farticles%2FPMC282245%23id-name%3DPMC&rft_id=info%3Abibcode%2F1988PNAS...85.7627M&rft_id=info%3Apmid%2F3174657&rft_id=info%3Adoi%2F10.1073%2Fpnas.85.20.7627&rft.issn=0027-8424&rft.aulast=Miyamoto&rft.aufirst=M.+M.&rft.au=Koop%2C+B.+F.&rft.au=Slightom%2C+J.+L.&rft.au=Goodman%2C+M.&rft.au=Tennant%2C+M.+R.&rft_id=https%3A%2F%2Fwww.ncbi.nlm.nih.gov%2Fpmc%2Farticles%2FPMC282245&rfr_id=info%3Asid%2Fen.wikipedia.org%3AHadamard+transform" class="Z3988"></span></span> </li> </ol></div></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1&useformat=desktop" 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=Hadamard_transform&oldid=1259857899">https://en.wikipedia.org/w/index.php?title=Hadamard_transform&oldid=1259857899</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Categories</a>: <ul><li><a href="/wiki/Category:Quantum_algorithms" title="Category:Quantum algorithms">Quantum algorithms</a></li><li><a href="/wiki/Category:Transforms" title="Category:Transforms">Transforms</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:CS1:_long_volume_value" title="Category:CS1: long volume value">CS1: long volume value</a></li><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Use_American_English_from_January_2019" title="Category:Use American English from January 2019">Use American English from January 2019</a></li><li><a href="/wiki/Category:All_Wikipedia_articles_written_in_American_English" title="Category:All Wikipedia articles written in American English">All Wikipedia articles written in American English</a></li><li><a href="/wiki/Category:Pages_with_French_IPA" title="Category:Pages with French IPA">Pages with French IPA</a></li><li><a href="/wiki/Category:Articles_to_be_expanded_from_April_2024" title="Category:Articles to be expanded from April 2024">Articles to be expanded from April 2024</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 27 November 2024, at 13:18<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=Hadamard_transform&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-59bbd5969d-vkxrt","wgBackendResponseTime":158,"wgPageParseReport":{"limitreport":{"cputime":"0.486","walltime":"0.691","ppvisitednodes":{"value":2211,"limit":1000000},"postexpandincludesize":{"value":52479,"limit":2097152},"templateargumentsize":{"value":1550,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":6,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":74434,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 430.528 1 -total"," 25.72% 110.739 1 Template:IPA"," 21.65% 93.205 1 Template:Reflist"," 17.13% 73.751 13 Template:Cite_journal"," 15.96% 68.704 2 Template:Cite_web"," 14.39% 61.961 1 Template:Short_description"," 9.61% 41.376 2 Template:Pagetype"," 5.83% 25.113 1 Template:Missing_information"," 5.37% 23.129 1 Template:Ambox"," 4.46% 19.192 1 Template:Redirect-distinguish"]},"scribunto":{"limitreport-timeusage":{"value":"0.273","limit":"10.000"},"limitreport-memusage":{"value":18994464,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-7fc47fc68d-pmb55","timestamp":"20241128202144","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Hadamard transform","url":"https:\/\/en.wikipedia.org\/wiki\/Hadamard_transform","sameAs":"http:\/\/www.wikidata.org\/entity\/Q1014065","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q1014065","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-05-04T14:44:38Z","dateModified":"2024-11-27T13:18:04Z","image":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/a\/aa\/1010_0110_Walsh_spectrum_%28single_row%29.svg","headline":"example of a generalized class of Fourier transforms"}</script> </body> </html>

CINXE.COM

Hadamard transform - Wikipedia