Quantum Circuits for the Unitary Permutation Problem

DOI10.1007/978-3-319-17142-5_28MaRDI QIDQ2948477zbMATH OpenOpenAlexFDO

Authors Stefano Facchini, Simon Perdrix

Publication date 30 September 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.5205

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Networks and circuits as models of computation; circuit complexity (68Q06) Quantum gates (81P65)

Abstract: We consider the Unitary Permutation problem which consists, given $n$ unitary gates $U_1,ldots,U_n$ and a permutation $sigma$ of $1,ldots,n$, in applying the unitary gates in the order specified by $sigma$, i.e. in performing $U_{sigma(n)}ldots{U}_{sigma(1)}$. This problem has been introduced and investigated by Colnaghi et al. where two models of computations are considered. This first is the (standard) model of query complexity: the complexity measure is the number of calls to any of the unitary gates $U_i$ in a quantum circuit which solves the problem. The second model provides quantum switches and treats unitary transformations as inputs of second order. In that case the complexity measure is the number of quantum switches. In their paper, Colnaghi et al. have shown that the problem can be solved within $n^2$ calls in the query model and $fracn(n-1)2$ quantum switches in the new model. We refine these results by proving that $nlo{g}_2(n)+Theta(n)$ quantum switches are necessary and sufficient to solve this problem, whereas $n^2-2n+4$ calls are sufficient to solve this problem in the standard quantum circuit model. We prove, with an additional assumption on the family of gates used in the circuits, that $n^2-o(n^{7/4+epsilon})$ queries are required, for any $epsilon>0$. The upper and lower bounds for the standard quantum circuit model are established by pointing out connections with the permutation as substring problem introduced by Karp.

Recommendations

• Permutational quantum computing
• Quantum queries on permutations
• Quantum complexity of permutations
• Quantum Queries on Permutations with a Promise
• Efficient circuits for exact-universal computation with qudits
• The magic of universal quantum computing with permutations
• Some algorithms for calculating unitary matrices for quantum circuits
• Computational complexity of uniform quantum circuit families and quantum Turing machines
• Efficient quantum circuits for Schur and Clebsch-Gordan transforms
• On quantum one-way permutations

Cited in

(4)

• scientific article; zbMATH DE number 7559395 (Why is no real title available?)
• A diagrammatic approach to information transmission in generalised switches
• The magic of universal quantum computing with permutations
• Quantum complexity of permutations

This page was built for publication: Quantum Circuits for the Unitary Permutation Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2948477)