Quantum circuit compilation and hybrid computation using Pauli-based computation

Filipa C. R. Peres1,2 and Ernesto F. Galvão1,3

1International Iberian Nanotechnology Laboratory (INL), Av. Mestre José Veiga, 4715-330 Braga, Portugal
2Departamento de Física e Astronomia, Faculdade de Ciências, Universidade do Porto, rua do Campo Alegre s/n, 4169–007 Porto, Portugal
3Instituto de Física, Universidade Federal Fluminense, Avenida General Milton Tavares de Souza s/n, Niterói, Rio de Janeiro 24210-340, Brazil

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


Pauli-based computation (PBC) is driven by a sequence of adaptively chosen, non-destructive measurements of Pauli observables. Any quantum circuit written in terms of the Clifford+$T$ gate set and having $t$ $T$ gates can be compiled into a PBC on $t$ qubits. Here we propose practical ways of implementing PBC as adaptive quantum circuits and provide code to do the required classical side-processing. Our schemes reduce the number of quantum gates to $O(t^2)$ (from a previous $O(t^3 / \log t)$ scaling) and space/time trade-offs are discussed which lead to a reduction of the depth from $O(t \log t)$ to $O(t)$ within our schemes, at the cost of $t$ additional auxiliary qubits. We compile examples of random and hidden-shift quantum circuits into adaptive PBC circuits. We also simulate hybrid quantum computation, where a classical computer effectively extends the working memory of a small quantum computer by $k$ virtual qubits, at a cost exponential in $k$. Our results demonstrate the practical advantage of PBC techniques for circuit compilation and hybrid computation.

Large-scale, fault-tolerant quantum computers are expected to solve tasks that are out of reach for their classical counterparts. This enticing prospect has propelled a lot of recent research in the fields of quantum information and quantum computation.
Unfortunately, current devices are still somewhat limited in their capabilities. Thus, smart schemes are needed that allow us to trade classical for quantum resources. In our work, we explore a universal model of quantum computation known as Pauli-based computation. We show that this model can be used to compile quantum circuits dominated by Clifford gates, demonstrating helpful quantum resource savings in many cases. We also describe gains in efficiency in hybrid quantum-classical computation, where the two types of computers work together to simulate a larger quantum device. Our paper is accompanied by open-access Python code that allows users to perform both compilation and hybrid computation on arbitrary user-specified circuits described using the common Clifford+$T$ gate set.
We expect our work to be relevant for near- and intermediate-term applications, but also in the long term, as the optimization of quantum resources should be of interest even after fault-tolerant quantum computing is achieved.

► BibTeX data

► References

[1] Peter W. Shor. ``Algorithms for quantum computation: discrete logarithms and factoring''. In Proceedings 35th Annual Symposium on Foundations of Computer Science. Pages 124–134. IEEE Press, Los Alamitos, CA (1994).

[2] Seth Lloyd. ``Universal Quantum Simulators''. Science 273, 1073–1078 (1996).

[3] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum Algorithm for Linear Systems of Equations''. Phys. Rev. Lett. 103, 150502 (2009).

[4] Ashley Montanaro. ``Quantum algorithms: an overview''. npj Quantum Information 2, 15023 (2016).

[5] John Preskill. ``Quantum Computing in the NISQ era and beyond''. Quantum 2, 79 (2018).

[6] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M. Martinis. ``Quantum supremacy using a programmable superconducting processor''. Nature 574, 505–510 (2019).

[7] Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, Peng Hu, Xiao-Yan Yang, Wei-Jun Zhang, Hao Li, Yuxuan Li, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-Wei Pan. ``Quantum computational advantage using photons''. Science 370, 1460–1463 (2020).

[8] Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He-Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang, Dachao Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao, Youwei Zhao, Liang Zhou, Qingling Zhu, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu, and Jian-Wei Pan. ``Strong Quantum Computational Advantage Using a Superconducting Quantum Processor''. Phys. Rev. Lett. 127, 180501 (2021).

[9] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’Brien. ``A variational eigenvalue solver on a photonic quantum processor''. Nature Communications 5, 4213 (2014).

[10] Vedran Dunjko, Yimin Ge, and J. Ignacio Cirac. ``Computational Speedups Using Small Quantum Devices''. Phys. Rev. Lett. 121, 250501 (2018).

[11] Aram W. Harrow. ``Small quantum computers and large classical data sets'' (2020). arXiv:2004.00026.

[12] Sergey Bravyi, Graeme Smith, and John A. Smolin. ``Trading Classical and Quantum Computational Resources''. Phys. Rev. X 6, 021043 (2016).

[13] Mithuna Yoganathan, Richard Jozsa, and Sergii Strelchuk. ``Quantum advantage of unitary Clifford circuits with magic state inputs''. Proc. R. Soc. A 475, 20180427 (2019).

[14] Padraic Calpin. ``Exploring Quantum Computation Through the Lens of Classical Simulation''. PhD thesis. UCL (University College London). (2020). url: https:/​/​discovery.ucl.ac.uk/​id/​eprint/​10091573.

[15] Daniel Gottesman. ``Stabilizer Codes and Quantum Error Correction''. PhD thesis. Caltech. (1997). arXiv:quant-ph/​9705052.

[16] Daniel Gottesman. ``The Heisenberg Representation of Quantum Computers''. In Group22: Proceedings of the XXII International Colloquium on Group Theoretical Methods in Physics. Pages 32–43. (1998). arXiv:quant-ph/​9807006.

[17] Igor L. Markov and Yaoyun Shi. ``Simulating Quantum Computation by Contracting Tensor Networks''. SIAM Journal on Computing 38, 963–981 (2008).

[18] Cupjin Huang, Michael Newman, and Mario Szegedy. ``Explicit lower bounds on strong quantum simulation'' (2018). arXiv:1804.10368.

[19] Hakop Pashayan, Joel J. Wallman, and Stephen D. Bartlett. ``Estimating Outcome Probabilities of Quantum Circuits Using Quasiprobabilities''. Phys. Rev. Lett. 115, 070501 (2015).

[20] Robert Raussendorf, Juani Bermejo-Vega, Emily Tyhurst, Cihan Okay, and Michael Zurel. ``Phase-space-simulation method for quantum computation with magic states on qubits''. Phys. Rev. A 101, 012350 (2020).

[21] Scott Aaronson and Daniel Gottesman. ``Improved simulation of stabilizer circuits''. Phys. Rev. A 70, 052328 (2004).

[22] Sergey Bravyi and David Gosset. ``Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates''. Phys. Rev. Lett. 116, 250501 (2016).

[23] Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, and Mark Howard. ``Simulation of quantum circuits by low-rank stabilizer decompositions''. Quantum 3, 181 (2019).

[24] Hammam Qassim, Joel J. Wallman, and Joseph Emerson. ``Clifford recompilation for faster classical simulation of quantum circuits''. Quantum 3, 170 (2019).

[25] Hammam Qassim, Hakop Pashayan, and David Gosset. ``Improved upper bounds on the stabilizer rank of magic states''. Quantum 5, 606 (2021).

[26] Aleks Kissinger and John van de Wetering. ``Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions''. Quantum Science and Technology 7, 044001 (2022).

[27] Xinlan Zhou, Debbie W. Leung, and Isaac L. Chuang. ``Methodology for quantum logic gate construction''. Phys. Rev. A 62, 052316 (2000).

[28] Sergey Bravyi and Alexei Kitaev. ``Universal quantum computation with ideal Clifford gates and noisy ancillas''. Phys. Rev. A 71, 022316 (2005).

[29] Earl T. Campbell, Barbara M. Terhal, and Christophe Vuillot. ``Roads towards fault-tolerant universal quantum computation''. Nature 549, 172–179 (2017).

[30] Daniel Litinski. ``Magic State Distillation: Not as Costly as You Think''. Quantum 3, 205 (2019).

[31] Ketan N. Patel, Igor L. Markov, and John P. Hayes. ``Optimal synthesis of linear reversible circuits''. Quantum Info. Comput. 8, 282–294 (2008).

[32] Robert Raussendorf and Hans J. Briegel. ``A One-Way Quantum Computer''. Phys. Rev. Lett. 86, 5188–5191 (2001).

[33] Michael A. Nielsen. ``Optical Quantum Computation Using Cluster States''. Phys. Rev. Lett. 93, 040503 (2004).

[34] Daniel E. Browne and Terry Rudolph. ``Resource-Efficient Linear Optical Quantum Computation''. Phys. Rev. Lett. 95, 010501 (2005).

[35] P. Walther, K. J. Resch, T. Rudolph, E. Schenck, H. Weinfurter, V. Vedral, M. Aspelmeyer, and A. Zeilinger. ``Experimental one-way quantum computing''. Nature 434, 169–176 (2005).

[36] Robert Prevedel, Philip Walther, Felix Tiefenbacher, Pascal Böhi, Rainer Kaltenbaek, Thomas Jennewein, and Anton Zeilinger. ``High-speed linear optics quantum computing using active feed-forward''. Nature 445, 65–69 (2007).

[37] Anne Broadbent, Joseph Fitzsimons, and Elham Kashefi. ``Universal Blind Quantum Computation''. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science. Pages 517–526. (2009).

[38] Matthew Amy, Dmitri Maslov, and Michele Mosca. ``Polynomial-Time T-Depth Optimization of Clifford+T Circuits Via Matroid Partitioning''. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 33, 1476–1489 (2014).

[39] Yunseong Nam, Neil J. Ross, Yuan Su, Andrew M. Childs, and Dmitri Maslov. ``Automated optimization of large quantum circuits with continuous parameters''. npj Quantum Information 4, 1 (2018).

[40] Alexander Cowtan, Silas Dilkes, Ross Duncan, Will Simmons, and Seyon Sivarajah. ``Phase Gadget Synthesis for Shallow Circuits''. Electronic Proceedings in Theoretical Computer Science 318, 213–228 (2020).

[41] Aleks Kissinger and John van de Wetering. ``Reducing the number of non-Clifford gates in quantum circuits''. Phys. Rev. A 102, 022406 (2020).

[42] Fang Zhang and Jianxin Chen. ``Optimizing T gates in Clifford+T circuit as $\pi/​4$ rotations around Paulis'' (2019). arXiv:1903.12456.

[43] Tianyi Peng, Aram W. Harrow, Maris Ozols, and Xiaodi Wu. ``Simulating Large Quantum Circuits on a Small Quantum Computer''. Phys. Rev. Lett. 125, 150504 (2020).

[44] Wei Tang, Teague Tomesh, Martin Suchara, Jeffrey Larson, and Margaret Martonosi. ``CutQC: Using Small Quantum Computers for Large Quantum Circuit Evaluations''. In Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems. Page 473–486. ASPLOS '21New York, NY, USA (2021). Association for Computing Machinery.

[45] Christophe Piveteau and David Sutter. ``Circuit knitting with classical communication'' (2023). arXiv:2205.00016.

[46] Angus Lowe, Matija Medvidović, Anthony Hayes, Lee J. O'Riordan, Thomas R. Bromley, Juan Miguel Arrazola, and Nathan Killoran. ``Fast quantum circuit cutting with randomized measurements''. Quantum 7, 934 (2023).

[47] Daniel Gottesman. ``An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation'' (2009). arXiv:0904.2557.

[48] Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland. ``Surface codes: Towards practical large-scale quantum computation''. Phys. Rev. A 86, 032324 (2012).

[49] Daniel Litinski. ``A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery''. Quantum 3, 128 (2019).

[50] Byung-Soo Choi and Rodney Van Meter. ``On the Effect of Quantum Interaction Distance on Quantum Addition Circuits''. J. Emerg. Technol. Comput. Syst. 7 (2011).

[51] Filipa C. R. Peres. ``Pauli-based model of quantum computation with higher-dimensional systems''. Phys. Rev. A 108, 032606 (2023).

[52] Yihui Quek, Mark M. Wilde, and Eneet Kaur. ``Multivariate trace estimation in constant quantum depth'' (2022). arXiv:2206.15405.

[53] Markus Heinrich and David Gross. ``Robustness of Magic and Symmetries of the Stabiliser Polytope''. Quantum 3, 132 (2019).

[54] Mark Howard and Earl Campbell. ``Application of a Resource Theory for Magic States to Fault-Tolerant Quantum Computing''. Phys. Rev. Lett. 118 (2017).

[55] Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma. ``Stabilizer Rényi Entropy''. Phys. Rev. Lett. 128, 050402 (2022).

[56] Blake Johnson. ``Bringing the full power of dynamic circuits to Qiskit Runtime''. url: https:/​/​research.ibm.com/​blog/​quantum-dynamic-circuits. (accessed: 2022-11-09).

[57] Qiskit Development Team. ``StatevectorSimulator''. url: https:/​/​qiskit.org/​documentation/​stubs/​qiskit.providers.aer.StatevectorSimulator.html. (accessed: 2022-11-01).

[58] Vivek V. Shende and Igor L. Markov. ``On the CNOT-cost of TOFFOLI gates''. Quantum Info. Comput. 9, 461–486 (2009).

[59] Sergio Boixo, Sergei V. Isakov, Vadim N. Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J. Bremner, John M. Martinis, and Hartmut Neven. ``Characterizing quantum supremacy in near-term devices''. Nature Physics 14, 595–600 (2018).

[60] Hsin-Yuan Huang, Richard Kueng, and John Preskill. ``Predicting many properties of a quantum system from very few measurements''. Nature Physics 16, 1050–1057 (2020).

[61] Alastair Kay. ``Quantikz''. url: https:/​/​doi.org/​10.17637/​rh.7000520.v4.

Cited by

[1] Michael Zurel, Lawrence Z. Cohen, and Robert Raussendorf, "Simulation of quantum computation with magic states via Jordan-Wigner transformations", arXiv:2307.16034, (2023).

[2] Qiuhao Chen, Yuxuan Du, Qi Zhao, Yuling Jiao, Xiliang Lu, and Xingyao Wu, "Efficient and practical quantum compiler towards multi-qubit systems with deep reinforcement learning", arXiv:2204.06904, (2022).

[3] Filipa C. R. Peres, "Pauli-based model of quantum computation with higher-dimensional systems", Physical Review A 108 3, 032606 (2023).

[4] Michael Zurel, Cihan Okay, and Robert Raussendorf, "Simulating quantum computation with magic states: how many "bits" for "it"?", arXiv:2305.17287, (2023).

[5] Mark Koch, Richie Yeung, and Quanlong Wang, "Speedy Contraction of ZX Diagrams with Triangles via Stabiliser Decompositions", arXiv:2307.01803, (2023).

The above citations are from SAO/NASA ADS (last updated successfully 2023-12-07 08:46:53). 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 2023-12-07 08:46:52).