New classes of reversible cellular automata
- URL: http://arxiv.org/abs/2411.00721v1
- Date: Fri, 01 Nov 2024 16:33:53 GMT
- Title: New classes of reversible cellular automata
- Authors: Jan Kristian Haugland, Tron Omland,
- Abstract summary: A shift-invariant vectorial Boolean function $F$ induces a proper lifting for every $ngeq k$.
We construct new families of such liftings for arbitrary large $k$ and discuss whether all have been identified for $kleq 6$.
- Score: 0.0
- License:
- Abstract: A Boolean function $f$ on $k$~bits induces a shift-invariant vectorial Boolean function $F$ from $n$ bits to $n$ bits for every $n\geq k$. If $F$ is bijective for every $n$, we say that $f$ is a proper lifting, and it is known that proper liftings are exactly those functions that arise as local rules of reversible cellular automata. We construct new families of such liftings for arbitrary large $k$ and discuss whether all have been identified for $k\leq 6$.
Related papers
- Limit formulas for norms of tensor power operators [49.1574468325115]
Given an operator $phi:Xrightarrow Y$ between Banach spaces, we consider its tensor powers.
We show that after taking the $k$th root, the operator norm of $phiotimes k$ converges to the $2$-dominated norm.
arXiv Detail & Related papers (2024-10-30T14:39:21Z) - 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) - IT$^3$: Idempotent Test-Time Training [95.78053599609044]
This paper introduces Idempotent Test-Time Training (IT$3$), a novel approach to addressing the challenge of distribution shift.
IT$3$ is based on the universal property of idempotence.
We demonstrate the versatility of our approach across various tasks, including corrupted image classification.
arXiv Detail & Related papers (2024-10-05T15:39:51Z) - Shift-invariant functions and almost liftings [0.0]
We investigate shift-invariant vectorial Boolean functions on $n$bits that are lifted from Boolean functions on $k$bits, for $kleq n$.
We show that if a Boolean function with diameter $k$ is an almost lifting, the maximum number of collisions of its lifted functions is $2k-1$ for any $n$.
We search for functions in the class of almost liftings that have good cryptographic properties and for which the non-bijectivity does not cause major security weaknesses.
arXiv Detail & Related papers (2024-07-16T17:23:27Z) - Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
We provide a systematic treatment of boundaries based on subgroups $Ksubseteq G$ with the Kitaev quantum double $D(G)$ model in the bulk.
The boundary sites are representations of a $*$-subalgebra $Xisubseteq D(G)$ and we explicate its structure as a strong $*$-quasi-Hopf algebra.
As an application of our treatment, we study patches with boundaries based on $K=G$ horizontally and $K=e$ vertically and show how these could be used in a quantum computer
arXiv Detail & Related papers (2022-08-12T15:05:07Z) - Entanglement Wedges for Gravitating Regions [0.0]
We conjecture that an arbitrary region $a$ can be assigned a generalized entanglement wedge $Esupset a$.
We prove that $E$ satisfies a no-cloning theorem and appropriate forms of strong subadditivity and nesting.
We propose that $E$ quantifies the range of holographic encoding, an important nonlocal feature of quantum gravity, in general spacetimes.
arXiv Detail & Related papers (2022-08-09T18:38:05Z) - Optimal universal quantum circuits for unitary complex conjugation [1.6492989697868894]
This work presents optimal quantum circuits for transforming a number $k$ of calls of $U_d$ into its complex conjugate $barU_d$.
Our circuits admit a parallel implementation and are proven to be optimal for any $k$ and $d$ with an average fidelity of $leftlangleFrightrangle =frack+1d(d-k)$.
arXiv Detail & Related papers (2022-05-31T20:43:29Z) - Agnostic learning with unknown utilities [70.14742836006042]
In many real-world problems, the utility of a decision depends on the underlying context $x$ and decision $y$.
We study this as agnostic learning with unknown utilities.
We show that estimating the utilities of only the sampled points$S$ suffices to learn a decision function which generalizes well.
arXiv Detail & Related papers (2021-04-17T08:22:04Z) - Vector Properties of Entanglement in a Three-Qubit System [0.0]
We show that dynamics of entanglement induced by different two-qubit coupling terms is entirely determined by mutual orientation of vectors $A$, $B$, $C$ which can be controlled by single-qubit transformations.
We illustrate the power of this vector description of entanglement by solving quantum control problems involving transformations between $W$, Greenberg-Horne-Zeilinger ($GHZ$) and biseparable states.
arXiv Detail & Related papers (2020-03-31T17:34:11Z) - On the Modularity of Hypernetworks [103.1147622394852]
We show that for a structured target function, the overall number of trainable parameters in a hypernetwork is smaller by orders of magnitude than the number of trainable parameters of a standard neural network and an embedding method.
arXiv Detail & Related papers (2020-02-23T22:51:52Z)
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.