Swap test

Formally, the swap test takes two input states ${\displaystyle |\varphi ⟩}$ and ${\displaystyle |\psi ⟩}$ and outputs a Bernoulli random variable that is 1 with probability ${\displaystyle \frac{1}{2}-\frac{1}{2}{|⟨\psi |\varphi ⟩|}^2}$ (where the expressions here use bra–ket notation). This allows one to, for example, estimate the squared inner product between the two states, ${\displaystyle {|⟨\psi |\varphi ⟩|}^2}$, to ${\displaystyle \epsilon }$ additive error by taking the average over ${\displaystyle O(\frac{1}{{\epsilon }^2})}$ runs of the swap test. This requires ${\displaystyle O(\frac{1}{{\epsilon }^2})}$ copies of the input states. The squared inner product roughly measures "overlap" between the two states, and can be used in linear-algebraic applications, including clustering quantum states.

Explanation of the circuit

Consider two states: ${\displaystyle |\varphi ⟩}$ and ${\displaystyle |\psi ⟩}$. The state of the system at the beginning of the protocol is ${\displaystyle |0,\varphi ,\psi ⟩}$. After the Hadamard gate, the state of the system is ${\displaystyle \frac{1}{\sqrt{2}}(|0,\varphi ,\psi ⟩+|1,\varphi ,\psi ⟩)}$. The controlled SWAP gate transforms the state into ${\displaystyle \frac{1}{\sqrt{2}}(|0,\varphi ,\psi ⟩+|1,\psi ,\varphi ⟩)}$. The second Hadamard gate results in $${\displaystyle \frac{1}{2}(|0,\varphi ,\psi ⟩+|1,\varphi ,\psi ⟩+|0,\psi ,\varphi ⟩-|1,\psi ,\varphi ⟩)=\frac{1}{2}|0⟩(|\varphi ,\psi ⟩+|\psi ,\varphi ⟩)+\frac{1}{2}|1⟩(|\varphi ,\psi ⟩-|\psi ,\varphi ⟩)}$$

The measurement gate on the first qubit ensures that it's 0 with a probability of

$${\displaystyle P(\text{First qubit}=0)=\frac{1}{2}(⟨\varphi |⟨\psi |+⟨\psi |⟨\varphi |)\frac{1}{2}(|\varphi ⟩|\psi ⟩+|\psi ⟩|\varphi ⟩)=\frac{1}{2}+\frac{1}{2}{|⟨\psi |\varphi ⟩|}^2}$$

when measured. If ${\displaystyle \psi }$ and ${\displaystyle \varphi }$ are orthogonal ${\displaystyle ({|⟨\psi |\varphi ⟩|}^2=0)}$, then the probability that 0 is measured is ${\displaystyle \frac{1}{2}}$. If the states are equal ${\displaystyle ({|⟨\psi |\varphi ⟩|}^2=1)}$, then the probability that 0 is measured is 1.

In general, for ${\displaystyle P}$ trials of the swap test using ${\displaystyle P}$ copies of ${\displaystyle |\varphi ⟩}$ and ${\displaystyle P}$ copies of ${\displaystyle |\psi ⟩}$, the fraction of measurements that are zero is ${\displaystyle 1-\frac{1}{P}\sum _{i=1}^P{M}_i}$, so by taking ${\displaystyle P\to \mathrm{\infty }}$, one can get arbitrary precision of this value.

Below is the pseudocode for estimating the value of ${\displaystyle |⟨\psi |\varphi ⟩{|}^2}$ using P copies of ${\displaystyle |\psi ⟩}$ and ${\displaystyle |\varphi ⟩}$:

<b id="mwWw">Inputs</b> <i id="mwXA">P</i> copies each of the <i id="mwXQ">n</i> qubits quantum states <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt55" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"|\\psi\\rangle"}}' id="mwXg"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle |\psi \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>ψ<!-- ψ --></mi> <mo fence="false" stretchy="false">⟩<!-- ⟩ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\psi \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cc27f1893b769a08cd6b296e115a29e61cab675e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.065ex; height:2.843ex;" alt="{\displaystyle |\psi \rangle }"/></span> and <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt56" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"|\\phi\\rangle"}}' id="mwXw"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle |\phi \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>ϕ<!-- ϕ --></mi> <mo fence="false" stretchy="false">⟩<!-- ⟩ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\phi \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/312d43de853a9e6ca74888e63394fc8081f56a43" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.937ex; height:2.843ex;" alt="{\displaystyle |\phi \rangle }"/></span> <b id="mwYA">Output</b> An estimate of <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt57" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"|\\langle \\psi | \\phi \\rangle |^2"}}' id="mwYQ"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle |\langle \psi |\phi \rangle |^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mo fence="false" stretchy="false">⟨<!-- ⟨ --></mo> <mi>ψ<!-- ψ --></mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>ϕ<!-- ϕ --></mi> <mo fence="false" stretchy="false">⟩<!-- ⟩ --></mo> <msup> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\langle \psi |\phi \rangle |^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/630889b110ce20f82e0e90be2513bd63c39c074d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.703ex; height:3.343ex;" alt="{\displaystyle |\langle \psi |\phi \rangle |^{2}}"/></span> <b id="mwYg">for</b> <i id="mwYw">j</i> ranging from 1 to <i id="mwZA">P</i>: initialize an ancilla qubit <i id="mwZQ">A</i> in state <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt58" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"|0\\rangle"}}' id="mwZg"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" 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> apply a Hadamard gate to the ancilla qubit <i id="mwZw">A</i> <b id="mwaA">for</b> <i id="mwaQ">i</i> ranging from 1 to <i id="mwag">n</i>: apply CSWAP to <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt59" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\psi_i"}}' id="mwaw"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \psi _{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>ψ<!-- ψ --></mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \psi _{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3e709a809cfd3cfbb647fe22c8d1f81573f4c7ae" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.313ex; height:2.509ex;" alt="{\displaystyle \psi _{i}}"/></span> and <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt60" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\phi_i"}}' id="mwbA"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \phi _{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>ϕ<!-- ϕ --></mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \phi _{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/0182dbf29b54844c92fd9b0311778a02a38398ec" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.185ex; height:2.509ex;" alt="{\displaystyle \phi _{i}}"/></span> (the <i id="mwbQ">i</i>th qubit of the <i id="mwbg">j</i>th copy of <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt61" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"|\\psi\\rangle"}}' id="mwbw"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle |\psi \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>ψ<!-- ψ --></mi> <mo fence="false" stretchy="false">⟩<!-- ⟩ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\psi \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/cc27f1893b769a08cd6b296e115a29e61cab675e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.065ex; height:2.843ex;" alt="{\displaystyle |\psi \rangle }"/></span> and <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt62" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"|\\phi\\rangle"}}' id="mwcA"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle |\phi \rangle }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>ϕ<!-- ϕ --></mi> <mo fence="false" stretchy="false">⟩<!-- ⟩ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\phi \rangle }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/312d43de853a9e6ca74888e63394fc8081f56a43" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.937ex; height:2.843ex;" alt="{\displaystyle |\phi \rangle }"/></span>), with <i id="mwcQ">A</i> as the control qubit apply a Hadamard gate to the ancilla qubit <i id="mwcg">A</i> measure <i id="mwcw">A</i> in the <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt63" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"Z"}}' id="mwdA"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle Z}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>Z</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle Z}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1cc6b75e09a8aa3f04d8584b11db534f88fb56bd" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.68ex; height:2.176ex;" alt="{\displaystyle Z}"/></span> basis and record the measurement <i id="mwdQ">M<sub id="mwdg">j</sub></i> as either a 0 or 1 compute <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt64" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"s = 1 - \\textstyle\\frac{2}{P} \\textstyle\\sum_{i = 1}^{P} M_i"}}' id="mwdw"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle s=1-\textstyle {\frac {2}{P}}\textstyle \sum _{i=1}^{P}M_{i}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>s</mi> <mo>=</mo> <mn>1</mn> <mo>−<!-- − --></mo> <mstyle displaystyle="false" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mn>2</mn> <mi>P</mi> </mfrac> </mrow> <mstyle displaystyle="false" scriptlevel="0"> <munderover> <mo>∑<!-- ∑ --></mo> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> <mo>=</mo> <mn>1</mn> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mi>P</mi> </mrow> </munderover> <msub> <mi>M</mi> <mrow class="MJX-TeXAtom-ORD"> <mi>i</mi> </mrow> </msub> </mstyle> </mstyle> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle s=1-\textstyle {\frac {2}{P}}\textstyle \sum _{i=1}^{P}M_{i}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/806d04c811a2e0d2e070a95c910310a374ff9f2a" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:19.444ex; height:3.676ex;" alt="{\displaystyle s=1-\textstyle {\frac {2}{P}}\textstyle \sum _{i=1}^{P}M_{i}}"/></span>. <b id="mweA">return</b> <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt65" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"s"}}' id="mweQ"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle s}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>s</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle s}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/01d131dfd7673938b947072a13a9744fe997e632" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}"/></span> as our estimate of <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt66" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"|\\langle \\psi | \\phi \\rangle |^2"}}' id="mweg"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle |\langle \psi |\phi \rangle |^{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mo fence="false" stretchy="false">⟨<!-- ⟨ --></mo> <mi>ψ<!-- ψ --></mi> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mi>ϕ<!-- ϕ --></mi> <mo fence="false" stretchy="false">⟩<!-- ⟩ --></mo> <msup> <mrow class="MJX-TeXAtom-ORD"> <mo stretchy="false">|</mo> </mrow> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle |\langle \psi |\phi \rangle |^{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/630889b110ce20f82e0e90be2513bd63c39c074d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.703ex; height:3.343ex;" alt="{\displaystyle |\langle \psi |\phi \rangle |^{2}}"/></span>