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.
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.
 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).
 Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum Algorithm for Linear Systems of Equations''. Phys. Rev. Lett. 103, 150502 (2009).
 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).
 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).
 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).
 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).
 Vedran Dunjko, Yimin Ge, and J. Ignacio Cirac. ``Computational Speedups Using Small Quantum Devices''. Phys. Rev. Lett. 121, 250501 (2018).
 Mithuna Yoganathan, Richard Jozsa, and Sergii Strelchuk. ``Quantum advantage of unitary Clifford circuits with magic state inputs''. Proc. R. Soc. A 475, 20180427 (2019).
 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.
 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.
 Hakop Pashayan, Joel J. Wallman, and Stephen D. Bartlett. ``Estimating Outcome Probabilities of Quantum Circuits Using Quasiprobabilities''. Phys. Rev. Lett. 115, 070501 (2015).
 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).
 Sergey Bravyi and David Gosset. ``Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates''. Phys. Rev. Lett. 116, 250501 (2016).
 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).
 Hammam Qassim, Joel J. Wallman, and Joseph Emerson. ``Clifford recompilation for faster classical simulation of quantum circuits''. Quantum 3, 170 (2019).
 Aleks Kissinger and John van de Wetering. ``Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions''. Quantum Science and Technology 7, 044001 (2022).
 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).
 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).
 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).
 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).
 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).
 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).
 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).
 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.
 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).
 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).
 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).
 Mark Howard and Earl Campbell. ``Application of a Resource Theory for Magic States to Fault-Tolerant Quantum Computing''. Phys. Rev. Lett. 118 (2017).
 Lorenzo Leone, Salvatore F. E. Oliviero, and Alioscia Hamma. ``Stabilizer Rényi Entropy''. Phys. Rev. Lett. 128, 050402 (2022).
 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).
 Qiskit Development Team. ``StatevectorSimulator''. url: https://qiskit.org/documentation/stubs/qiskit.providers.aer.StatevectorSimulator.html. (accessed: 2022-11-01).
 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).
 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).
 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).
 Filipa C. R. Peres, "Pauli-based model of quantum computation with higher-dimensional systems", Physical Review A 108 3, 032606 (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).
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.