Quantum multi-state Swap Test: an algorithm for estimating overlaps of arbitrary number quantum states

Abstract Estimating the overlap between two states is an important task with several applications in quantum information. However, the typical swap test circuit can only measure a sole pair of quantum states at a time. In this study, a recursive quantum circuit is designed to measure overlaps of n quantum states $\left | {\phi _{1} } \right \rangle ,\left | {\phi _{2} } \right \rangle ,\ldots\left | {\phi _{n} }\right \rangle $ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>|</mml:mo> <mml:msub> <mml:mi>ϕ</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>〉</mml:mo> </mml:mrow> <mml:mo>,</mml:mo> <mml:mrow> <mml:mo>|</mml:mo> <mml:msub> <mml:mi>ϕ</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>〉</mml:mo> </mml:mrow> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mrow> <mml:mo>|</mml:mo> <mml:msub> <mml:mi>ϕ</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>〉</mml:mo> </mml:mrow> </mml:math> concurrently with $O(k2^{k})$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>k</mml:mi> </mml:msup> <mml:mo>)</mml:mo> </mml:math> controlled-swap(CSWAP) gates and $O(k)$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>k</mml:mi> <mml:mo>)</mml:mo> </mml:math> ancillary qubits, where $k=\left \lceil {\log n} \right \rceil $ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>k</mml:mi> <mml:mo>=</mml:mo> <mml:mrow> <mml:mo>⌈</mml:mo> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>⌉</mml:mo> </mml:mrow> </mml:math> . All pairwise overlaps among input quantum states $|\langle \phi _{i}|\phi _{j}\rangle |^{2}$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mo>|</mml:mo> <mml:mo>〈</mml:mo> <mml:msub> <mml:mi>ϕ</mml:mi> <mml:mi>i</mml:mi> </mml:msub> <mml:msup> <mml:mrow> <mml:mo>|</mml:mo> <mml:msub> <mml:mi>ϕ</mml:mi> <mml:mi>j</mml:mi> </mml:msub> <mml:mo>〉</mml:mo> <mml:mo>|</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:msup> </mml:math> can be obtained in this circuit. Compared with existing scheme for measuring the overlap of multiple quantum states, the circuit provides higher precision and less consumption of ancillary qubits. In addition, some simulation experiments are performed on IBM quantum cloud platform to verify the superiority of this algorithm.