Optimal local unitary encoding circuits for the surface code

Oscar Higgott; Matthew Wilson; James Hefford; James Dborin; Farhan Hanif; Simon Burton; Dan E. Browne

doi:10.22331/q-2021-08-05-517

Optimal local unitary encoding circuits for the surface code

Oscar Higgott¹, Matthew Wilson^1,2, James Hefford^1,2, James Dborin^1,3, Farhan Hanif¹, Simon Burton¹, and Dan E. Browne¹

¹Department of Physics and Astronomy, University College London, Gower Street, London WC1E 6BT, United Kingdom
²Department of Computer Science, University of Oxford, Oxford OX1 3QD, United Kingdom
³London Centre for Nanotechnology, University College London, Gordon St., London WC1H 0AH, United Kingdom

Published:	2021-08-05, volume 5, page 517
Eprint:	arXiv:2002.00362v5
Doi:	https://doi.org/10.22331/q-2021-08-05-517
Citation:	Quantum 5, 517 (2021).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

The surface code is a leading candidate quantum error correcting code, owing to its high threshold, and compatibility with existing experimental architectures. Bravyi {et al.} [7] showed that encoding a state in the surface code using local unitary operations requires time at least linear in the lattice size $L$, however the most efficient known method for encoding an unknown state, introduced by Dennis {et al.} [18], has $O(L^2)$ time complexity. Here, we present an optimal local unitary encoding circuit for the planar surface code that uses exactly $2L$ time steps to encode an unknown state in a distance $L$ planar code. We further show how an $O(L)$ complexity local unitary encoder for the toric code can be found by enforcing locality in the $O(\log L)$-depth non-local renormalisation encoder. We relate these techniques by providing an $O(L)$ local unitary circuit to convert between a toric code and a planar code, and also provide optimal encoders for the rectangular, rotated and 3D surface codes. Furthermore, we show how our encoding circuit for the planar code can be used to prepare fermionic states in the compact mapping, a recently introduced fermion to qubit mapping that has a stabiliser structure similar to that of the surface code and is particularly efficient for simulating the Fermi-Hubbard model.

Featured image: A circuit for encoding a distance 6 surface code from a distance 4 surface code

Popular summary

Kitaev’s seminal toric code and surface code have become cornerstones of both quantum computing theory and theoretical condensed matter physics. However, the most efficient known methods for preparing an unknown state in these codes using local unitary operations are far from optimal: Bravyi et al. [PRL 97, 050401 (2006)] showed that any method must take time at least linear in the lattice size L, whereas the fastest known method by Dennis et al. [Journal of Mathematical Physics 43, 4452 (2002)] takes time quadratic in L.

In our work, we construct unitary encoding circuits for the toric and surface code that are asymptotically optimal, with a number of time steps scaling linearly in L.
Our circuits encode rotated, planar and rectangular surface codes, as well as the 3D surface code. We further show how our encoding circuits can be used to encode states in the compact mapping, a fermion-to-qubit mapping that is particularly efficient for simulating fermionic lattice models.

Since encoding circuits do not require stabiliser measurements, our methods do not require ancilla qubits, and can be implemented on devices that do not yet support mid-circuit measurements. Our work therefore reduces the resources required to experimentally demonstrate topological quantum order, and has applications in the simulation of fermionic systems.

► BibTeX data

@article{Higgott2021optimallocalunitary,
  doi = {10.22331/q-2021-08-05-517},
  url = {https://doi.org/10.22331/q-2021-08-05-517},
  title = {Optimal local unitary encoding circuits for the surface code},
  author = {Higgott, Oscar and Wilson, Matthew and Hefford, James and Dborin, James and Hanif, Farhan and Burton, Simon and Browne, Dan E.},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {517},
  month = aug,
  year = {2021}
}

► References

[1] Miguel Aguado and Guifré Vidal. Entanglement renormalization and topological order. Phys. Rev. Lett., 100: 070404, Feb 2008. 10.1103/PhysRevLett.100.070404. URL https://link.aps.org/doi/10.1103/PhysRevLett.100.070404.
https://doi.org/10.1103/PhysRevLett.100.070404

[2] Dorit Aharonov and Yonathan Touati. Quantum circuit depth lower bounds for homological codes. arXiv preprint arXiv:1810.03912, 2018.
arXiv:1810.03912

[3] J Pablo Bonilla Ataides, David K Tuckett, Stephen D Bartlett, Steven T Flammia, and Benjamin J Brown. The xzzx surface code. Nature communications, 12 (1): 1–12, 2021. 10.1038/s41467-021-22274-1.
https://doi.org/10.1038/s41467-021-22274-1

[4] Robert Beals, Stephen Brierley, Oliver Gray, Aram W Harrow, Samuel Kutin, Noah Linden, Dan Shepherd, and Mark Stather. Efficient distributed quantum computing. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 469 (2153): 20120686, 2013. 10.1098/rspa.2012.0686.
https://doi.org/10.1098/rspa.2012.0686

[5] H Bombin and Miguel A Martin-Delgado. Optimal resources for topological two-dimensional stabilizer codes: Comparative study. Physical Review A, 76 (1): 012305, 2007. 10.1103/PhysRevA.76.012305.
https://doi.org/10.1103/PhysRevA.76.012305

[6] Hector Bombin, Guillaume Duclos-Cianci, and David Poulin. Universal topological phase of two-dimensional stabilizer codes. New Journal of Physics, 14 (7): 073048, 2012. 10.1088/1367-2630/14/7/073048.
https://doi.org/10.1088/1367-2630/14/7/073048

[7] Sergey Bravyi, Matthew B Hastings, and Frank Verstraete. Lieb-robinson bounds and the generation of correlations and topological quantum order. Physical review letters, 97 (5): 050401, 2006. 10.1103/PhysRevLett.97.050401.
https://doi.org/10.1103/PhysRevLett.97.050401

[8] Sergey Bravyi, Guillaume Duclos-Cianci, David Poulin, and Martin Suchara. Subsystem surface codes with three-qubit check operators. arXiv preprint arXiv:1207.1443, 2012.
arXiv:1207.1443

[9] Sergey B. Bravyi and Alexei Yu. Kitaev. Fermionic quantum computation. Annals of Physics, 298 (1): 210–226, 2002. ISSN 0003-4916. https://doi.org/10.1006/aphy.2002.6254. URL https://www.sciencedirect.com/science/article/pii/S0003491602962548.
https://doi.org/10.1006/aphy.2002.6254
https://www.sciencedirect.com/science/article/pii/S0003491602962548

[10] Nikolas P Breuckmann and Barbara M Terhal. Constructions and noise threshold of hyperbolic surface codes. IEEE transactions on Information Theory, 62 (6): 3731–3744, 2016. 10.1109/TIT.2016.2555700.
https://doi.org/10.1109/TIT.2016.2555700

[11] Stephen Brierley. Efficient implementation of quantum circuits with limited qubit interactions. arXiv preprint arXiv:1507.04263, 2015.
arXiv:1507.04263

[12] Benjamin J Brown, Wonmin Son, Christina V Kraus, Rosario Fazio, and Vlatko Vedral. Generating topological order from a two-dimensional cluster state using a duality mapping. New Journal of Physics, 13 (6): 065010, 2011. 10.1088/1367-2630/13/6/065010.
https://doi.org/10.1088/1367-2630/13/6/065010

[13] Donny Cheung, Dmitri Maslov, and Simone Severini. Translation techniques between quantum circuit architectures. In Workshop on Quantum Information Processing, 2007.

[14] John Chiaverini, Dietrich Leibfried, Tobias Schaetz, Murray D Barrett, RB Blakestad, J Britton, Wayne M Itano, John D Jost, Emanuel Knill, Christopher Langer, et al. Realization of quantum error correction. Nature, 432 (7017): 602, 2004. 10.1038/nature03074.
https://doi.org/10.1038/nature03074

[15] Richard Cleve and Daniel Gottesman. Efficient computations of encodings for quantum error correction. Physical Review A, 56 (1): 76–82, Jul 1997. ISSN 1094-1622. 10.1103/physreva.56.76. URL http://dx.doi.org/10.1103/PhysRevA.56.76.
https://doi.org/10.1103/physreva.56.76

[16] Julia Cramer, Norbert Kalb, M Adriaan Rol, Bas Hensen, Machiel S Blok, Matthew Markham, Daniel J Twitchen, Ronald Hanson, and Tim H Taminiau. Repeated quantum error correction on a continuously encoded qubit by real-time feedback. Nature communications, 7: 11526, 2016. 10.1038/ncomms11526.
https://doi.org/10.1038/ncomms11526

[17] Nicolas Delfosse and Gilles Zémor. Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel. Physical Review Research, 2 (3): 033042, 2020. 10.1103/PhysRevResearch.2.033042.
https://doi.org/10.1103/PhysRevResearch.2.033042

[18] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. Topological quantum memory. Journal of Mathematical Physics, 43 (9): 4452–4505, 2002. 10.1063/1.1499754.
https://doi.org/10.1063/1.1499754

[19] Charles Derby, Joel Klassen, Johannes Bausch, and Toby Cubitt. Compact fermion to qubit mappings. Phys. Rev. B, 104: 035118, Jul 2021. 10.1103/PhysRevB.104.035118. URL https://link.aps.org/doi/10.1103/PhysRevB.104.035118.
https://doi.org/10.1103/PhysRevB.104.035118

[20] Austin G. Fowler, Ashley M. Stephens, and Peter Groszkowski. High-threshold universal quantum computation on the surface code. Phys. Rev. A, 80: 052312, Nov 2009. 10.1103/PhysRevA.80.052312. URL https://link.aps.org/doi/10.1103/PhysRevA.80.052312.
https://doi.org/10.1103/PhysRevA.80.052312

[21] Keisuke Fujii and Yuuki Tokunaga. Error and loss tolerances of surface codes with general lattice structures. Phys. Rev. A, 86: 020303, Aug 2012. 10.1103/PhysRevA.86.020303. URL https://link.aps.org/doi/10.1103/PhysRevA.86.020303.
https://doi.org/10.1103/PhysRevA.86.020303

[22] Ming Gong, Xiao Yuan, Shiyu Wang, Yulin Wu, Youwei Zhao, Chen Zha, Shaowei Li, Zhen Zhang, Qi Zhao, Yunchao Liu, Futian Liang, Jin Lin, Yu Xu, Hui Deng, Hao Rong, He Lu, Simon C Benjamin, Cheng-Zhi Peng, Xiongfeng Ma, Yu-Ao Chen, Xiaobo Zhu, and Jian-Wei Pan. Experimental exploration of five-qubit quantum error correcting code with superconducting qubits. National Science Review, 01 2021. ISSN 2095-5138. 10.1093/nsr/nwab011. URL https://doi.org/10.1093/nsr/nwab011. nwab011.
https://doi.org/10.1093/nsr/nwab011

[23] Daniel Gottesman. Stabilizer codes and quantum error correction. arXiv preprint quant-ph/9705052, 1997.
arXiv:quant-ph/9705052

[24] Alioscia Hamma and Daniel A Lidar. Adiabatic preparation of topological order. Physical review letters, 100 (3): 030502, 2008. 10.1103/PhysRevLett.100.030502.
https://doi.org/10.1103/PhysRevLett.100.030502

[25] Vojtěch Havlíček, Matthias Troyer, and James D. Whitfield. Operator locality in the quantum simulation of fermionic models. Phys. Rev. A, 95: 032332, Mar 2017. 10.1103/PhysRevA.95.032332. URL https://link.aps.org/doi/10.1103/PhysRevA.95.032332.
https://doi.org/10.1103/PhysRevA.95.032332

[26] Clare Horsman, Austin G Fowler, Simon Devitt, and Rodney Van Meter. Surface code quantum computing by lattice surgery. New Journal of Physics, 14 (12): 123011, dec 2012. 10.1088/1367-2630/14/12/123011. URL https://doi.org/10.1088/1367-2630/14/12/123011.
https://doi.org/10.1088/1367-2630/14/12/123011

[27] Zhang Jiang, Jarrod McClean, Ryan Babbush, and Hartmut Neven. Majorana loop stabilizer codes for error mitigation in fermionic quantum simulations. Phys. Rev. Applied, 12: 064041, Dec 2019. 10.1103/PhysRevApplied.12.064041. URL https://link.aps.org/doi/10.1103/PhysRevApplied.12.064041.
https://doi.org/10.1103/PhysRevApplied.12.064041

[28] Julian Kelly, Rami Barends, Austin G Fowler, Anthony Megrant, Evan Jeffrey, Theodore C White, Daniel Sank, Josh Y Mutus, Brooks Campbell, Yu Chen, et al. State preservation by repetitive error detection in a superconducting quantum circuit. Nature, 519 (7541): 66, 2015. 10.1038/nature14270.
https://doi.org/10.1038/nature14270

[29] A Yu Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303 (1): 2–30, 2003. 10.1016/S0003-4916(02)00018-0.
https://doi.org/10.1016/S0003-4916(02)00018-0

[30] Robert König and Fernando Pastawski. Generating topological order: No speedup by dissipation. Phys. Rev. B, 90: 045101, Jul 2014. 10.1103/PhysRevB.90.045101. URL https://link.aps.org/doi/10.1103/PhysRevB.90.045101.
https://doi.org/10.1103/PhysRevB.90.045101

[31] Robert König and Fernando Pastawski. Generating topological order: no speedup by dissipation. Physical Review B, 90 (4): 045101, 2014.

[32] Aleksander Kubica, Beni Yoshida, and Fernando Pastawski. Unfolding the color code. New Journal of Physics, 17 (8): 083026, 2015. 10.1088/1367-2630/17/8/083026.
https://doi.org/10.1088/1367-2630/17/8/083026

[33] Ying Li. A magic state’s fidelity can be superior to the operations that created it. New Journal of Physics, 17 (2): 023037, 2015. 10.1088/1367-2630/17/2/023037.
https://doi.org/10.1088/1367-2630/17/2/023037

[34] Pengcheng Liao and David L Feder. Quantum circuit for toric code state preparation via graph states. arXiv preprint arXiv:2103.12268, 2021.
arXiv:2103.12268

[35] Norbert M Linke, Mauricio Gutierrez, Kevin A Landsman, Caroline Figgatt, Shantanu Debnath, Kenneth R Brown, and Christopher Monroe. Fault-tolerant quantum error detection. Science advances, 3 (10): e1701074, 2017. 10.1126/sciadv.1701074.
https://doi.org/10.1126/sciadv.1701074

[36] Justyna Łodyga, Paweł Mazurek, Andrzej Grudka, and Michał Horodecki. Simple scheme for encoding and decoding a qubit in unknown state for various topological codes. Scientific reports, 5: 8975, 2015. 10.1038/srep08975.
https://doi.org/10.1038/srep08975

[37] Chao-Yang Lu, Wei-Bo Gao, Jin Zhang, Xiao-Qi Zhou, Tao Yang, and Jian-Wei Pan. Experimental quantum coding against qubit loss error. Proceedings of the National Academy of Sciences, 105 (32): 11050–11054, 2008. 10.1073/pnas.0800740105.
https://doi.org/10.1073/pnas.0800740105

[38] Dmitri Maslov. Linear depth stabilizer and quantum fourier transformation circuits with no auxiliary qubits in finite-neighbor quantum architectures. Physical Review A, 76 (5), Nov 2007. ISSN 1094-1622. 10.1103/physreva.76.052310. URL http://dx.doi.org/10.1103/PhysRevA.76.052310.
https://doi.org/10.1103/physreva.76.052310

[39] D. Nigg, M. Müller, E. A. Martinez, P. Schindler, M. Hennrich, T. Monz, M. A. Martin-Delgado, and R. Blatt. Quantum computations on a topologically encoded qubit. Science, 345 (6194): 302–305, 2014. ISSN 0036-8075. 10.1126/science.1253742. URL https://science.sciencemag.org/content/345/6194/302.
https://doi.org/10.1126/science.1253742
https://science.sciencemag.org/content/345/6194/302

[40] Nissim Ofek, Andrei Petrenko, Reinier Heeres, Philip Reinhold, Zaki Leghtas, Brian Vlastakis, Yehan Liu, Luigi Frunzio, SM Girvin, Liang Jiang, et al. Extending the lifetime of a quantum bit with error correction in superconducting circuits. Nature, 536 (7617): 441–445, 2016. 10.1038/nature18949.
https://doi.org/10.1038/nature18949

[41] John Preskill. Quantum Computing in the NISQ era and beyond. Quantum, 2: 79, August 2018. ISSN 2521-327X. 10.22331/q-2018-08-06-79. URL https://doi.org/10.22331/q-2018-08-06-79.
https://doi.org/10.22331/q-2018-08-06-79

[42] Robert Raussendorf and Jim Harrington. Fault-tolerant quantum computation with high threshold in two dimensions. Phys. Rev. Lett., 98: 190504, May 2007. 10.1103/PhysRevLett.98.190504. URL https://link.aps.org/doi/10.1103/PhysRevLett.98.190504.
https://doi.org/10.1103/PhysRevLett.98.190504

[43] Joschka Roffe, David Headley, Nicholas Chancellor, Dominic Horsman, and Viv Kendon. Protecting quantum memories using coherent parity check codes. Quantum Science and Technology, 3 (3): 035010, jun 2018. 10.1088/2058-9565/aac64e. URL https://doi.org/10.1088/2058-9565/aac64e.
https://doi.org/10.1088/2058-9565/aac64e

[44] KJ Satzinger, Y Liu, A Smith, C Knapp, M Newman, C Jones, Z Chen, C Quintana, X Mi, A Dunsworth, et al. Realizing topologically ordered states on a quantum processor. arXiv preprint arXiv:2104.01180, 2021.
arXiv:2104.01180

[45] Philipp Schindler, Julio T. Barreiro, Thomas Monz, Volckmar Nebendahl, Daniel Nigg, Michael Chwalla, Markus Hennrich, and Rainer Blatt. Experimental repetitive quantum error correction. Science, 332 (6033): 1059–1061, 2011. ISSN 0036-8075. 10.1126/science.1203329. URL https://science.sciencemag.org/content/332/6033/1059.
https://doi.org/10.1126/science.1203329
https://science.sciencemag.org/content/332/6033/1059

[46] Jacob T. Seeley, Martin J. Richard, and Peter J. Love. The bravyi-kitaev transformation for quantum computation of electronic structure. The Journal of Chemical Physics, 137 (22): 224109, 2012. 10.1063/1.4768229.
https://doi.org/10.1063/1.4768229

[47] Kanav Setia, Sergey Bravyi, Antonio Mezzacapo, and James D. Whitfield. Superfast encodings for fermionic quantum simulation. Phys. Rev. Research, 1: 033033, Oct 2019. 10.1103/PhysRevResearch.1.033033. URL https://link.aps.org/doi/10.1103/PhysRevResearch.1.033033.
https://doi.org/10.1103/PhysRevResearch.1.033033

[48] Mark Steudtner and Stephanie Wehner. Quantum codes for quantum simulation of fermions on a square lattice of qubits. Phys. Rev. A, 99: 022308, Feb 2019. 10.1103/PhysRevA.99.022308. URL https://link.aps.org/doi/10.1103/PhysRevA.99.022308.
https://doi.org/10.1103/PhysRevA.99.022308

[49] Tim Hugo Taminiau, Julia Cramer, Toeno van der Sar, Viatcheslav V Dobrovitski, and Ronald Hanson. Universal control and error correction in multi-qubit spin registers in diamond. Nature nanotechnology, 9 (3): 171, 2014. 10.1038/nnano.2014.2.
https://doi.org/10.1038/nnano.2014.2

[50] Frank Verstraete and J Ignacio Cirac. Mapping local hamiltonians of fermions to local hamiltonians of spins. Journal of Statistical Mechanics: Theory and Experiment, 2005 (09): P09012, 2005. 10.1088/1742-5468/2005/09/P09012.
https://doi.org/10.1088/1742-5468/2005/09/P09012

[51] Christophe Vuillot. Is error detection helpful on ibm 5q chips? arXiv preprint arXiv:1705.08957, 2017.
arXiv:1705.08957

[52] Gerald Waldherr, Y Wang, S Zaiser, M Jamali, T Schulte-Herbrüggen, H Abe, T Ohshima, J Isoya, JF Du, P Neumann, et al. Quantum error correction in a solid-state hybrid spin register. Nature, 506 (7487): 204, 2014. 10.1038/nature12919.
https://doi.org/10.1038/nature12919

[53] Xiao-Gang Wen. Quantum orders in an exact soluble model. Phys. Rev. Lett., 90: 016803, Jan 2003. 10.1103/PhysRevLett.90.016803. URL https://link.aps.org/doi/10.1103/PhysRevLett.90.016803.
https://doi.org/10.1103/PhysRevLett.90.016803

[54] James D. Whitfield, Vojtěch Havlíček, and Matthias Troyer. Local spin operators for fermion simulations. Phys. Rev. A, 94: 030301, Sep 2016. 10.1103/PhysRevA.94.030301. URL https://link.aps.org/doi/10.1103/PhysRevA.94.030301.
https://doi.org/10.1103/PhysRevA.94.030301

[55] Bujiao Wu, Xiaoyu He, Shuai Yang, Lifu Shou, Guojing Tian, Jialin Zhang, and Xiaoming Sun. Optimization of cnot circuits on topological superconducting processors. arXiv preprint arXiv:1910.14478, 2019.
arXiv:1910.14478

[56] Xiaosi Xu, Simon C. Benjamin, and Xiao Yuan. Variational circuit compiler for quantum error correction. Phys. Rev. Applied, 15: 034068, Mar 2021. 10.1103/PhysRevApplied.15.034068. URL https://link.aps.org/doi/10.1103/PhysRevApplied.15.034068.
https://doi.org/10.1103/PhysRevApplied.15.034068

[57] Beni Yoshida. Classification of quantum phases and topology of logical operators in an exactly solved model of quantum codes. Annals of Physics, 326 (1): 15–95, 2011. ISSN 0003-4916. https://doi.org/10.1016/j.aop.2010.10.009. URL https://www.sciencedirect.com/science/article/pii/S0003491610001867. January 2011 Special Issue.
https://doi.org/10.1016/j.aop.2010.10.009
https://www.sciencedirect.com/science/article/pii/S0003491610001867

Cited by

[1] Dongxiao Quan, Chensong Liu, Xiaojie Lv, and Changxing Pei, "Implementation of Fault-Tolerant Encoding Circuit Based on Stabilizer Implementation and “Flag” Bits in Steane Code", Entropy 24 8, 1107 (2022).

[2] Paul Webster, Michael Vasmer, Thomas R. Scruby, and Stephen D. Bartlett, "Universal fault-tolerant quantum computing with stabilizer codes", Physical Review Research 4 1, 013092 (2022).

[3] Ryan Levy, Zoe Gonzalez Izquierdo, Zhihui Wang, Jeffrey Marshall, Joseph Barreto, Louis Fry-Bouriaux, Daniel T. O'Connor, Paul A. Warburton, Nathan Wiebe, Eleanor Rieffel, and Filip A. Wudarski, "Towards solving the Fermi-Hubbard model via tailored quantum annealers", arXiv:2207.14374, (2022).

[4] Paul Webster, Michael Vasmer, Thomas R. Scruby, and Stephen D. Bartlett, "Universal Fault-Tolerant Quantum Computing with Stabiliser Codes", arXiv:2012.05260, (2020).

[5] Jihao Fan, Jun Li, Ya Wang, Yonghui Li, Min-Hsiu Hsieh, and Jiangfeng Du, "Partially Concatenated Calderbank-Shor-Steane Codes Achieving the Quantum Gilbert-Varshamov Bound Asymptotically", arXiv:2107.05174, (2021).

The above citations are from Crossref's cited-by service (last updated successfully 2023-09-21 14:31:34) and SAO/NASA ADS (last updated successfully 2023-09-21 14:31:35). The list may be incomplete as not all publishers provide suitable and complete citation data.

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.