A quantum algorithm for computing the unit group of an arbitrary degree number field
From MaRDI portal
Publication:5259563
DOI10.1145/2591796.2591860zbMath1315.68134OpenAlexW2060301675MaRDI QIDQ5259563
Fang Song, Sean Hallgren, Kirsten Eisenträger, Alexei Yu. Kitaev
Publication date: 26 June 2015
Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://authors.library.caltech.edu/70983/
Number-theoretic algorithms; complexity (11Y16) Algebraic number theory computations (11Y40) Quantum algorithms and complexity in the theory of computing (68Q12)
Related Items
Computation of lattice isomorphisms and the integral matrix similarity problem, Improved reversible and quantum circuits for Karatsuba-based integer multiplication., Quantum algorithms for variants of average-case lattice problems via filtering, Sample complexity of hidden subgroup problem, NTRU Fatigue: How Stretched is Overstretched?, Digital Signatures Based on the Hardness of Ideal Lattice Problems in All Rings, Log-\(\mathcal{S}\)-unit lattices using explicit Stickelberger generators to solve approx ideal-SVP, Quantum algorithm based on the \(\varepsilon\)-random linear disequations for the continuous hidden shift problem, SICs and algebraic number theory, The special case of cyclotomic fields in quantum algorithms for unit groups, Twisted-PHS: using the product formula to solve approx-SVP in ideal lattices, Approximate short vectors in ideal lattices of \(\mathbb{Q}(\zeta_{p^e})\) with precomputation of \({\mathrm {Cl}}(\mathcal{O}_K)\), Short Stickelberger Class Relations and Application to Ideal-SVP, On the quantum attacks against schemes relying on the hardness of finding a short generator of an ideal in \(\mathbb{Q}(\zeta_{2^s})\), Short principal ideal problem in multicubic fields, Quantum-access-secure message authentication via blind-unforgeability, On the ideal shortest vector problem over random rational primes, A Subfield Lattice Attack on Overstretched NTRU Assumptions, Random self-reducibility of ideal-SVP via Arakelov random walks, Deterministic algorithms for the hidden subgroup problem, On the quantum complexity of the continuous hidden subgroup problem
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Efficient algorithms for privately releasing marginals via convex relaxations
- The Geometry of Differential Privacy: The Small Database and Approximate Cases
- Faster Algorithms for Privately Releasing Marginals
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- Privately Releasing Conjunctions and the Statistical Query Barrier
- On the geometry of differential privacy
- Interactive privacy via the median mechanism
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Lower Bounds in Differential Privacy
- Iterative Constructions and Private Data Release
- Characterizing the sample complexity of private learners
- Faster private release of marginals on small databases
- Bounds on the Sample Complexity for Private Learning and Private Data Release
- Differential Privacy and the Fat-Shattering Dimension of Linear Queries
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- Collusion-secure fingerprinting for digital data
- On the complexity of differentially private data release
- Advances in Cryptology – CRYPTO 2004
- Answering n {2+o(1)} counting queries with differential privacy is hard
- Theory of Cryptography