Quantum Circuits for the Unitary Permutation Problem

Stefano Facchini 1 Simon Perdrix 2, 3
1 LIG Laboratoire d'Informatique de Grenoble - CAPP
LIG - Laboratoire d'Informatique de Grenoble
3 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
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 $\frac{n(n-1)}2$ quantum switches in the new model. We refine these results by proving that $n\log_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.
Type de document :
Communication dans un congrès
TAMC 2015, May 2015, Singapore, Singapore. 9076, pp.324-331, 2015, Theory and Applications of Models of Computation. 〈10.1007/978-3-319-17142-5_28〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00994182
Contributeur : Simon Perdrix <>
Soumis le : mercredi 21 mai 2014 - 09:56:53
Dernière modification le : jeudi 11 janvier 2018 - 06:27:33

Identifiants

Citation

Stefano Facchini, Simon Perdrix. Quantum Circuits for the Unitary Permutation Problem. TAMC 2015, May 2015, Singapore, Singapore. 9076, pp.324-331, 2015, Theory and Applications of Models of Computation. 〈10.1007/978-3-319-17142-5_28〉. 〈hal-00994182〉

Partager

Métriques

Consultations de la notice

241