Fast algorithms for classical specifications of stabiliser states and Clifford gates
The stabiliser formalism plays a central role in quantum computing, error correction, and fault tolerance. Conversions between and verifications of different specifications of stabiliser states and Clifford gates are important components of many classical algorithms in quantum information, e.g. for...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2025-01-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2025-01-08-1586/pdf/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841554209262010368 |
|---|---|
| author | Nadish de Silva Wilfred Salmon Ming Yin |
| author_facet | Nadish de Silva Wilfred Salmon Ming Yin |
| author_sort | Nadish de Silva |
| collection | DOAJ |
| description | The stabiliser formalism plays a central role in quantum computing, error correction, and fault tolerance. Conversions between and verifications of different specifications of stabiliser states and Clifford gates are important components of many classical algorithms in quantum information, e.g. for gate synthesis, circuit optimisation, and simulating quantum circuits. These core functions are also used in the numerical experiments critical to formulating and testing mathematical conjectures on the stabiliser formalism.
We develop novel mathematical insights concerning stabiliser states and Clifford gates that significantly clarify their descriptions. We then utilise these to provide ten new fast algorithms which offer asymptotic advantages over any existing implementations. We show how to rapidly verify that a vector is a stabiliser state, and interconvert between its specification as amplitudes, a quadratic form, and a check matrix. These methods are leveraged to rapidly check if a given unitary matrix is a Clifford gate and to interconvert between the matrix of a Clifford gate and its compact specification as a stabiliser tableau.
For example, we extract the stabiliser tableau of a $2^n \times 2^n$ matrix, promised to be a Clifford gate, in $O(n 2^n)$ time. Remarkably, it is not necessary to read all the elements of a Clifford gate matrix to extract its stabiliser tableau. This is an asymptotic speedup over the best-known method that is exponential in the number of qubits.
We provide implementations of our algorithms in $\texttt{Python}$ and $\texttt{C++}$ that exhibit vastly improved practical performance over existing algorithms in the cases where they exist. |
| format | Article |
| id | doaj-art-c3b0837bea1f4c17916948fd3254c589 |
| institution | Kabale University |
| issn | 2521-327X |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften |
| record_format | Article |
| series | Quantum |
| spelling | doaj-art-c3b0837bea1f4c17916948fd3254c5892025-01-08T18:14:33ZengVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenQuantum2521-327X2025-01-019158610.22331/q-2025-01-08-158610.22331/q-2025-01-08-1586Fast algorithms for classical specifications of stabiliser states and Clifford gatesNadish de SilvaWilfred SalmonMing YinThe stabiliser formalism plays a central role in quantum computing, error correction, and fault tolerance. Conversions between and verifications of different specifications of stabiliser states and Clifford gates are important components of many classical algorithms in quantum information, e.g. for gate synthesis, circuit optimisation, and simulating quantum circuits. These core functions are also used in the numerical experiments critical to formulating and testing mathematical conjectures on the stabiliser formalism. We develop novel mathematical insights concerning stabiliser states and Clifford gates that significantly clarify their descriptions. We then utilise these to provide ten new fast algorithms which offer asymptotic advantages over any existing implementations. We show how to rapidly verify that a vector is a stabiliser state, and interconvert between its specification as amplitudes, a quadratic form, and a check matrix. These methods are leveraged to rapidly check if a given unitary matrix is a Clifford gate and to interconvert between the matrix of a Clifford gate and its compact specification as a stabiliser tableau. For example, we extract the stabiliser tableau of a $2^n \times 2^n$ matrix, promised to be a Clifford gate, in $O(n 2^n)$ time. Remarkably, it is not necessary to read all the elements of a Clifford gate matrix to extract its stabiliser tableau. This is an asymptotic speedup over the best-known method that is exponential in the number of qubits. We provide implementations of our algorithms in $\texttt{Python}$ and $\texttt{C++}$ that exhibit vastly improved practical performance over existing algorithms in the cases where they exist.https://quantum-journal.org/papers/q-2025-01-08-1586/pdf/ |
| spellingShingle | Nadish de Silva Wilfred Salmon Ming Yin Fast algorithms for classical specifications of stabiliser states and Clifford gates Quantum |
| title | Fast algorithms for classical specifications of stabiliser states and Clifford gates |
| title_full | Fast algorithms for classical specifications of stabiliser states and Clifford gates |
| title_fullStr | Fast algorithms for classical specifications of stabiliser states and Clifford gates |
| title_full_unstemmed | Fast algorithms for classical specifications of stabiliser states and Clifford gates |
| title_short | Fast algorithms for classical specifications of stabiliser states and Clifford gates |
| title_sort | fast algorithms for classical specifications of stabiliser states and clifford gates |
| url | https://quantum-journal.org/papers/q-2025-01-08-1586/pdf/ |
| work_keys_str_mv | AT nadishdesilva fastalgorithmsforclassicalspecificationsofstabiliserstatesandcliffordgates AT wilfredsalmon fastalgorithmsforclassicalspecificationsofstabiliserstatesandcliffordgates AT mingyin fastalgorithmsforclassicalspecificationsofstabiliserstatesandcliffordgates |