Fast algorithms for classical specifications of stabiliser states and Clifford gates
- URL: http://arxiv.org/abs/2311.10357v3
- Date: Sun, 26 May 2024 20:36:03 GMT
- Title: Fast algorithms for classical specifications of stabiliser states and Clifford gates
- Authors: Nadish de Silva, Wilfred Salmon, Ming Yin,
- Abstract summary: 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.
We provide example implementations of our algorithms in Python.
- Score: 14.947570152519281
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: The stabiliser formalism plays a central role in quantum computing, error correction, and fault-tolerance. Stabiliser states are used to encode computational basis states. Clifford gates are those which can be easily performed fault-tolerantly in the most common error correction schemes. Their mathematical properties are the subject of significant research interest. 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 for 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 Clifford gate matrix with $N^2$ entries in $O(N \log N)$ time. Remarkably, it is not necessary to read all the elements of a Clifford matrix to extract its stabiliser tableau. This is an asymptotic speedup over the best-known method that is superexponential in the number of qubits. We provide example implementations of our algorithms in Python.
Related papers
- Clifford Manipulations of Stabilizer States: A graphical rule book for
Clifford unitaries and measurements on cluster states, and application to
photonic quantum computing [0.9935277311162707]
We develop a rule-book and a tableau simulator for arbitrary stabilizer manipulations of cluster states.
We extend our graphical rule-book to include dual-rail photonic-qubit cluster state manipulations.
We show how stabilizer descriptions of multi-qubit fusions can be mapped linear optical circuits.
arXiv Detail & Related papers (2023-12-04T22:40:24Z) - Bases for optimising stabiliser decompositions of quantum states [14.947570152519281]
We introduce and study the vector space of linear dependencies of $n$-qubit stabiliser states.
We construct elegant bases of linear dependencies of constant size three.
We use them to explicitly compute the stabiliser extent of states of more qubits than is feasible with existing techniques.
arXiv Detail & Related papers (2023-11-29T06:30:05Z) - Efficient quantum algorithms for stabilizer entropies [0.0]
We efficiently measure stabilizer entropies (SEs) for integer R'enyi index $n>1$ via Bell measurements.
We provide efficient bounds of various nonstabilizerness monotones which are intractable to compute beyond a few qubits.
Our results open up the exploration of nonstabilizerness with quantum computers.
arXiv Detail & Related papers (2023-05-30T15:55:04Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - Iterative Qubit Coupled Cluster using only Clifford circuits [52.77024349608834]
We draw attention to a variant of the iterative qubit coupled cluster (iQCC) method that only uses Clifford circuits.
This method is useful for near-term variational quantum algorithm applications as it generates good initial parameters.
It may also be useful beyond the NISQ era to create short-depth Clifford pre-optimized circuits.
arXiv Detail & Related papers (2022-11-18T20:31:10Z) - Transversal Injection: A method for direct encoding of ancilla states
for non-Clifford gates using stabiliser codes [55.90903601048249]
We introduce a protocol to potentially reduce this overhead for non-Clifford gates.
Preliminary results hint at high quality fidelities at larger distances.
arXiv Detail & Related papers (2022-11-18T06:03:10Z) - Improved Graph Formalism for Quantum Circuit Simulation [77.34726150561087]
We show how to efficiently simplify stabilizer states to canonical form.
We characterize all linearly dependent triplets, revealing symmetries in the inner products.
Using our novel controlled-Pauli $Z$ algorithm, we improve runtime for inner product computation from $O(n3)$ to $O(nd2)$ where $d$ is the maximum degree of the graph.
arXiv Detail & Related papers (2021-09-20T05:56:25Z) - Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
We show that the problem of calculating the $c-disjointness, or even approximating it to within a constant multiplicative factor, is NP-complete.
We provide bounds on the disjointness for various code families, including the CSS codes,$d codes and hypergraph codes.
Our results indicate that finding fault-tolerant logical gates for generic quantum error-correcting codes is a computationally challenging task.
arXiv Detail & Related papers (2021-08-10T15:00:20Z) - Quadratic Clifford expansion for efficient benchmarking and
initialization of variational quantum algorithms [0.8808007156832224]
Variational quantum algorithms are considered to be appealing applications of near-term quantum computers.
We propose a perturbative approach for efficient benchmarking of variational quantum algorithms.
arXiv Detail & Related papers (2020-11-19T16:09:00Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
We show that families of algorithms fail to produce nearly optimal solutions with high probability.
For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
arXiv Detail & Related papers (2020-04-25T05:45:59Z) - Classical Coding Approaches to Quantum Applications [2.5382095320488665]
In deep-space optical communications, current receivers for the pure-state-quantum channel first measure each qubit channel output and then classically post-process the measurements.
In this dissertation we investigate a recently proposed quantum algorithm for this task, which is inspired by classical belief-propagation algorithms.
We show that the algorithm is optimal for each bit and it appears to achieve optimal performance when deciding the full transmitted message.
arXiv Detail & Related papers (2020-04-14T23:31:46Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.