Search

The Learning-With-Errors (LWE) problem is a crucial computational challenge with significant implications for post-quantum cryptography and computational learning theory. Here we propose a quantum-classical hybrid algorithm with Ising model (HAWI) to address the LWE problem. Our approach involves transforming the LWE problem into the Shortest Vector Problem (SVP), using variable qubits to encode lattice vectors into an Ising Hamiltonian. We then identify the low-energy levels of the Hamiltonian to extract the solution, making it suitable for implementation on current noisy intermediate-scale quantum (NISQ) devices. We prove that the number of qubits required is less than $m(3m-1)/2$, where $m$ is the number of samples in the algorithm. Our algorithm is heuristic, and its time complexity depends on the specific quantum algorithm employed to find the Hamiltonian's low-energy levels. If the Quantum Approximate Optimization Algorithm (QAOA) is used to solve the Ising Hamiltonian problem, and the number of iterations satisfies $y < O\left(m\log m\cdot 2^{0.2972k}/pk^2\right)$, our algorithm will outperform the classical Block Korkine-Zolotarev (BKZ) algorithm, where $k$ is the block size related to problem parameters, and $p$ is the number of layers in QAOA. We demonstrate the algorithm by solving a $2$-dimensional LWE problem on a real quantum device with $5$ qubits, showing its potential for solving meaningful instances of the LWE problem in the NISQ era.

Current multimodal large language models (MLLMs) face significant challenges in visual document understanding (VDU) tasks due to the high resolution, dense text, and complex layouts typical of document images. These characteristics demand a high level of detail perception ability from MLLMs. While increasing input resolution improves detail perception capability, it also leads to longer sequences of visual tokens, increasing computational costs and straining the models' ability to handle long contexts. To address these challenges, we introduce DocKylin, a document-centric MLLM that performs visual content slimming at both the pixel and token levels, thereby reducing token sequence length in VDU scenarios. We introduce an Adaptive Pixel Slimming (APS) preprocessing module to perform pixel-level slimming, increasing the proportion of informative pixels. Moreover, we propose a novel Dynamic Token Slimming (DTS) module to conduct token-level slimming, filtering essential tokens and removing others to adaptively create a more compact visual sequence. Experiments demonstrate DocKylin's promising performance across various VDU benchmarks and the effectiveness of each component.

For an abstract elementary class $\mathbf{K}$ and a cardinal $\lambda \geq LS(\mathbf{K})$, we prove under mild cardinal arithmetic assumptions, categoricity in two succesive cardinals, almost stability for $\lambda^+$-minimal types and continuity of splitting in $\lambda$, that stability in $\lambda$ is equivalent to the existence of a model in $\lambda^{++}$. The forward direction holds without any cardinal or categoricity assumptions, this result improves both [Vas18b, 12.1] and [MaYa24, 3.14]. Moreover, we prove a categoricity theorem for abstract elementary classes with weak amalgamation and tameness under mild structural assumptions in $\lambda$. A key feature of this result is that we do not assume amalgamation or arbitrarily large models.

There are many results in the literature where superstablity-like independence notions, without any categoricity assumptions, have been used to show the existence of larger models. In this paper we show that \emph{stability} is enough to construct larger models for small cardinals assuming a mild locality condition for Galois types. $\mathbf{Theorem.}$ Suppose $\lambda<2^{\aleph_0}$. Let $\mathbf{K}$ be an abstract elementary class with $\lambda \geq LS(\mathbf{K})$. Assume $\mathbf{K}$ has amalgamation in $\lambda$, no maximal model in $\lambda$, and is stable in $\lambda$. If $\mathbf{K}$ is $(<\lambda^+, \lambda)$-local, then $\mathbf{K}$ has a model of cardinality $\lambda^{++}$. The set theoretic assumption that $\lambda<2^{\aleph_0}$ and model theoretic assumption of stability in $\lambda$ can be weakened to the model theoretic assumptions that $|\mathbf{S}^{na}(M)|< 2^{\aleph_0}$ for every $M \in \mathbf{K}_\lambda$ and stability for $\lambda$-algebraic types in $\lambda$. This is a significant improvement of Theorem 0.1., as the result holds on some unstable abstract elementary classes.

Fine-tuning pre-trained Vision Transformers (ViTs) has showcased significant promise in enhancing visual recognition tasks. Yet, the demand for individualized and comprehensive fine-tuning processes for each task entails substantial computational and memory costs, posing a considerable challenge. Recent advancements in Parameter-Efficient Transfer Learning (PETL) have shown potential for achieving high performance with fewer parameter updates compared to full fine-tuning. However, their effectiveness is primarily observed in simple tasks like image classification, while they encounter challenges with more complex vision tasks like dense prediction. To address this gap, this study aims to identify an effective tuning method that caters to a wider range of visual tasks. In this paper, we introduce Hierarchical Side-Tuning (HST), an innovative PETL method facilitating the transfer of ViT models to diverse downstream tasks. Diverging from existing methods that focus solely on fine-tuning parameters within specific input spaces or modules, HST employs a lightweight Hierarchical Side Network (HSN). This network leverages intermediate activations from the ViT backbone to model multi-scale features, enhancing prediction capabilities. To evaluate HST, we conducted comprehensive experiments across a range of visual tasks, including classification, object detection, instance segmentation, and semantic segmentation. Remarkably, HST achieved state-of-the-art performance in 13 out of the 19 tasks on the VTAB-1K benchmark, with the highest average Top-1 accuracy of 76.1%, while fine-tuning a mere 0.78M parameters. When applied to object detection and semantic segmentation tasks on the COCO and ADE20K testdev benchmarks, HST outperformed existing PETL methods and even surpassed full fine-tuning., Comment: 10 pages, 8 figures

Revealing the energy and spatial characteristics of impurity induced states in superconductors is essential for understanding their mechanism and fabricating new quantum state by manipulating impurities. Here by using high-resolution scanning tunneling microscopy/spectroscopy, we investigated the spatial distribution and magnetic field response of the impurity states in (Li1-xFex)OHFeSe. We detected two pairs of strong in-gap states on the "dumbbell" shaped defects. They display clear damped oscillations with different phase shifts and a direct phase-energy correlation. These features have long been predicted for classical Yu-Shiba-Rusinov (YSR) state, which are demonstrated here with unprecedented resolution for the first time. Moreover, upon applying magnetic field, all the in-gap state peaks remarkably split into two rather than shift, and the splitting strength is field orientation dependent. Via detailed numerical model calculations, we found such anisotropic splitting behavior can be naturally induced by a high-spin impurity coupled to anisotropic environment, highlighting how magnetic anisotropy affects the behavior of YSR states., Comment: Main text with supplementary (accepted by Phys. Rev. Lett.)

This paper is a contribution to "neo-stability" type of result for abstract elementary classes. Under certain set theoretic assumptions, we propose a definition and a characterization of NIP in AECs. The class of AECs with NIP properly contains the class of stable AECs. We show that for an AEC $K$ and $\lambda\geq LS(K)$, $K_\lambda$ is NIP if and only if there is a notion of nonforking on it which we call a w*-good frame. On the other hand, the negation of NIP leads to being able to encode subsets.

State-of-the-art parallel sorting algorithms for distributed-memory architectures are based on computing a balanced partitioning via sampling and histogramming. By finding samples that partition the sorted keys into evenly-sized chunks, these algorithms minimize the number of communication rounds required. Histogramming (computing positions of samples) guides sampling, enabling a decrease in the overall number of samples collected. We derive lower and upper bounds on the number of sampling/histogramming rounds required to compute a balanced partitioning. We improve on prior results to demonstrate that when using $p$ processors, $O(\log^* p)$ rounds with $O(p/\log^* p)$ samples per round suffice. We match that with a lower bound that shows that any algorithm with $O(p)$ samples per round requires at least $\Omega(\log^* p)$ rounds. Additionally, we prove the $\Omega(p \log p)$ samples lower bound for one round, thus proving that existing one round algorithms: sample sort, AMS sort and HSS have optimal sample size complexity. To derive the lower bound, we propose a hard randomized input distribution and apply classical results from the distribution theory of runs., Comment: 12 pages

Recently, monolayer CoSb/SrTiO$_3$ has been proposed as a candidate harboring interfacial superconductivity in analogy with monolayer FeSe/SrTiO$_3$. Experimentally, while the CoSb-based compounds manifesting as nanowires and thin films have been realized on SrTiO$_3$ substrates, serving as a rich playground, their electronic structures are still unknown and yet to be resolved. Here, we have fabricated CoSb$_{1-x}$ nanoribbons with quasi-one-dimensional stripes on SrTiO$_3$(001) substrates using molecular beam epitaxy, and investigated the electronic structure by in situ angle-resolved photoemission spectroscopy. Straight Fermi surfaces without lateral dispersions are observed. CoSb$_{1-x}$/SrTiO$_3$ is slightly hole doped, where the interfacial charge transfer is opposite to that in monolayer FeSe/SrTiO$_3$. The spectral weight near Fermi level exhibits power-law-like suppression and obeys a universal temperature scaling, serving as the signature of Tomonaga-Luttinger liquid (TLL) state. The obtained TLL parameter of $\sim$0.21 shows the underlying strong correlations. Our results not only suggest CoSb$_{1-x}$ nanoribbon as a representative TLL system, but also provide clues for further investigations on the CoSb-related interface., Comment: 27 pages, 3 figures