# Quantum Circuits for Sparse Isometries

Emanuel Malvetti1, Raban Iten2, and Roger Colbeck3

1Department of Chemistry, Technische Universität München, Lichtenbergstraße 4, 85747 Garching, Germany
2ETH Zürich, 8093 Zürich, Switzerland
3Department of Mathematics, University of York, YO10 5DD, UK

### Abstract

We consider the task of breaking down a quantum computation given as an isometry into C-NOTs and single-qubit gates, while keeping the number of C-NOT gates small. Although several decompositions are known for general isometries, here we focus on a method based on Householder reflections that adapts well in the case of sparse isometries. We show how to use this method to decompose an arbitrary isometry before illustrating that the method can lead to significant improvements in the case of sparse isometries. We also discuss the classical complexity of this method and illustrate its effectiveness in the case of sparse state preparation by applying it to randomly chosen sparse states.

In order to realise a quantum computation on a quantum computer it is useful to break it down into a sequence of elementary gates. The number of elementary gates required for an arbitrary quantum computation scales exponentially in the number of qubits the computation acts on. However, useful quantum computations often come from a much smaller class and hence we would like decomposition methods that can exploit additional structure. In this work we introduce decomposition schemes that work on the set of sparse computations, showing that the number of elementary gates required dramatically decreases with the sparseness. Minimizing the number of elementary gates is particularly important for near term quantum devices, since each additional gate adds noise to the computation. We optimize our decomposition schemes for sparse computations on such devices, i.e., for a small number of qubits. The decomposition schemes have been implemented in UniversalQCompiler, an open source software package for compiling quantum computations.

### ► References

[1] A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, Elementary gates for quantum computation,'' Phys. Rev. A 52, 3457–3467 (1995).
https:/​/​doi.org/​10.1103/​PhysRevA.52.3457

[2] V. V. Shende, I. L. Markov, and S. S. Bullock, Minimal universal two-qubit controlled-not-based circuits,'' Phys. Rev. A 69, 062321 (2004).
https:/​/​doi.org/​10.1103/​PhysRevA.69.062321

[3] V. V. Shende, I. L. Markov, and S. S. Bullock, Smaller two-qubit circuits for quantum communication and computation,'' in Proceedings Design, Automation and Test in Europe Conference and Exhibition, Vol. 2 (2004) pp. 980–985.
https:/​/​doi.org/​10.1109/​DATE.2004.1269020

[4] V. V. Shende, S. S. Bullock, and I. L. Markov, Synthesis of quantum-logic circuits,'' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 25, 1000–1010 (2006).

[5] M. Plesch and Č. Brukner, Quantum-state preparation with universal gate decompositions,'' Phys. Rev. A 83, 032302 (2011).
https:/​/​doi.org/​10.1103/​PhysRevA.83.032302

[6] V. Bergholm, J. J. Vartiainen, M. Möttönen, and M. M. Salomaa, Quantum circuits with uniformly controlled one-qubit gates,'' Phys. Rev. A 71, 052330 (2005).
https:/​/​doi.org/​10.1103/​PhysRevA.71.052330

[7] R. Iten, R. Colbeck, I. Kukuljan, J. Home, and M. Christandl, Quantum circuits for isometries,'' Phys. Rev. A 93, 032318 (2016a).
https:/​/​doi.org/​10.1103/​PhysRevA.93.032318

[8] E. Knill, Approximation by quantum circuits,'' e-print arXiv:quant-ph/​9508006 (1995).
arXiv:quant-ph/9508006

[9] R. Iten, R. Colbeck, and M. Christandl, Quantum circuits for quantum channels,'' Physical Review A 95, 052316 (2016b).
https:/​/​doi.org/​10.1103/​PhysRevA.95.052316

[10] R. Iten, O. Reardon-Smith, L. Mondada, E. Redmond, R. Singh Kohli, and R. Colbeck, Introduction to UniversalQCompiler,'' e-print arXiv:1904.01072 (2019).
arXiv:1904.01072

[11] V. V. Shende, A. K. Prasad, I. L. Markov, and J. P. Hayes, Synthesis of reversible logic circuits,'' IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 22, 710–722 (2003).

[12] S. P. Jordan and P. Wocjan, Efficient quantum circuits for arbitrary sparse unitaries,'' Phys. Rev. A 80, 062301 (2009).
https:/​/​doi.org/​10.1103/​PhysRevA.80.062301

[13] V. Kliuchnikov, Synthesis of unitaries with Clifford+T circuits,'' e-print arXiv:1306.3200 (2013).
arXiv:1306.3200

[14] T. G. de Brugière, M. Baboulin, B. Valiron, and C. Allouche, Quantum circuits synthesis using Householder transformations,'' Computer Physics Communications 248, 107001 (2020).
https:/​/​doi.org/​10.1016/​j.cpc.2019.107001

[15] D. Maslov, Advantages of using relative-phase Toffoli gates with an application to multiple control Toffoli optimization,'' Phys. Rev. A 93, 022311 (2016).
https:/​/​doi.org/​10.1103/​PhysRevA.93.022311

[16] A. S. Householder, Unitary triangularization of a nonsymmetric matrix,'' J. ACM 5, 339–342 (1958).
https:/​/​doi.org/​10.1145/​320941.320947

[17] P. A. Ivanov, E. S. Kyoseva, and N. V. Vitanov, Engineering of arbitrary $\mathrm{U}(n)$ transformations by quantum Householder reflections,'' Phys. Rev. A 74, 022323 (2006).
https:/​/​doi.org/​10.1103/​PhysRevA.74.022323

[18] B. Torosov, E. Kyoseva, and N. Vitanov, Fault-tolerant composite Householder reflection,'' Journal of Physics B: Atomic 48, 135502 (2015).
https:/​/​doi.org/​10.1088/​0953-4075/​48/​13/​135502

[19] S. Fenner, Implementing the fanout gate by a Hamiltonian,'' e-print arXiv:quant-ph/​0309163 (2003).
arXiv:quant-ph/0309163

[20] P. Heggernes and P. Matstoms, Finding good column orderings for sparse QR factorization,'' in Second SIAM Conference on Sparse Matrices (1996).

[21] C. Gidney, Factoring with $n+2$ clean qubits and $n-1$ dirty qubits,'' e-print arXiv:1706.07884 (2017).
arXiv:1706.07884

### Cited by

[1] Davide Orsucci and Vedran Dunjko, "On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number", arXiv:2101.11868.

The above citations are from SAO/NASA ADS (last updated successfully 2021-04-23 10:42:26). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2021-04-23 10:42:24).