SWAP test for an arbitrary number of quantum states

Abstract

We develop a recursive algorithm to generalize the quantum SWAP test for an arbitrary number m of quantum states requiring O(m) controlled-swap (CSWAP) gates and O(logm)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log m)$$\end{document} ancillary qubits. We construct a quantum circuit able to simultaneously measure overlaps |⟨ϕi,ϕj⟩|2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|\langle \phi _i, \phi _j\rangle |^2$$\end{document} of m arbitrary pure states |ϕ1…ϕm⟩\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${|{\phi _1\ldots \phi _m}\rangle }$$\end{document}. Our construction relies on a pairing unitary that generates a superposition state where every pair of input states is labeled by a basis state formed by the ancillaries. By implementing a simple genetic algorithm, we give numerical evidence indicating that our method of labeling each pair of inputs using CSWAP gates is optimal up to m=8\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m=8$$\end{document}. Potential applications of the new circuits in the context of quantum machine learning are discussed.