Improved Graph Formalism for Quantum Circuit Simulation
- URL: http://arxiv.org/abs/2109.10210v3
- Date: Thu, 7 Oct 2021 06:46:55 GMT
- Title: Improved Graph Formalism for Quantum Circuit Simulation
- Authors: Alexander Tianlin Hu, Andrey Boris Khesin
- Abstract summary: 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.
- Score: 77.34726150561087
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Improving the simulation of quantum circuits on classical computers is
important for understanding quantum advantage and increasing development speed.
In this paper, we explore a new way to express stabilizer states and further
improve the speed of simulating stabilizer circuits with a current existing
approach. First, we discover a unique and elegant canonical form for stabilizer
states based on graph states to better represent stabilizer states and show how
to efficiently simplify stabilizer states to canonical form. Second, we develop
an improved algorithm for graph state stabilizer simulation and establish
limitations on reducing the quadratic runtime of applying controlled-Pauli $Z$
gates. We do so by creating a simpler formula for combining two Pauli-related
stabilizer states into one. Third, to better understand the linear dependence
of stabilizer states, 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(n^3)$
to $O(nd^2)$ where $d$ is the maximum degree of the graph.
Related papers
- Improved bounds for testing low stabilizer complexity states [6.169364905804677]
We improve the state-of-the-art parameters for the tolerant testing of stabilizer states.
We also study the problem of testing low stabilizer rank states.
arXiv Detail & Related papers (2024-10-31T17:56:57Z) - Faster Computation of Stabilizer Extent [3.8061090528695543]
We propose fast numerical algorithms to compute the stabilizer extent.
Our algorithm can compute the stabilizer fidelity and the stabilizer extent for random pure states up to $n=9$ qubits.
arXiv Detail & Related papers (2024-06-24T14:28:15Z) - Stabilizer ground states for simulating quantum many-body physics: theory, algorithms, and applications [0.5735035463793009]
We apply stabilizer states to tackle quantum many-body ground state problems.
We develop an exact and linear-scaled algorithm to obtain stabilizer ground states of 1D local Hamiltonians.
arXiv Detail & Related papers (2024-03-13T11:54:25Z) - 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) - Improved Stabilizer Estimation via Bell Difference Sampling [0.43123403062068827]
We study the complexity of learning quantum states in various models with respect to the stabilizer formalism.
We prove that $Omega(n)$ $T$gates are necessary for any Clifford+$T$ circuit to prepare pseudorandom quantum states.
We show that a modification of the above algorithm runs in time.
arXiv Detail & Related papers (2023-04-27T01:58:28Z) - Simulating scalar field theories on quantum computers with limited
resources [62.997667081978825]
We present a quantum algorithm for implementing $phi4$ lattice scalar field theory on qubit computers.
The algorithm allows efficient $phi4$ state preparation for a large range of input parameters in both the normal and broken symmetry phases.
arXiv Detail & Related papers (2022-10-14T17:28:15Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems.
By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
arXiv Detail & Related papers (2021-08-03T17:49:09Z) - Learning Stabilizing Controllers for Unstable Linear Quadratic
Regulators from a Single Trajectory [85.29718245299341]
We study linear controllers under quadratic costs model also known as linear quadratic regulators (LQR)
We present two different semi-definite programs (SDP) which results in a controller that stabilizes all systems within an ellipsoid uncertainty set.
We propose an efficient data dependent algorithm -- textsceXploration -- that with high probability quickly identifies a stabilizing controller.
arXiv Detail & Related papers (2020-06-19T08:58:57Z) - Sparse Identification of Nonlinear Dynamical Systems via Reweighted
$\ell_1$-regularized Least Squares [62.997667081978825]
This work proposes an iterative sparse-regularized regression method to recover governing equations of nonlinear systems from noisy state measurements.
The aim of this work is to improve the accuracy and robustness of the method in the presence of state measurement noise.
arXiv Detail & Related papers (2020-05-27T08:30:15Z) - Multi-Objective Matrix Normalization for Fine-grained Visual Recognition [153.49014114484424]
Bilinear pooling achieves great success in fine-grained visual recognition (FGVC)
Recent methods have shown that the matrix power normalization can stabilize the second-order information in bilinear features.
We propose an efficient Multi-Objective Matrix Normalization (MOMN) method that can simultaneously normalize a bilinear representation.
arXiv Detail & Related papers (2020-03-30T08:40:35Z)
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.