Optimal constant-cost implementations of Clifford operations using global interactions

Jonathan Nemirovsky, Lee Peleg, Amit Ben Kish, Yotam Shapira · 2025

Read Optimal constant-cost implementations of Clifford operations using global interactions by Jonathan Nemirovsky, Lee Peleg, Amit Ben Kish, Yotam Shapira (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-20730.txt.

Introduction

Jonathan Nemirovsky, Lee Peleg, Amit Ben Kish. Yotam Shapira show how to run any chain of Clifford operations on a quantum computer with at most four uses of a global entangling gate. The setting pairs free single qubit moves with programmable all to all gates, as found on trapped ion machines.

Four uses is the best possible count, and the method needs no spare qubits to reach it. The team first shows any chain of two qubit link gates fits in four global steps, then extends the result to all Clifford moves at no extra cost. They also check the drive power the plan needs and find it lower than a standard route, making the scheme practical as well as tight.

Catalog record

CREATORJonathan Nemirovsky, Lee Peleg, Amit Ben Kish, Yotam Shapira
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE15 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-20730

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Optimal constant-cost implementations of Clifford operations using global interactions Jonathan Nemirovsky, Lee Peleg, Amit Ben Kish, Yotam Shapira Abstract We investigate quantum circuits built from arbitrary single-qubit operations combined with programmable all-to-all multiqubit entangling gates that are native to, among other systems, trapped-ion quantum computing platforms. We report a constant-cost of no more than four applications of such Clifford entangling multiqubit gates to realize any sequence of Clifford operations of any length, without ancillae, which is the theoretically optimal gate count cost. We do this by implementing any sequence of CNOT gates of any length with four applications of such gates, without ancillae, and show that the extension to general Clifford operations incurs no additional cost. We investigate the required qubit drive power that is associated with our implementation and show that it is lower than that of a standard approach. Our work introduces a practical and computationally efficient algorithm to realize these compilations. Clifford operations are central to many quantum information processing applications such as quantum error correction, simulation algorithms, generation of pseudo-random unitaries, qubit permutations, compilation of quantum circuits and benchmarking van den Berg and Temme 2020 ; Haferkamp et al. 2023 ; Kueng and Gross 2015 ; Zhu 2017 ; Elben et al. 2023 ; Huang et al. 2022 ; Huang et al. 2020 ; Nemirovsky et al. 2025a ; Nemirovsky et al. 2025b . Thus, it is of considerable interest to develop efficient decompositions of Clifford operations. Here we provide an explicit algorithm that decomposes arbitrary Clifford operations into a quantum circuit that utilizes single-qubit rotations and, at most, four multiqubit programmable all-to-all entangling gates, which saturates the lower bound Cleve et al. 2025 . Previous works have shown implementations of Clifford operations using such multiqubit gates with a gate count that is linear (in the number of qubit), logarithmic or constant Maslov and Nam 2018 ; Van de Wetering 2021 ; Maslov and Zindorf 2022 ; Bravyi et al. 2022 ; Cleve et al. 2025 , with Ref. Bravyi et al. 2022 greatly inspiring this work. Explicitly, the multiqubit Clifford gate over n qubits we consider is, U_{\text{MQ}}^{\text{(P)}}\left(\xi\right)=e^{-i\frac{\pi}{2}\sum_{k=1}^{n}\xi_{kk}P_{k}-i\frac{\pi}{4}\sum_{k>j}^{n}\xi_{kj}P_{k}P_{j}}, (1) where P_{k} is the P\in\{X,Y,Z\} Pauli operator, acting on the k th qubit and \xi\in\mathbb{F}_{2}^{n\times n} is an arbitrary symmetric matrix of zeros and ones, such that for k\neq j , \frac{\pi}{4}\xi_{kj} is a correlated P\otimes P rotation between the k th and j th qubits. We note that U_{\text{MQ}}^{\text{(X)}} and U_{\text{MQ}}^{\text{(Z)}} are equivalent up to single-qubit Hadamard gates, yet in our derivations below it is simpler to use them both. These gates can be economically implemented on trapped-ions based quantum computers Feng et al. 2023 ; Pogorelov et al. 2021 ; Yao et al. 2022 ; Guo et al. 2024 ; Schwerdt et al. 2024 ; Nemirovsky et al. 2025a , where the long-range Coulomb coupling between the ions underpins the all-to-all programmability Grzesiak et al. 2020 ; Shapira et al. 2020 ; Shapira et al. 2023 ; Lu et al. 2019 ; Baßler et al. 2023 ; Lu et al. 2019 ; Lu et al. 2025 ; Shapira et al. 2025 . Additional quantum computing modalities have the potential to generate such programmable multiqubit interactions Evered et al. 2023 ; Young et al. 2021 ; Cooper et al. 2024 ; Song et al. 2025 , and can as well benefit from our method. Our decomposition relies on two steps. We first show that an arbitrary Clifford operation can be decomposed to the form (operating left to right), U_{\text{C}}=-\text{P}-\text{S}_{Z}-\text{H}_{\text{all}}-\text{R}_{XX}-\text{CX}-\text{R}_{ZZ}-\text{S}_{Z}-\text{H}-, (2) by a simple extension of the decompositions in Refs. Proctor and Young 2023 ; Bravyi et al. 2022 ; Bravyi and Maslov 2021 ; Nemirovsky et al. 2025c , with -\text{P}- a layer of Pauli gates, -\text{S}_{Z}- a layer of single-qubit Z^{1/2} phase gates, -\text{H}_{\text{all}}- a layer of Hadamard gates over all qubits, -\text{R}_{XX}- and -\text{R}_{ZZ}- correlated rotation layers of R_{XX}=\exp\left(i\frac{\pi}{4}X\otimes X\right) and R_{ZZ}=\exp\left(i\frac{\pi}{4}Z\otimes Z\right) gates, respectively, -\text{CX}- a classical linear reversible circuit made of CNOT gates and -\text{H}- a layer of Hadamard gates. Clearly the -\text{R}_{ZZ}- layer can be implemented with a single use of U_{\text{MQ}}^{\text{(Z)}} and similarly the -\text{R}_{XX}- with a single use of U_{\text{MQ}}^{\text{(X)}} . Next, we show that the linear reversible circuit, -\text{CX}- , can be decomposed with at most four multiqubit gates. Moreover, this decomposition starts with a U_{\text{MQ}}^{\text{(X)}} gate and terminates with a U_{\text{MQ}}^{\text{(Z)}} gate. These ‘edge’ gates are then merged with the correlated rotation layers, such that sequence -\text{R}_{ZZ}-\text{CX}-\text{R}_{XX}- from Eq. ( 2 ) is implemented with, at most, four multiqubit gates. Since all other gates in the decomposition are single-qubit gates, then overall the Clifford operation itself is implemented with, at most, four multiqubit gates. This gate cost is the lower bound, as shown in Ref. Cleve et al. 2025 . We work within the symplectic matrix formalism, in which Clifford operations over n qubits are mapped in a homeomorphism to 2n\times 2n matrices over the binaries \mathbb{F}_{2}=\left\{0,1\right\} Gottesman 1997 ; Aaronson and Gottesman 2004 . The symplectic matrix is equivalent, up to Pauli strings which are easy to compute, to the Clifford operation. Specifically, the symplectic forms of the -\text{CX}- layer, U_{\text{MQ}}^{\text{(Z)}}\left(\xi\right) and U_{\text{MQ}}^{\text{(X)}}\left(\xi\right) are given by, \displaystyle S(U_{\text{MQ}}^{\text{(Z)}}(\xi))=\begin{bmatrix}I_{n}&0\\ \xi&I_{n}\end{bmatrix}, (3) \displaystyle S(U_{\text{MQ}}^{\text{(X)}}(\xi))=\begin{bmatrix}I_{n}&\xi\\ 0&I_{n}\end{bmatrix}, (4) \displaystyle S\left(-\text{CX}-\right)=\begin{bmatrix}C^{-T}&0\\ 0&C\end{bmatrix}, (5) with \xi a symmetric matrix as in Eq. ( 1 ), I_{n} the n\times n identity operator and C an invertible matrix such that C^{-T} is its inverse transpose. These representation are explicitly derived in Ref. Nemirovsky et al. 2025c . We first derive the general decomposition in Eq. ( 2 ). We start from the known decomposition in Refs. Bravyi and Maslov 2021 ; Proctor and Young 2023 , U_{C}=-\text{P}-\text{CX}-\text{R}_{\text{ZZ}}-\text{S}_{Z}-\text{H}_{\text{all}}-\text{R}_{\text{ZZ}}-\text{S}_{\text{Z}}-\text{H}-, (6) We proceed by commuting the -\text{H}_{\text{all}}- layer towards the left-hand side. Since this layer operates with a Hadamard on all qubits it transforms -\text{S}_{Z}-\mapsto-\text{S}_{X}- , a set of X^{1/2} single qubit rotations and similarly -\text{R}_{\text{ZZ}}-\mapsto-\text{R}_{\text{XX}}- . The -\text{CX}- layer is modified such that the roles of target and control qubits are exchanged, retaining a -\text{CX}- layer structure. We obtain, U_{C}=-\text{P}-\text{H}_{\text{all}}-\text{CX}-\text{R}_{\text{XX}}-\text{S}_{\text{X}}-\text{R}_{\text{ZZ}}-\text{S}_{\text{Z}}-\text{H}-, (7) In the symplectic representation, Eq. ( 7 ) becomes, \begin{split}S(U_{C})=&S(-\text{H}-)S(-\text{R}_{\text{ZZ}}-\text{S}_{\text{Z}}-)\\ &S(-\text{R}_{\text{XX}}-\text{S}_{\text{X}}-)S(-\text{CX}-)S(-\text{H}_{\text{all}}-)\end{split} (8) Focusing on \tilde{S}\equiv S(-\text{R}_{\text{XX}}-\text{S}_{\text{X}}-)S(-\text{CX}-) , we note that, \begin{split}\tilde{S}&=\begin{bmatrix}I&M\\ 0&I\end{bmatrix}\begin{bmatrix}C^{-T}&0\\ 0&C\end{bmatrix}=\begin{bmatrix}C^{-T}&0\\ 0&C\end{bmatrix}\begin{bmatrix}I&C^{T}MC\\ 0&I\end{bmatrix}\\ &=S(-\text{CX}-)S(-\text{R}_{\text{XX}}-\text{S}_{\text{X}}-).\end{split} (9) That is, the layers commute by modifying the \text{R}_{\text{XX}}- and -\text{S}_{\text{X}}- layers. We note that this fact is also intuitive by considering the operation of CNOT gates on phase-gadgets Nemirovsky et al. 2025b . Applying Eq. ( 9 ) to Eq. ( 8 ), and commuting the -\text{S}_{\text{X}}- layer with -\text{H}_{\text{all}}- , we obtain the decomposition shown in Eq. ( 2 ) above, concluding the proof. Next we show a decomposition of the -\text{CX}- layer with at most four multiqubit gates that starts with U_{\text{MQ}}^{\text{(X)}} and terminates with U_{\text{MQ}}^{\text{(Z)}} . We recall that the symplectic matrix of the -\text{CX}- layer, S\left(-\text{CX}-\right) , follows the block form in Eq. ( 5 ), with C a known invertible matrix. We choose symmetric invertible matrices E_{1} and E_{2} such that C=E_{1}^{-1}E_{2} , such a decomposition exists and is found efficiently Taussky 1972 . We also define F=E_{1}^{-1}+E_{2}^{-1} . With this, S\left(-\text{CX}-\right) is given by (see step-by-step realization in the SM SM ), S\left(-\text{CX}-\right)=\begin{bmatrix}I_{n}&0\\ FC^{T}&I_{n}\end{bmatrix}\begin{bmatrix}I_{n}&E_{1}\\ 0&I_{n}\end{bmatrix}\begin{bmatrix}I_{n}&0\\ F&I_{n}\end{bmatrix}\begin{bmatrix}I_{n}&E_{2}\\ 0&I_{n}\end{bmatrix}. (10) Crucially, F

Read the complete text