Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSparse Interpolation With Errors in Chebyshev Basis Beyond Redundant-Block Decoding
48
0
0.0
(
0
)
Added by
Zhi-Hong Yang
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present sparse interpolation algorithms for recovering a polynomial with $le B$ terms from $N$ evaluations at distinct values for the variable when $le E$ of the evaluations can be erroneous. Our algorithms perform exact arithmetic in the field of scalars $mathsf{K}$ and the terms can be standard powers of the variable or Chebyshev polynomials, in which case the characteristic of $mathsf{K}$ is $ e 2$. Our algorithms return a list of valid sparse interpolants for the $N$ support points and run in polynomial-time. For standard power basis our algorithms sample at $N = lfloor frac{4}{3} E + 2 rfloor B$ points, which are fewer points than $N = 2(E+1)B - 1$ given by Kaltofen and Pernet in 2014. For Chebyshev basis our algorithms sample at $N = lfloor frac{3}{2} E + 2 rfloor B$ points, which are also fewer than the number of points required by the algorithm given by Arnold and Kaltofen in 2015, which has $N = 74 lfloor frac{E}{13} + 1 rfloor$ for $B = 3$ and $E ge 222$. Our method shows how to correct $2$ errors in a block of $4B$ points for standard basis and how to correct $1$ error in a block of $3B$ points for Chebyshev Basis.
rate research
Read More
To interpolate a supersparse polynomial with integer coefficients, two alternative approaches are the Prony-based big prime technique, which acts over a single large finite field, or the more recently-proposed small primes technique, which reduces the unknown sparse polynomial to many low-degree dense polynomials. While the latter technique has not yet reached the same theoretical efficiency as Prony-based methods, it has an obvious potential for parallelization. We present a heuristic small primes interpolation algorithm and report on a low-level C implementation using FLINT and MPI.
Given a straight-line program whose output is a polynomial function of the inputs, we present a new algorithm to compute a concise representation of that unknown function. Our algorithm can handle any case where the unknown function is a multivariate polynomial, with coefficients in an arbitrary finite field, and with a reasonable number of nonzero terms but possibly very large degree. It is competitive with previously known sparse interpolation algorithms that work over an arbitrary finite field, and provides an improvement when there are a large number of variables.
With the rapid developments in quantum hardware comes a push towards the first practical applications on these devices. While fully fault-tolerant quantum computers may still be years away, one may ask if there exist intermediate forms of error correction or mitigation that might enable practical applications before then. In this work, we consider the idea of post-processing error decoders using existing quantum codes, which are capable of mitigating errors on encoded logical qubits using classical post-processing with no complicated syndrome measurements or additional qubits beyond those used for the logical qubits. This greatly simplifies the experimental exploration of quantum codes on near-term devices, removing the need for locality of syndromes or fast feed-forward, allowing one to study performance aspects of codes on real devices. We provide a general construction equipped with a simple stochastic sampling scheme that does not depend explicitly on a number of terms that we extend to approximate projectors within a subspace. This theory then allows one to generalize to the correction of some logical errors in the code space, correction of some physical unencoded Hamiltonians without engineered symmetries, and corrections derived from approximate symmetries. In this work, we develop the theory of the method and demonstrate it on a simple example with the perfect $[[5,1,3]]$ code, which exhibits a pseudo-threshold of $p approx 0.50$ under a single qubit depolarizing channel applied to all qubits. We also provide a demonstration under the application of a logical operation and performance on an unencoded hydrogen molecule, which exhibits a significant improvement over the entire range of possible errors incurred under a depolarizing channel.
Given a black box function to evaluate an unknown rational polynomial f in Q[x] at points modulo a prime p, we exhibit algorithms to compute the representation of the polynomial in the sparsest shifted power basis. That is, we determine the sparsity t, the shift s (a rational), the exponents 0 <= e1 < e2 < ... < et, and the coefficients c1,...,ct in Q{0} such that f(x) = c1(x-s)^e1+c2(x-s)^e2+...+ct(x-s)^et. The computed sparsity t is absolutely minimal over any shifted power basis. The novelty of our algorithm is that the complexity is polynomial in the (sparse) representation size, and in particular is logarithmic in deg(f). Our method combines previous celebrated results on sparse interpolation and computing sparsest shifts, and provides a way to handle polynomials with extremely high degree which are, in some sense, sparse in information.
In this paper, we give new explicit representations of the Hilbert scheme of $mu$ points in $PP^{r}$ as a projective subvariety of a Grassmanniann variety. This new explicit description of the Hilbert scheme is simpler than the previous ones and global. It involves equations of degree $2$. We show how these equations are deduced from the commutation relations characterizing border bases. Next, we consider infinitesimal perturbations of an input system of equations on this Hilbert scheme and describe its tangent space. We propose an effective criterion to test if it is a flat deformation, that is if the perturbed system remains on the Hilbert scheme of the initial equations. This criterion involves in particular formal reduction with respect to border bases.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
