Stabilizer rank and higher-order Fourier analysis
- URL: http://arxiv.org/abs/2107.10551v2
- Date: Fri, 4 Feb 2022 16:27:01 GMT
- Title: Stabilizer rank and higher-order Fourier analysis
- Authors: Farrokh Labib
- Abstract summary: We establish a link between stabilizer states, stabilizer rank, and higher-order Fourier analysis.
We show that the qudit analog of the $n$-qubit magic state has stabilizer rank $Omega(n)$, generalizing their result to qudits of any prime dimension.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We establish a link between stabilizer states, stabilizer rank, and
higher-order Fourier analysis -- a still-developing area of mathematics that
grew out of Gowers's celebrated Fourier-analytic proof of Szemer\'edi's theorem
\cite{gowers1998new}. We observe that $n$-qudit stabilizer states are so-called
nonclassical quadratic phase functions (defined on affine subspaces of
$\mathbb{F}_p^n$ where $p$ is the dimension of the qudit) which are fundamental
objects in higher-order Fourier analysis. This allows us to import tools from
this theory to analyze the stabilizer rank of quantum states. Quite recently,
in \cite{peleg2021lower} it was shown that the $n$-qubit magic state has
stabilizer rank $\Omega(n)$. Here we show that the qudit analog of the
$n$-qubit magic state has stabilizer rank $\Omega(n)$, generalizing their
result to qudits of any prime dimension. Our proof techniques use explicitly
tools from higher-order Fourier analysis. We believe this example motivates the
further exploration of applications of higher-order Fourier analysis in quantum
information theory.
Related papers
- Geometry of degenerate quantum states, configurations of $m$-planes and invariants on complex Grassmannians [55.2480439325792]
We show how to reduce the geometry of degenerate states to the non-abelian connection $A$.
We find independent invariants associated with each triple of subspaces.
Some of them generalize the Berry-Pancharatnam phase, and some do not have analogues for 1-dimensional subspaces.
arXiv Detail & Related papers (2024-04-04T06:39:28Z) - Vertex-minor universal graphs for generating entangled quantum subsystems [3.1758167940451987]
We study the notion of $k$-stabilizer universal quantum state, that is, an $n$-qubit quantum state, such that it is possible to induce any stabilizer state on any $k$ qubits.
These states generalize the notion of $k$-pairable states introduced by Bravyi et al., and can be studied from a perspective using graph states and $k$-vertex-minor universal graphs.
arXiv Detail & Related papers (2024-02-09T09:17:19Z) - Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting [64.0722630873758]
We consider rather general and broad class of Markov chains, Ito chains, that look like Euler-Maryama discretization of some Differential Equation.
We prove the bound in $W_2$-distance between the laws of our Ito chain and differential equation.
arXiv Detail & Related papers (2023-10-09T18:38:56Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously.
Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples.
We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
arXiv Detail & Related papers (2023-09-25T17:54:19Z) - Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach [6.169364905804677]
The approximate stabilizer rank of a quantum state is the minimum number of terms in any approximate decomposition of that state into stabilizer states.
We improve the lower bound on the approximate rank to $tilde Omega(sqrt n)$ for a wide range of the approximation parameters.
arXiv Detail & Related papers (2023-05-17T15:09:41Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis.
We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$.
Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
arXiv Detail & Related papers (2022-08-19T18:00:34Z) - New techniques for bounding stabilizer rank [0.0]
We present number-theoretic and algebraic-geometric techniques for bounding the stabilizer rank of quantum states.
We show an explicit sequence of product states with exponential stabilizer rank but approximate stabilizer rank, and to provide alternate (and simplified) proofs of the best-known lower bounds on stabilizer rank and approximate stabilizer rank.
arXiv Detail & Related papers (2021-10-15T00:29:21Z) - 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) - Lower Bounds on Stabilizer Rank [3.265773263570237]
We prove that for a sufficiently small constant $delta, the stabilizer rank of any state which is $$-close to those states is $Omega(sqrtn/log n)$.
This is the first non-trivial lower bound for approximate stabilizer rank.
arXiv Detail & Related papers (2021-06-06T19:27:51Z) - Learning Set Functions that are Sparse in Non-Orthogonal Fourier Bases [73.53227696624306]
We present a new family of algorithms for learning Fourier-sparse set functions.
In contrast to other work that focused on the Walsh-Hadamard transform, our novel algorithms operate with recently introduced non-orthogonal Fourier transforms.
We demonstrate effectiveness on several real-world applications.
arXiv Detail & Related papers (2020-10-01T14:31:59Z) - Quantum Fourier Analysis [1.776439648597615]
Quantum Fourier analysis is a new subject that combines an algebra with analytic estimates.
This provides interesting tools to investigate phenomena such as quantum symmetry.
We cite several applications of the quantum Fourier analysis in subfactor theory, in category theory, and in quantum information.
arXiv Detail & Related papers (2020-02-10T00:25:53Z)
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.