SIC-POVMs from Stark Units: Dimensions n^2+3=4p, p prime
- URL: http://arxiv.org/abs/2403.02872v1
- Date: Tue, 5 Mar 2024 11:36:33 GMT
- Title: SIC-POVMs from Stark Units: Dimensions n^2+3=4p, p prime
- Authors: Ingemar Bengtsson, Markus Grassl, Gary McConnell
- Abstract summary: We show that a Stark unit from a ray class field extension of a real quadratic field serves as a seed from which the SIC is constructed.
We give solutions for seventeen different dimensions of this form, reaching $d = 39604$.
- Score: 1.7188280334580197
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The existence problem for maximal sets of equiangular lines (or SICs) in
complex Hilbert space of dimension $d$ remains largely open. In a previous
publication (arXiv:2112.05552) we gave a conjectural algorithm for how to
construct a SIC if $d = n^2+3 = p$, a prime number. Perhaps the most surprising
number-theoretical aspect of that algorithm is the appearance of Stark units in
a key role: a single Stark unit from a ray class field extension of a real
quadratic field serves as a seed from which the SIC is constructed. The
algorithm can be modified to apply to all dimensions $d = n^2+3$. Here we focus
on the case when $d= n^2+3 = 4p$, $p$ prime, for two reasons. First, special
measures have to be taken on the Hilbert space side of the problem when the
dimension is even. Second, the degrees of the relevant ray class fields are
`smooth' in a sense that facilitates exact calculations. As a result the
algorithm becomes easier to explain. We give solutions for seventeen different
dimensions of this form, reaching $d = 39604$. Several improvements relative to
our previous publication are reported, but we cannot offer a proof that the
algorithm works for any dimensions where it has not been tested.
Related papers
- A simple and improved algorithm for noisy, convex, zeroth-order optimisation [59.51990161522328]
We construct an algorithm that returns a point $hat xin barmathcal X$ such that $f(hat x)$ is as small as possible.
We prove that this method is such that the $f(hat x) - min_xin barmathcal X f(x)$ is of smaller order than $d2/sqrtn$ up to poly-logarithmic terms.
arXiv Detail & Related papers (2024-06-26T18:19:10Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems.
We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
arXiv Detail & Related papers (2023-02-03T03:19:14Z) - Quasi-Newton Steps for Efficient Online Exp-Concave Optimization [10.492474737007722]
Online Newton Step (ONS) can guarantee a $O(dln T)$ bound on their regret after $T$ rounds.
In this paper, we sidestep generalized projections by using a selfconcordant barrier as a regularizer.
Our final algorithm can be viewed as a more efficient version of ONS.
arXiv Detail & Related papers (2022-11-02T17:57:21Z) - An Efficient Quantum Decoder for Prime-Power Fields [1.0878040851638]
We show that for $q = pm$ where $p$ is small relative to the code block-size $n$, there is a quantum algorithm that solves the problem in time.
On the other hand, classical algorithms can efficiently solve the problem only for much smaller inverse factors.
arXiv Detail & Related papers (2022-10-20T19:35:50Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem.
We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
arXiv Detail & Related papers (2022-04-13T22:18:47Z) - Approximating Output Probabilities of Shallow Quantum Circuits which are
Geometrically-local in any Fixed Dimension [0.0]
We present an algorithm that can compute the quantity $|x|C|0otimes n>|2$ to within any inverse-polynomial additive error in quasi-polynomial time.
This is an extension of the result [CC21], which originally proved this result for $D = 3$.
arXiv Detail & Related papers (2022-02-16T21:37:16Z) - Dimension towers of SICs. II. Some constructions [0.0]
A SIC is a maximal equiangular tight frame in a finite dimensional Hilbert space.
We provide a recipe for how to calculate sets of vectors in dimension $d(d-2)$ that share these properties.
arXiv Detail & Related papers (2022-02-01T17:44:01Z) - The Fine-Grained Hardness of Sparse Linear Regression [12.83354999540079]
We show that there are no better-than-brute-force algorithms for the problem.
We also show the impossibility of better-than-brute-force algorithms when the prediction error is measured.
arXiv Detail & Related papers (2021-06-06T14:19:43Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$.
Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
arXiv Detail & Related papers (2020-12-14T18:14:08Z) - Quantum algorithms for spectral sums [50.045011844765185]
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices.
We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
arXiv Detail & Related papers (2020-11-12T16:29:45Z) - Private Learning of Halfspaces: Simplifying the Construction and
Reducing the Sample Complexity [63.29100726064574]
We present a differentially private learner for halfspaces over a finite grid $G$ in $mathbbRd$ with sample complexity $approx d2.5cdot 2log*|G|$.
The building block for our learner is a new differentially private algorithm for approximately solving the linear feasibility problem.
arXiv Detail & Related papers (2020-04-16T16:12:10Z)
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.