Low-overhead tailoring and learning of noise in graph states

The gist Low-Overhead Tailoring and Learning of Noise in Graph States establishes a low Clifford hierarchy circuit-based scheme for tailoring and learning noise in (hyper)graph states by converting the noisy input state into a diagonal form, which proves to have a lower resource overhead The work proposes novel methods for characterizing the noise properties of an entangled state at a lower cost than that of state generation.

Noise Tailoring and State Transformation

The core idea involves diagonalizing a noisy multi-qubit (hyper)graph state and deriving the convolution equation of diagonal noise rate, which proves to have a lower resource overhead. This process is achieved by employing gates from a lower level of the Clifford hierarchy than those used in the target graph state, together with depth-one transversal CNOT operations. To prepare the Bell-like measurement circuit acting on two copies of the noisy graph states, this circuit transforms the noise of each copy into some dephasing noise and then obtains the final measurement outcome following the self-convolution of the dephasing rate. Two strategies are proposed for decoding this self-convolution to reveal the dephasing noise rate: 1) Walsh-Hadamard transform (WHT) and 2) convolution power method (CPM).

Noise Learning Schemes

The paper outlines two primary methods for estimating the diagonal elements of the noisy state, denoted as noise tailoring.

1. Walsh-Hadamard transform (WHT): This method uses WHT for the self-convolution of the target dephasing rate, which requires neither Pauli eigenvalue estimation nor cyclic benchmarking of the noise channel. The fast Walsh Hadamard transform (FWHT) algorithm enables this calculation within O(n squared n) time, which can be reduced to O(V log(V)) if the support of µ' is known to belong to proper subspace V.

2. Convolution power method (CPM): CPM approximates the noise by truncating the higher-order component in the perturbed expansion of the solution, and is valid for low infidelity cases. The approximate solution p' is found by sampling outcomes from each term of a geometric series expansion, resulting in an expression like p = wX−1l=0⌊l2X⌋k=0C2k+1lµ∗k+1 + O(3wδ 2w+s + (δw)!, which is exact when δ → 0.

Complexity and Efficiency

The proposed scheme achieves polynomial time complexities for noise estimation, guaranteeing bounded noise estimation error with respect to the l2-norm, which usually requires exponential complexity with existing noise estimation methods. Specifically, constant sampling and polynomial time complexities are sufficient to guarantee bounded noise estimation error with respect to the l2-norm. Theorem 1 shows that by measuring two copies of ρp with the unitaries of one-step lower Clifford hierarchy and transversal CNOT gates applied to the state, we can obtain a quadratic equation of p. The average number of two-qubit gates for the merged feedback is at most n 2/4.

Error Bounds and Projection

The analysis provides rigorous bounds on the estimation error, showing that the l1 distance between p and p' is asymptotically twice shorter than the distance between sampled distributions, i.e., ∥p − p′∥1 ≤ (1/2 + δ)∥µ − µ′∥1. The projection of the quasi-probability onto the probability simplex yields a non-negative distribution p(+), and this transformation ensures that the distance from p to p(+) does not increase, i.e., ∥p(+) − p∥2 ≤ ∥p′ − p∥2. The complexity of this projection is O(A log(A)), where A is the support size of p'.

Practical Performance

Numerical simulations demonstrate the accuracy and efficiency of the noise detection algorithm, showing that for small noise rates δ, the average rate converges to ≃ 0.5 + δ by increasing n. The Z-noise case exhibits the best performance in terms of sampling complexity because Z-noise commutes with every CCZ gate and does not propagate to other qubits. The work implies that quantum computing based on a largely entangled resource state can circumvent the conventional problem of the inefficiency in noise learning and recovery.

Future Directions

Further refinement is needed to encompass a wider fidelity region, and generalizing the scheme to estimate the off-diagonal elements of the input state ρ remains an open problem. The non-linearity of the noise equation suggests that interpreting it as the cost of trying to detect the noise of magic states using lower Clifford hierarchy resources is a potential avenue for future work.

Acknowledgments

The authors thank Myungshik Kim for the thoughtful discussions throughout the project. This work was supported by the Korean government [Ministry of Science and ICT (MSIT)], the NRF grants funded by the Korea government (MSIT) (No. RS-2024-00413957, No. RS2024-00438415, and RS2023-NR076733), the Institute of Information & Communications Technology Planning & Evaluation (IITP) grant funded by the Korea government (MSIT) (IITP-2025-RS-2020-II201606 and IITP2025-RS-2024-00437191), and the Institute of Applied Physics at Seoul National University. This research was also supported by the education and training program of the Quantum Information Research Support Center, funded through the National research foundation of Korea (NRF) by the Ministry of science and ICT(MSIT) of the Korean government (No.2021M3H3A1036573). J.S. thanks support from the Innovate UK (Project No.10075020) and Schmidt Sciences, LLC.

Appendix A: Clifford hierarchy of multiple controlled-Z gates

This section shows that the kth-order multiple controlled-Z gate is of kth-order Clifford hierarchy. Lemma 1 proves that the n + 1-qubit unitary P ⊗ U is of kth-order Clifford hierarchy and if k > 1, UP, PU ∈ Cl(k)n. Proposition 6 confirms that CAZ with A = k' + 1 is a unitary of k-th ordered Clifford hierarchy.

Appendix B: Gate merging

This section demonstrates how to merge three non-local parts into one by showing that the second tailoring part commutes with the transversal CNOT gates, allowing them to be merged into the feedback section. Proposition 7 proves that the number of two-qubit Clifford gates to run the noise tailoring and learning of third-order hypergraph states is O(n 2), where the average over measurement copies is at most Θ(n 2/4).

Appendix C: Validity and complexity of WHT

The proof shows that P ≥ 0 if Pe,b ≥ 0, which implies P ≥ 0. Proposition 9 establishes the time complexity for WHT as O(V log(V)).

Appendix D: Convolution power method (CPM)

Lemma 2 provides a geometric series formula for the inverse of the convolution operator, and Equation (D3) gives the general expression for p. The analysis shows that under certain conditions on δ, the matrix norm of the inverse part is upper bounded by O(1).

1. Improved noise learning for graph states by using a low Clifford hierarchy circuit-based scheme for tailoring and learning noise in (hyper)graph states generated by multiple controlled-Z gates. This allows for characterizing the noise properties of an entangled state at a lower cost than state generation, providing richer information on noise rates and enable[s] noise mitigation, thereby providing guarantees for the preparation of graph states.

2. Enhanced error correction protocols by utilizing the derived convolution equation of diagonal noise rate and applying efficient decoding methods like the Walsh-Hadamard transform (WHT) or Convolution Power Method (CPM) to estimate tailored noise with constant sampling and polynomial time complexities are sufficient to guarantee bounded noise estimation error with respect to the l2-norm.

3. Development of a more accurate state preparation platform by using noise tailoring techniques, which can be achieved by transforming the noisy input state into a diagonal form, enabling real quantum simulation by using the same conversion technique into the graph state input.

4. Creation of a system for characterizing noise properties that offers better guarantees than existing methods, as it allows one to attain richer information on noise rates and enable[s] noise mitigation, thereby providing guarantees for the preparation of graph states compared to state verification methods.