Quantum Circuits for the Unitary Permutation Problem

DOI10.1007/978-3-319-17142-5_28zbMATH Open1459.81030arXiv1405.5205OpenAlexW2274873607MaRDI QIDQ2948477FDOQ2948477

Authors: Stefano Facchini, Simon Perdrix 

Publication date: 30 September 2015

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

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.

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

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

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)

Cited In (4)

• Title not available (Why is that?)
• The magic of universal quantum computing with permutations
• A diagrammatic approach to information transmission in generalised switches
• 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)