26838 research outputs found
Sort by
An improved quantum algorithm for 3-tuple lattice sieving
Get PDFThe assumed hardness of the Shortest Vector Problem in high-dimensional lattices is one of the cornerstones of post-quantum cryptography. The fastest known heuristic attacks on SVP are via so-called sieving methods. While these still take exponential time in the dimension , they are significantly faster than non-heuristic approaches and their heuristic assumptions are verified by extensive experiments. -Tuple sieving is an iterative method where each iteration takes as input a large number of lattice vectors of a certain norm, and produces an equal number of lattice vectors of slightly smaller norm, by taking sums and differences of of the input vectors. Iterating these "sieving steps" sufficiently many times produces a short lattice vector. The fastest attacks (both classical and quantum) are for , but taking larger reduces the amount of memory required for the attack. In this paper we improve the quantum time complexity of 3-tuple sieving from to , using a two-level amplitude amplification aided by a preprocessing step that associates the given lattice vectors with nearby "center points" to focus the search on the neighborhoods of these center points. Our algorithm uses classical bits and QCRAM bits, and qubits. This is the fastest known quantum algorithm for SVP when total memory is limited to
The next gap in the subrank of 3-tensors
Get PDFRecent works of Costa–Dalai, Christandl–Gesmundo–Zuiddam, Blatter–Draisma–Rupniewski, and Briët–Christandl–Leigh–Shpilka–Zuiddam have investigated notions of discreteness and gaps in the possible values that asymptotic tensor ranks can take. In particular, it was shown that the asymptotic subrank and asymptotic slice rank of any nonzero 3-tensor is equal to 1, equal to 1.88, or at least 2 (over any field), and that the set of possible values of these parameters is discrete (in several regimes). We determine exactly the next gap, showing that the asymptotic subrank and asymptotic slice rank of any nonzero 3-tensor is equal to 1, equal to 1.88, equal to 2, or at least 2.68
Will it glue? On short-depth designs beyond the unitary group
Get PDFWe study the formation of short-depth designs beyond the unitary group. We provide a range of results on several groups of broad interest in quantum information science: the Clifford group, the orthogonal group, the unitary symplectic groups, and the matchgate group. For all of these groups, we prove that analogues of unitary designs cannot be generated by any circuit ensemble with light-cones that are smaller than the system size. This implies linear lower bounds on the circuit depth in one-dimensional systems. For the Clifford and orthogonal group, we moreover show that a broad class of circuits cannot generate designs in sub-linear depth on any circuit architecture. We show this by exploiting observables in the higher-order commutants of each group, which allow one to distinguish any short-depth circuit from truly random. While these no-go results rule out short-depth unitary designs, we prove that slightly weaker forms of randomness -- including additive-error state designs and anti-concentration in sampling distributions -- nevertheless emerge at logarithmic depths in many cases. Our results reveal that the onset of randomness in shallow quantum circuits is a widespread yet subtle phenomenon, dependent on the interplay between the group itself and the context of its application
Rethinking dataset discovery with DataScout
No full textDataset Search—the process of finding appropriate datasets for a given task—remains a critical yet under-explored challenge in data science workflows. Assessing dataset suitability for a task (e.g., training a classification model) is a multi-pronged affair that involves understanding: data characteristics (e.g. granularity, attributes, size), semantics (e.g., data semantics, creation goals), and relevance to the task at hand. Present-day dataset search interfaces are restrictive—users struggle to convey implicit preferences and lack visibility into the search space and result inclusion criteria—making query iteration challenging. To bridge these gaps, we introduce DataScout to proactively steer users through the process of dataset discovery via—(i) AI-assisted query reformulations informed by the underlying search space, (ii) semantic search and filtering based on dataset content, including attributes (columns) and granularity (rows), and (iii) dataset relevance indicators, generated dynamically based on the user-specified task. A within-subjects study with 12 participants comparing DataScout to keyword and semantic dataset search reveals that users uniquely employ DataScout’s features not only for structured explorations, but also to glean feedback on their search queries and build conceptual models of the search space
Challenges and opportunities of Table Representation Learning (Dagstuhl Seminar 25182)
No full textThe growing volume and importance of structured data have sparked increasing interest in Table Representation Learning (TRL), an emerging field that leverages neural models to learn abstract, general-purpose representations for tabular data to support a wide range of downstream tasks such as tabular prediction, table question answering, tabular data cleaning, and many more. This seminar gathered the different communities (ML, NLP, IR, DB) who work on this topic to discuss the challenges & long-term vision of this field.
From the organizers: Carsten Binnig, Julian Eisenschlos, Madelon Hulsebos, Frank Hutter
Governing fields for hyperelliptic function fields
Get PDFWe study the 8-rank of class groups of hyperelliptic function fields and show that such 8-ranks are governed by splitting conditions in so-called governing fields. A similar result was proven for quadratic number fields by Stevenhagen, who used a theory of Rédei symbols and Rédei reciprocity to do so. We introduce a version of the Rédei reciprocity law for function fields and use this to show existence of governing fields
Fast assessment of Eulerian trails in graphs with applications
Get PDFEnumerating or counting combinatorial objects in graphs is a fundamental data mining task. We consider the problem of assessing the number of Eulerian trails in directed graphs, which is formalized as follows: Given a directed graph G = (V, E), with |V| = n nodes and |E| = m edges, and an integer z, assess whether the number #ET(G) of Eulerian trails of G is at least z. This problem underlies many applications in domains ranging from data privacy to computational biology, data compression, and transportation networks. Practitioners currently address this problem by applying the famous BEST theorem, which, in fact, counts #ET(G) instead of just assessing whether #ET(G) ≥ z. Unfortunately, this solution takes O(nω) arithmetic operations, where ω < 2.373 denotes the matrix multiplication exponent. Since in most real-world graphs, the number m of edges is comparable to the number n of nodes, and z is moderate in practice, the algorithmic challenge is: Can we solve the problem faster for certain values ofm andz? We want to design a combinatorial algorithm for assessing whether #ET(G) ≥ z, which does not resort to the BEST theorem and has a predictably bounded cost as a function of m and z. We address this challenge as follows. We first introduce a general algorithmic scheme for assessing (and enumerating) Eulerian trails. We then introduce a novel tree data structure to reduce the number of iterations in this general scheme. Finally, we complement the above with further combinatorial insight leading to an algorithm with a worst-case bound of O(m · min{z, #ET(G)}) time. Our experiments using six benchmark datasets with multi-million edges from different domains show that our implementations are up to two orders of magnitude faster than the BEST theorem, perform much fewer than mz iterations and scale near-linearly with m in most cases. Our experiments further show that our implementations bring substantial efficiency benefits in a data privacy application which employs the BEST theorem for the assessment
