Tomoyuki Yamakami
email: tomoyukiyamakami@gmail.com

How Does Adiabatic Quantum Computation Fit into Quantum Automata Theory?

Keywords: adiabatic quantum computation, quantum finite automata, Hamiltonian, Schrödinger equation

Quantum computation has emerged as a powerful computational medium of our time, having demonstrated the efficiency in solving the integer factoring and searching a database faster than any currently known classical computer algorithm. Adiabatic evolution of quantum systems have been studied as a potential means that physically realizes quantum computation. Up to now, all the research on adiabatic quantum systems has dealt with polynomial time-bounded computation and little attention has been paid to, for example, adiabatic quantum systems consuming only constant memory space. Such quantum systems can be modeled in a form similar to quantum finite automata. This exposition dares to ask a bold question of how to make adiabatic quantum computation fit into the rapidly progressing framework of quantum automata theory. As our answer to this eminent but profound question, we first lay out a basic framework of adiabatic evolutionary quantum systems (AEQSs) with limited computational resources and then establish their close connection to quantum finite automata. We also explore fundamental structural properties of languages solved quickly by such adiabatic evolutionary quantum systems.

1 Motivations and a Quick Overview

Adiabatic Quantum Computation

Quantum computation has gained large popularity over the past few decades. There are several important milestones to remember in our time. Shor proposed a polynomial-time quantum algorithm of factoring a positive integer and computing discrete logarithms whereas Grover presented a quantum way to locate a key in a unstructured database quadratically faster than traditional search. Basis of such quantum computation has been modeled typically by quantum Turing machines and quantum circuits. See, e.g., [START_REF] Gruska | Quantum Computing[END_REF][START_REF] Kitaev | Classical and Quantum Computation[END_REF][START_REF] Nielsen | Quantum Computation and Quantum Information[END_REF].

In a given quantum system, its quantum state |ψ(t) evolves according to the Schrödinger equation ı d dt |ψ(t) = H(t)|ψ(t) using a specified time-dependent Hamiltonian H(t) (which is simply a Hermitian matrix), where is the reduced Planck constant. In early 2000's, Farhi, Goldstone, Gutmann, and Sipser [START_REF] Farhi | Quantum computation by adiabatic evolution[END_REF] and Farhi, Goldstone, Gutmann, Lapan, Lundgren, and Preda [START_REF] Farhi | A quantum evolution algorithm applied to random instances of an NP-complete problem[END_REF] developed a quantum algorithm based on a variant of quantum annealing, called adiabatic quantum computation, in which an initial quantum system whose ground state is easily prepared gradually evolves to find a solution represented by a ground state of a final quantum system. A crucial point is how fast this evolution takes place. Unfortunately, it turns out that the algorithm of Farhi et al. [START_REF] Farhi | A quantum evolution algorithm applied to random instances of an NP-complete problem[END_REF] requires exponential time to execute [START_REF] Van Dam | How powerful is adiabatic quantum computation?[END_REF].

Adiabatic quantum computation is dictated by a quadruple (n, ε, H ini , H f in ) of two Hamiltonians H ini and H f in of dimension 2 n and a closeness bound ε such that H ini 's ground state (i.e., an eigenvector of the smallest eigenvalue) is easily prepared and the outcome of the system becomes the ground state of H f in and this ground state is ε-close to the desired solution. Such a quantum system starts with the ground state |ψ g (0) of H(0) = H ini at time t = 0. If H(t) changes sufficiently slowly, the evolving quantum state |ψ(t) stays close to the ground state |ψ g (t) of H(t). For the efficiency of adiabatic quantum computation, we have concerned with the evolution time of the underlying quantum system and the structural complexity of two Hamiltonians used in the system. The running time of the system is determined roughly by the evolution time of the system and is basically proportional to the reciprocal of the spectral gap of H ini and H f in according to the well-known adiabatic theorem [START_REF] Kato | On the adiabatic theorem of quantum mechanics[END_REF][START_REF] Messiah | Quantum Mechanics[END_REF]. See Section 2.3.

Later, van Dam, Mosca, and Vazirani [START_REF] Van Dam | How powerful is adiabatic quantum computation?[END_REF] gave a detailed analysis of adiabatic quantum computation and presented how to simulate adiabatic quantum computation on quantum circuits. In addition, Aharonov, van Dam, Kemp, Landau, Lloyd, and Regev [START_REF] Aharonov | Adiabatic quantum computation is equivalent to standard quantum computation[END_REF] demonstrated how to simulate quantum circuit computation by adiabatic quantum computation and thus established the (polynomial) equivalence between adiabatic quantum computation and standard quantum computation.

Although adiabatic quantum computation is no more powerful than standard quantum computation, it seems to remain as significant potentials to realize restricted variants of quantum computation. With the current technology, it still seems to be difficult to build a large-scale adiabatic quantum computing device since making local evolution in a large system is quite sensitive to decoherence. It is rather better to make global evolution in a small system. It thus remains more realistic to prepare Hamiltonians of adiabatic quantum computation using a memory-restricted quantum device. We may wonder what would happen if we restrict our attention onto a constant-memory model of Turing machine, which is conceptually realized by finite(-state) automata. To seek for yet-unearthed potentials of adiabatic quantum computation in such a realistic setting, this exposition intends to make a new, bold step by taking an automata-theoretic approach toward adiabatic quantum computability. Since adiabatic quantum computation follows the gradual evolution between two Hamiltonians H ini and H f in , the key to the realization of such computation relies on how easily we can build these Hamiltonians. This fact motivates us to consider the circumstances where the matrices are "generated" by memory-restricted device, namely, quantum finite automata. This exposition reports an initial result of our bold attempt to deal with adiabatic quantum computation from a viewpoint of quantum finite automata.

At first glance, since our desired quantum algorithm to solve a given decision problem requires outcomes of only one-bit solutions, it seems sufficient for us to prepare either |1 or |0 as a unique ground state of a final Hamiltonian H f in . For such a preparation, however, we should know the solution well ahead of quantum computation. Without knowing any solution of the problem, we may not in general prepare H f in prior to the start of the computation. Farhi et al. [START_REF] Farhi | A quantum evolution algorithm applied to random instances of an NP-complete problem[END_REF]'s idea of designing a final Hamiltonian H f in to solve Search-2SAT (i.e., a search version of the satisfiability problem for 2CNF formulas) is to encode a solution of the problem directly into H f in without knowing the solution. In a similar fashion, we want to find a way to prepare H f in without apparently computing any solution to the target problem. This exposition proposes the use of quantum finite automata as a mechanical tool to directly generate Hamiltonians as the automata read input symbols one by one. In this way, we can prepare Hamiltonians even without knowing a solution to a given decision problem.

Quantum Automata Theory

A quantum finite automaton takes an input string given onto its read-only input tape and, as reading the input symbol one by one, it changes inner states in a quantum manner until it finally terminates. This process can be described as quantum transitions of inner states according to input symbols. The theory of quantum finite automata has been developed significantly since the first installment of quantum finite automata in 1990s (see, e.g., a survey [START_REF] Ambainis | Automata and quantum computing[END_REF]).

Since a paradigm of adiabatic quantum computation looks quite different from a standard framework of quantum finite automata, we certainly face the following challenging question. Is it possible for us to make adiabatic quantum computation fit into the framework of quantum automata theory?

An Overview of Main Contributions

This exposition attempts to answer the aforementioned question of how adiabatic quantum computation fits into quantum automata theory.

We need to define a scaled-down model for adiabatic quantum computation, aiming at capturing an essence of such computation in terms of quantum finite automata. For this purpose, we introduce an adiabatic evolutionary quantum system (AEQS, pronounced as "eeh-ks") consisting of an input alphabet, a size parameter, a closeness bound, two Hamiltonians for each input, and acceptance/rejection criteria for each input size (whose precise definition will be given in Section 2.4). Lemma 1. For any language L over an alphabet Σ, there is a series of AEQSs {S x } x∈ Σ of finite size such that, for any x, S x computes L(x).

Although this lemma demonstrates the power of AEQSs, it does not provide us with a constructive mechanism of generating AEQSs.

In this exposition, we are focused on how to prepare two Hamiltonians of AEQSs using variants of quantum finite automata. The use of algorithmic construction of Hamiltonians also provides the uniformity condition to adiabatic quantum computation. After giving the basic notions and notation in Section 2, we will demonstrate how to design (or program) AEQSs for several languages (of Proposition 2) in Section 3.

Concerning the computational complexity of AEQSs, we wish to limit the behaviors of AEQSs. To describe the families of decision problems (or equivalently, languages) associated with AEQSs under a set F of certain "natural" conditions on key ingredients, two Hamiltonians, we use the notation AEQS(F). In general, the complexity class AEQS(F) is composed of all decision problems (or languages), each of which is solved (or recognized) with "high-accuracy" by a certain AEQS whose Hamiltonians satisfy the conditions specified by F. This helps us discuss various types of conditions, which play essential roles in determining the computational complexity of AEQSs. Of all possible types of conditions, we are focused on the following 4 condition types.

Firstly, we are interested in how to "generate" two Hamiltonians of AEQSs. In particular, we consider the case where those Hamiltonians are generated by certain one-way quantum quasi-automata (abbreviated as 1qqa's), each of which acts as a means to produce a series of Kraus operators according to each input symbol so that the product of its adjoint and itself matches the target Hamiltonians (whose precise definition will be given in Section 2.2). We use the notation F ="1qqa" to denote the use of 1qqa's to generate Hamiltonians of AEQSs. We also define another condition set F ="2cqqa" using 2-way classical-head quantum quasi-automata (or 2cqqa's) in place of 1qqa's. In a similar manner, we define F ="1qpdqa" to mean the use of one-way quantum pushdown quasi-automata (abbreviated as 1qpdqa's) induced from a quantum version of pushdown automata.

Secondly, we are concerned with the (system) size of AEQSs, where the (system) size of an AEQS is the logarithm of the dimension of its Hamiltonians. We write F ="constsize" (constant size), F ="logsize" (logarithmic size), and F ="linsize" (linear size) to express the sizes of target AEQSs.

Thirdly, we pay attention to the value of the spectral gap of a final Hamiltonian of an AEQS, where the spectral gap is the difference between the first and the second smallest eigenvalues. This value provides an upper bound of the runtime of the AEQS. For instance, if the final Hamiltonian of an AEQS have their spectral gap inverse-polynomially large, then the adiabatic evolution of the AEQS takes only polynomially many steps. Notice that, even if Hamiltonians are generated by 1qqa's, there seems a chance that the spectral gap is exponentially small. From this fact, we introduce the notation F ="polygap" to mean that the spectral gap is at least 1/n O(1) (i.e., inverse-polynomially large). Similarly, F ="constgap" indicates that the spectral gap is at least 1/O(1) (i.e., constantly large).

Fourthly, we look into the ground energy level of a final Hamiltonian of an AEQS. In certain cases [START_REF] Farhi | A quantum evolution algorithm applied to random instances of an NP-complete problem[END_REF][START_REF] Farhi | Quantum computation by adiabatic evolution[END_REF], it is possible to set the ground energy of a final Hamiltonian to be 0. This motivates us to define F ="0-energy" for the situation where the ground energy of a final Hamiltonian is 0 for every input x.

Proposition 2. Let N denote the set of all natural numbers. The following statements hold. 1. For each fixed string a ∈ {0, 1} * , the regular language L a = {ax | x ∈ {0, 1} * } is in AEQS(1qqa, constgap). 2. The reversible unary language L even defined as

L even = {a 2n | n ∈ N} is in AEQS(1qqa, constgap, 0-energy). 3. The deterministic context-free language L eq = {0 n 1 n | n ∈ N} is in
AEQS(2cqqa, logsize, polygap). 4. The language T RI consists of all strings of the form

w 1 #w 2 #w 3 such that w 1 , w 2 , w 3 ∈ {0, 1} * , |w 1 | = |w 2 | = |w 3 |, (w 1 = w R 2 ) XOR (w 1 = w R 3 )
. This language is in AEQS(1qpdqa, linsize, polygap).

We show a more general theorem below. 1MOQFA is a language family characterized by bounded-error 1-way measure-once quantum finite automata [START_REF] Moore | Quantum automata and quantum grammars[END_REF].

Theorem 3. 1MOQFA ⊆ AEQS(1qqa, constsize, constgap, 0-energy).
Next, we target the class REG of all regular languages. If we use 1qqa's to generate Hamiltonians, then we obtain the following relations. Here, we expand 1qqa's by allowing them to have O(n) inner states. To express such machines, we use the term "linsize-1qqa's." Theorem 4. REG ⊆ AEQS(linsize-1qqa, constgap, 0-energy).

We further explore structural properties of AEQS(F). A language family L is said to be closed under a binary operation • if, for any two languages L 1 , L 2 ∈ L, L 1 • L 2 also belongs to L. We say that F allows a swap of acceptance/rejection criteria if the new AEQS obtained from any given AEQS satisfying F by exchanging its S rej respectively denote sets of indices providing criteria for acceptance and rejection of ground states. Additionally, we say that F allows the amplification of accuracy if, for any AEQS satisfying F and any constant c > 0, there always exists another computationally-equivalent AEQS with F whose accuracy is at least c times as high as the original AEQS's. Proposition 5. Let F be any nonempty set of conditions. Each of the following statements holds. 1. AEQS(F) is closed under complementation if F allows a swap of acceptance/rejection criteria.

AEQS(F) is closed under XOR if F allows the amplification of accuracy.

This exposition is merely the initial attempt to expand the scope of adiabatic quantum computability and to relate it to quantum finite automata using the new notion of AEQSs. We expect that this exposition marks the beginning of a series of exciting research works, aiming at the deeper understanding of adiabatic quantum computation.

2 Preparations: Notions and Notation

Numbers, Vectors, and Matrices

The notation N expresses the set of all natural numbers (that is, nonnegative integers) and we set N + = N -{0}. Given two integers m, n with m ≤ n, the integer interval [m, n] Z is the set {m, m + 1, m + 2, . . . , n}, which is compared to a real interval [a, b]. Let C denote the set of all complex numbers; in particular, we set ı = √ -1. All polynomials are assumed to have nonnegative integer coefficients and all logarithms are taken to the base 2.

We deal with finite-dimensional Hilbert spaces. To express (column) vectors of such a space, we use Dirac's notation |• . A density operator (or a density matrix) expresses a mixed quantum state. Given a complex matrix A, A † indicates the complex conjugate transpose of A. For any matrix A and its index pair (q, r), the notation A[q, r] indicates the (q, r)-entry of A. Similarly, for a vector v, v[i] denotes the ith entry of v. Given any square complex matrix A, the notation e A expresses a matrix exponential defined by e A = ∞ k=0 1 k! A k (where 0! = 1 and A 0 = I) and the spectral norm A is defined by

A = max |φ =0 { A|φ 2
|φ 2 }, where • 2 indicates the 2 -norm. For a number ε ∈ [0, 1] and for two vectors v 1 and v 2 in the same Hilbert space, we say that

v 1 is ε-close to v 2 if v 1 -v 2 2 ≤ ε.
The commutator [A, B] of square matrices A and B is defined as AB -BA.

We use the notation W for the Walsh-Hadamard transform. For convenience, we write |â = W |a for any a ∈ {0, 1}. The Hadamard basis is {| 0 , | 1 } and the computational basis is {|0 , |1 }.

A Hamiltonian is a complex Hermitian matrix. For any Hamiltonian H, we set ∆(H) to be the spectral gap of H, which is the difference between the lowest eigenvalue and the second lowest eigenvalue of H. The lowest eigenvalue is called the ground energy of H and its eigenvector is called the ground state of H.

Languages and Quantum Quasi-Automata

An alphabet is a finite nonempty set of "symbols" or "letters." A string over an alphabet Σ is a finite sequence of symbols in Σ. The length of a string x is the total number of symbols in x and is denoted by |x|. In particular, the empty string has length 0 and is denoted by λ. The notation Σ * stands for the set of all strings over Σ. A language over Σ is a subset of Σ * . Hereafter, we freely identify a decision problem with its associated language.

A one-way quantum finite automaton1 (abbreviated as a 1qfa) with mixed states and quantum operations M is a septuple

(Q, Σ, {| c, $}, {A σ } σ∈ Σ , q 0 , Q acc , Q rej ), where Q is a finite set of inner states, Σ is an (input) alphabet, |
c and $ are respectively the left endmarker and the right endmarker, Σ = Σ ∪ {| c, $}, and each A σ is a quantum operation 2 acting on the Hilbert space of linear operators on the configuration space spanned by the basis vectors {|q | q ∈ Q} [START_REF] Ambainis | Algebraic results on quantum automata[END_REF][START_REF] Freivalds | Improved constructions of mixed state quantum automata[END_REF][START_REF] Yakaryilmaz | Unbounded-error quantum computation with small space bounds[END_REF]. Such a quantum operation A σ has a Kraus representation with Kraus operators (or operation elements) {A σ,j } j∈[k] for a certain constant k ∈ N + . More precisely, A σ takes the form A σ (H) = k j=1 A σ,j HA † σ,j for any linear operator H and satisfies the completeness relation k j=1 A † σ,j A σ,j = I. In particular, when k = 1, we identify A σ,1 with A σ and then obtain A σ (H) = A σ HA † σ . Given strings y 1 , y 2 , • • • , y k in Σ, we abbreviate a matrix multiplication

A y k • A y k-1 • • • A y2 • A y1 as A y1y2•••y k-1 y k .
Given a language L, M recognizes with error probability at most ε if, for any x ∈ L, tr(P acc A | cx$ (ρ 0 )) ≥ 1 -ε and, for any x / ∈ L, tr(P rej A | cx$ (ρ 0 )) ≥ 1 -ε, where ρ 0 = |q 0 q 0 | and P acc and P rej are projections onto the spaces spanned by {|q | q ∈ Q acc } and by {|q | q ∈ Q rej }, respectively. This model is in essence equivalent to a garbage-tape model used in [START_REF] Yamakami | Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice[END_REF]. In contrast, a one-way measure-once quantum finite automaton (or a 1moqfa) applies only unitary operators until it reads $. The state complexity of a finite automaton is the total number of inner states of the automaton. We write 1MOQFA and 1QFA mix to denote the collections of all languages recognized respectively by bounded-error 1moqfa's and bounded-error 1qfa's with mixed states and quantum operators.

We attempt to run finite automata to produce Hamiltonians, which are necessary to carry out adiabatic quantum computation. For this purpose, we need to modify the aforementioned model of 1qfa's so that they can produce "matrices." A one-way quantum quasi-automaton (or a 1qqa, for short) is a 1qfa equipped with mixed states and quantum operators with no use of initial state and final state. More formally, a 1qqa M is a quadruple (Q, Σ, {A σ } σ∈ Σ , Λ 0 ), where each A σ is a quantum operation on the Hilbert space of linear operators on the configuration space and Λ 0 is a Hermitian operator acting on the same space. This machine M can produce a matrix A | cx$ for any given input x ∈ Σ * . Notice that A | cx$ (B) is a Hermitian matrix for any Hermitian B. From this fact, we say that a Hamiltonian H is generated by a 1qqa M if H coincides with A | cx$ (Λ 0 ). As a natural extension of 1qqa's, in a model of 2-way classical-head quantum quasi-automaton (or 2cqqa), firstly we apply either a quantum operation A σ to a finite quantum register or a projection measurement on the quantum register and, secondly we use a deterministic procedure to apply A σ when a two-way tape head reads an input symbol σ; in the case of a measurement, we apply A σ,τ instead, where τ is a result of the measurement.

Similarly to [START_REF] Nakanishi | Quantum pushdown automata with garbage tape[END_REF], a 1-way quantum pushdown quasi-automaton (or a 1qpdqa) is a 1-way quantum finite automaton equipped with a stack in which we can push and pop stack symbols as an input tape head reads input symbols.

Adiabatic Evolution of a Quantum System

Loosely following [START_REF] Farhi | Quantum computation by adiabatic evolution[END_REF], we briefly discuss how a quantum system evolves according to the Schrödinger equation of the following general form: ı d dt |ψ(t) = H(t)|ψ(t) for a time-dependent Hamiltonian H(t) and a time-dependent quantum state |ψ(t) . To carry out adiabatic quantum computation, we prepare two Hamiltonians H ini and H f in acting on the same Hilbert space and, for a suffi-ciently large constant T > 0, we define

H(t) = 1 -t T H ini + t T H f in for a time parameter t ∈ [0, T ], provided that [H ini , H f in ] = 0. To ensure [H ini , H f in ] = 0,
we often use the Hadamard basis for H ini and the computational basis for H f in [START_REF] Farhi | A quantum evolution algorithm applied to random instances of an NP-complete problem[END_REF].

At time t = 0, we assume that the quantum system is initialized to be the ground state |ψ g (0) of H ini . We allow the system to gradually evolve by applying H(t) discretely from time t = 0 to t = T . Let |ψ(t) denote the quantum state at time t ∈ [0, T ]. This evolutionary process is referred to as an adiabatic evolution according to H for T steps. We take the smallest value T for which |ψ(T ) is ε-close to the ground state of H f in . For convenience, we call this T the minimum evolution time of the system. The runtime of the system is then defined to be T •max t∈[0,T ] H(t) and the outcome of the system is the quantum state |ψ(T ) . The adiabatic theorem [START_REF] Kato | On the adiabatic theorem of quantum mechanics[END_REF][START_REF] Messiah | Quantum Mechanics[END_REF] gives a lower bound on T . The following assertion is taken from [START_REF] Aharonov | Adiabatic quantum computation is equivalent to standard quantum computation[END_REF]. For any constant δ > 0, if For a practical simulation of the system, it is useful to consider a refinement of the time intervals. Let R be a fixed number satisfying T R and consider a refined time interval of

T ≥ Ω H f in -Hini 1+δ ε δ min t∈[0,T ] {∆(H(t)) 2+δ } ,
[ jT R , (j+1)T R ] for each index j ∈ [0, R -1] Z .
Lemma 6. Given a quantum system (n, ε, H ini , H f in ) of adiabatic evolution, let T be the minimum evolution time. Let U T denote a unitary matrix satisfying

|ψ(T ) = U T |ψ(0) . Let R be a number with T R. Let α j = 1 T R 1 -2j+1 2R and β j = 1 T R 2j+1 2R for each index j ∈ [0, R-1] Z . It then follows that U T can be approx- imated by the matrix V R = e -ıα R Hini • e -ıβ R H f in • • • e -ıα1Hini • e -ıβ1H f in .

Adiabatic Evolutionary Quantum Systems

Our major target of this exposition is decision problems (or equivalently, languages). Instead of searching solutions as in [START_REF] Farhi | A quantum evolution algorithm applied to random instances of an NP-complete problem[END_REF], we are asked to determine "acceptance" (yes) or "rejection" (no) of any given input string. Let us define our quantum systems that evolve adiabatically. Since adiabatic quantum computation is dictated by the ground states of an initial Hamiltonian and a final Hamiltonian, we thus need to specify these Hamiltonians for each given input.

We loosely adapt the definition of Aharonov et al. [START_REF] Aharonov | Adiabatic quantum computation is equivalent to standard quantum computation[END_REF] but modify it significantly to match our purpose. First of all, we wish to realize adiabatic quantum computation by a new notion of an adiabatic evolutionary quantum system (or an AEQS, pronounced as "eeh-ks"). An AEQS S is a septuple (m, Σ, ε, {H

(x) ini } x∈Σ * , {H (x) f in } x∈Σ * , {S (n) acc } n∈N , {S (n) rej } n∈N ), where m : Σ * → N is a size function, Σ is an (input) alphabet, ε is an accuracy bound in [0, 1], both H (x) ini and H (x)
f in are Hamiltonians acting on the same Hilbert space of 2 m(x) dimension (where this space is referred to as the system's evolution space), and S (n) rej ) is called an (acceptance/rejection) criteria pair ). The func-tion m(x) is called the (system) size of S, expressing how large the evolution space is.

An evolution process of an AEQS can be described as in Section 2.3. Letting T x indicate the minimum evolution time of this system, we define

H (x) (t) to be 1 -t Tx H (x) ini + t Tx H (x)
f in for any real number t ∈ [0, T x ]. At time t = 0, the AEQS is initialized to be the ground state |ψ g (0) of H (x) (0) (= H (x) ini ). The system slowly evolves by applying H (x) (t) discretely from time t = 0 to t = T x . The AEQS is considered to take the runtime of

T x • max t∈[0,Tx] H (x) (t) .
To solve a mathematical problem using the adiabatic evolution of a quantum system, following [START_REF] Farhi | A quantum evolution algorithm applied to random instances of an NP-complete problem[END_REF], we may assume that H

(0) of H (x) ini is |u 0 if u 0 satisfies that u 0 ∈ S (x) 0 and h(u 0 ) = min{h(u) | u ∈ S (x) 0 }.
To work on decision problems, in particular, we need to specify accepting and rejecting quantum states in the evolution space on which H (x) (t) acts. This can be done by incorporating the two sets S To determine the outcome of an AEQS, we want to design the AEQS to make the ground state of H . The adiabatic quantum size complexity of L is m(x), where "x" expresses a "symbolic" input.

Proof Sketch of Lemma 1. Let Σ be any alphabet and let L be any language over Σ. For each fixed string x ∈ Σ * , we define an AEQS S x as follows:

H (x) ini = |--| and H (x) f in = |L(x) L(x)|, where |-= 1 √ 2 (|0 -|1 ) and L(x) = 1 -L(x)
for every input x ∈ Σ * and L(x) is the characteristic function of L. Note that the ground state of H

(x) ini is |+ = 1 √ 2 (|0 + |1 ) and that of H (x)
f in is |L(x) . It then follows that x ∈ L iff S x outputs L(x). The accuracy of S x thus turns out to be 1.

2

We consider a complexity class of decision problems solved by certain AEQSs.

Definition 8. Let F indicate a set of conditions imposed on Hamiltonians. The complexity class, highly-accurate AEQS(F), is the collection of all languages, each of which is recognized by a certain AEQS on each input with accuracy at least an absolute constant ε ∈ (1/2, 1] and Hamiltonians of the AEQS satisfy the conditions specified by F. Since we discuss mostly highly-accurate AEQS's in the subsequent sections, we often drop the prefix "highly-accurate" and simply call them AEQS's.

As an example, we may use F to specify a type of quantum quasi-automata, such as 1qqa's. We may also use F to refer to the condition that the spectral gaps of Hamiltonians are at most the reciprocal of a certain polynomial. By the adiabatic theorem, this condition implies that the corresponding AEQSs run for polynomially many steps.

One of the difficulties that we face in constructing an AEQS is how to prepare its Hamiltonians, in particular, H

f in and to define (acceptance/rejection) criteria pairs (S (n) acc , S (n) rej ). In this exposition, we aim at relating AEQSs to quantum finite automata. Since AEQSs are dictated by Hamiltonians, we say that an AEQS S is generated by 1qqa's if (1) there exist two 1qqa's M 0 and M 1 such that H rej for any pair i, j ∈ N. We can expand this definition to 2cqqa's and 1qpdqa's. Possibly, we can relax Condition 92) by requiring a one-way reversible finite automaton (or 1rfa) to determine whether or not "q is in S (n) acc " (as well as "q is in S (n) rej ") from inputs of the form (1 n , q). In the subsequent section, we will demonstrate how to design (or program) AEQSs for the simple languages given in Proposition 2.

How to Program AEQSs: Proof of Proposition 2

In what follows, we will demonstrate only (1)-(2) of Proposition 2.

(1) We want to construct the desired AEQS for the language L a = {ax | x ∈ {0, 1} * } for each fixed string a ∈ {0, 1} * . Here, we consider only the simplest case where a = 0. Write Σ for {0, 1} for simplicity.

Our goal is to construct H

(x) ini = W 3 diag(0, 1, 1)W † 3 , H (0y)
f in = diag(1, 3/4, 1/4), and H (1y) f in = diag(1, 1/4, 3/4) using 1qqa's, where W 3 is an appropriate 3 × 3 unitary matrix forcing the condition [H

(x) ini , H (x) f in ] = 0. Since the ground energy of H (x)
f in is 1/4, it follows that the spectral gap is {q 0 }. We choose Λ 0 = |q 0 q 0 | + |q 1 q 1 |. We further define Kraus operators {A σ,i } σ∈ Σ,i∈ [START_REF] Farhi | A quantum evolution algorithm applied to random instances of an NP-complete problem[END_REF] as follows. f in = |q 0 q 0 | + L even (x)|q 1 q 1 | + L even (x)|q 2 q 2 |, where L even (x) is the characteristic function of L even and L even (x) = 1 -L even (x). The ground state of H Aharonov et al. [START_REF] Aharonov | Adiabatic quantum computation is equivalent to standard quantum computation[END_REF] demonstrated how to simulate quantum circuits by adiabatic quantum computation with polynomial overhead. Our concern here is the AEQSs of constant size, and thus our situation significantly differs from their's.

(x) = |x|, Q = {q | c , q 0 , q 1 }, S (|x|
Let A | c,1 |q | c = |q | c , A | c,2 |q 0 = 1 √ 2 |q | c , A | c,3 |q 0 = 1 √ 2 |q 0 , A | c,4 |q 1 = 1 √ 2 |q | c , A | c,5 |q 1 = 1 √ 2 |q 1 , and A $,i = A | c,i . Moreover, let A 0,1 |q | c = |q 0 , A 0,2 |q 0 = |q 0 , A 0,3 |q 1 = |q 1 , A 1,1 |q | c = |q 1 , A 1,2 = A 0,
Proof Sketch of Theorem 3. We intend to show that 1MOQFA ⊆ AEQS(1qqa, constsize, copnstgap, 0-energy). Let L ∈ 1MOQFA and choose a 1moqfa M = (Q, Σ, {| c, $}, {U σ } σ∈ Σ , q 0 , Q acc , Q rej ) for L with error probability at most ε for a certain constant ε ∈ [0, 1/2). For simplicity, we assume that |Q| is of the form 2 k0 for a certain constant k 0 ∈ N + and that all elements in Q are expressed as k 0 -bit strings. Let ρ 0 = |q 0 q 0 | and ρ i+1 = U xi ρ i U † xi for each i ∈ [0, n + 1] Z , where x i denotes the (i + 1)th symbol of | cx$. Let P acc and P rej be two projections onto the Hilbert spaces H acc and H rej spanned by {|q | q ∈ Q acc } and {|q | q ∈ Q rej }, respectively. Note that, for any x ∈ L, tr(P acc ρ n+2 ) ≥ 1 -ε and, for any x / ∈ L, tr(P rej ρ n+2 ) ≥ 1 -ε. Our goal is to show how to simulate M by a suitable AEQS. We define H

  rej also satisfies F, where S (n) acc and S (n)

  of all indices for which |u are eigenvectors of H (x) ini and h(u) is a real value associated with |u . The ground state |ψ g

  rej . We define QS (n) acc and QS (n) rej respectively to be the Hilbert spaces spanned by {|u | u ∈ S (n) acc } and {|u | u ∈ S (n) rej }. We call QS (n) acc and QS (n) rej the accepting space and the rejecting space, respectively.

Definition 7 .

 7 sufficiently "close" to a certain accepting or rejecting quantum state, which belongs to QS(m(x)) acc ∪ QS (m(x)) rej . The closeness of the ground state of H (x)f in to such a quantum state corresponds to the accuracy of the AEQS to the desired solution of a decision problem on each input x. Given a decision problem L and any constant ε ∈ [0, 1/2), we say that an AEQS S = (m, Σ, ε, {H(x) ini } x∈Σ * , {H (x) f in } x∈Σ * , {S (n) acc } n∈N , {S (n) rej } n∈N )solves (or recognizes) L with accuracy at least ε if (i) for each input x ∈ Σ * , there exists a unique ground state |ψ g (0) of H (x) ini , (ii) for any string x ∈ L, the ground state of H (x) f in is (1 -ε)-close to a certain quantum state in QS (m(x)) acc , and (iii) for any string x ∈ Σ * -L, the ground state of H (x) f in is (1 -ε)-close to a certain quantum state in QS (m(x)) rej

  are generated respectively by M 0 and M 1 for each input x ∈ Σ * , and (2) S

) acc = {q 1

 1 } and S (|x|) rej =

  [START_REF] Ambainis | Algebraic results on quantum automata[END_REF] , and A 1,3 = A 0,3 . For all other pairs (σ, i) ∈ Σ ×[START_REF] Farhi | A quantum evolution algorithm applied to random instances of an NP-complete problem[END_REF], let A σ,i |q = 0. It then follows that5 i=1 A † σ,i A σ,i = I for any σ ∈ Σ. It is not difficult to show that A | c0y$ (Λ 0 ) = H (0y) f in and A | c1y$ (Λ 0 ) = H (1y)f in . (2) Next, we are focused on the reversible unary languageL even = {a 2n | n ∈ N}. Let m(x) = |x|, Q = {q 0 , q 1 , q 2 }, S(|x|) acc = {q 1 }, and S (|x|) rej = {q 2 }. Let U | c |q 0 = |q 1 , U | c |q 1 = |q 0 , U | c |q 2 = |q 2 , and U $ = I. Moreover, let U a |q 0 = |q 0 , U a |q 1 = |q 2 , and U a |q 2 = |q 1 . It then follows that, for any inputx ∈ {a} * , U | cx$ |q 0 = |q 1 if x ∈ L even and U | cx$ |q 0 = |q 2 if x / ∈ L even . Let us define H (x) f in = U | cx$ Λ 0 U † | cx$ ,where Λ 0 = q∈Q-{q0} |q q|. Since U | cx$ |q 1 = |q 0 and U | cx$ |q 2 = |q 2 if x ∈ L even , and |q 1 otherwise, it follows that H (x)

  becomes |q 1 if x ∈ L even , and |q 2 otherwise. Therefore, we obtain ∆(H(x) f in ) = 1.Note that the ground energy is 0.4 Basic Simulations between QFAs and AEQSs

4. 1

 1 Proof of Theorem 3

  of the desired AEQS as H(x) ini = W ⊗k0 Λ 0 W ⊗k0 and H (x) f in = U | cx$ Λ 0 U † | cx$ , where Λ 0 = q∈Q-{q0} |q q|. For each x ∈ Σ * , let |φ x = U | cx$ |q 0 . By the definition of H (x) f in , |φ x is its ground state because H (x) f in |φ x = U | cx$ ΛU † | cx$ U | cx$ |q 0 = U | cx$ Λ|q 0 = 0. Note

  then |ψ(T ) (with an appropriately chosen global phase) is ε-close to the ground state of H f in , provided that H(t) has a unique ground state for each value t ∈ [0, T ].

This model is called general quantum finite automata in a survey[START_REF] Ambainis | Automata and quantum computing[END_REF].

This is a completely positive, trace preserving map and is also called a superoperator.

that, if x ∈ L, then P acc |φ x 2 ≥ 1 -ε. This implies that there is a vector

cx$ is unitary, {|ψ q } q∈Q-{q0} consists of all nonzero eigenvectors and they must be 1. Therefore, the spectral gap of

Finally, we are ready to describe the proof of Theorem 4. This proof is composed of two critical simulations between AEQSs and 1qfa's with mixed states and quantum operators. Since REG = 1QFA mix , it suffices to simulate such a 1qfa by an appropriately chosen AEQS. Lemma 9. Any 1qfa M with mixed states and quantum operators can be exactly simulated by a certain AEQS whose Hamiltonians are generated by certain linearsize 1qqa's with the spectral gap of 1 and the ground energy of 0.

Proof of Theorem 4. Let L be any regular language. Take a 1qfa M with mixed states and quantum operators that recognizes L with bounded-error probability. By Lemma 9, there exists an AEQS S that simulates M . 2


1 The term "progressive," as employed in this article, refers to any theory or doctrine advocating human progress in all areas of life, notably through emphasis on social equality and individual freedom, as opposed to a conservative thought, which sees social inequality as the natural and eternal condition of humanity. 2 For a brief history of the terms "reaction" and "reactionary", see, for example,

A Reactionary Dimension in Progressive Revolutionary Theories?

The Case of James Connolly's Socialism Founded on the Re-Conversion of Ireland to the Celtic System of Common Ownership

Olivier Coquelin

The terms "reaction" and "reactionary" were coined during the French Revolution to describe those conservative groups and individuals opposed to the progressive 1 tenets of the revolutionaries, who looked back nostalgically to the traditional rules of the Ancien Régime. 2 According to the political theorist Andrew Heywood, both terms have since been mainly used to refer to three different expressions of conservative thought: opposition to any change or innovation so as to preserve the existing order in the name of traditions and customs inherited from the past; desire to reform the existing order so as to protect it from destruction; desire to change or destroy the existing order so as to restore the vestiges of a prestigious past. 3 While the first two features are generally viewed as moderate forms of reactionary politics, the latter takes on a more radical hue to the point of being sometimes of a revolutionary nature-as in the school of thought known as the "conservative revolution" launched by

A REACTIONARY DIMENSION IN PROGRESSIVE REVOLUTIONARY THEORIES?

German intellectuals in 1918 in order to re-establish the position of spiritual and political leadership held by Germany in Europe at the time of the medieval Holy Roman Empire. 4 However, if credence is given to one of the commonest definitions of the concept of revolution, understood as a dramatic break from any existing order "to bring about something altogether new," to quote Hannah Arendt, 5 one may wonder whether the above-mentioned radical reactionaries are genuine revolutionaries. Since their intentions are inspired by ancient paradigms, they cannot be perceived as "altogether new," but merely new as regards the present system. If such is not the case, does this mean that only radical progressive theories or movements -some of them adopting the slogan "of the past let us wipe the slate clean" 6 -can be described as authentically revolutionary? This is disputable, to say the least, because any thorough analysis of those radical progressive theories-at least from the 18 th century-will reveal some elements celebrating a bygone mythical and glorious past which is used as a vindication of any movement or struggle for the establishment of a new order or society. For example, certain 18 th century English reformers and radicals extolled the restoration of the ancient Anglo-Saxon democracy; 7 4 Andrew Heywood, Political Ideas and Concepts: An Introduction (London: The Macmillan Press, 1994), 285-93. For a detailed analysis of the conservative revolutionary movement in Germany, see for example Roger Woods, The Conservative Revolution in the Weimar Republic (Basingstoke: Palgrave Macmillan, 1996). 5 Hannah Arendt, On Revolution (Harmondsworth: Penguin Books, 1973, orig. 1963), 21. 6 Line of the famous song called the Internationale which was originally written and composed in France in the latter half of the 19 th century, and has since been widely sung throughout the world by many radical and revolutionary activists and sympathizers, including the communists, the anarchists, the socialists, and the social democrats. 7 Among the key figures of 18 th century English radicalism adhering to the notion of lost Anglo-Saxon democracy was John Cartwright (1740-1824). His proposals, as expressed in his 1776 pamphlet Take Your Choice, prefigured the Chartist programme of the late 1830s and the 1840s, notably through his advocacy of annual parliaments, the secret ballot, and universal male suffrage. On this topic,

OLIVIER COQUELIN

certain 19 th century socialists and communists were inspired by classless primitive societies-including ancient Celtic societies-based on common ownership of land; 8 the contemporary anarcho-primitivists are advocating a return to the egalitarian ways of life of primitive societies; 9 etc. Hence, one may ask the following questions: To what extent are progressive revolutionary theories imbued with a reactionary dimension? Can the oxymoron "progressive reactionary" be used as opposed to conservative reactionaries? In this case, wouldn't the dialectical divide between progressive and conservative be more pertinently employed than that between progressive and reactionary? In an attempt to answer the above questions, this article will explore some aspects of the revolutionary theories drawn up by the Irish historical figure, James Connolly (1868-1916), whose socialism 10 was based on the idea of re-converting Ireland to the Celtic system of common ownership. In so doing it will not fail to see, for example, Edward Royle and James Walvin, English Radicals and Reformers, 1760-1848 (Lexington, Massachusetts: University Press of Kentucky, 1982). 8 This category encompasses in particular the Marxists, as we shall see below. 9 At the root of anarcho-primitivism was a castigation of civilization and its concomitant destructive effects on nature and humanity, as opposed to the more environmentally-friendly, peaceful and egalitarian pre-civilized period. One of the major figures of the anarcho-primitivist movement is the American philosopher, John Zerzan (1943-), who in 2005 edited a collection of essays written by radical thinkers, including Henry David Thoreau, Charles Fourier, William Morris, Ivan Illich, Fredy Perlman, etc., whose ideas had greatly inspired anarcho-primitivism from the 1970s. See John Zerzan, ed., Against Civilization: Readings and Reflections (Los Angeles: Feral House, 2005). For a more comprehensive approach to anarcho-primitivism, see the essay written by the British anarchist author, John Moore (1957-2002) entitled "A Primitivist Primer: What is Anarcho-Primitivism?" Available from Eco-Action-Ecological Direct Action <http://www.eco-action.org/dt/primer.html> (accessed 15 September, 2008). 10 "Socialism" is used in this article as a generic term to refer to the various theories conceived in the 19 th century and advocating collective ownership and management of the means of production, capital, land, property, etc., in the interest of the community as a whole. It is worth noting here that in the Marxist theory of historical materialism socialism also represents the transitional stage between capitalism and communism.

A REACTIONARY DIMENSION IN PROGRESSIVE REVOLUTIONARY THEORIES?

separate myth from reality as for Connolly's use of Celtic Ireland in the theoretical expression of his progressive revolutionary designs. James Connolly was born in 1868 in Edinburgh (Scotland) of Irish parents. Sharing the same miserable living conditions as most Irish immigrants in Edinburgh, from the age of ten Connolly was compelled to hold a number of unskilled jobs to supplement the meagre income of his family. When he was fourteen, he joined the British army. As a soldier, he spent a few years in Ireland, where he supposedly developed strong patriotic feelings towards the land of his parents and ancestors. In 1889, he deserted the army, returned to Scotland and married his fiancée, Lillie Reynolds, the following year. The young couple took up residence in Edinburgh. During these Scottish years Connolly became active in socialist politics and trade-union affairs. He became a cobbler in 1895, but his business suffered because he was more interested in politics than in profits. As a result, in May 1896 he emigrated to Dublin, where he was hired as a paid organiser of the Dublin Socialist Club, which was shortly afterwards renamed as the Irish Socialist Republican Party (ISRP). Financial difficulties forced him to move once more. He reached the United States in 1903 and became a member of Daniel De Leon's Socialist Labor Party (SLP), the Industrial Workers of the World (IWW), and Eugene Debs' Socialist Party of America (SPA). Upon his return to Ireland in 1910, he joined the Irish Socialist Party and the Irish Transport and General Workers' Union (ITGWU) founded by James Larkin in 1908. In July 1911, he was made the secretary and organiser of the Transport Union in Belfast. He conscientiously carried out his duties during the 1913 Dublin Lock-Out, and in October 1914 was elected the head of the ITGWU and of the Irish Citizen Army (ICA). The latter was a paramilitary body created in the middle of the Dublin great industrial dispute of 1913 to protect strikers against police brutality. From 1915 onwards, under Connolly's leadership, the Citizen Army was involved into the struggle for national independence. Consequently, Connolly agreed to act in conjunction with the Military Council of the Irish Republican Brotherhood (IRB) in January 1916, thereby allying his minute Citizen Army with the nationalist militia, known as the Irish Volunteers and ruled by the revolutionary IRB. As a member of the Provisional Government of the Irish Republic, Connolly was one of the OLIVIER COQUELIN main architects of the abortive Easter Rising of 1916 during which he was seriously wounded. Forced to surrender with the other surviving rebels, after a week of street fighting in Dublin against the British troops, he was court-martialled and executed by a firing squad in May 1916, thus following fifteen other rebel leaders to the grave. 11 While Connolly was undoubtedly a man of action dedicated to the achievement of his dearest ideals, he could also be described as a genuine thinker. Despite the fact that he left school at the age of ten, life granted him opportunities to educate himself. His determination to raise his intellectual level eventually bore fruit, as he became recognized as a historian, an economist, a journalist, a songwriter, a poet, and a playwright. But it was above all his political writings that brought him fame as a non-doctrinaire Marxist theoretician. Indeed, originating from an Irish background firmly attached to the Motherland's destiny, Connolly was not insensitive to Irish national demands, which he tailored to his Marxist-inspired thinking, as in the following passage he wrote in 1896:

The struggle for Irish freedom has two aspects: it is national and social. Its national ideal can never be realized until Ireland stands forth before the world a nation free and independent. It is social and economic; because no matter what the form of government may be, as long as one class owns as their private property the land and instruments of labor, from which all mankind derive their subsistence, that class will always have it in their power to plunder and enslave the remainder of their fellow-creatures. 12 A REACTIONARY DIMENSION IN PROGRESSIVE REVOLUTIONARY THEORIES?

But Connolly's Marxist approach to Irish history also led him to draw his theoretical inspiration from the ideals of primitive communism13 which had supposedly survived in Celtic Ireland until the mid-seventeenth century. Thus, guided notably by the research of such a prominent 19 th century anthropologist as Lewis Morgan (1818-81), he asserted as early as 1897 that "Nationalism without Socialism -without a reorganisation of society on the basis of a broader and more developed form of that common property which underlay the social structure of Ancient Erin -is only national recreancy." 14 The assumption that socialism was "the modern application of the social principle which underla[id] the Brehon laws,"15 often recurred in Connolly's work, but was first somewhat theorized in his 1897 pamphlet entitled Erin's Hope: The End and the Means, in which he tried to demonstrate, among other things, that in the 17 th century the English government imposed on Ireland a social order which had been previously unknown in Ireland, namely feudalism. For, before this dramatic change occurred, the Celtic system of clan or common ownership had been based on the democratic principle that property belonged to the community and was subservient to the interests of the people. An Irish system that was, to quote Connolly's own words, "on a par with those conceptions of social rights and duties which we find the ruling classes to-day denouncing so fiercely as 'Socialistic.'" 16 When the English rulers realized that the national subjection of Ireland could not be achieved as long as the politically subjected nation remained economically free, they strove to overcome this obstacle by instituting the lands of the tribe as the private property of the chief. As a result, the chief

OLIVIER COQUELIN

was constrained to relinquish his Irish title, the symbol of a free election, to an English title, such as duke or earl, in accordance with a "thoroughly individualistic" English civilization. Thus emerged Irish landowners who adhered to a new social order against which their forefathers had struggled until the break-up of the Kilkenny Confederation 17 in 1649 when the clans were dispersed. And to eradicate "a social system abhorrent to the best traditions of a Celtic people," 18 Connolly argued that the Irish nation could not rely on a native bourgeoisie which was inclined to treason, contrary to the working class which, "in emancipating [themselves] (…) must, perforce, free [their] country." 19 He also advocated the establishment of a socialist republic in such a way as to abolish "the dread of foreign competition and render perfectly needless any attempt to create an industrial hell in Ireland." 20 Irish agricultural production, henceforward democratically managed, would be used first to feed the people and, when needed, to purchase the manufactured goods produced only abroad. Connolly underscored the importance of the Irish workers as the true inheritors of the ancient Celtic social traditions to fight independently of a propertied class, which would most probably be inclined to defend the socio-economic status quo in a politically emancipated Ireland. 21 This essay laid the foundations for what was to become thirteen years later Connolly's major work, namely Labour in Irish History, in which he blatantly pronounced himself to be in favour of "the re- 17 The "Kilkenny Confederation" was founded in 1642 as a result of the rebellion launched the previous year by Irish Catholic gentry to deter any invasion of the country by visceral anti-Catholic English Long Parliament and Scottish Covenanters. The Kilkenny Confederation was to control most of the Irish territory and to join forces with a royalist coalition against the "Rump Parliament" in 1648.

A REACTIONARY DIMENSION IN PROGRESSIVE REVOLUTIONARY THEORIES?

conversion of Ireland to the Gaelic principle of common ownership by a people of their source of food and maintenance." 22 Connolly's Ireland, therefore, was imbued with "the Gaelic ideas of equality and democracy," extirpated from the mid-seventeenth century in an effort to instil in the minds of the Irish people "feudal ideas of the divine right of kings to rule, and of subjects to unquestionably obey." 23 But how relevant were Connolly's assumptions in relation to the historical facts? Since his death in 1916, most comprehensive studies have actually somewhat contradicted Connolly's belief that a primitive form of communism based on common ownership of land had prevailed in Ireland until the demise of the Gaelic culture and civilization in the midseventeenth century. Thus, for example, in his 1921 Celtic Ireland, the eminent scholar of Irish history Eoin MacNeill (1867-1945) firmly emphasized that no documents offered any conclusive evidence as to the collective nature of the lands owned by the tribe (túath), and in so doing agreed wholeheartedly with what Sir Henry Maine (1822-88) had already alluded several decades before when writing that "all the Brehon writers seem (…) to have a bias towards private (…), as distinguished from collective, property". 24 This assertion has been more or less explicitly confirmed in more recent surveys and research works by, among others, D.A. Binchy, Gearóid Mac Niocaill, Kenneth Nicholls, Joseph Peden, Fergus Kelly, and Dáibhí Ó Cróinín. 25 These studies suggest that the term 22 James Connolly, "Labour in Irish History", in Connolly, CW, 22. 23

OLIVIER COQUELIN

"communism" used by Connolly to designate the socio-economic structure of Gaelic Ireland is inappropriate for two major reasons: first, because Gaelic society was highly hierarchical and aristocratic; and second, because private ownership of assets, including lands and cattle, was a determining factor for a man's status and grade in Gaelic society.

Thus, prior to the Norman invasion in the latter half of the 12 th century, the population of Celtic Ireland was legally divided into two main categories: the "free" (sóer) who were de jure members of the assembly of the basic political unit of Celtic Ireland, namely the túath, in which, among other things, the king (rí) was elected;26 and the "unfree" (dóer) who were barred from these assemblies. The free men actually comprised all the landowners, including the kings, noblemen (flaith), and commoners (ócaire and bóaire), themselves subdivided into various social strata depending on the amount of assets and the number of clients each free man in his respective class possessed. In addition to the landowners, other prominent figures of Gaelic society belonged to the category of free men: the poets (fili), the musicians-the most prominent of them being the harpists (cruit)-the lawyers (brithem and aigne), the clergymen-among whom were the monks (manach), the priests (sacerdos), and the abbots (abb) -the physicians (liaig or midach), and the skilled craftsmen-more precisely the wood craftsmen (sáer), the blacksmiths (gobae), the silversmiths (cerd), and the coppersmiths (umaige). The "unfree" class, for its part, encompassed all the landless men among whom were the outlaws, the tenants at will (bothach and fuidir), the serfs (sen-chléithe), and the "male" and "female" slaves (mug and cumal). 27 This means that elements of chattel slavery and feudalism were present in Gaelic society, and it was a feudal system which during the five centuries long conquest

A REACTIONARY DIMENSION IN PROGRESSIVE REVOLUTIONARY THEORIES?

of Ireland by England (from the 12 th to the 17 th century) was to be gradually implemented in lieu of the socio-political order governed by Brehon laws, which nonetheless underwent endemic revival between the 13 th and the 16 th century. 28 Obviously all these parameters ran counter to Connolly's theory of an egalitarian and democratic Celtic Ireland. However, some aspects of communal property and organization really had a legal existence in Gaelic Ireland, as the non-privately owned woodlands and mountain peaks used equally by all members of the túath, or the kin-group (fine) which, to quote Gearóid Mac Niocaill, "in some respects (…) often acted as a kind of cooperative,"29 in the form of arrangements between kinsmen for jointownership, joint-tenancy and joint-farming (including joint-ploughing and joint-pasturing), and of collective decisions made by the members of the derb-fine30 as regards land affairs. 31 Moreover, Gaelic society contained some indisputable "progressive" or "liberal," not to say "libertarian"32 tendencies (at least by modern standards and if compared with feudal England and Europe), particularly in regard to such issues as women's land and property rights, marriage and sexual life, contractual relationships, social mobility, criminality, etc. 33

OLIVIER COQUELIN

One may also argue in Connolly's defence that, as Joseph Peden points out, the original translations of the old Irish law tracts carried out by Eugene O'Curry (1794-1862) and John O'Donovan (1806-61) and published between 1864 and 1901 were filled with errors and inaccuracies which undoubtedly misled many otherwise competent and influential historians, such as Patrick Joyce (1827-1914) in his 1906 Social History of Ancient Ireland, or Prosper Boissonnade (1862-1935) who, in his 1921 Life and Work in Medieval Europe, asserted notably that:

The soil of Ireland (belonging) to 184 tribes or clans (…) the clans held the land in common (…) no man held individual property save his household goods, and each held only the right of usufruct over his strip of tribal domain (…) in each district of Ireland the free population lived communistically in immense wooden buildings (…) they lived and fed in common, seated on long benches, and all the families of the district slept there upon beds of reeds... 34 In fact, only the philological explorations of the old Irish texts by leading Celticists, including Eoin MacNeill, were to give rise to different interpretations of Gaelic Ireland. 35 Hence, it is clear that Connolly has been unjustly charged by at least one of his biographers with having idealized the social organisation of ancient and medieval Ireland, an idealization purportedly deriving from "an uncritical reading of the Brehon laws." 36 As distinct from this assumption, other commentators have suggested that Connolly's use of Celtic Ireland was rather intended to dissociate the Irish Labour movement from a condescending and dogmatic British counterpart through the revival of what Connolly Nicholls,[59][60][61][62][63][64][83][84][85][86][87]Mac Niocaill,[49][50][51][52][53][54][55][56][66][67] Quoted in Peden, "PRCIL", 81-82. See also Prosper Boissonnade, Life and Work in Medieval Europe (New York: Harper Torch, 1964, orig. 1921)

A REACTIONARY DIMENSION IN PROGRESSIVE REVOLUTIONARY THEORIES?

perceived as symbols, myths and memories of a genuine past likely to be combined with contemporary socialist political issues in a revolutionary attempt to overthrow a social system resulting from a rupture produced by the colonial process. Connolly's revolutionary scheme actually disregarded the orthodox Marxist concept of development stages, especially the stage of industrial modernization, which was seen as an offspring of capitalism. His idea, instead, was to modernize and democratise an essentially agricultural Ireland in a process inspired by ancient Celtic paradigms which had undergone over two centuries of near extinction. 37 Thus, the reactionary element in Connolly's revolutionary theories and designs is also implicitly highlighted by this alternative interpretation.

It is therefore in his ambition to re-convert Ireland to an indisputable mythical Celtic system of common ownership that one can see that Connolly's progressive revolutionary theories encompassed a reactionary dimension in line with a Marxist tradition to which he belonged (even though he was non-dogmatic). That reactionary dimension in Marxist thought was implicitly expressed by Friedrich Engels in his Origin of the Family, Private Property and the State, published in 1884. Using Lewis Morgan's anthropological methodology, Engels (1820-95) argued that in the successive stages of human progress the three main modes of production characteristic of the civilized period, namely slavery, feudalism and capitalism, were responsible for the evils suffered by the vast majority of human beings exploited by a ruling class closely associated with the development of the State. By contrast, in the preceding stages of savagery and barbarism, "production was essentially collective, just as consumption proceeded by direct distribution of the products within larger or smaller communistic communities." Stateless

OLIVIER COQUELIN

"communistic communities" which, as Connolly was also to assert later, had survived in the particular case of Ireland until the seventeenth century when the English jurists "were sent over to transform the clan lands into domains of the English crown." Civilization as a modern phenomenon based on the exploitation of man by man, consequently, had to be eradicated through a revolution aimed at the resurgence and modernization of the principles and production relations prevailing in the preceding eras. And, to support and conclude his argument, Engels cited Lewis Morgan who had written in reference to civilization: Democracy in government, brotherhood in society, equality in rights and privileges, and universal education, foreshadow the next higher plane of society to which experience, intelligence and knowledge are steadily tending. It will be a revival, in a higher form, of the liberty, equality and fraternity of the ancient gentes. 38 Hence, the basically reactionary character underpinning the Marxist theory of historical materialism reveals itself in the attention given to the successive modes of production which it identifies in human history, ranging from primitive to "modern" communism, and including slavery, feudalism, capitalism, and socialism. The fundamental difference with the traditional reactionaries, accordingly, lies in the ideological nature of their respective revolutionary aims: conservative and elitist for the traditional right-wing reactionaries, progressive and egalitarian for the Marxist-oriented reactionaries. It remains to be seen, as part of a future study, to what extent the other modern and contemporary progressive revolutionary theories of those notably mentioned in the introduction to this article may be described as reactionary.

37

  David Lloyd, "Rethinking National Marxism: James Connolly and 'Celtic Communism'", Interventions: International Journal of Postcolonial Studies, 5(3) (Nov. 2003): 345-370; David Lloyd, "Why Read Connolly?", Interventions: International Journal of Postcolonial Studies, 10(1) (2008): 116-123; Jonathan Githens-Mazer, "Ancient Erin, Modern Socialism: Myths, Memories and Symbols of the Irish Nation in the Writings of James Connolly", Interventions: International Journal of Postcolonial Studies, 10(1) (2008): 86-101.

  The following year, the Confederation led by Owen Roe O'Neill (1590-1649) was finally defeated by Oliver Cromwell's New Model Army. The defeat completed the conquest of Ireland by England initiated in the latter half of the 12 th century. For a detailed study of the Kilkenny Confederation, see, for example,

	Pádraig Lenihan, Confederate Catholics at War, 1641-49 (Cork: Cork University
	Press, 2001).
	18 Connolly, EHEM,10.

19 Ibid., 21. 20 Ibid., 20. 21 Ibid.,[5][6][7][8][9][10][11][12][13][14][15][16][17][18][19][20][21][22][23]

  Ibid., 19. 24 See Sir Henry Sumner Maine, Lectures on the Early History of Institutions, 7 th edition (London: John Murray, 1914, orig. 1874), 105. See also Eoin MacNeill, Celtic Ireland (Dublin: Academic Press, 1981, orig. 1921), 146. 25 See notably D.A. Binchy, "Secular Institutions", in Early Irish Society ed.

	Myles Dillon, 52-65 (Dublin: At the Sign of the Three Candles, 1954); Gearóid
	Mac Niocaill, Ireland before the Vikings (Dublin: Gill and Macmillan, 1972), 42-
	70; Kenneth Nicholls, Gaelic and Gaelicised Ireland in the Middle Ages (Dublin:
	The Lilliput Press, 2003, orig. 1972), 22-147; Joseph R. Peden, "Property Rights
	in Celtic Irish Law", Journal of Libertarian Studies, 1(2) (1977): 81-95; Fergus
	Kelly, A Guide to Early Irish Law (Dublin: Dublin Institute for Advanced
	Studies, 2005, orig. 1988); Dáibhí Ó Cróinín, Early Medieval Ireland, 400-1200
	(Harlow: Longman, 1995), 63-146.

  , 78-79. Boissonnade's book was first published in French in 1921 under the title of Le Travail dans l'Europe Chrétienne au Moyen Age; it was first translated into English by Eileen Power in 1927. 35 Peden, ibid., 81-82.

36 See Allen,[35][36][37][38][39][40]

It is interesting to note here that since 1920 James Connolly has been the subject of numerous biographical essays. The latest one, published in 2005, was the work of the former General Secretary of the Irish Congress of Trade Unions, Donal Nevin. See Donal Nevin, James Connolly: A Full Life (Dublin: Gill and Macmillan, 2005).

James Connolly, "Irish Socialist Republic: To the Irish People (issued in 1896 and republished in March 1908 in The Harp)", in James Connolly: The Lost Writings ed. Aindrias Ó Cathasaigh, (London: Pluto Press, 1997), 98.

The term "communism," as used in the present study, refers to egalitarian, stateless and classless societies in which the means of production and property are owned and managed in common.

James Connolly, "Socialism and Nationalism," in James Connolly, CollectedWorks, Vol.1 (Dublin: New Books Publications, 1987), 307.

The Workers' Republic, 13 August, 1898. Quoted in R.M. Fox, James Connolly: the Forerunner (Tralee: Kerryman Press, 1946), 46; Kieran Allen, The Politics of James Connolly (London: Pluto Press, 1990), 36.

James Connolly, Erin's Hope: the End and the Means (Dublin: New Books Publications, 1972, orig. 1897), 8.

However, some historians argue that the free commoners, although members of the assembly of the túath, were nonetheless excluded from the process of electing a new king, an electoral process which therefore would have been the exclusive prerogative of the noblemen. Such a statement was made, for example, by D. Blair Gibson (El Camino College, USA) in his paper entitled, "Celtic Democracy: Appreciating the Role Played by Alliances and Elections in Celtic Political Systems" presented at the 28th Annual Harvard CelticColloquium, on October 11, 2008.

For a concise description of the social structure of Gaelic Ireland, see Kelly, 7-98.

Nicholls, Ó Cróinín,[110][111][112][113][114][115][116][117][118][119][120][121][122][123][124]

Mac Niocaill, 51.

The derb-fine was a kin-group whose male members descended from a common great grandfather.

For example, the "kin-land" could not be sold and alienated without the consent of all the male members of the derb-fine.

See, for example, Joseph R. Peden, "Stateless Societies: Ancient Ireland", The Libertarian Forum (April 1971): 3-4, 8.

As regards Irish women, despite the fundamentally patriarchal nature of Gaelic society, they nonetheless enjoyed rights that were denied to their counterparts by most legal systems in Christian Europe. For example, in the case when a man had no male offspring, his daughter(s) could inherit his land and property, and managed the full production of it. The Brehon laws also allowed women to divorce their husbands in certain circumstances (sexual dissatisfaction, illtreatment, abandonment, etc.). On the "socialistic" and "progressive" aspects of Gaelic Ireland, seeKelly,[11][12][99][100][101][102][103][104][105][106][107][108][109][214][215][216][217][218][219][220][221][222][223][224] Ó Cróinín,

My italics. See Friedrich Engels, The Origin of the Family, Private Property and the State (Hottingen-Zurich: 1884). Available from the Marxists Internet Archive (MIA, http//marx.org/) <http://ww w.marxists.org/archive/marx/works/1884/origin-family/index.htm> (accessed September 24, 2008).