Efficient quantum processing of ideals in finite rings

• URL: http://arxiv.org/abs/0908.0022v2
• Date: Wed, 5 Jul 2023 17:22:01 GMT
• Title: Efficient quantum processing of ideals in finite rings
• Authors: Pawel M. Wocjan, Stephen P. Jordan, Hamed Ahmadi, and Joseph P. Brennan
• Abstract summary: We show how to find an additive basis representation for I in poly(log |R|) time. We then show that our algorithm is a useful primitive allowing quantum computers to rapidly solve a wide variety of problems regarding finite rings.
• Score: 1.1724565818034947
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Suppose we are given black-box access to a finite ring R, and a list of generators for an ideal I in R. We show how to find an additive basis representation for I in poly(log |R|) time. This generalizes a quantum algorithm of Arvind et al. which finds a basis representation for R itself. We then show that our algorithm is a useful primitive allowing quantum computers to rapidly solve a wide variety of problems regarding finite rings. In particular we show how to test whether two ideals are identical, find their intersection, find their quotient, prove whether a given ring element belongs to a given ideal, prove whether a given element is a unit, and if so find its inverse, find the additive and multiplicative identities, compute the order of an ideal, solve linear equations over rings, decide whether an ideal is maximal, find annihilators, and test the injectivity and surjectivity of ring homomorphisms. These problems appear to be hard classically.

Related papers

• Quantum Algorithms for Representation-Theoretic Multiplicities [0.0]
  We give quantum algorithms for computing Kostka, Littlewood-Richardson, Plethysm and Kronecker coefficients. We show that there is an efficient classical algorithm for the Kostka numbers under this restriction and conjecture the existence of an analogous algorithm for the Littlewood-Richardson coefficients. We argue why such classical algorithm does not straightforwardly work for the Plethysm and Kronecker coefficients and conjecture that our quantum algorithms lead to superpolynomial speedups for these problems.
  arXiv  Detail & Related papers  (2024-07-24T21:34:05Z)
• Connecting Kani's Lemma and path-finding in the Bruhat-Tits tree to compute supersingular endomorphism rings [0.0]
  We give a deterministic time algorithm to compute the endomorphism ring of a supersingular elliptic curve in characteristic p. We use techniques of higher-dimensional isogenies to navigate towards the local endomorphism ring.
  arXiv  Detail & Related papers  (2024-02-07T18:10:54Z)
• The supersingular endomorphism ring problem given one endomorphism [5.01069065110753]
  We prove that the endomorphism ring of E can be computed in classical time. We also prove that the action of smooth ideals on elliptic curves can be computed in time.
  arXiv  Detail & Related papers  (2023-09-21T09:22:43Z)
• Embedding Integer Lattices as Ideals into Polynomial Rings [29.240943119083678]
  We study the additional structure of ideal lattices further and find that a given ideal lattice in a ring can be embedded as an ideal into infinitely many different rings by embedding the coefficient. We find a flaw in Ding and Lindner's algorithm that causes some ideal lattices can't be identified by their algorithm.
  arXiv  Detail & Related papers  (2023-07-24T03:06:49Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  We find a generalization-time algorithm that finds the RUM that best approximates the given distribution on average. Our theoretical result can also be made practical: we obtain a that is effective and scales to real-world datasets.
  arXiv  Detail & Related papers  (2023-05-22T17:43:34Z)
• Isotropic Gaussian Processes on Finite Spaces of Graphs [71.26737403006778]
  We propose a principled way to define Gaussian process priors on various sets of unweighted graphs. We go further to consider sets of equivalence classes of unweighted graphs and define the appropriate versions of priors thereon. Inspired by applications in chemistry, we illustrate the proposed techniques on a real molecular property prediction task in the small data regime.
  arXiv  Detail & Related papers  (2022-11-03T10:18:17Z)
• An efficient quantum algorithm for lattice problems achieving subexponential approximation factor [2.3351527694849574]
  We give a quantum algorithm for solving the Bounded Distance Decoding (BDD) problem with a subexponential approximation factor on a class of integer lattices. The running time of the quantum algorithm is for one range of approximation factors and subexponential time for a second range of approximation factors. This view makes for a clean quantum algorithm in terms of finite abelian groups, uses relatively little from lattice theory, and suggests exploring approximation algorithms for lattice problems in parameters other than dimension alone.
  arXiv  Detail & Related papers  (2022-01-31T18:58:33Z)
• Computing the quantum guesswork: a quadratic assignment problem [6.445605125467573]
  Previous approaches to the computation of the guesswork were based on standard semi-definite programming techniques. We show that computing the quantum guesswork of qubit ensembles with uniform probability distribution leads to a more-than-quadratic speedup. As examples, we compute the guesswork of regular and quasi-regular sets of qubit states.
  arXiv  Detail & Related papers  (2021-12-03T01:24:57Z)
• Fuzzy Clustering with Similarity Queries [56.96625809888241]
  The fuzzy or soft objective is a popular generalization of the well-known $k$-means problem. We show that by making few queries, the problem becomes easier to solve.
  arXiv  Detail & Related papers  (2021-06-04T02:32:26Z)
• Subgroup-based Rank-1 Lattice Quasi-Monte Carlo [51.877197074344586]
  We propose a simple closed-form rank-1 lattice construction method based on group theory. Our method achieves superior approximation performance on benchmark integration test problems and kernel approximation problems.
  arXiv  Detail & Related papers  (2020-10-29T03:42:30Z)
• 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)

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.