Process Tomography for Clifford Unitaries Timothy Skaras, Paul Ginsparg Abstract We present an algorithm for performing quantum process tomography on an unknown n n -qubit unitary C C from the Clifford group. Our algorithm uses Bell basis measurements to deterministically learn C C with 4 ​ n + 3 4n+3 queries, which is the asymptotically optimal query complexity. In contrast to previous algorithms that required access to C † C^{\dagger} to achieve optimal query complexity, our algorithm achieves the same performance without querying C † C^{\dagger} . Additionally, we show the algorithm is robust to perturbations and can efficiently learn the closest Clifford to an unknown non-Clifford unitary U U using query overhead that is logarithmic in the number of qubits. I Introduction In the general case, learning an unknown quantum state or unknown quantum channel requires resources exponential in system size: quantum state tomography requires exponential copy complexity 1 1 1 By copy complexity, we mean the number of copies of the unknown state required to complete the task. haah2016sample , and quantum process tomography requires exponential query complexity haah2023query . It is worth noting, however, that these bounds apply when there is no prior information about the unknown state or process. Recent work zhao2024learning has highlighted that although most unitaries or states have exponential gate complexity, such states and processes are not physical in the sense that they cannot arise in polynomial time in real systems governed by local Hamiltonians. Indeed, if the unknown state or process is known to have certain structure, in many cases the learning task can be performed much more efficiently. For instance, various work has investigated the copy complexity of quantum state tomography on an unknown stabilizer state. From Holevo’s theorem holevo1973bounds , the copy complexity of state tomography on an n -qubit stabilizer state is \Omega(n) . Gottesman and Aaronson gottesman_aaronson_08080052 described two algorithms for this task: one which used \mathcal{O}(n^{2}) single-copy measurements and another which used entangled measurements on \mathcal{O}(n) copies. While the latter is theoretically optimal, collective measurement on this many copies is impractical. Montanaro montanaro2017learning described an algorithm which used two-copy Bell basis measurements to perform state tomography with overall \mathcal{O}(n) copy complexity. For the task of process tomography, Low low2009learning proposed an algorithm for learning an unknown Clifford C with \mathcal{O}(n) query complexity. This query complexity was shown to be optimal, but the algorithm required access to the inverse process C^{\dagger} . More recent work lai2022learning describes a probabilistic algorithm for learning C without C^{\dagger} , but the method uses \mathcal{O}(n^{2}) queries and is therefore not asymptotically optimal. In this work, we propose a deterministic 4n+3 query complexity algorithm for process tomography on a Clifford unitary which does not require access to C^{\dagger} . Our algorithm queries C on Bell basis states to deterministically learn how C transforms Pauli operators. Lastly, we consider the case in which we have oracle access to an unknown non-Clifford unitary U . We find that by repeating each step of our original algorithm multiple times, we can learn the closest Clifford to U with minimal overhead. II Background The n -qubit Pauli group \mathcal{P}_{n} is generated by the single-qubit Pauli operators X_{j}=\begin{pmatrix}0&1\\ 1&0\end{pmatrix},\,Y_{j}=\begin{pmatrix}0&-i\\ i&0\end{pmatrix},\,Z_{j}=\begin{pmatrix}1&0\\ 0&-1\end{pmatrix}, which are understood as acting on the j^{th} qubit for j=1,\ldots,n . We denote Pauli operators using pairs of bits: P^{00}=I,\quad P^{01}=X,\quad P^{10}=Z,\quad P^{11}=Y. (1) Using bit strings \vec{a},\vec{b}\in\{0,1\}^{n} , we extend this notation to denote n -qubit Pauli operators P^{\vec{a},\vec{b}}=P^{a_{1}b_{1}}\otimes\cdots\otimes P^{a_{n}b_{n}}. This notation is convenient because multiplying Pauli operators is the same as modulo 2 addition on the labels up to a global phase P^{\vec{a},\vec{b}}P^{\vec{c},\vec{d}}=\kappa P^{\vec{a}\oplus\vec{c},\vec{b}\oplus\vec{d}} where \kappa=i^{\vec{a}\cdot\vec{d}-\vec{b}\cdot\vec{c}} . We can decompose any n -qubit Pauli as a product of single qubit X and Z operators with a global phase factor P^{\vec{a},\vec{b}}=i^{\vec{a}\cdot\vec{b}}\prod_{i=1}^{n}Z_{i}^{a_{i}}X_{i}^{b_{i}}. (2) Once we include multiplicative factors of \pm 1 and \pm i , these Pauli operators form a closed group under matrix multiplication known as the Pauli group, which can be written \mathcal{P}_{n}=\{i^{k}P^{\vec{a},\vec{b}}|\vec{a},\vec{b}\in\{0,1\}^{n},k\in\{0,1,2,3\}\} . Our circuits will make use of measurements in the Bell basis. On two qubits, there are four Bell pair states \displaystyle\ket{\Phi^{00}}=\frac{1}{\sqrt{2}}(\ket{00}+\ket{11}) \displaystyle,\quad\ket{\Phi^{01}}=\frac{1}{\sqrt{2}}(\ket{01}+\ket{10}), \displaystyle\ket{\Phi^{10}}=\frac{1}{\sqrt{2}}(\ket{00}-\ket{11}) \displaystyle,\quad\ket{\Phi^{11}}=\frac{1}{\sqrt{2}}(\ket{01}-\ket{10}). By inspection, we see that any Bell pair can be written as a Pauli acting on one half of \ket{\Phi^{00}} : \ket{\Phi^{ij}}=Z_{1}^{i}X_{1}^{j}\ket{\Phi^{00}}=X_{2}^{j}Z_{2}^{i}\ket{\Phi^{00}}. (3) Generalizing to larger systems, we denote a Bell state on 2n qubits as |\Phi^{\vec{i},\vec{j}}\rangle=\ket{\Phi^{i_1j_1}}_{1,n+1}\cdots\ket{\Phi^{i_n j_n}}_{n,2n} where \vec{i},\vec{j}\in\{0,1\}^{n} and \ket{\Phi^{i_1j_1}}_{r,s} denotes a Bell pair on qubits r and s . If we have a Bell state on two registers of n qubits \mathcal{A} and \mathcal{B} , we can write |\Phi^{\vec{i},\vec{j}}\rangle_{\mathcal{A}\mathcal{B}}=(-i)^{\vec{i}\cdot\vec{j}}P_{\mathcal{A}}^{\vec{i},\vec{j}}|\Phi^{\vec{0},\vec{0}}\rangle_{\mathcal{A}\mathcal{B}}=i^{\vec{i}\cdot\vec{j}}P_{\mathcal{B}}^{\vec{i},\vec{j}}|\Phi^{\vec{0},\vec{0}}\rangle_{\mathcal{A}\mathcal{B}}, (4) which generalizes the observation in eq. ( 3 ). The state |\Phi^{\vec{0},\vec{0}}\rangle is a maximally entangled state which, for simplicity, we will sometimes denote as \ket{\Phi_{d}} , where d is the dimension of each subsystem \mathcal{A} and \mathcal{B} . This state can also be written as \ket{\Phi_{d}}=\frac{1}{\sqrt{d}}\sum_{i=0}^{d-1}\ket{i,i}. (5) The n -qubit Clifford group \mathcal{C}_{n} is defined as the normalizer for \mathcal{P}_{n} : \mathcal{C}_{n}=\{U\in U(2^{n})\,|\,U\mathcal{P}_{n}U^{\dagger}\subseteq\mathcal{P}_{n}\}. The Gottesman-Chuang hierarchy gottesman1999demonstrating generalizes the Clifford group, and we denote the k^{th} level of this hierarchy on n qubits as \mathcal{C}^{(k)}_{n} . This hierarchy is defined recursively as \mathcal{C}_{n}^{(k)}=\{U\in U(2^{n})\,|\,U\mathcal{P}_{n}U^{\dagger}\subseteq\mathcal{C}_{n}^{(k-1)}\}, with the assumption that \mathcal{C}_{n}^{(1)}=\mathcal{P}_{n} . Note that the Clifford group \mathcal{C}_{n}=\mathcal{C}_{n}^{(2)} is the second level in this hierarchy. Without loss of generality, let us suppose C\in\mathcal{C}_{n} is an unknown Clifford unitary such that CZ_{i}C^{\dagger}=(-1)^{f_{i}}P^{\vec{a}_{i},\vec{b}_{i}}\qquad CX_{i}C^{\dagger}=(-1)^{h_{i}}P^{\vec{c}_{i},\vec{d}_{i}}, (6) where \vec{a}_{i},\vec{b}_{i},\vec{c}_{i},\vec{d}_{i}\in\{0,1\}^{n} and f_{i},h_{i}\in\{0,1\} . For any element C of the Clifford group, we can decompose it as C=\widetilde{C}P^{\vec{h},\vec{f}} (7) where \widetilde{C}Z_{i}\widetilde{C}^{\dagger}=P^{\vec{a}_{i},\vec{b}_{i}},\qquad\widetilde{C}X_{i}\widetilde{C}^{\dagger}=P^{\vec{c}_{i},\vec{d}_{i}}, (8) and \vec{h},\vec{f} have their elements determined by h_{i},f_{i} in eq. ( 6 ). Eq. ( 7 ) follows from the fact that if C flips the sign of Z_{i} (i.e., f_{i}=1 ), this is the same as P^{\vec{h},\vec{f}} having an X Pauli operator on the i^{th} qubit. More formally, the Clifford decomposition in eq. ( 7 ) is a manifestation of the fact that \widetilde{C}\in\mathcal{C}_{n}/\mathcal{P}_{n} . We will use the fact that the quotient group \mathcal{C}_{n}/\mathcal{P}_{n} is isomorphic to the symplectic group over the binary field \mathbb{F}_{2} koenig2014efficiently : \mathcal{C}_{n}/\mathcal{P}_{n}\cong\text{Sp}(2n,\mathbb{F}_{2}). We define the symplectic group as being 2n\times 2n matrices S with entries in \mathbb{F}_{2} such that S^{T}\Lambda(n)S=\Lambda(n)\equiv\begin{pmatrix}0_{n}&I_{n}\\ I_{n}&0_{n}\end{pmatrix}. (9) This relationship is equivalent to enforcing the constraint that \widetilde{C} must map Paulis Z_{i} and X_{i} in such a way that preserves their algebra, i.e., preserves all pairwise commutation and anti-commutation relationships. In this representation, we map Z_{i},X_{i} to standard basis elements of the vector space \mathbb{F}_{2}^{2n} Z_{i}=\begin{pmatrix}\vec{e}_{i}\\ \vec{0}\end{pmatrix},\quad X_{i}=\begin{pmatrix}\vec{0}\\ \vec{e}_{i}\end{pmatrix}. An arbitrary Pauli element up to multiplicative phase factor is therefore P^{\vec{a},\vec{b}}=\begin{pmatrix}\vec{a}\\ \vec{b}\\ \end{pmatrix}, where \vec{a} and \vec{b} are understood to be column vectors. More concretely, we can write the transformation described by Clifford \widetilde{C} in eq. ( 8 ) as a symplectic matrix S S=\begin{pmatrix}\vec{a}_{1}&\cdots&\vec{a}_{n}&\vec{c}_{1}&\cdots&\vec{c}_{n}\\ \\[-8.0pt] \vec{b}_{1}&\cdots&\vec{b}_{n}&\vec{d}_{1}&\cdots&\vec{d}_{n}\\ \end{pmatrix}\equiv\begin{pmatrix}A&C\\ B&D\end{pmatrix}, where A,B,C,D\in\mathbb{F}_{2}^{n\times n} are matrices defined to have columns given by \vec{a}_{i},\vec{b}_{i},\vec{c}_{i},\vec{d}_{i} respectively. We use the symplectic relationship ( 9 ) to write an explicit expression for the inverse of S , which is the symplectic representation for \widetilde{C}^{\dagger} . Multiplying both sides of eq. ( 9 ) by \Lambda gives us \Lambda S^{T}\Lambda S=I , which implies S^{-1}=\Lambda S^{T}\Lambda=\begin{pmatrix}D^{T}&C^{T}\\ B^{T}&A^{T}\end{pmatrix}. (10) A Pauli operator P\in\mathcal{P}_{n} is said to stabilize a state \ket{\psi} if P\ket{\psi}=\ket{\psi} . An n -qubit stabilizer state is a quantum state that can be prepared by applying a Clifford unitary to the state \ket{0}^{\otimes n} . We denote as \text{Stab}(\ket{\psi})\subseteq\mathcal{P}_{n} the set of Pauli operators that stabilize \ket{\psi} . This subset of the Pauli group forms a subgroup under matrix multiplication and is called the stabilizer group for \ket{\psi} . III Learning Clifford Unitaries In this section, we describe our algorithm to learn an unknown n -qubit Clifford unitary C . The algorithm is deterministic and guaranteed to learn the unknown Clifford with only 4n+3 queries to C . In the first stage of the algorithm, we use a subroutine based on the Twin- C circuit depicted in fig. to learn the symplectic representation S used to describe \widetilde{C} . In the second stage we use the circuit in fig. to learn P^{\vec{h},\vec{f}} . By eq. ( 7 ), these two unitaries determine C .