Rotation-Optimal Noncommutative Prefix Scans in Bit-Reversed Homomorphic Layouts

• URL: http://arxiv.org/abs/2607.03631v1
• Date: Fri, 03 Jul 2026 23:14:45 GMT
• Title: Rotation-Optimal Noncommutative Prefix Scans in Bit-Reversed Homomorphic Layouts
• Abstract summary: We study ordered prefix computation on $n=2m$ elements of an associative, possibly noncommutative monoid stored in bit-reversed order.<n>A direct transported-predecessor scan uses $mcdot(m+1)/2$ rotations because one logical shift decomposes into several cyclic displacement classes.<n>We instantiate the exclusive scan for radix carry and borrow in bit-reversed CKKS slots, avoiding layout restoration and the final logical-predecessor shift.
• Score: 1.0732935873226024
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Packed homomorphic encryption evaluates slotwise operations in parallel, but nonlocal communication is realized by cyclic rotations whose cost depends on the physical slot layout. We study ordered prefix computation on $n=2^m$ elements of an associative, possibly noncommutative monoid stored in bit-reversed order. A direct transported-predecessor scan uses $m\cdot(m+1)/2$ rotations because one logical shift decomposes into several cyclic displacement classes. We introduce a replicated-aggregate invariant: every slot of an aligned logical block stores the same complete block aggregate. Since these copies are semantically interchangeable, one global rotation per level supplies each slot with a valid sibling aggregate, without reaching the exact logical partner. The resulting inclusive or exclusive scan uses $m$ rotations, depth $m$, two live state vectors, and at most $2\cdot m-1$ packed monoid compositions. In a model where all non-routing operations are slotwise and every cyclic rotation invocation is counted, these bounds are exact: $D^\star(m)=R^\star(m)=m$. Equality is rigid: the $m$ offsets contain exactly one representative of each $2$-adic valuation. With at most $K$ directly keyed offsets, we prove a product lower bound and an exact frontier $K\cdot(2^{m/K}-1)$ whenever $K$ divides $m$. We instantiate the exclusive scan for radix carry and borrow in bit-reversed \CKKS slots, avoiding layout restoration and the final logical-predecessor shift. In our implementation at $m=7$, the replicated scan reduces the direct bit-reversed baseline from $28$ to $7$ rotations, lowers evaluation-key storage by $70.0\%$, lowers peak heap usage by $63.9\%$, and improves isolated scan latency by $19.9\%$. In a depth-$5$ downstream pipeline, retaining six additional modulus levels avoids one bootstrap and gives a mean paired speedup of $4.31\times$ with $95\%$ confidence interval $[3.69,4.92]$.

Related papers

• Ordered-Angle Coding for Exact Multiuser Unanimity Testing [0.0]
  We introduce ordered-angle coding for binary-unanimity testing among $n$ transformation-only users in a serial quantum architecture.<n>Bell entanglement is not required for the additive algebra, but it keeps the traveler locally maximally mixed in every honest trial.
  arXiv  Detail & Related papers  (2026-09-04T18:28:01Z)
• Sharp Minimax Regret for Infinite-Memory Logistic Prediction [55.29259818039367]
  Lag $j$ can affect prediction by scale $r_j$ and enters only $n_T,j=T-j+1$ prediction rounds.<n>For every summable envelope, a localized mixture proves $cR_T(r)leq C_T(r)$.<n>For exponential and envelopes, under the stated finite-sample condition, a Toeplitz-design converse proves $cR_T(r)geq c_T(r)$.
  arXiv  Detail & Related papers  (2026-08-27T01:31:46Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• Incremental Sheaf Cohomology on Cellular Complexes: O(1)-in-n Lazy Edit Processing under Bounded Local Geometry [0.0]
  algorithmic framework for incremental maintenance of first sheaf cohomology $H1(X; mathcalF)$ on dynamically evolving 1-dimensional cellular complexes equipped with finite-dimensional cellular sheaves.
  arXiv  Detail & Related papers  (2026-06-02T21:26:02Z)
• Asymmetric Linear-Combination-of-Unitaries Realization of Quantum Convolution via Modular Adders [1.8228930355273179]
  Circular convolution over $mathbbZ/NmathbbZ$ can be implemented on quantum hardware within the linear-combination-of-unitaries (LCU) framework.<n>We introduce a reversal matrix $J_n=Xotimes n$ and define reflected shifts $widetildeL_i,n=L_i,nJ_n$.<n>The resulting symmetrized operator differs from circular convolution only by one known input-side $J_n$ layer.
  arXiv  Detail & Related papers  (2026-03-16T12:52:05Z)
• Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
  We show that the Rényi tripartite information $I_3() exhibits a qualitatively $exclusion-dependent scaling at small Fermi momentum.<n>A direct consequence is a replica obstruction: $I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal cannot be reconstructed from integer Rényi data.
  arXiv  Detail & Related papers  (2026-03-09T22:27:00Z)
• Exact Coset Sampling for Quantum Lattice Algorithms [9.910562011343009]
  We give a simple replacement for the contested "domain-extension" in Step 9 of a recent windowed-QFT lattice algorithm with complex-Gaussian windows.<n>Our new subroutine replaces domain extension by a pair-shift difference that cancels unknown offsets exactly.
  arXiv  Detail & Related papers  (2025-09-15T18:10:28Z)
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  We study first-order methods for convex optimization problems with functions $f$ satisfying the recently proposed $ell$-smoothness condition $||nabla2f(x)|| le ellleft(||nabla f(x)||right),$ which generalizes the $L$-smoothness and $(L_0,L_1)$-smoothness.
  arXiv  Detail & Related papers  (2025-08-09T08:28:06Z)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  We consider a centralized distributed learning setup where all workers jointly find an unbiased bound LDeltaepsilon2,$ better poly-logarithmically in $n$, even in the homogeneous (i.i.d.) case, where all workers access the same distribution.
  arXiv  Detail & Related papers  (2025-06-30T13:27:39Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
  arXiv  Detail & Related papers  (2024-10-07T19:47:13Z)
• Low Depth Phase Oracle Using a Parallel Piecewise Circuit [3.629687485125086]
  We explore the important task of applying a phase $exp(i,f(x))$ to a computational basis state $left| x right>$.<n>The closely related task of rotating a target qubit by an angle depending on $f(x)$ is also studied.<n>We find that strategies prioritising execution speed can achieve circuit depth as low as $O(logn+logS)$ for a register of $n$ qubits and a piecewise approximation of $S$ sections.
  arXiv  Detail & Related papers  (2024-09-06T19:57:13Z)
• Efficient, direct compilation of SU(N) operations into SNAP & Displacement gates [0.0]
  Map $Phi$ gives us the ability to compile directly any $d$-dimensional unitary into a sequence of SNAP and displacement gates. We find numerically that the error on compiled circuits can be made arbitrarily small by breaking each rotation into $m$ $theta/m$ rotations.
  arXiv  Detail & Related papers  (2023-07-21T20:58:17Z)
• Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions [51.19236668224547]
  We study low rank approximation of tensors, focusing on the tensor train and Tucker decompositions. For tensor train decomposition, we give a bicriteria $(1 + eps)$-approximation algorithm with a small bicriteria rank and $O(q cdot nnz(A))$ running time. In addition, we extend our algorithm to tensor networks with arbitrary graphs.
  arXiv  Detail & Related papers  (2022-07-15T11:55:09Z)
• Deep Learning Meets Projective Clustering [66.726500395069]
  A common approach for compressing NLP networks is to encode the embedding layer as a matrix $AinmathbbRntimes d$. Inspired by emphprojective clustering from computational geometry, we suggest replacing this subspace by a set of $k$ subspaces.
  arXiv  Detail & Related papers  (2020-10-08T22:47:48Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  We study the setup where each of $n$ users holds an element from a discrete set. The goal is to count the number of distinct elements across all users.
  arXiv  Detail & Related papers  (2020-09-21T04:13:34Z)

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.