Results 11 to 20 of about 61 (48)
On the Power of Non-adaptive Learning Graphs [PDF]
, 2016 We introduce a notion of the quantum query complexity of a certificate structure. This is a formalization of a well-known observation that many quantum query algorithms only require the knowledge of the position of possible certificates in the input ...
Belovs, Aleksandrs, Rosmanis, Ansis
core +1 more source
Quantum Algorithms for Learning Symmetric Juntas via the Adversary Bound [PDF]
, 2015 In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function f on n variables that only depends on k variables, and, when restricted to them, equals some predefined function h.
Belovs, Aleksandrs
core +2 more sources
Quantum computation of discrete logarithms in semigroups
Journal of Mathematical Cryptology, 2014 We describe an efficient quantum algorithm for computing discrete logarithms in semigroups using Shor's algorithms for period finding and the discrete logarithm problem as subroutines.
Childs Andrew M., Ivanyos Gábor
doaj +1 more source
Quantum Equivalence of the DLP and CDHP for Group Actions [PDF]
, 2021 International audienceIn this short note we give a polynomial-time quantum reduction from the vectorization problem (DLP) to the parallelization problem (CDHP) for group actions. Combined with the trivial reduction from par-allelization to vectorization,
Galbraith, Steven +3 more
core +1 more source
Constructing elliptic curve isogenies in quantum subexponential time
Journal of Mathematical Cryptology, 2014 Given two ordinary elliptic curves over a finite field having the same cardinality and endomorphism ring, it is known that the curves admit a nonzero isogeny between them, but finding such an isogeny is believed to be computationally difficult.
Childs Andrew +2 more
doaj +1 more source
EXPONENTIAL IMPROVEMENT IN PRECISION FOR SIMULATING SPARSE HAMILTONIANS
Forum of Mathematics, Sigma, 2017 We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods. Specifically, we show that a
DOMINIC W. BERRY +4 more
doaj +1 more source
Quantum speedup for graph sparsification, cut approximation, and Laplacian solving [PDF]
, 2022 Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian. In its strongest form, “spectral sparsification” reduces the number of edges to near-
Apers, S.M.G. (Simon) +1 more
core +1 more source
Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields [PDF]
, 2017 We consider the problem of recovering (that is, interpolating) and identity testing of a “hidden” monic polynomial f, given an oracle access to (Formula presented.) for (Formula presented.), where (Formula presented.) is finite field of q elements ...
Ivanyos, Gábor +4 more
core +4 more sources
A mathematical framework for quantum neural networks [PDF]
, 2023 Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2023, Director: Bruno Juliá-Díaz[en] This thesis focuses on dissipative quantum neural networks, a subfield of quantum machine learning.
Urgell Ollé, Núria
core
Cryptanalysis of the Cryptosystems Based on the Generalized Hidden Discrete Logarithm Problem [PDF]
, 2023 In this paper, we will show the hidden discrete logarithm problem(HDLP) and the generalized form of HDLP(GHDLP) over non-commutative associative algebras (FNAAs) can be reduced to discrete logarithm problem(DLP) in a finite field through analyzing the ...
Ma Yanlong
core