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
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
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.
Featured image: CNOT count for sparse state preparation decompositions of $n$ qubit states with $2^s$ non-zero entries.
Popular summary
► BibTeX data
► 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).
https://doi.org/10.1109/TCAD.2005.855930
[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).
https://doi.org/10.1109/TCAD.2003.811448
[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-03-19 06:10:19). 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-03-19 06:10:17).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
Checkout PrimeXBT
Trade with the Official CFD Partners of AC Milan
Source: https://quantum-journal.org/papers/q-2021-03-15-412/
