Categorical computation

Abstract

In quantum computing, the computation is achieved by linear operators in or between Hilbert spaces. In this work, we explore a new computation scheme, in which the linear operators in quantum computing are replaced by (higher) functors between two (higher) categories. If from Turing computing to quantum computing is the first quantization of computation, then this new scheme can be viewed as the second quantization of computation. The fundamental problem in realizing this idea is how to realize a (higher) functor physically. We provide a theoretical idea of realizing (higher) functors physically based on the physics of topological orders.

Graphical abstract

Keywords

quantum computation / categorical computation / topological order

1 Classical and quantum computation

Classical computation or Turing computation can be summarized mathematically as the computation of functions between sets. More precisely, for any positive integers $n$, and

$\text{a function}f:\{0,1{\}}^n\to \{0,1{\}}^n,$

we design a finite set of gates $S$, each of which is also a function between two sets, such that $f$ can be realized by a circuit constructed from the gates in $S$. The classical computer is physically possible because we can realize or simulate a function between two sets physically through a circuit consisting of a family of more elementary physically realizable functions (i.e., gates).

The quantum computation can be summarized mathematically as the computation of linear maps (or linear operators). More precisely, for any positive integers $n$, and

$\text{a linear map}F:({\mathbb{C}}^2{)}^{\otimes n}\to ({\mathbb{C}}^2{)}^{\otimes n},$

we design a finite set of gates, each of which is also a linear map between two finite dimensional Hilbert spaces, such that $F$ can be physically realized by a quantum circuit of gates. A quantum computer is physically possible because we can physically realize linear operators in Hilbert spaces. A quantum computation is a physical way of realizing parallel computation via quantum mechanics. The idea is to replace the bit $\{0,1\}$ by a qubit ${\mathbb{C}}^2$, which can be viewed as a linear span of two states $|0⟩$ and $|1⟩$. Different from $\{0,1\}$, the states in a qubit are much more than $|0⟩$ and $|1⟩$. A generic state $|a⟩$ is a superposition of them, i.e.,

$|a⟩=a_0|0⟩+a_1|1⟩=(\begin{array}{c}{a}_0\\ a_1\end{array}),\mathrm{\forall }{a}_1,a_2\in \mathbb{C}.$

It means that $|a⟩$ can be in either the state $|0⟩$ or the state $|1⟩$ with potentially non-trivial probabilities. Using $|0⟩$ and $|1⟩$, a linear map $F:{\mathbb{C}}^2\to {\mathbb{C}}^2$ can be expressed as a matrix.

$\begin{array}{rl}& F:(\begin{array}{c}{a}_0\\ a_1\end{array})\mapsto (\begin{array}{cc}{F}_{00}& F_{01}\\ F_{10}& F_{11}\end{array})(\begin{array}{c}{a}_0\\ a_1\end{array})\\ & =(\begin{array}{c}{F}_{00}{a}_0+F_{01}{a}_1\\ F_{10}{a}_0+F_{11}{a}_1\end{array}).\end{array}$

This linear operator $F$ that realizes the parallel computation of both $F(|0⟩)$ and $F(|1⟩)$ at the same time can be viewed as a probabilistic circuit (or quantum circuit), which can be simulated by a family of more elementary linear operators called quantum gates.

2 The idea of categorification

The idea of categorification was originated from the second quantization in physics. Second quantization has a long history. It is a way to obtain higher dimensional quantum field theories (QFT) from quantum mechanics, which can also be viewed as a 0+1D (spacetime dimension) QFT. In the early 90’s of the 20th century, Crain and Frenkel introduced the idea of categorification aiming at constructing higher dimensional QFTs [1]. Roughly speaking, the categorification can be viewed as a mathematical formulation of the second quantization. The process of categorification lifts lower categorical structures to higher categorical structures. The idea of categorification that we need in this work is rather simple and can be summarized by the following diagram:

Scheme1

Full size|PPT slide

where we use “c” to represent the process of categorification.

Remark 2.0.1. The reversed process is called de-categorification and can be realized by computing a generalized notion of “dimension” also called $K_0$-group in mathematics (see [2] for a recent review). For example, the $K_0$-group of a 2-category is a 1-category, that of a 1-category is a vector space, and that of a vector space is its dimension (i.e., a number).　　　　　　　　　　　　　　　　　♢

Therefore, we see that if we categorify the usual quantum computation, we should obtain the computation of $n$-functors between $n$-categories. This new computation can be called a second quantized computation or a categorified quantum computation, or perhaps, even better an $n$-categorical computation.

Now we explain why a 1-categorical computation can be viewed as a parallel quantum computation. We recall the definition of a $1$-category. For the convenience of physical applications, 1-categories and 1-functors are all assumed to be $\mathbb{C}$-linear.

Definition 2.0.2. A 1-category $\mathcal{C}$ consists of

1) a set of objects $\text{Ob}(\mathcal{C})=\{a,b,c,\cdots \}$; (We often use $a,b,c\in \mathcal{C}$ for simplicity.)

2) a vector space ${\mathrm{hom}}_{\mathcal{C}}(a,b)$ over $\mathbb{C}$ for each orders pair $(a,b)$ and $a,b\in \mathcal{C}$; (a vector $f\in {\mathrm{hom}}_{\mathcal{C}}(a,b)$ is called a morphism from $a$ to $b$ and is often denoted by $a\stackrel{f}{\to }b$ or $f:a\to b$).

3) a distinguished vector $1_a\in {\mathrm{hom}}_{\mathcal{C}}(a,a)$;

4) a $\mathbb{C}$-linear composition map $\circ$ for $a,b,c\in \mathcal{C}$:

$\begin{array}{rl}{\mathrm{h}\mathrm{o}\mathrm{m}}_{\mathcal{C}}(b,c){\otimes }_{\mathbb{C}}{\mathrm{h}\mathrm{o}\mathrm{m}}_{\mathcal{C}}(a,b)& \stackrel{\circ }{\to }{\mathrm{h}\mathrm{o}\mathrm{m}}_{\mathcal{C}}(a,c)\\ g{\otimes }_{\mathbb{C}}f& \mapsto g\circ f;\end{array}$

satisfying the following conditions:

1) $(h\circ g)\circ f=h\circ (g\circ f)$ for all $a\stackrel{f}{\to }b\stackrel{g}{\to }c\stackrel{h}{\to }d$;

2) $f\circ 1_a=f$ and $1_b\circ f=f$ for all $f:a\to b$.　　　　　■

If readers encounter the notion of a category for the first time, it is useful to keep in mind the following picture of the basic structures in a category.

$\begin{array}{}\text{(2.0.1)}& \begin{array}{c}\text{includegraphics}[width=0.3\text{paperwidth}]fop-21251-kongliang-Scheme2.jpg\end{array}\end{array}$

Example 2.0.3. We provide three most useful examples of 1-categories.

1) $\text{Vec}$ is the 1-category of finite dimensional vector spaces over $\mathbb{C}$. Its objects $a,b,c,\cdots$ are finite dimensional vector spaces, and ${\mathrm{hom}}_{\text{Vec}}(a,b)$ are precisely the space of all the linear maps from $a$ to $b$. The composition maps are the usual composition of linear maps, and the identity morphism $1_a:a\to a$ is the identity linear map.

2) $\text{Rep}(G)$ is the 1-category of finite dimensional representations of a finite group $G$. More precisely, its objects are finite dimensional representations of $G$ and 1-morphisms are linear maps that intertwine the $G$-actions. The compositions and the identity morphisms are the same as those in $\text{Vec}$.

3) ${\text{Vec}}_G$ is the 1-category of finite dimensional $G$-graded vector spaces for a finite group $G$. As a $\mathbb{C}$-linear 1-category, it is a direct sum of $|G|$-copies of $\text{Vec}$, i.e., ${\text{Vec}}_G={\oplus }_{g\in G}{\text{Vec}}_g$.

Remark 2.0.4. An $n$-category $\mathcal{C}$ can be described by the same diagram in (2.0.1) except that the hom space ${\mathrm{hom}}_{\mathcal{C}}(a,b)$ now becomes an $(n-1)$-category and the composition map $\circ$ now becomes an $(n-1)$-functor (see Remark 2.0.8).　　　　　　　　　　　　　　　　　　♢

Definition 2.0.5. A 1-functor $\mathcal{F}:\mathcal{C}\to \mathcal{D}$ between two 1-categories consists of

1) a map $\mathcal{F}:\text{Ob}(\mathcal{C})\to \text{Ob}(\mathcal{D})$ (we slightly abuse the notation here);

2) a linear map ${\mathcal{F}}_{a,b}:{\mathrm{hom}}_{\mathcal{C}}(a,b)\to {\mathrm{hom}}_{\mathcal{D}}(\mathcal{F}(a),\mathcal{F}(b))$ for all $a,b\in \mathcal{C}$;

satisfying the following conditions:

1) ${\mathcal{F}}_{a,a}(1_a)=1_{\mathcal{F}(a)}$, for all $a\in \mathcal{C}$;

2) ${\mathcal{F}}_{b,c}(g)\circ {\mathcal{F}}_{a,b}(f)={\mathcal{F}}_{a,c}(g\circ f)$ for all $f\in {\mathrm{hom}}_{\mathcal{C}}(a,b),$ $g\in {\mathrm{hom}}_{\mathcal{C}}(b,c)$.　　　　　　　　　　　　　　　　■

We provide an intuitive picture of such a 1-functor $\mathcal{F}$ by the following diagram: $\mathrm{\forall }a,b,c\in \mathcal{C}$,

$\begin{array}{}\text{(2.0.2)}& \begin{array}{c}\text{includegraphics}[width=0.38\text{paperwidth}]fop-21251-kongliang-Scheme3.jpg\end{array}\end{array}$

Then one can see immediately that if we can physically realize the 1-functor $\mathcal{F}$, it automatically realizes all linear maps ${\mathcal{F}}_{a,b}$ for all $a,b\in \mathcal{C}$ at the same time. In this sense, a 1-functor can be viewed as a parallel quantum computing.

Example 2.0.6. For a given vector space $V\in \text{Vec}$, we can define two 1-functors as follows:

1) $-\otimes V:\text{Vec}\to \text{Vec}$ by $a\mapsto a\otimes V$ for an object $a\in \text{Vec}$ and by $(a\stackrel{f}{\to }b)\mapsto (a\otimes V\stackrel{f\otimes 1_V}{\to }b\otimes V)$ for a morphism $f$.

2) $-\oplus V:\text{Vec}\to \text{Vec}$ by $a\mapsto a\oplus V$ for an object $a\in \text{Vec}$ and by $(a\stackrel{f}{\to }b)\mapsto (a\oplus V\stackrel{f\oplus 1_V}{\to }b\oplus V)$ for a morphism $f$.　　　　　　　　　　　　　　　　♦

Remark 2.0.7. A natural transformation $\varphi :\mathcal{F}\to \mathcal{G}$ between two 1-functors $\mathcal{F},\mathcal{G}:\mathcal{C}\to \mathcal{D}$ is a family of morphisms $\{{\varphi }_a:\mathcal{F}(a)\to \mathcal{G}(a){\}}_{a\in \mathcal{C}}$ such that ${\varphi }_b\circ \mathcal{F}(f)=$ $\mathcal{G}(f)\circ {\varphi }_a$ for all morphism $f\in {\mathrm{hom}}_{\mathcal{C}}(a,b)$. All 1-categories (as objects), 1-functors (as 1-morphisms) and natural transformations (as 2-morphisms) form a 2-category denoted by $\mathsf{C}\mathsf{A}\mathsf{T}$.　　　　　　　　　　　　　　　　　♢

Remark 2.0.8. An $n$-functor between two $n$-categories $\mathcal{F}:\mathcal{C}\to \mathcal{D}$ can be illustrated by the same diagram (2.0.2) except that ${\mathrm{hom}}_{\mathcal{C}}(a,b)$ is now an $(n-1)$-category and ${\mathcal{F}}_{a,b}$ is now an $(n-1)$-functor. Then one can see that an $n$-functor realizes all $(n-1)$-functors ${\mathcal{F}}_{a,b}$ for all $a,b\in \text{Ob}(\mathcal{C})$ at the same time. In this sense, an $n$-functor can be viewed as a parallel $(n-1)$-categorical computing.　　　♢

A natural categorification of the one-dimensional vector space $\mathbb{C}$ is $\text{Vec}$ and a natural categorification of the $n$-dimensional vector space ${\mathbb{C}}^n$ is the product (or equivalently, the direct sum) ${\text{Vec}}^n$ of $n$ copies of $\text{Vec}$. A 1-category in the form ${\text{Vec}}^n$ is referred to as a finite semisimple 1-category or separable 1-category. Then the categorification of tensor product $\otimes$ of vector spaces is Deligne’s tensor product $⊠$ of 1-categories, i.e., ${\text{Vec}}^m⊠{\text{Vec}}^n={\text{Vec}}^{mn}$. A 1-categorical computation is therefore defined to be

$\text{a 1-functor}F:({\text{Vec}}^2{)}^{⊠n}\to ({\text{Vec}}^2{)}^{⊠n},$

where ${\text{Vec}}^2$ is better referred to as a 1-categorical bit (or a 1-cabit).

Remark 2.0.9. A direct generalization of 1-categorical computation is to replace the 1-categorical bit ${\text{Vec}}^2$ by an $n$-categorical bit (or an $n$-cabit) $n{\text{Vec}}^2$, where $n\text{Vec}$ is the $n$-category of $n$-vector spaces and can be obtained from $\text{Vec}$ by repeated delooping (i.e., $n\text{Vec}={\mathrm{\Sigma }}^{n-1}\text{Vec}=$ ${\mathrm{\Sigma }}^n\mathbb{C}$) [3]. In general, there are more choices for $n$-categorical bits. For example, an $n$-categorical bit can be chosen to be a separable $n$-category, which is different from $n\text{Vec}$ in general [4].　　　　　　　　　　　　　　　　　　♢

3 Physical realization of a 1-functor

In this section, we explain that a theoretical idea of realizing a 1-functor physically by the physics of topological orders (see [5] for a review of topological orders and references therein). The first topological orders that were discovered in physics labs are in 2d (spatial dimension) fractional quantum Hall systems. Since this work only discusses a theoretical idea, we assume that physical materials that realize topological orders are abundant. Throughout this work, $n$d represents the spatial dimension.

Consider the physical configuration of topological orders depicted in the first picture in Fig.1. It depicts a (potentially unstable) anomaly-free 1d (spatial dimension) topological order, together with a 0d boundary. By the mathematical theory of topological order (see for example [6]), the 0d boundary can be mathematically described by a pair $(\mathcal{X},x)$, where $\mathcal{X}$ is a separable 1-category (i.e., a finite semisimple 1-category)^†

More precisely, $\mathcal{X}$ should be a unitary finite semisimple 1-category. We hide the unitarity requirement for convenience because the unitarity is not essential in the understanding of our ideas.

and $x$ is an object in $\mathcal{X}$. Physically, this $x$ is a particle-like topological defect located at the boundary, and 1-morphisms in $\mathcal{X}$ can be viewed as instantons.

Fig.1 The physical realization of a 1-functor $\mathcal{F}:\mathcal{X}\to \mathcal{X}$.

Full size|PPT slide

According to the boundary-bulk relation [6,7], the categorical description of the bulk is the center of that of a boundary. As a consequence, the 1d topological order in the first picture in Fig.1 can be described by the 1-category of 1-functors from $\mathcal{X}$ to $\mathcal{X}$, denoted by $\mathcal{F}\text{un}(\mathcal{X},\mathcal{X})$. Objects $\mathcal{F},\mathcal{G}$ in $\mathcal{F}\text{un}(\mathcal{X},\mathcal{X})$ are particle-like topological defects in this 1d topological order. The fusion of two such defects corresponds to the composition of two 1-functors. Given such a particle-like defect, say $\mathcal{F}$, if we push it to the boundary, then it fuses with the boundary particle $x$ and change it to $\mathcal{F}(x)$ (see Fig.1). In other words, a 1-functor $\mathcal{F}$ can be realized by a creating a particle-like defect in the 1d topological order followed by a fusion process. Creating a defect in a topological order can be physically achieved by inserting an impurity. The whole process can be simplified to inserting an impurity in the neighborhood of the boundary.

Remark 3.0.1. In this way, we realize any 1-functors between two different separable 1-categories ${\mathcal{X}}_1$ and ${\mathcal{X}}_2$ because they are just the special cases when $\mathcal{X}={\mathcal{X}}_1\oplus {\mathcal{X}}_2$.　　　　　　　　　　　　　　　　　　♢

All (anomaly-free) 1d topological orders can be mathematically described by $\mathcal{F}\text{un}(\mathcal{X},\mathcal{X})$ for some separable 1-category $\mathcal{X}$. When $\mathcal{X}\ne \text{Vec}$, $\mathcal{F}\text{un}(\mathcal{X},\mathcal{X})$ is a multi-fusion 1-category instead of a fusion 1-category (see a review [8]). Mathematically, it means that the identity 1-functor ${\text{id}}_{\mathcal{X}}$ is not a simple object in $\mathcal{F}\text{un}(\mathcal{X},\mathcal{X})$, or equivalently, ${\mathrm{hom}}_{\mathcal{F}\text{un}(\mathcal{X},\mathcal{X})}({\text{id}}_{\mathcal{X}},{\text{id}}_{\mathcal{X}})$≄$\mathbb{C}$. Physically, it means that the multi-fusion 1-category $\mathcal{F}\text{un}(\mathcal{X},\mathcal{X})$ describes an unstable phase, which can flow to a stable one if we introduce certain perturbation to the phase [6]. In this case, this unstableness demands fine tuning, which makes the physical realization not fault tolerant.

This problem can be solved by replacing the potentially unstable physical configuration depicted in the first picture in Fig.2 by a stable higher dimensional physical configuration as depicted in the second picture in Fig.2. In this new configuration, $\mathcal{C}$ labels an anomaly-free 2d topological order, and $\mathcal{P},\mathcal{Q}$ label two 1d gapped boundaries of $\mathcal{C}$, and the same pair $(\mathcal{X},x)$ is now realized as a domain wall between $\mathcal{P}$ and $\mathcal{Q}$. Mathematically, $\mathcal{C}$ is a modular tensor 1-category [9], and $\mathcal{P},\mathcal{Q}$ are fusion 1-categories. All separable 1-category $\mathcal{X}$ can be realized as a corner of this configuration by properly selecting $\mathcal{P},\mathcal{C},\mathcal{Q}$. The second picture in Fig.2 can reproduce the first picture by a dimensional reduction process (i.e., by closing the fan). After the dimensional reduction, $\mathcal{F}\text{un}(\mathcal{X},\mathcal{X})$ is unstable as a 1d phase, but before the dimensional reduction, everything is stable. Then a 1-functor $\mathcal{F}:\mathcal{X}\to \mathcal{X}$ can be realized by introducing a 0d domain wall $(\mathcal{M},m)$ in $\mathcal{P}$ and a 0d wall $(\mathcal{N},n)$ in $\mathcal{Q}$, and a 1d domain wall $\mathcal{R}$ in $\mathcal{C}$, then pushing $(\mathcal{M},m),\mathcal{R},(\mathcal{N},n)$ down to the corner (i.e., squeezing the triangle to a point) such that they fuse with $(\mathcal{X},x)$ to give $(\mathcal{X},\mathcal{F}(x))$ [10]. In reality, this process can be achieved by simply inserting new materials in a highly controlled way in the neighborhood of the corner directly. All 1-functors $\mathcal{F}:\mathcal{X}\to \mathcal{X}$ can be physically realized in this way by properly selecting $\mathcal{M},\mathcal{R},\mathcal{N}$. We believe that this way of doing computation is fault tolerant because topological defects are stable under the perturbation of local operators.

Fig.2 These figures illustrate the idea of fixing the unstable problem in Fig.1.

Full size|PPT slide

However, as one can see, such a “1-functor” does not realize any parallel quantum computing because only two objects $x,\mathcal{F}(x)\in \mathcal{X}$ appear in above process. It is not surprising because a 0d boundary is essentially a quantum mechanics system. In order to achieve the second quantization of quantum computing, we need to consider higher dimensional topological orders. A more realistic realization of 1-functor is given in the discussion of Fig.3 and Fig.4 (see also Remark 4.0.4).

Fig.3 The idea of physically realizing a monoidal 1-functor.

Full size|PPT slide

Fig.4 The idea of realizing a monoidal functor $\mathcal{F}:\mathcal{A}\to \mathcal{B}$ defined by $a\mapsto 1_{{\mathcal{F}}^{\prime }}{⊠}_{\mathcal{A}}a{⊠}_{\mathcal{A}}{1}_{{\mathcal{F}}^{″}}\in \mathcal{B}$ in a 2d fractional quantum Hall system.

Full size|PPT slide

Remark 3.0.2. A physical realization of 1-functor does not demands that of 1-category as a prerequisite because “a physical realization of 1-functors” should be viewed as a realization of 1-morphisms in a 2-category that is only equivalent to the 2-category $\mathsf{C}\mathsf{A}\mathsf{T}$. However, the ingredients of a 1-category $\mathcal{A}$, i.e., $\{{\mathrm{hom}}_{\mathcal{A}}(a,b){\}}_{a,b\in \mathcal{A}}$ and composition maps, do have physical meanings as the spaces of instantons and the fusion of instantons, respectively (see an expository review [11]). The space of instantons can also be viewed as the space of ground state degeneracy (GSD) by the state-field correspondence. Unfortunately, it is not clear to us how to experimentally extract or control the information of instantons in spacetime directly. It is also not clear if it is necessary because categorical computation demands us to think about everything, including information storage and processing, not in the usual set-theoretical way by manipulating instantons but in a categorical way by manipulating functors. We leave this issue to the future.　　　　　　　　　　　　 　　　　　　　　♢

4 Higher categorical computation

Above ideas generalize to higher categories and higher functors via higher dimensional topological orders but with important new features. We first generalize the discussion in Section 3 to $n$-functors between $n$-categories, then we give more details on the $n=2$ case.

Roughly speaking, an $n$-category $\mathcal{C}$ consists of a set of objects $a,b,c,\cdots$, the hom space ${\mathrm{hom}}_{\mathcal{C}}(a,b)$ is an $(n-1)$-category, the identity 1-morphisms and the compositions of morphisms (as $(n-1)$-functors) satisfying more complicated axioms (recall Remark 2.0.4). We prefer not to give details. An $n$-functor is defined similarly to a 1-functor (recall Remark 2.0.8). In particular, an $n$-functor $\mathcal{F}:\mathcal{C}\to \mathcal{D}$ consists of all $(n-1)$-functors ${\mathcal{F}}_{a,b}:{\mathrm{hom}}_{\mathcal{C}}(a,b)\to {\mathrm{hom}}_{\mathcal{D}}(\mathcal{F}(a),\mathcal{F}(b))$ at the same time. Therefore, an $n$-categorical computation can be viewed as a parallel $(n-1)$-categorical computation. The first major challenge for above ideas to work is to figure out how to realize higher functors physically.

Using the same Fig.1, now let $\mathcal{X}$ be a separable $n$-category [4, Definition 3.3] and $x$ an object in $\mathcal{X}$. The pair $(\mathcal{X},x)$ now describes a potentially anomalous $(n-1)$D (spatial dimension) topological order [3,4,6]. By the boundary-bulk relation, its $n$d bulk is again given by $\mathcal{F}\text{un}(\mathcal{X},\mathcal{X})$, which is now a multi-fusion $n$-category. An $n$-fucntor $\mathcal{F}:\mathcal{X}\to \mathcal{X}$ labels a topological defect of codimension 1 in the $n$d bulk, and can be realized physically in the same way as illustrated in Fig.1 and Fig.2, where $\mathcal{C}$ should be viewed as an $(n+1)$D bulk phase. We provide more details later for $n=2$ cases.

Unlike the $n=1$ case where a separable 1-categories is simply a finite product of $\text{Vec}$, a separable $n$-category does not have such a decomposition when $n\ge 2$. In general, a separable $n$-category is a finite direct sum of indecomposable separable $n$-category [3,4,12,13]. An indecomposable separable $n$-category is connected by 1-morphisms. In other words, there is only one connecting component. In general, an indecomposable separable $n$-category can have infinitely many simple objects. Its full subcategory consisting of only two objects $x$ and $y$ can be illustrated by the following diagram:

$\begin{array}{c}\text{includegraphics}[width=0.31\text{paperwidth}]fop-21251-kongliang-Scheme4.jpg\end{array}$

where $\mathrm{hom}(x,x)$ and $\mathrm{hom}(y,y)$ are multi-fusion $(n-1)$-categories, and $\mathrm{hom}(x,y),\mathrm{hom}(y,x)$ are separable $(n-1)$-categories. Therefore, the notion of a separable $n$-category can be defined inductively.

Example 4.0.1. We illustrate an example of an indecomposable separable 2-category $2\text{Rep}({\mathbb{Z}}_2)$ by the following diagram [12].

$\begin{array}{c}\text{includegraphics}[width=0.35\text{paperwidth}]fop-21251-kongliang-Scheme5.jpg\end{array}$

where $x=1$ and $y=1_c$ denote the only two simple objects in $2\text{Rep}({\mathbb{Z}}_2)$, and $\mathrm{hom}(1,1)=\text{Rep}({\mathbb{Z}}_2)$ is the 1-category of finite dimensional representations of the ${\mathbb{Z}}_2$-group, and $\mathrm{hom}(1_c,1_c)={\text{Vec}}_{{\mathbb{Z}}_2}$ is the 1-category of ${\mathbb{Z}}_2$-graded vector spaces. All other objects are finite direct sum of $1$ and $1_c$. The separable 2-category $2\text{Rep}({\mathbb{Z}}_2)$ has a physical meaning in 3d finite gauge theory with the gauge group $G={\mathbb{Z}}_2$ [14].　　　　　　　　　　　　　　　　♦

Remark 4.0.2. The classification of separable $n$-categories is not known. It was known that a separable $n$-category is the representation category of a multi-fusion $(n-1)$-category [3,4,12]. Unfortunately, even the classification of fusion 1-categories is not known.　　　　　　　　♢

Therefore, when $n\ge 2$, there is no canonical choice of an $n$-categorical bit. The simpest choice is $n{\text{Vec}}^2$ (recall Remark 2.0.9), but this choice does not exhibit the richness of $n$-categorical computation. An $n$-categorical computation is then should be defined as

$\text{an}n\text{-functor}F:\mathcal{X}\to \mathcal{X},$

where $\mathcal{X}$ is a separable $n$-category.

Importantly, the data $(\mathcal{X},x)$ is essentially equivalent to the multi-fusion $(n-1)$-category ${\mathrm{hom}}_{\mathcal{X}}(x,x)$ [3,4]. The above physical realization of an $n$-functor $\mathcal{F}:\mathcal{X}\to \mathcal{X}$ can also be viewed as a physical realization of a monoidal $(n-1)$-functor from ${\mathrm{hom}}_{\mathcal{X}}(x,x)$ to ${\mathrm{hom}}_{\mathcal{X}}(\mathcal{F}(x),\mathcal{F}(x))$. This physical realization of a monoidal $(n-1)$-functor can be stated as a precise mathematical theorem (see [15, Theorem 3.2.3] for $n=2$ and [16] for general $n$).

Remark 4.0.3. Topological orders were proposed long ago to provide the physical realization of the fault tolerant quantum computation [17,18] (see for example [19] for a review and references therein). Our proposal suggests that the physics of topological orders might allows us to do $n$-categorical computations in a fault tolerant way. ♢

Although the physical realization of topological orders cannot go beyond 3d (spatial dimension), it is already very interesting and rich in 1d and 2d cases because anomalous 1d topological orders and 2d topological orders are abundant. In the rest of this paper, we further illustrate the idea for anomalous 1d topological orders because it is experimentally realizable either as a gapped domain wall in a 2d fractional quantum Hall system or a gapped boundary in a toric code model achieved in quantum simulation (see for example [20,21] and references therein).

An anomalous 1d topological order can be described by a pair $(\mathcal{X},x)$, where $\mathcal{X}$ is a separable 2-category and $x\in \mathcal{X}$ is a distinguished object^†

Without loss of generality, we can assume $x$ is indecomposable.

. Equivalently, it can also be described a fusion 1-category $\mathcal{A}:={\mathrm{hom}}_{\mathcal{X}}(x,x)$, the objects of which are particle-like topological excitations (or topological defects). We illustrate the idea of physically realizing a monoidal 1-functor $\mathcal{F}:\mathcal{A}\to \mathcal{B}$ from $\mathcal{A}$ to another multi-fusion 1-category $\mathcal{B}$ in Fig.3.

Since the 1d topological order $\mathcal{A}$ is anomalous, it can only be a gapped boundary of a 2d topological order, whose particle-like topological excitations form a braided fusion 1-category given by the Drinfeld center of $\mathcal{A}$ [6,7,22], denoted by ${\mathfrak{Z}}_1(\mathcal{A})$. Consider a gapped domain wall between the bulk of $\mathcal{A}$ and the anomaly-free 2d phase $\mathcal{C}$ labeled by $\mathcal{F}$. The particle-like topological excitations on the wall form a multi-fusion 1-category still denoted by $\mathcal{F}$.

Topological excitations $a_1,\cdots ,a_n$ in the anomalous 1d topological order can be arranged to be separated with equal distance. According to [15, Theorem 3.2.3], the gapped domain wall or the fusion category $\mathcal{F}$ determines (actually is equivalent to) a monoidal functor from $\mathcal{A}$ to $\mathcal{B}:=\mathcal{F}{⊠}_{{\mathfrak{Z}}_1(\mathcal{A})}\mathcal{A}$ defined by

$a\mapsto 1_{\mathcal{F}}{⊠}_{{\mathfrak{Z}}_1(\mathcal{A})}a\in \mathcal{F}{⊠}_{{\mathfrak{Z}}_1(\mathcal{A})}\mathcal{A}=\mathcal{B},\mathrm{\forall }a\in \mathcal{A},$

where $1_{\mathcal{F}}$ denotes the trivial particle (or the tensor unit) in $\mathcal{F}$. In other words, a physical realization of above functor can be achieved by (1) fusing a 2d phase with a gapped boundary onto the bulk of $\mathcal{A}$ such that a new 2d phase $\mathcal{C}$ and a gapped domain wall $\mathcal{F}$ between $\mathcal{C}$ and the bulk of $\mathcal{A}$ are created; (2) fusing $\mathcal{F}$ with $\mathcal{A}$.^†

One way to realize “fusing $\mathcal{F}$ with $\mathcal{A}$” is to create $\mathcal{F}$ in a neighborhood of $\mathcal{A}$.

) In a special case $\mathcal{C}$ coincides with the bulk of $\mathcal{A}$, one can replace the step (1) by selecting a line in the bulk of $\mathcal{A}$ then modifying the microscopic physics along the line to create a gapped domain wall $\mathcal{F}$ directly. Note that this modification might be achieved by a macroscopic process (e.g., gluing new materials or chemicals along the line). Since both $\mathcal{C}$ and $\mathcal{F}$ are many-body systems, this type of computation need manipulate infinitely degrees of freedom in the thermodynamics limit and is thus a second quantized computation.

Remark 4.0.4. If we fix the location of $a_i\in \mathcal{A}$ as in Fig.3, we can ignore the monoidal structure on $\mathcal{A}$ and view $\mathcal{F}$ as a physical realization of a 1-functor.　　　　　　♢

For example, it is possible to control and arrange anyons in 2d in the experiments of fractional quantum Hall systems (see for example [23] and references therein). As depicted in Fig.4, by simply arranging these anyons in fractional quantum Hall systems along the dashed line in Fig.4, we obtain a realization of $\mathcal{A}$ in Fig.3, where ${\mathfrak{Z}}_1(\mathcal{A})=\mathcal{A}⊠\overline{\mathcal{A}}$ is now a double layered fractional quantum Hall system. An example of $\mathcal{F}$ is realized by two 1d domain walls ${\mathcal{F}}^{\prime }$ and ${\mathcal{F}}^{″}$ sitting on the two sides of the dashed line as depicted in Fig.4, i.e., $\mathcal{F}={\mathcal{F}}^{\prime }⊠{\mathcal{F}}^{″}$.

Remark 4.0.5. The idea illustrated in Fig.3 and Fig.4 can be automatically generalized to 3d topological orders to give a physical realization of monoidal 2-functors.　　　　　　　　　　　　　　　　　　　　　　♢

The theoretical idea we present here is still far from an experimental realization. At this stage, it is too early to tell if the categorical computation is technologically possible or impossible. It depends on the future development of the physics of topological phases, the discovery of new topological materials and the technology advances in controlling and engineering topological defects. We also do not know if it can be more efficient than classical/quantum computation. However, we believe that this theoretical idea deserves some attentions from theorists who are working closely with experimentalists. Moreover, theoretically, it seems rather obvious that categorical computation is suitable or very likely to be powerful in computing (higher) categories and (higher) functors. On the other hand, it is not clear how to simulate a category or a functor by a classical computer or a quantum computer.

We believe that it is worthwhile to make this naive idea available to experts so that more ideas and discussion can follow. For example, many natural questions can be asked based on the proposal of this work, such as the details of the physical realization, in what sense the computation can be made “universal”, what possible gates are, what the complexity theory of categorical computation is, etc..

Remark 4.0.6. We want to remind readers that the higher categorical computation is fundamentally different from the quantum computing based on the braidings between anyons or higher dimensional topological defects in higher dimensional topological orders. Both fusion matrices and braiding matrices for higher dimensional topological defects are the defining data of certain natural transformations between higher functors. Therefore, it might be possible to use fusions or braidings of higher dimensional topological defects to simulate or compute certain categorical structures. It is very interesting to explore the relation or possible interaction between these two different ideas of computing. We will leave it to the future.　　　　　　　　　　　　　　　　　　♢

References

[1] L. Crane, I. B. Frenkel, Four dimensional topological quantum field theory. Hopf categories, and the canonical bases. J. Math. Phys., 1994, 35(10): 5136

[2] C. Weibel, The K-book: An introduction to algebraic K-theory, Graduate Studies in Math. Vol. 145, AMS, 2013

[3] T. Johnson-Freyd. On the classification of topological orders. Commun. Math. Phys., 2022, 393(2): 989

[4] L.KongH. Zheng, Categories of quantum liquids I, J. High Energy Phys. 2022, 70 (2022), arXiv: 2011.02859

[5] X. G. Wen. Choreographed entanglement dances: Topological states of quantum matter. Science, 2019, 363(6429): eaal3099

[6] L.KongX. G. WenH.Zheng, Boundary-bulk relation for topological orders as the functor mapping higher categories to their centers, arXiv: 1502.01690 (2015)

[7] L. Kong, X. G. Wen, H. Zheng. Boundary-bulk relation in topological orders. Nucl. Phys. B, 2017, 922: 62

[8] P.EtingofS. GelakiD.NikshychV.Ostrik, Tensor Categories, American Mathematical Society, Providence, RI, 2015

[9] V.G. Turaev, Quantum Invariant of Knots and 3-Manifolds, de Gruyter Studies in Mathematics, Vol. 18, Walter de Gruyter, Berlin, 1994

[10] Y. Ai, L. Kong, H. Zheng. Topological orders and factorization homology. Adv. Theor. Math. Phys., 2017, 21(8): 1845

[11] L.KongZ. H. Zhang, An invitation to topological orders and category theory, arXiv: 2205.05565 (2022)

[12] C.L. DouglasD.J. Reutter, Fusion 2-categories and a state-sum invariant for 4-manifolds, arXiv: 1812.11933 (2018)

[13] D.GaiottoT. Johnson-Freyd, Condensations in higher categories, arXiv: 1905.09566 (2019)

[14] L.KongY. TianZ.H. Zhang, Defects in the 3-dimensional toric code model form a braided fusion 2-category, J. High Energy Phys. 2020, 78 (2020), arXiv: 2009.06564

[15] L. Kong, H. Zheng. The center functor is fully faithful. Adv. Math., 2018, 339: 749

[16] L.KongH. Zheng, Categories of quantum liquids II, arXiv: 2107.03858 (2021)

[17] A. Y. Kitaev. Fault-tolerant quantum computation by anyons. Ann. Phys., 2003, 303(1): 2

[18] M.Freedman, P/NP and the quantum field computer, Proc. Natl. Acad. Sci. USA 95(1), 98 (1998)

[19] Z.Wang, Topological Quantum Computation, CBMS Regional Conference Series in Mathematics Publication, Vol. 112, 2010

[20] K. J. Satzinger, Y. J. Liu, A. Smith, C. Knapp. . Realizing topologically ordered states on a quantum processor. Science, 2021, 374(6572): 1237

[21] G. Semeghini, H. Levine, A. Keesling, S. Ebadi, T. T. Wang, D. Bluvstein, R. Verresen, H. Pichler, M. Kalinowski, R. Samajdar, A. Omran, S. Sachdev, A. Vishwanath, M. Greiner, V. Vuletic, M. D. Lukin. Probing topological spin liquids on a programmable quantum simulator. Science, 2021, 374(6572): 1242

[22] A. Kitaev, L. Kong. Models for gapped boundaries and domain walls. Commun. Math. Phys., 2012, 313(2): 351

[23] J. Nakamura, S. Liang, G. C. Gardner, M. J. Manfra. Direct observation of anyonic braiding statistics. Nat. Phys., 2020, 16(9): 931

Acknowledgements

We thank Zheng-Wei Liu, Ce Shen, Xiao-Ming Sun, Zhong Wang and Bo Yang for comments. We are supported by Guangdong Provincial Key Laboratory (Grant No. 2019B121203002). L.K. is also supported by the National Natural Science Foundation of China under Grant No. 11971219 and Guangdong Basic and Applied Basic Research Foundation under Grant No. 2020B1515120100. H.Z. is also supported by the National Natural Science Foundation of China under Grant No. 11871078.

RIGHTS & PERMISSIONS

2023 Higher Education Press