1Department of Computer Science, University of Oxford, UK
2Riverlane, 1st Floor St Andrews House, 59 St Andrews Street, Cambridge, UK
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
In this paper we propose a technique for distributing entanglement in architectures in which interactions between pairs of qubits are constrained to a fixed network $G$. This allows for two-qubit operations to be performed between qubits which are remote from each other in $G$, through gate teleportation. We demonstrate how adapting $textit{quantum linear network coding}$ to this problem of entanglement distribution in a network of qubits can be used to solve the problem of distributing Bell states and GHZ states in parallel, when bottlenecks in $G$ would otherwise force such entangled states to be distributed sequentially. In particular, we show that by reduction to classical network coding protocols for the $k$-pairs problem or multiple multicast problem in a fixed network $G$, one can distribute entanglement between the transmitters and receivers with a Clifford circuit whose quantum depth is some (typically small and easily computed) constant, which does not depend on the size of $G$, however remote the transmitters and receivers are, or the number of transmitters and receivers. These results also generalise straightforwardly to qudits of any prime dimension. We demonstrate our results using a specialised formalism, distinct from and more efficient than the stabiliser formalism, which is likely to be helpful to reason about and prototype such quantum linear network coding circuits.
► BibTeX data
► References
[1] Scott Aaronson and Daniel Gottesman. Improved simulation of stabilizer circuits. Phys, Rev. A, 70 (5): 052328, Nov 2004. 10.1103/PhysRevA.70.052328.
https://doi.org/10.1103/PhysRevA.70.052328
[2] R. Ahlswede, , S. . R. Li, and R. W. Yeung. Network information flow. IEEE Transactions on Information Theory, 46 (4): 1204–1216, July 2000. ISSN 0018-9448. 10.1109/18.850663.
https://doi.org/10.1109/18.850663
[3] K. Appel and W. Haken. Every planar map is four colorable. part i: Discharging. Illinois J. Math., 21 (3): 429–490, 09 1977. 10.1215/ijm/1256049011. URL https://doi.org/10.1215/ijm/1256049011.
https://doi.org/10.1215/ijm/1256049011
[4] D. M. Appleby. SIC-POVMs and the extended clifford group. J. Math. Phys, 46 (3): 052107, 2005. 10.1063/1.1896384.
https://doi.org/10.1063/1.1896384
[5] Daniel Brélaz. New methods to color the vertices of a graph. Commun. ACM, 22 (4): 251–256, April 1979. ISSN 0001-0782. 10.1145/359094.359101. URL http://doi.acm.org/10.1145/359094.359101.
https://doi.org/10.1145/359094.359101
[6] K. Cai and G. Han. On network coding advantage for multiple unicast networks. In 2015 IEEE International Symposium on Information Theory (ISIT), pages 366–370, June 2015. 10.1109/ISIT.2015.7282478.
https://doi.org/10.1109/ISIT.2015.7282478
[7] Alexander Cowtan, Silas Dilkes, Ross Duncan, Alexandre Krajenbrink, Will Simmons, and Seyon Sivarajah. On the Qubit Routing Problem. In Wim van Dam and Laura Mancinska, editors, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019), volume 135 of Leibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:32, Dagstuhl, Germany, 2019. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-112-2. 10.4230/LIPIcs.TQC.2019.5. URL http://drops.dagstuhl.de/opus/volltexte/2019/10397.
https://doi.org/10.4230/LIPIcs.TQC.2019.5
http://drops.dagstuhl.de/opus/volltexte/2019/10397
[8] N. Das and B. K. Rai. On the message dimensions of vector linearly solvable networks. IEEE Communications Letters, 20 (9): 1701–1704, Sep. 2016. 10.1109/LCOMM.2016.2583418.
https://doi.org/10.1109/LCOMM.2016.2583418
[9] N. de Beaudrap and S. Herbert. Code for exhaustive search of local complementation of a graph state, 2020. URL https://arxiv.org/src/1910.03315v2/anc.
https://arxiv.org/src/1910.03315v2/anc
[10] Niel de Beaudrap. A linearized stabilizer formalism for systems of finite dimension. Quantum Information & Computation, 13: 73–115, 2013. URL http://stacks.iop.org/1367-2630/18/i=10/a=103028.
http://stacks.iop.org/1367-2630/18/i=10/a=103028
[11] Niel de Beaudrap and Martin Roetteler. Quantum linear network coding as one-way quantum computation. arXiv e-prints, 27, 03 2014. 10.4230/LIPIcs.TQC.2014.217.
https://doi.org/10.4230/LIPIcs.TQC.2014.217
[12] Jeroen Dehaene and Bart de Moor. Clifford group, stabilizer states, and linear and quadratic operations over GF(2). Physical Review A, 68 (4): 042318, Oct 2003. 10.1103/PhysRevA.68.042318.
https://doi.org/10.1103/PhysRevA.68.042318
[13] R. Dougherty and K. Zeger. Nonreversibility and equivalent constructions of multiple-unicast networks. IEEE Transactions on Information Theory, 52 (11): 5067–5077, Nov 2006. ISSN 0018-9448. 10.1109/TIT.2006.883634.
https://doi.org/10.1109/TIT.2006.883634
[14] T. Etzion and A. Wachter-Zeh. Vector network coding based on subspace codes outperforms scalar linear network coding. In 2016 IEEE International Symposium on Information Theory (ISIT), pages 1949–1953, July 2016. 10.1109/ISIT.2016.7541639.
https://doi.org/10.1109/ISIT.2016.7541639
[15] Google. A preview of Bristlecone, Google’s new quantum processor. URL https://research.googleblog.com/2018/03/a-preview-of-bristlecone-googles-new.html.
https://research.googleblog.com/2018/03/a-preview-of-bristlecone-googles-new.html
[16] Daniel Gottesman. The Heisenberg Representation of Quantum Computers. Chaos Solitons Fractals, 10: 1749–1758, 1999.
[17] Daniel Gottesman and Isaac L. Chuang. Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations. Nature, 402 (6760): 390–393, 1999. ISSN 1476-4687. 10.1038/46503. URL https://doi.org/10.1038/46503.
https://doi.org/10.1038/46503
[18] F. Hahn, A. Pappa, and J. Eisert. Quantum network routing and local complementation. npj Quantum Information, 5 (1): 76, 2019. 10.1038/s41534-019-0191-6. URL https://doi.org/10.1038/s41534-019-0191-6.
https://doi.org/10.1038/s41534-019-0191-6
[19] M. Hein, J. Eisert, and H. J. Briegel. Multiparty entanglement in graph states. Physical Review A, 69 (6): 062311, Jun 2004. 10.1103/PhysRevA.69.062311.
https://doi.org/10.1103/PhysRevA.69.062311
[20] Steven Herbert. On the depth overhead incurred when running quantum algorithms on near-term quantum computers with limited qubit connectivity. Quantum Information & Communication, 20 (9-10): 787–806, Aug 2020.
[21] Steven Herbert and Akash Sengupta. Using Reinforcement Learning to find Efficient Qubit Routing Policies for Deployment in Near-term Quantum Computers. arXiv e-prints, art. arXiv:1812.11619, Dec 2018.
arXiv:1812.11619
[22] IBM. IBM quantum computing. URL https://www.ibm.com/quantum-computing/.
https://www.ibm.com/quantum-computing/
[23] Intel. Intel quantum computing. URL https://www.intel.com/content/www/us/en/research/quantum-computing.html.
https://www.intel.com/content/www/us/en/research/quantum-computing.html
[24] Aleks Kissinger and Arianne Meijer-van de Griend. CNOT circuit extraction for topologically-constrained quantum memories. arXiv:1904.00633, 2019.
arXiv:1904.00633
[25] H. Kobayashi, F. Le Gall, H. Nishimura, and M. Rötteler. Constructing quantum network coding schemes from classical nonlinear protocols. In 2011 IEEE International Symposium on Information Theory Proceedings, pages 109–113, July 2011. 10.1109/ISIT.2011.6033701.
https://doi.org/10.1109/ISIT.2011.6033701
[26] Hirotada Kobayashi, François Le Gall, Harumichi Nishimura, and Martin Rötteler. General scheme for perfect quantum network coding with free classical communication. In Automata, Languages and Programming, pages 622–633, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. ISBN 978-3-642-02927-1. 10.1007/978-3-642-02927-1_52.
https://doi.org/10.1007/978-3-642-02927-1_52
[27] R. Koetter and M. Medard. An algebraic approach to network coding. IEEE/ACM Transactions on Networking, 11 (5): 782–795, Oct 2003. 10.1109/TNET.2003.818197.
https://doi.org/10.1109/TNET.2003.818197
[28] April Rasala Lehman and Eric Lehman. Complexity classification of network information flow problems. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’04, pages 142–150, Philadelphia, PA, USA, 2004. Society for Industrial and Applied Mathematics. ISBN 0-89871-558-X. URL http://dl.acm.org/citation.cfm?id=982792.982814.
http://dl.acm.org/citation.cfm?id=982792.982814
[29] D. Leung, J. Oppenheim, and A. Winter. Quantum network communication—the butterfly and beyond. IEEE Transactions on Information Theory, 56 (7): 3478–3490, July 2010. 10.1109/TIT.2010.2048442.
https://doi.org/10.1109/TIT.2010.2048442
[30] S. . R. Li, R. W. Yeung, and Ning Cai. Linear network coding. IEEE Transactions on Information Theory, 49 (2): 371–381, Feb 2003. ISSN 1557-9654. 10.1109/TIT.2002.807285.
https://doi.org/10.1109/TIT.2002.807285
[31] S. . R. Li, Ning Cai, and R. W. Yeung. On theory of linear network coding. In Proceedings. International Symposium on Information Theory, 2005. ISIT 2005., pages 273–277, Sep. 2005. 10.1109/ISIT.2005.1523337.
https://doi.org/10.1109/ISIT.2005.1523337
[32] S. R. Li, Q. T. Sun, and Z. Shao. Linear network coding: Theory and algorithms. Proceedings of the IEEE, 99 (3): 372–387, March 2011. ISSN 1558-2256. 10.1109/JPROC.2010.2093851.
https://doi.org/10.1109/JPROC.2010.2093851
[33] Z. Li, B. Li, and L. C. Lau. A constant bound on throughput improvement of multicast network coding in undirected networks. IEEE Transactions on Information Theory, 55 (3): 1016–1026, March 2009. ISSN 0018-9448. 10.1109/TIT.2008.2011516.
https://doi.org/10.1109/TIT.2008.2011516
[34] Zongpeng Li and Baochun Li. Network coding in undirected networks, 2004a.
[35] Zongpeng Li and Baochun Li. Network coding: The case of multiple unicast sessions. Proceedings of the 42nd Allerton Annual Conference on Communication, Control, and Computing, 10 2004b.
[36] Rigetti. The quantum processing unit (Rigetti). URL https://www.rigetti.com/qpu.
https://www.rigetti.com/qpu
[37] Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas. Efficiently four-coloring planar graphs. In Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, STOC ’96, pages 571–575, New York, NY, USA, 1996. ACM. ISBN 0-89791-785-5. 10.1145/237814.238005. URL http://doi.acm.org/10.1145/237814.238005.
https://doi.org/10.1145/237814.238005
[38] Takahiko Satoh, Francois Le Gall, and Hiroshi Imai. Quantum network coding for quantum repeaters. Phys. Rev. A, 86: 032331, Sep 2012. 10.1103/PhysRevA.86.032331. URL https://link.aps.org/doi/10.1103/PhysRevA.86.032331.
https://doi.org/10.1103/PhysRevA.86.032331
[39] M. Steffen, D. P. DiVincenzo, J. M. Chow, T. N. Theis, and M. B. Ketchen. Quantum computing: An IBM perspective. IBM Journal of Research and Development, 55 (5): 13:1–13:11, Sept 2011. ISSN 0018-8646. 10.1147/JRD.2011.2165678.
https://doi.org/10.1147/JRD.2011.2165678
[40] V. G. Vizing. On an estimate of the chromatic class of a p-graph, 1964.
[41] Alwin Zulehner, Alexandru Paler, and Robert Wille. An efficient methodology for mapping quantum circuits to the ibm qx architectures. In IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. IEEE, 2018. 10.1109/TCAD.2018.2846658.
https://doi.org/10.1109/TCAD.2018.2846658
Cited by
[1] Steven Herbert, “Increasing the classical data throughput in quantum networks by combining quantum linear network coding with superdense coding”, Physical Review A 101 6, 062332 (2020).
The above citations are from SAO/NASA ADS (last updated successfully 2020-11-03 11:36:40). 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 2020-11-03 11:36:39).
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.
Source: https://quantum-journal.org/papers/q-2020-11-01-356/
