text:
# The Representation of Natural Numbers in Quantum Mechanics

## I Introduction

As is well known numbers play an essential role in physics and in many other disciplines. The results of both experimental work and theoretical computations are often given as numbers. Comparison of these numbers is essential to the validation process for any physical theory such as quantum mechanics. As inputs to or outputs of computations or experiments, numbers correspond to states of physical systems. From an information theoretic viewpoint, this correspondence is essential as these states carry information. As Landauer has emphasized, ”Information is Physical” . This is taken very seriously here.

However, the fact that many states of many physical systems correspond to numbers, has, for the most part, been assumed and used implicitly. There has been little attempt to make explicit the assumptions and conditions involved in representing numbers by states of physical systems.

This paper represents one approach to making some of the assumptions and conditions explicit. The emphasis is on the mathematical and physical aspects in the representation of numbers by states of physical systems. No new models of computation are presented. However making the assumptions explicit does offer some insight into the importance of various conditions that may not have been realized so far. An example (Section V) is the essential role played by the condition that there exist physically realizable dynamical operators that can efficiently implement basic arithmetic operations. The fact that these conditions are satisfied for a wide variety of systems, as shown by the ubiquitous existence of computers, does not detract from their importance.

Such a study is also relevant to the development of a coherent theory of mathematics and physics together, which, in one form or another, is a goal of many physicists . Any such coherent theory must take account in detail of how numbers are represented by states of physical systems.

In this paper considerations will be limited to quantum systems. This is not a serious limitation because of the assumed universal applicability of quantum mechanics or a related theory such as quantum field theory. In this case all physical systems are quantum systems and all states of these systems are (pure or mixed) quantum states. This is the case whether the systems are microscopic or macroscopic or whether macroscopic systems can be described by classical mechanics.

For quantum systems numbers are represented by tensor products of states of different degrees of freedom of a system. Usually the system is composite with each degree of freedom associated with a component system. For microscopic systems one condition systems must satisfy is that they have states for which the switching time, $`t_{sw}`$, is short compared to the decoherence time $`t_{dec}`$ or $`t_{sw}t_{dec}`$ . This is a dynamic condition as it is based on the Hamiltonian for the systems including their interaction with other systems and the environment.

This condition eliminates many state spaces of microscopic quantum systems for representation of numbers. A 2-dimensional example would be the state space based on two highly excited states of nuclei that have halflives short compared to $`t_{sw}`$. On the other hand spin projection states of spin $`1/2`$ ground state nuclei in in molecules in a magnetic field are suitable and are used in NMR quantum computers .

Macroscopic quantum systems are such that $`t_{sw}t_{dec}`$ for all states of interest. In this case the systems are candidates for number representation for classical computation if the systems have states that are stabilized by environmental interactions for times long compared to the switching time. The widespread existence of macroscopic computers shows that both $`t_{sw}t_{dec}`$ and environmental stabilization occurs for many quantum systems.

Because of the recent widespread interest in quantum computing, the emphasis of this paper is on number representation by states of microscopic quantum systems. However most of the material also applies to macroscopic systems.

The first step in giving an exact meaning to the representation of numbers by tensor product states of quantum systems is to specify exactly what natural numbers are. Without such a specification all computations are meaningless physical operations. Here the axiomatic approach is used by defining a nonempty set as a set of all natural numbers if it is a model of the axioms of number theory or arithmetic . These axioms are discussed in the next section along with changes needed to account for the limitation of this paper to tensor product states with an arbitrary but fixed finite number $`L`$ of components, or $`kary`$ representations of length $`L`$. The corresponding arithmetic becomes arithmetic modulo $`k^L`$.

It is possible to model the axioms directly on a physical Hilbert space $`^{phy}`$ describing a composite quantum system with $`L`$ components. However the literature on quantum computing makes much use of product qubit states of the form $`|\underset{¯}{s}`$ where $`\underset{¯}{s}`$ is any function from $`1,2,\mathrm{},L`$ to $`\{0,1\}`$. Since the Hilbert space of these states is a very useful reference base for discussing quantum computation that is independent of any physical model, this approach will be used here.

To this end a purely mathematical model of these axioms is described in Section III that is based on a tensor product Hilbert space $`^{arith}=_{j=1}^L_j`$ of $`L`$ $`k`$ dimensional Hilbert spaces $`_j`$. Unitary operators on this space are defined to correspond to the basic arithmetic operations, successor, plus, and times, whose properties are given by the axioms. The presence of $`L`$ successor operators, one for each power of $`k`$, rather than just one as described by the axioms, is based on the condition of efficient implementation discussed later on.

Tensor product states of physical properties of microscopic composite quantum systems belonging to the Hilbert space $`^{phy}`$ are discussed in Section IV. A priori these states, as products over a label set $`A`$ of $`L`$ physical parameter values, do not correspond to any number. Also operators on these states are meaningless regarding any numerical interpretation.

This is remedied by describing tensor product preserving unitary operators from $`^{arith}`$ to $`^{phy}`$. For each of these operators, $`^{phy}`$, along with induced representations of the operators for the basic arithmetic operations, becomes a model for the axioms of modular arithmetic.

So far nothing has been said about the physical realizability of any of these models of the axioms. This is especially relevant for the operators as they are many system nonlocal operators. This is remedied in Section V where the important condition of efficient implementability of the basic arithmetic operations is described. In essence the condition requires that a composite quantum system be such that there exist physically realizable Hamiltonians that can implement the basic arithmetic operations. In addition the space-time and thermodynamic resources required for implementation must be polynomial in $`L`$. The importance of this condition rests in the fact that it is additional to and independent of the axioms of arithmetic. To see this one notes that there are many models of the axioms that do not satisfy this requirement. A simple physical model is any one based on an unary representation of the numbers as most arithmetic operations are inefficient in this representation.

The question arises if use of $`^{arith}`$ can be bypassed by modeling the axioms directly on $`^{phy}`$ where $`^{phy}`$ has an arbitrary tensor product structure. In general this is possible as any structure satisfying the axioms is acceptable. The discussion of this in Section VI is based on a description of properties of a set of operators indexed by a set of physical parameters. The properties are also defined to address the question of necessary and sufficient conditions to conclude that $`^{phy}`$ must have a tensor product structure suitable for length $`L`$ $`kary`$ representations of numbers.

A final section discusses some other aspects and open questions resulting from this work. The importance of the efficient implementability condition in excluding most models of modular arithmetic on $`^{phy}`$ is noted as are some aspects of the use of numbers to describe $`kary`$ representations of length $`L`$.

It must be emphasized that the work of this paper is one attempt to make explicit the assumptions and conditions that are assumed implicitly in the representation of numbers by states of quantum systems and in work in the the literature on quantum computing. Examples of this work are given in papers by Beckman et. al.  and Vedral et.al. that describe networks of quantum gates to carry out basic arithmetic operations. The description is in terms of unitary operators on $`^{arith}`$ (extended to include ancillary qubits) as ordered products of polynomially many elementary gate operators. The distinction between physical models, with the associated requirement of efficient physical implementation, and mathematical models is not maintained (and is not needed) in the papers. Also efficient physical implementability implies more than minimizing the number of ancillary qubits and restriction to polynomially many gate operations. These aspects are discussed more in Sections III and V.

## II The Axiomatic Description of Numbers

The first step in making explicit what is involved in the representation of numbers by quantum states is to define the natural numbers. One method of doing this is to follow mathematical logic and define any nonempty set to be a set of natural numbers if it is a model for the axioms of arithmetic or number theory . A model for any axiom system is a collection of elements in which all the axioms are true.

Here the main interest is models of arithmetic based on Hilbert spaces that are tensor products of an arbitrary but fixed number of component spaces. As a result the axioms to be satisfied are those for arithmetic modulo $`N`$ where $`N`$ is arbitrary but fixed. This arithmetic satisfies some of the axioms for all natural numbers. Others need to be either deleted or modified. It also satisfies axioms for a commutative ring with identity .

The exact form and content of axioms for modular arithmetic is not important here. What is important is that both the arithmetic and ring axioms have in common the required existence of binary operations $`+`$ and $`\times `$ with certain properties. Also an unary successor operation $`S`$ is required by the arithmetic axioms. The properties the binary operations must have include commutativity, associativity, the existence of identities $`0`$ and $`S(0)`$ for $`+`$ and $`\times `$, and the distributivity of $`\times `$ relative to $`+`$. Also $`S`$ commutes with $`+`$ and $`x\times S(y)=x\times y+x`$ for all $`x,y`$.***The importance of these axioms lies in the requirement of the existence of binary operations $`+,\times `$ with certain properties. The fact that some of the axioms may be redundant is of no importance here. The arithmetic axioms defining an order relation and the induction schema are not considered as they are not needed for the purposes of this paper. However it is useful to keep in mind that the ordering axioms establish the discreteness of the natural numbers in the sense that there is no number between $`x`$ and its successor $`S(x)`$.

## III Abstract Hilbert Space Models

The next step is the description of a purely mathematical model of these axioms based on whatever mathematical systems are appropriate for the physical systems being considered. Since interest here is in $`kary`$ representations of length $`L`$ of natural numbers for composite quantum systems, a model based on an abstract Hilbert space $`^{arith}`$ is needed. To this end let $`^{arith}=_{j=1}^L_j`$ be an $`L`$ fold tensor product Hilbert space where $`_j`$ is a $`k`$ dimensional Hilbert space.

For each $`j`$, the basis states of interest in $`_j`$ have the form $`|\mathrm{},j`$ where $`j`$ denotes the label or property characterizing a qubyte and $`\mathrm{}=0,1,\mathrm{},k1`$. A product state basis in $``$ can be given in the form $`|\underset{¯}{s}=_{j=1}^L|\underset{¯}{s}(j),j`$ where $`\underset{¯}{s}`$ is any function from $`1,\mathrm{},L`$ to $`0,\mathrm{},k1`$. (Here qubits or qubytes  refer to quantum bits or bytes of information for $`k=2`$ or $`k2`$ respectively.)

The presence of the parameter $`j`$ in the state and not as a subscript, as in $`_{j=1}^L|\underset{¯}{s}(j)_j`$, is required as the action of operators corresponding to the basic arithmetic operations depends on the value of $`j`$. It is not possible to express this dependence if $`j`$ appears as a subscript of $``$ and not between $`|`$ and $``$.

An important function of the axioms is to provide properties of the unary operation $`S`$ and the binary operations $`+`$ and $`\times `$. For reasons based on efficient implementation (Section V), it is quite useful to define $`L`$ different successor operators, $`V_j^{+1}`$, for $`j=1,\mathrm{},L`$. These operators are defined to correspond to the addition of $`k^{j1}modk^L`$ where $`V_1^{+1}`$ corresponds to $`S`$ in the axioms. These operators and those for $`+`$ and $`\times `$ correspond to the basic arithmetic operations.

It is to be emphasized that definitions of the $`+,`$ and $`\times `$ are given to show their dependence on the $`V_j^{+1}`$. Also they are required by the axioms of arithmetic. The purpose is definitely not to present the definitions as something new as these operators are widely used.

For instance the widely discussed networks of quantum gates are examples of the abstract models considered here for $`k=2`$. In the networks the states in $`^{arith}`$ are represented by horizontal qubit lines and ordered products of gate operators represent operators in $`B(^{arith})`$. Specific examples of this for the basic arithmetic operations of addition, multiplication and modular exponentiation are described in .

It is also the case that in many physical models space and time directions can be assigned to the abstract networks. In this case the spatial ordering of the qubit lines is part of any mapping of the abstract models based on $`^{arith}`$ to physical models based on $`^{phy}`$ in which the corresponding component systems are distinguished by spatial positions. These mappings are examples of the mappings ”$`g`$” discussed in Section IV. The time ordering of the quantum gates corresponds to mapping the ordering of gate operators in the abstract model to a time ordered product of physically implementable quantum gate operators. This is part of the requirement of physical implementability (Section V).

### A Definitions of the $`V_j^{+1}`$

The definition of the $`V_j^{+1}`$ is straightforward. For each $`j`$ let $`u_j`$ be a cyclic shift  of period $`k`$ that acts on the states $`|\mathrm{},j`$ according to $`u_j|\mathrm{},j=|\mathrm{}+1modk,j`$. $`u_j`$ is the identity on all states $`|m,j^{}`$ where $`j^{}j`$. Define $`V_j^{+1}`$ by

$$V_j^{+1}=\{\begin{array}{cc}u_jP_{(k1),j}+V_{j+1}^{+1}u_jP_{(k1),j}\hfill & \text{if }1j<L\hfill \\ u_L\hfill & \text{if }j=L\hfill \end{array}$$
(1)
Here $`P_{(k1),j}=|k1,jk1,j|1_j`$ is the projection operator for finding the $`j`$ component state $`|k1,j`$ and the other components in any state. $`P_{m,j}`$ and $`u_j`$ satisfy the commutation relation $`u_jP_{m,j}=P_{m+1,j}u_jmodk`$ for $`m=0,\mathrm{},k1`$. Also $`P_{(k1),j}=1P_{(k1),j}`$. This follows from the fact that the label spaces for each qubyte are one dimensional so that the operator $`1_j|jj|1_j`$ is the identity on the Hilbert space spanned by the $`k^L`$ states $`|\underset{¯}{s}`$

This definition is implicit in that $`V_j^{+1}`$ is defined in terms of $`V_{j+1}^{+1}`$. An explicit definition is given by

$`V_j^{+1}`$ $`=`$ $`{\displaystyle \underset{n=j}{\overset{L}{}}}u_nP_{(k1),n}{\displaystyle \underset{\mathrm{}=j}{\overset{n1}{}}}u_{\mathrm{}}P_{(k1),\mathrm{}}`$ (3)
$`+{\displaystyle \underset{\mathrm{}=j}{\overset{L}{}}}u_{\mathrm{}}P_{(k1),\mathrm{}}`$
In this equation the unordered product is used because for any $`p,q`$, $`u_mP_{p,m}`$ commutes with $`u_nP_{q,n}`$ for $`mn`$. Also for $`n=j`$ the product factor with $`j\mathrm{}n1`$ equals $`1`$.

There are two basic properties the operators $`V_j^{+1}`$ must have: they are cyclic shifts and, for each $`j<L`$, they satisfy

$$(V_j^{+1})^k=V_{j+1}^{+1}$$
(4)
Also if $`j=L`$ then $`(V_L^{+1})^k=1`$. To show that $`V_j^{+1}`$ is a shift, let $`|\underset{¯}{s}`$ be a product state such that for each $`m=1,2,\mathrm{},L`$ the component states $`|\underset{¯}{s}_m,u_m|\underset{¯}{s},(u_m)^2|\underset{¯}{s},\mathrm{},(u_m)^{k1}|\underset{¯}{s}`$ are pairwise orthonormal. It then follows from Eq. 3 and the properties of the $`u_m`$ that any product state $`|\underset{¯}{s}`$ is orthogonal to the state $`V_j^{+1}|\underset{¯}{s}`$ and that $`V_j^{+1}`$ is norm preserving on these states.

Assume that Eq. 4 is valid. Then for each $`j`$ $`(V_j^{+1})^{k^{Lj+1}}=1`$. This, and the facts that for all tensor product states $`|\underset{¯}{s},V_j^{+1}|\underset{¯}{s}`$ is also a tensor product state which is orthogonal to $`|\underset{¯}{s}`$, show that $`V_j^{+1}`$ is a cyclic shift. The existence of a tensor product basis that is common to all the $`V_j^{+1}`$ follows from Eq. 4.

To prove Eq. 4 it is easiest to use Eq. 1. Since $`V_{j+1}^{+1}`$ commutes with $`u_{\mathrm{}}P_{n,\mathrm{}}`$ for all $`\mathrm{}j`$ and the commutation relations $`P_{n,j}u_j=u_jP_{(n1),j}`$ and $`P_{n,j}u_j=u_jP_{(n1),j}`$ hold, one has for each $`mk`$

$$(V_j^{+1})^m=(u_j)^m\underset{\mathrm{}=1}{\overset{m}{}}P_{(k\mathrm{}),j}+V_{j+1}^{+1}(u_j)^m(\underset{\mathrm{}=1}{\overset{m}{}}P_{(k\mathrm{}),j}).$$

Here $`P_{n,j}=1P_{n,j}`$. For $`m=k`$ the term with the product of the projection operators gives $`0`$ and the sum of the projection operators gives unity. The desired result follows from the fact that $`(u_j)^k=1`$. Also $`(V_L^{+1})^k=1`$ follows directly from the definition of $`V_L^{+1}`$.

The above shows that informally the action of $`V_j^{+1}`$ corresponds to addition $`modk^L`$ of $`k^{j1}`$ on the product basis. This cannot yet be proved as addition $`modk^L`$ has not yet been defined. Also the adjoint $`(V_j^{+1})^{}`$ of $`V_j^{+1}`$ corresponds informally to subtraction $`modk^L`$ of $`k^{j1}`$. This can be seen from the fact that $`(V_j^{+1})^{}V_j^{+1}=1`$ where

$`(V_j^{+1})^{}`$ $`=`$ $`{\displaystyle \underset{n=j}{\overset{L}{}}}P_{(k1),n}u_n^{}{\displaystyle \underset{\mathrm{}=j}{\overset{n1}{}}}P_{(k1),\mathrm{}}u_{\mathrm{}}^{}`$ (6)
$`+{\displaystyle \underset{\mathrm{}=j}{\overset{L}{}}}P_{(k1),\mathrm{}}u_{\mathrm{}}^{}.`$
This result is obtained using the commutativity of the shifts and projection operators for different component systems.

It should be noted that the operators $`V_j^{+1}`$ play an important role in quantum computation. This is the case even though for each product state $`|\underset{¯}{s}`$ the state $`V_j^{+1}|\underset{¯}{s}`$ is also a product state and is not a linear superposition of these states. The importance comes from the fact that these operators along with their efficient implementation are used to define the basic arithmetic operations for a quantum computer and to carry out quantum algorithms. For example in Shor’s factoring quantum algorithm , they are used in the step in which the function $`f_y(s)=y^smodN`$ is calculated for each component state $`|\underset{¯}{s}`$.

### B Plus

It is straightforward to define the plus ($`+`$) operation in terms of the $`V_j^{+1}`$. To ensure unitarity the definition will be based on states of the form $`|\underset{¯}{s,w}=|\underset{¯}{s}|\underset{¯}{w}`$ that describe two $`L`$ qubyte product states.

To define the $`+`$ operation let $`V_j^+\mathrm{}=(V_j^{+1})^{\mathrm{}}`$ represent $`\mathrm{}`$ iterations of $`V_j^{+1}`$. Then $`+`$ is defined by

$`+|\underset{¯}{s}|\underset{¯}{w}`$ $`=`$ $`|\underset{¯}{s}V_L^{+s_L}V_{L1}^{+s_{L1}}\mathrm{}V_2^{+s_2}V_1^{+s_1}|\underset{¯}{w}`$ (8)
$`=|\underset{¯}{s},\underset{¯}{s+w}`$
Here the numeral expression $`|\underset{¯}{s+w}`$ is defined to be that generated from $`\underset{¯}{w}`$ by the action of the product $`_{j=1}^LV_j^{+s_j}`$. Note that the different $`V_j^{+1}`$ commute.

For pairs of product states, which are first used here, the domains of the functions $`\underset{¯}{s}`$ and $`\underset{¯}{w}`$ must be different. This is based on the requirement that an algorithm must be able to distinguish components of $`|\underset{¯}{s}`$ from components of $`|\underset{¯}{w}`$. This can be achieved by setting $`|\underset{¯}{s}|\underset{¯}{w}=|\underset{¯}{sw}`$ where $`\underset{¯}{sw}`$ denotes the concatenation of $`\underset{¯}{w}`$ to $`\underset{¯}{s}`$. That is, $`\underset{¯}{sw}`$ is a function from $`1,\mathrm{},2L`$ to $`0,\mathrm{},k1`$ where $`\underset{¯}{sw}(h)=\underset{¯}{s}(h)`$ for $`hL`$ and $`\underset{¯}{sw}(h)=\underset{¯}{w}(hL)`$ for $`h>L`$.

As defined the $`+`$ operator is unitary on the Hilbert space spanned by all pairs of length $`L`$ numeral expression states. Thus a reversible implementation of it is possible where the procedure makes use of the procedures for implementing the $`V_j^{+1}`$. Eq. 8 shows that the procedure can be carried out by carrying out, for each $`j=1,2,\mathrm{},L`$, $`s_j`$ iterations of $`V_j^{+1}`$ where $`s_j`$ is the number $`\underset{¯}{s}(j)`$ associated with the qubyte state $`|\underset{¯}{s}(j),j`$ in $`|\underset{¯}{s}=_{j=1}^L|\underset{¯}{s}(j),j`$. Since $`+`$ is unitary, so is the adjoint, $`+^{}`$. Since $`+`$ was defined to correspond to addition modulo $`k^L`$, the adjoint corresponds to subtraction modulo $`k^L`$. That is if $`+|\underset{¯}{s}|\underset{¯}{w}=|\underset{¯}{s}|\underset{¯}{s+w}`$ then $`+^{}|\underset{¯}{s}|\underset{¯}{s+w}=|\underset{¯}{s}|\underset{¯}{w}`$.

### C Times

Here a definition of multiplication is given that is based on efficient iteration of $`+`$ and is similar to the method taught in primary school. The method is efficient relative to that for $`+`$.

Reversibility of the operations requires that the operator $`\times `$ be unitary. (Caution: the adjoint of $`\times `$ is not division.) This means that both input product states and the product state with the result must be preserved. It is also convenient to have one extra product state for storing and acting on intermediate results. This state begins and ends as $`|\underset{¯}{0}`$. For initial states of the form, $`|\underset{¯}{s},\underset{¯}{w},\underset{¯}{0},\underset{¯}{0}=|\underset{¯}{s}|\underset{¯}{w}|\underset{¯}{0}|\underset{¯}{0}`$,

$$\times |\underset{¯}{s},\underset{¯}{w},\underset{¯}{0},\underset{¯}{0}=|\underset{¯}{s},\underset{¯}{w},\underset{¯}{0},\underset{¯}{s\times w}$$
(9)
where $`|\underset{¯}{s\times w}`$ is the state resulting from the action of $`\times `$. It is supposed to correspond to the result of multiplying, $`modk^L`$, the numbers corresponding to the states $`|\underset{¯}{s}`$ and $`\underset{¯}{w}`$.

In order to define $`\times `$ explicitly one needs to be able to generate the states $`|\underset{¯}{k^{j1}\times w}`$ corresponding to multiplication of $`w`$ by $`k^{j1}`$. For each $`j=1,\mathrm{},L`$ these states are added to themselves $`s_j`$ times. The final result is obtained by adding all the resulting states so obtained. Details are provided in the Appendix.

### D Required Properties of the $`V_J^{+1}`$, Plus, Times

As was noted the operators $`V_j^{+1},+,\times `$ must satisfy the properties expressed by the axioms for modular arithmetic. These include the axioms for arithmetic  modified for modularity and the p\[resence of $`L`$ successors, and possibly axioms for a commutative ring with identity .

Properties that must be satisfied include that expressed by Eq. 4 and the requirements that the successor operations commute with $`+`$, (i.e. $`+(1V_j^{+1})=(1V_j^{+1})+`$), the existence of additive and multiplicative identities, which are the states $`|\underset{¯}{0}`$ and $`|\underset{¯}{1}=V_1^{+1}|\underset{¯}{0}`$, and the distributivity of $`\times `$ over $`+`$. Also $`+`$ and $`\times `$ are associative and commutative.

Proof of these properties from the definitions and Eq. 4, which has already been proved, is straight forward and will not be given here. Note that the proofs of some of the properties do use the corresponding properties of the numbers appearing in the exponents. For example to prove that addition is commutative, $`|\underset{¯}{s+w}=|\underset{¯}{w+s}`$, Eqs. 8 and 3 give $`|\underset{¯}{s+w}=_{h=1}^L(V_j^{+1})^{s_h+w_h}|\underset{¯}{0}`$ and $`|\underset{¯}{w+s}=_{h=1}^L(V_j^{+1})^{w_h+s_h}|\underset{¯}{0}`$. The equality of these two states follows from $`s_h+w_h=w_h+s_h`$ for each $`h`$.

## IV Physical Hilbert Space Models

The Hilbert space models described so far are purely abstract in that they do not refer to any physical properties. They do however, serve as a common reference point for models based on physical properties of physical systems. They also give a useful method to associate numbers with quantum states of these systems.

To begin, let $`A`$ and $`B`$ be sets of $`L`$ and $`k`$ different physical parameters or values of some physical properties or observables $`\widehat{A}`$ and $`\widehat{B}`$. The $`A`$ parameters are used to distinguish or label different components of a composite quantum system and $`B`$ is a set of values of a different physical property associated with each component system. For example $`A`$ could be a set of $`L`$ arbitrary locations of component spin $`1/2`$ systems on a 2 dimensional surface and $`B=\{,\}`$ denoting spin aligned along or opposite some axis of quantization. Another example, representative of NMR quantum computation , has $`A`$ as a set of hyperfine splittings of nuclear spin states and $`B=\{,\}`$. Here the values of $`A`$ must contain sufficient information so the physical process can distinguish between the different nuclear spins.

Let $`\underset{¯}{t}`$ be any function from $`A`$ to $`B`$ and $`|\underset{¯}{t}=_{aϵA}|\underset{¯}{t}(a),a`$ be the corresponding tensor product state. Let $`^{phy}=_{aϵA}_a`$ be the $`k^L`$ dimensional Hilbert space spanned by all the states $`|\underset{¯}{t}`$. Each $`_a`$ is a $`k`$ dimensional Hilbert space spanned by states of the form $`|h,a`$ where $`hϵB`$.

The presence of $`a`$ as a separate part in each component state $`|\underset{¯}{t}(a),a`$, and not as a state subscript as in $`|\underset{¯}{t}(a)_a`$, is essential as an algorithm uses the value of $`a`$ to distinguish the different component systems. This is based on the view that the state of the composite quantum system contains all the quantum information available to the algorithm. In particular the states must contain sufficient information so that the algorithm can distinguish among the component systems. This is especially the case for any algorithm whose dynamics is described by a Hamiltonian that is selfadjoint and time independent. This is an example of Landauer’s dictum ”Information is Physical” .

This description can be generalized in that the physical property observable $`\widehat{B}`$ of the component systems can depend on the values of $`a`$ in $`A`$. An example this, which also has different component systems replaced by different degrees of freedom of one system, is shown by an ion trap example . Here the states of one degree of freedom are the ground and first excited state of the ion in the harmonic well trap. The corresponding states of the other are the ground and first excited electronic state of the ion. This type of generalization will not be pursued here.

### A Representation of Numbers and Arithmetic Operations in $`^{phy}`$

The goal here is for states in $`^{phy}`$ to represent numbers. However, it is clear that, a priori, neither the product states $`|\underset{¯}{t}=_{aϵA}|\underset{¯}{t}(a),a`$ nor linear superpositions of these states represent numbers. For the $`|\underset{¯}{t}`$ the reason is that there is no association between the labels $`a`$ and powers of $`k`$; also there is no association between the range set $`B`$ of $`\underset{¯}{t}`$ and the numbers $`0,1,\mathrm{},k1`$.

This can be remedied by use of unitary maps from $`^{arith}`$ to $`^{phy}`$ that preserve the tensor product structure. One way of doing this is to let $`g`$ and $`d`$ be any bijections (one-one onto) maps from $`1,2,\mathrm{},L`$ to $`A`$ and from $`0,1,\mathrm{},k1`$ to $`B`$. For each pair $`g,d`$ and each $`j`$ there is a corresponding unitary operator $`w_{g,d,j}`$ that maps states $`|h,j`$ in $`_j`$ where $`0hk1`$ to states in $`_{g(j)}`$ according to $`w_{g,d,j}|h,j=|d(h),g(j)`$. This induces a unitary operator $`W_{g,d}=_{j=1}^Lw_{g,d,j}`$ from the product space $`^{arith}`$ to $`^{phy}`$ where

$`W_{g,d}|\underset{¯}{s}=`$ $`_{j=1}^Lw_{g,d,j}|\underset{¯}{s}(j),j`$ (10)
$`=`$ $`_{j=1}^L|d(\underset{¯}{s}(j)),g(j)=|\underset{¯}{s}_g^d.`$ (11)
Here $`|\underset{¯}{s}_g^d`$ is the physical parameter based state in $`^{phy}`$ that corresponds, under $`W_{g,d}`$ to the number state $`|\underset{¯}{s}`$ in $`^{arith}`$.

This process can be inverted, using the adjoint $`W_{g,d}^{}`$ to relate physical parameter states in $`^{phy}`$ to number states in $`^{arith}`$. One has

$`W_{g,d}^{}|\underset{¯}{t}=`$ $`_{aϵA}w_{g,d,g^1(a)}^{}|\underset{¯}{t}(a),a`$ (12)
$`=`$ $`_{aϵA}|d^1(\underset{¯}{t}(a)),g^1(a)=|\underset{¯}{t}_{g^1}^{d^1}.`$ (13)
Here $`|\underset{¯}{t}_{g^1}^{d^1}`$ is the number state in $`^{arith}`$ corresponding to the physical state $`|\underset{¯}{t}`$. Note that $`W_{g,d}^{}=W_{g^1,d^1}`$ where $`g^1,d^1`$ are the inverses of $`g`$ and $`d`$, and $`w_{g^1,d^1,a}=w_{g,d,g^1(a)}^{}`$.

The operators $`W_{g,d}`$ also induce representations of the $`V_j^{+1},+,`$ and $`\times `$ operators on the physical parameter states in $`^{phy}`$. For the $`V_j^{+1}`$ one defines $`V_{g,j}^{d,+1}`$ by

$$V_{g,j}^{d,+1}=W_{g,d}V_j^{+1}W_{g,d}^{}.$$
(14)
An equivalent definition can be given by direct reference to the maps $`g,d`$ and the operators $`w_{g,d,j}`$:

$`V_{g,j}^{d,+1}`$ $`=`$ $`{\displaystyle \underset{n=j}{\overset{L}{}}}u_{g(n)}^dP_{d(k1),g(n)}{\displaystyle \underset{\mathrm{}=j}{\overset{n1}{}}}u_{g(\mathrm{})}^dP_{d(k1),g(\mathrm{})}`$ (16)
$`+{\displaystyle \underset{\mathrm{}=j}{\overset{L}{}}}u_{g(\mathrm{})}^dP_{d(k1),g(\mathrm{})}.`$
Here $`P_{d(k1),g(\mathrm{})}=w_{g,d,\mathrm{}}P_{k1,\mathrm{}}w_{g,d,\mathrm{}}^{}`$ and $`u_{g(\mathrm{})}=w_{g,d,\mathrm{}}u_{\mathrm{}}w_{g,d,\mathrm{}}^{}`$.

In a similar fashion one can use the $`W_{g,d}`$ to define the operator $`+_{g,d}`$ acting on the physical parameter states in $`^{phy}^{phy}`$. The definition is based on that given for the operator $`+`$ acting on $`^{phy}^{phy}`$ Eq. 8. One has

$$+_{g,d}=(W_{g,d}W_{g,d})+(W_{g,d}^{}W_{g,d}^{}).$$
(17)
The operator $`\times _{g,d}`$ is defined similarly from $`\times `$ as defined in the Appendix.

It is clear from the above that there is no unique correspondence between states in the arithmetic and physical Hilbert spaces. There are $`L!`$ possible bijections $`g`$ and $`k!`$ possible bijections $`d`$. Thus some or many of the $`L!k!`$ unitary operators $`W_{g,d}`$ associate a different physical parameter state $`|\underset{¯}{s}_g^d`$ with the number state $`|\underset{¯}{s}`$. Conversely the $`g`$ and $`d`$ dependence of $`W_{g,d}^{}`$ shows that many different number states $`|\underset{¯}{t}_g^d`$ can be associated with the physical state $`|\underset{¯}{t}`$. The multiplicity of these correspondences depends on the states $`|\underset{¯}{s}`$ or $`|\underset{¯}{t}`$ and the choices of $`g`$ and $`d`$.

It follows from the unitarity of $`W_{g,d}`$ that if the operators $`V_j^{+1},+,\times `$ and the states $`|\underset{¯}{s}`$ in $`^{arith}`$ satisfy the axioms of modular arithmetic, then so do the operators $`V_{g,j}^{d,+1},+_{g.d},\times _{g,d}`$ and states $`|\underset{¯}{s}_g^d`$ in $`^{phy}`$. In this way all the states $`|\underset{¯}{s}_g^d`$ in $`^{phy}`$ and the operators $`V_{g,j}^{d,+1},+_{g,d},\times _{g.d}`$ are a model of the axioms of modular arithmetic. The fact that superposition of the states $`|\underset{¯}{s}_g^d`$ plays an important role in quantum computation does not affect this conclusion.

This argument also applies to any unitary map $`U`$ from $`^{arith}`$ to $`^{phy}`$ independent of whether $`U`$ is tensor product preserving or not. However most of these maps are not of interest because the operators $`UV_j^{+1}U^{}`$ are not physically implementable (Section V). Also the states $`U|\underset{¯}{s}`$ nay not be stable or even preparable.

### B Grover’s and Shor’s Algorithms

Since the spaces $`^{arith}`$ and $`^{phy}`$, and arithmetic models constructed on these spaces are unitarily equivalent, one might think that dynamically an algorithm is independent of the unitary map used. This is not true in general even if one restricts the maps to have the form of $`W_{g,d}`$: some algorithms are independent of these maps and others are not.

To see this one notes that dynamically any quantum algorithm carried out on a composite physical system must be sensitive to the values of the physical parameters for the system. This means that the physical dynamics of an algorithm must be described by some evolution operator acting on the states in $`^{phy}`$ or some other physical model of the system states. The physical dynamics is not described on $`^{arith}`$.

It follows that any algorithm that can be described in terms of states based on physical parameters is independent of the unitary maps $`W_{g,d}`$. The dynamics does not depend on these maps because what number a physical state represents is irrelevant to the algorithm. On the other hand, algorithms that compute numerical functions must be described on $`^{arith}`$ as number is of the essence for these. It follows that the dynamics of these algorithms depends on the maps $`W_{g,d}`$.

Grover’s Algorithm  and Shor’s Algorithm  are examples of the two types of algorithm. Grover’s Algorithm corresponds to a quantum search of a set of data where each element of the data base corresponds to a quantum state. The goal is to find the one unknown but unique state with some property different from the others. Here the quantum state representing each data element will be taken to be a tensor product of qubit states. This is not necessary, as Lloyd  has shown. However, the price for this is the need for an exponential overhead of resources.

Here the relevant feature of Grover’s Algorithm is that it can be both defined and implemented on $`^{phy}`$ with no reference to numbers represented by states in $`^{arith}`$. To see this let $`k=2`$ and $`B=\{,\}`$ for spin up, spin down. The initial state can be written as $`\psi =(1/\sqrt{N})_{\underset{¯}{t}}|\underset{¯}{t}`$ where $`|\underset{¯}{t}=_{aϵA}|\underset{¯}{t}(a),a`$ and $`N=2^L`$.

Dynamically Grover’s Algorithm  consists of iterations of the unitary operator $`WI_\underset{¯}{}WI_{\underset{¯}{t_u}}`$ on $`^{phy}`$. Here $`I_\underset{¯}{}=12|\underset{¯}{}\underset{¯}{}|`$ where $`|\underset{¯}{}`$ is the state with all $`L`$ systems in the $`|`$ state. $`I_{\underset{¯}{t_u}}=12|\underset{¯}{t_u}\underset{¯}{t_u}|`$ and $`W`$ is the Walsh Hadamard transformation. Here $`|\underset{¯}{t_u}`$ is the unknown product state that is to be amplified, and $`W=_{aϵA}(1/\sqrt{2})(\sigma _x+\sigma _z)_a`$ is a tensor product of single qubit operators. The $`\sigma _x,\sigma _z`$ are the Pauli spin operators and $`\psi =W|\underset{¯}{}`$.

Shor’s Algorithm  for finding the two prime factors of a large number is quite different in that it is essential that the tensor product states represent numbers. This can be seen from the steps of the algorithm

$`{\displaystyle \frac{1}{\sqrt{N}}}{\displaystyle \underset{\underset{¯}{s}}{}}|\underset{¯}{s}|\underset{¯}{i}{\displaystyle \frac{1}{\sqrt{N}}}{\displaystyle \underset{\underset{¯}{s}}{}}|\underset{¯}{s}|\underset{¯}{f_m(s)}`$ (18)
$``$ $`{\displaystyle \frac{1}{N}}{\displaystyle \underset{\underset{¯}{w}}{}}|\underset{¯}{w}{\displaystyle \underset{\underset{¯}{s}}{}}e^{2\pi iws/N}|\underset{¯}{f_m(s)}`$ (19)
Here $`|\underset{¯}{i}`$ is the initial product state, usually shown as a constant sequence of $`0s`$. $`f_m`$ is a numerical function defined by $`f_m(x)=m^xmodM`$ where m and $`M`$ are relatively prime. The number $`M`$, which is to be factored, and $`N`$ are related by $`M^22^N2M^2`$ .

Eq. 19 shows that the dynamics of Shor’s algorithm can be initially formulated as a unitary step operator $`U_{Sh}`$ acting on $`^{arith}`$. However, physically, the dynamics is represented by the operator $`W_{g,d}U_{Sh}W_{g,d}^{}`$ acting on $`^{phy}`$. This shows that physically the dynamical implementation of Shor’s Algorithm depends on the numberings $`g`$ and $`d`$ of the physical parameter sets $`A`$ and $`B`$.

More generally the requirement that the numerical function calculated by the algorithm be invariant under any unitary map from $`^{arith}`$ to $`^{phy}`$ means that the physical implementation of the algorithm depends on the unitary map. For example, let $`W_{g,d}`$ be a unitary map as defined by Eq. 11 and $`A`$ be a set of space locations of spin $`1/2`$ systems with spin up $`()`$ spin down $`()`$ representing (through $`d^1`$) $`0,1`$. Then the algorithm dynamics clearly depends on $`g`$ as $`g`$ determines which space location is associated with which power of $`2`$. A similar argument holds for the dynamics dependence on $`d`$. Also the correct interpretation of the measurement of the output depends on both $`g`$ and $`d`$.

## V Efficient Implementability of Arithmetic Operations

Probably the most important requirement is that of efficient implementablity of basic arithmetic operations. This means that, for states of a physical system to represent numbers, it must be possible to physically implement these operations and the implementation must be efficient. This includes at least the operations described by the axioms as efficient implementation of these is a necessary condition for states of a quantum system to represent numbers.

In the case of the $`V_{g,j}^{d,+1}`$ physical implementability means there must exist a physically realizable Hamiltonian $`H_{g,j}^d`$ such that for some time $`t_j`$, $`U_{g,j}^d(t_j)=e^{iH_{g,j}^dt_j}`$ corresponds to carrying out $`V_{g,j}^{d,+1}`$ on the states of the system. As $`V_{g,j}^{d,+1}`$ is unitary, one has $`e^{iH_{g,j}^dt_j}=V_{g,j}^{d,+1}`$. The presence of the indices $`d,g`$ shows the dependence of $`H_{g,j}^d`$ on the $`W_{g,d}`$.

Efficient implementation means that the time $`t_j`$ must be short. For microscopic systems this is equivalent to the condition that $`t_j`$ must be less than the decoherence time $`t_{dec}`$. If the Hamiltonian and system are such that $`V_{g,j}^{d,+1}`$ is carried out in a number $`n_j`$ of basic switching steps of duration $`\mathrm{\Delta }`$, then $`n_j=t_j/\mathrm{\Delta }<t_{dec}/\mathrm{\Delta }`$  must hold.

For macroscopic systems the efficiency requirement is different as $`t_{dec}<<\mathrm{\Delta }`$. In this case $`n_j`$ must be polynomial and not exponential in $`L`$. This means that $`n_j=O(L^c)`$ with $`c0`$ and $`c`$ not too large. $`O()`$ means ”of the order of”.

The efficiency requirement is much stricter for microscopic systems than for macroscopic ones. The reason is that for most systems $`t_{dec}`$ is small . This is one reason why quantum computers are so hard to implement compared to macroscopic computers. However, the requirement that $`n_j`$ be polynomial in $`L`$ would also apply to any microscopic system for which $`t_{dec}/\mathrm{\Delta }`$ is very large, (e.g. $`t_{dec}`$ is several hours or even longer).

The above is rather general in that it assumes that for each $`j`$ there is a distinct Hamiltonian $`H_{g,j}^d`$ to implement $`V_{g,j}^{d,+1}`$. However for many systems all the $`V_{g,j}^{d,+1}`$ may be implemented by just one Hamiltonian $`H_g^d`$ with the different values of $`j`$ expressed by different states of some ancillary systems.

The requirement of efficient implementation is the reason that the $`V_{g,j}^{d,+1}`$ are defined separately for each $`j`$ rather than defining them from $`V_{g,1}^{d,+1}`$ by $`V_{g,j}^{d,+1}=(V_{g,1}^{d,+1})^{k^{j1}}`$. Here $`V_{g,1}^{d,+1}`$ corresponds to the successor operation $`\mathrm{"}+1\mathrm{"}`$ in axiomatic arithmetic . The exponential dependence on $`j`$ shown by this equation shows that if efficient implementation were required just for $`V_{g,1}^{d,+1}`$, then carrying out of the $`V_{g,j}^{d,+1}`$ is not efficient as exponentially many repetitions of the procedure for $`V_{g,1}^{d,+1}`$ would be required.

For many physical systems, efficient implementation of the $`V_{g,j}^{d,+1}`$ can be carried out by shifting the procedure for implementation of $`V_{g,1}^{d,+1}`$ along path $`g`$ in $`A`$ until a component system in the state $`|g(j)`$ is encountered. At this point implementation of $`V_{g,1}^{d,+1}`$ is started.

Efficient implementability for the basic arithmetic operations also implies that there exist Hamiltonians $`H_{g,d}^+`$ and $`H_{g,d}^\times `$ that efficiently carry out $`+_{g,d}`$ and $`\times _{g,d}`$. Since the definitions of $`+`$ and $`\times `$ are given in terms of the $`V_j^{+1}`$,(Eq. 8 and the Appendix), it follows that if the $`V_{g,j}^{d,+1}`$ can be efficiently implemented, so can $`+_{g,d}`$ and $`\times _{g,d}`$. For microscopic systems the fact that the times $`t_+,t_\times `$ required for these implementations are greater than those for the $`V_{g,j}^{d,+1}`$ means that the values of $`L`$ for which $`t_+<t_{dec}`$ and $`t_\times <t_{dec}`$ may be less than those possible for just the $`V_{g,j}^{d,+1}`$.

Another aspect of the efficient implementability condition is that the thermodynamic resources required to implement $`V_{g,j}^{d,+1}`$ must be polynomial and not exponential in $`j`$. This takes account of the fact that all computations occur in a noisy environment and one must spend thermodynamic resources to protect the system from errors. This is especially the case for quantum computation for which entanglements of states that develop as the computation progresses must be protected from decoherence . Methods of protecting these states include the use of quantum error correction codes  and possibly generation and use of EPR pairs . These considerations are another reason why it is important to minimize the time required to implement $`V_{g,j}^{d,+1}`$.

There are many physical systems where the resources needed to implement $`V_{g,j}^{d,+1}`$ (other than those involved in the shift) are either independent of $`j`$ or are at most polynomial in $`L`$. The needed resources do not depend exponentially on $`j`$ or $`L`$. These systems satisfy the requirement of efficient implementability. There are others that do not. Consider, for example, a 1-D lattice of systems where the intensity of environmental interference and noise grows exponentially with $`j`$. Here the thermodynamic resources needed to protect the system from decoherence, etc., would grow exponentially with $`j`$. Another simpler type of system that would be excluded would be a row of isolated harmonic oscillator potentials each containing a single spinless particle. The proposed two qubit states are the ground and first excited states in the well. However the spring constants of the wells depend exponentially on $`j`$. For example the spring constant $`p(j+1)`$ of the $`j+1st`$ well is related to that for the $`jth`$ well by $`p(j+1)=kp(j)`$.

For networks of quantum gates efficient implementation of the basic arithmetic operations has two components. The number of quantum gates (or steps) in the network must be polynomial in $`L`$, as in , and the resources needed to implement individual quantum gates must be polynomial in the locations of the individual systems addressed by each gate. In the physical models described above, this second requirement is not satisfied as resources needed to implement a quantum gate between the $`jth`$ and $`j^{}th`$ qubits depend exponentially on $`j`$ and $`j^{}`$. The fact that one would not build such models or could not build such models for large $`L`$ is not relevant here.

The condition of efficient implementability also places restrictions on the values of $`k`$ allowed for $`kary`$ representations. In general values of $`k`$ are used that are quite small (e.g. $`k=2,k=10`$, etc.). Except for special cases, $`k=1`$ (unary) representations are excluded as arithmetic operations are exponentially hard. Also the value of $`k`$ cannot be too large. One reason is that there are physical limitations on the amount of information that can be reliably stored and distinguished per unit space time volume . Also the requirement of efficient implementation enters in that for large $`k`$ (e.g. $`k=10^6`$), even a simple process such as adding two single digit numbers becomes quite lengthy.

## VI Is the Model $`^{arith}`$ Necessary?

The preceding was based on first constructing a purely mathematical Hilbert space model $`^{arith}`$for mdoular arithmetic and then using this to construct a physical model on a space $`^{phy}`$ that has the same tensor product structure as $`^{arith}`$. The question arises if the purely mathematical model based on $`^{arith}`$ is necessary. Can one go directly from the axioms of modular arithmetic to physical models without the use of the model based on $`^{arith}`$?

In general this is possible as any structure, physical or mathematical, that satisfies the axioms is acceptable. However, the intermediate mathematical models serve as a useful reference point for discussions. This is clear from the literature in which much use is made of such a model. For instance any reference to product qubit states $`|\underset{¯}{0},|0110110\mathrm{}`$, etc. and linear superpositions of these states is implicitly using a model based on $`^{arith}`$.

Another point, already noted, is that the axioms of arithmetic, modular or not, make no mention of efficient implementability. Models based on unary representations are just as valid as are any others. This is true even if additional axioms are added giving the properties of the $`V_j^{+1}`$ operators.

This raises the following questions: Suppose one starts with an arbitrary quantum system with states in a space $`^{phy}`$ whose tensor product structure (if any) is unknown. Can operators, indexed by values in a set of physical parameters for the system, be defined with properties such that they satisfy the axioms of modular arithmetic? As will be seen in the following, this seems possible. If one also requires that the operators and those for the basic arithmetic operations be efficiently implementable, does it follow that $`^{phy}`$ must have a tensor product structure based on the defined operators and their properties? At present, the answer is not known.

To be specific, the interest is in constructing a model of arithmetic $`modk^L`$ directly on the state space $`^{phy}`$ of a quantum system where $`^{phy}`$ has an arbitrary tensor product structure. A set $`A`$ of $`L`$ operators $`V_a`$ on $`^{phy}`$ indexed by the physical parameters $`aϵA`$ is required to have properties that are necessary conditions for $`^{phy}`$ to have the tensor product structure suitable for length $`L`$ $`kary`$ representations of numbers. These properties are,

1. Each $`V_a`$ is a cyclic shift.
2. The $`V_a`$ all commute with one another.
3. For each $`aϵA`$, if $`(V_a)^k1`$ there is a unique $`a^{}a`$ such that $`(V_a)^k=V_a^{}`$.
4. For each $`a^{}`$ , if there is an $`aa^{}`$ such that $`(V_a)^k=V_a^{}`$, then $`a`$ is unique.
5. There is just one $`a`$ for which $`(V_a)^k=1`$.
6. For just one $`a`$ there are no $`a^{}`$ such that $`(V_a^{})^k=V_a`$.

The properties reflect those possessed by the $`V_j^{+1}`$, note especially Eq. 4. Properties 3-6 can be used to establish a numbering of the label set $`A`$ with the maximum and minimum labels given by properties 5 and 6. The commutativity and cyclic shift properties  give the existence of of a set $``$ of pairwise orthogonal subspaces of states such that for each $`a`$ and each subspace $`\beta `$ in $``$, $`V_a\beta `$ is in $``$ and is orthogonal to $`\beta `$. In the special case that the subspaces in $``$ are one dimensional, the subspaces $`\beta `$ in $``$ correspond to pairwise orthogonal states $`|\beta `$ such that for each $`|\beta `$ in $``$, $`V_a|\beta `$ and $`|\beta `$ are orthogonal.

One can use property 3 along with iterations $`(V_a)^h`$ for $`h=0,1,\mathrm{}k1`$ for each $`a`$ to generate a cyclic ordering or numbering of the states in $``$ and show that the set contains $`k^L`$ states. However none of this is sufficient to select a state as the zero state. This must be done by making an arbitrary choice.

There is a unique state $`|\beta _{\underset{¯}{0}}`$ in $``$ which is the zero state.

Based on this choice one can associate with each string of numbers, $`n_L,n_{L1},\mathrm{}n_{\mathrm{}},\mathrm{},n_2,n_1=\underset{¯}{n}`$ with $`0n_{\mathrm{}}k1`$ for each $`\mathrm{}`$ a unique state $`|\beta _{\underset{¯}{n}}`$. The association is given by

$$|\beta _{\underset{¯}{n}}=\underset{\mathrm{}=1}{\overset{L}{}}(V_a_{\mathrm{}})^n_{\mathrm{}}|\beta _{\underset{¯}{0}}.$$

where the properties of the $`V_a`$ show that the states $`|\beta _{\underset{¯}{n}}`$ for different number strings $`\underset{¯}{n}`$ are orthogonal.

The above can also be used to define addition as in Eq. 8 and show that $`|\beta _{\underset{¯}{0}}`$ is the additive identity. This and use of the discussion in Section III suggests that these operators and the associated states do satisfy the axioms of arithmetic $`modk^L`$. However examples can be constructed to show that it is very unlikely that the existence of operators with these properties are sufficient conditions for $`^{phy}`$ to have a tensor product structure suitable for $`kary`$ representations of length $`L`$. If one adds the additional requirement that these operators be efficiently implementable, then it is an open question if all these conditions are sufficient to require that $`^{phy}`$ has a tensor product structure suitable for $`kary`$ representations of length $`L`$.

## VII Discussion

Several points about the work done here should be noted. The state descriptions of composite quantum systems used in this paper have not taken account of whether or not the component systems are distinguishable by properties other than those explicitly shown in the states. This is based on the consideration that the only properties used by a quantum algorithm are those expressed explicitly in the states and operators representing the basic arithmetic operations. For indistinguishable systems, it is suspected that taking account of their bosonic or fermionic nature, as has been done elsewhere , will not change the results obtained. However, this must be investigated.

The condition of efficient implementation of the basic arithmetic operations is the main restrictive condition on states of quantum systems that represent numbers. As noted it excludes $`k=1`$ and large $`k`$. It also greatly restricts which unitary operators from $`^{arith}`$ to $`^{phy}`$ are allowed. To see this note that any unitary operator $`U`$, tensor product preserving or not, from $`^{arith}`$ to $`^{phy}`$ gives a model of the axioms of modular arithmetic on $`^{phy}`$. The numbers are represented by the states $`U|\underset{¯}{s}`$ and the basic operators by $`UV_j^{+1}U^{}`$ and $`(UU)+(U^{}U^{})`$ and similarly for $`\times `$. However most of these $`U`$ can be excluded because the corresponding basic operators on $`^{phy}`$ are not efficiently implementable. Also for most $`U`$ there is no way to physically prepare the states $`U|\underset{¯}{s}`$. This is the main reason for the restriction that $`U`$ be tensor product preserving with the form of $`W_{g,d}`$.

Unfortunately there is no way to define exactly which $`U`$ operators are allowed and which are not. The reason is that there is no way to precisely define the meaning of physical realizability. One needs an hypothesis for physical realizability equivalent to the Church-Turing Hypothesis  for computable functions. Earlier attempts to characterize realizable physical procedures as collections of instructions , or state preparation and observation proceedures as instruction booklets or programs for robots  have not been generally accepted. This problem also arises in describing exactly the class of tasks that a quantum robot  can carry out.

Another aspect of the representation of numbers by quantum states is that the sets of numbers $`1,\mathrm{},L`$ and $`0,\mathrm{},k1`$ have been used to describe $`kary`$ representations of numbers of length $`L`$ by quantum states. For example numbers in either of these sets are used to describe the $`V_j^{+1}`$ operations. Also the definitions of $`+`$ and $`\times `$ were given in terms of numbers of iterations of $`V_j^{+1}`$ and $`+`$ respectively.

Two components of this should be noted. One is that the role of these numbers is limited to the dynamical implementation of the $`V_{g,j}^{d,+1},+_{g,d}`$, and $`\times _{g,d}`$. For example, any method based on a Hamiltonian $`H_g^d`$ that implements $`V_{g,j}^{d,+1}`$ as a translation of a procedure for implementing $`V_{g,1}^{d,+1}`$ by $`j`$ sites along $`g`$ requires motion along $`g`$ until the site $`g(j)`$ is reached. This can be done by repeated subtraction of $`1`$ from $`j`$, interleaved with motion of some system, such as a head or quantum robot , along $`g`$ until $`g(j)`$ is reached. Also the ”carry $`1`$” operation, which is part of $`V_{g,j}^{d,+1}`$ means that motion along the remaining $`Lj`$ elements of path $`g`$ must be built into $`H_g^d`$.

Similar arguments apply for the efficient carrying out of the $`+_{g,d}`$ operation as this requires up to $`k`$ iterations of $`V_{g,j}^{d,+1}`$ for each $`j`$. One method of implementation requires interleaving the implementation of a procedure for $`V_{g,j}^{+1}`$ with subtractions of $`1`$ from a state $`|\underset{¯}{s}_j`$, Eq. 8, until $`|\underset{¯}{0}_j`$ is obtained.

Implementation of these operations by quantum systems means that numbers up to $`L`$ and $`k`$ must also be represented by quantum states of systems. These systems can either be mobile and part of the head or fixed external systems. Thus the arguments and conditions already discussed apply to these representations too.

The other component is that the magnitudes of the numbers represented by the states of systems that are part of the dynamics are exponentially smaller than those represented by the system on which the dynamics is acting. States of a composite quantum system satisfying the conditions for $`kary`$ number representations of length $`L`$, represent the first $`k^L`$ numbers. Numbers appearing in the dynamics range up to $`k`$ and $`L=\mathrm{log}_kk^L`$. This exponential decrease is a consequence of the requirement of efficient implementability of arithmetic operations.

The conditions discussed in this paper, including the requirement of efficient physical implementability, also apply to the quantum states of ancillary systems that are used to implement the dynamics of an algorithm. This is evident in any algorithm which interleaves evaluation of some numerical function with carrying out an action until a specified function value is reached. For instance, implementation of the $`V_{g,j}^{d,+1}`$, e.g. by use of a head or quantum robot with an on board quantum computer , would require a quantum computer with at least $`O([\mathrm{log}_m(L)]+1)`$ qubytes for an $`mary`$ representation of numbers up to $`L`$. ($`[]`$ denotes the largest integer in.) Here the dynamics that carries out these operations is subject to all the requirements described so far. It is also part of the dynamics for implementing $`V_{g,j}^{d,+1}`$.

These considerations suggest that it may not be possible to describe the representation of numbers by states of a composite quantum system without the use of states of other systems already assumed to represent numbers. These states are part of the dynamics of the basic arithmetic operations.

Whether this is true or not is a question for the future. However, if this impossibility is the case, one is helped by the fact that the number of states needed to represent numbers in the dynamics is exponentially smaller than the number of states representing numbers of the composite system on which the dynamics acts.

Finally it should be noted that much of the discussion, including the efficient implementability condition, which has been applied to microscopic quantum systems, also applies to macroscopic quantum systems. In this case $`t_{dec}t_{sw}`$ so the limitation that the number of steps is $`<t_{dec}/t_{sw}`$ is not applicable. Instead efficient implementation means that there exists a dynamics such that the number of steps needed to carry out arithmetic operations is polynomial in $`L`$. Also the states of the system used to represent numbers are those that are stabilized by the interactions with the environment, the ”pointer states” . The fact that these conditions are much less onerous than the limitations on microscopic systems is shown by the widespread use of macroscopic computers and counting devices and timers.

In conclusion it is reemphasized that this work is one approach to making explicit the assumptions and conditions involved in the representation of natural numbers by states of quantum systems. It is based on separating the mathematical concept of numbers, as models of a set of axioms, from the physical concept of efficient implementabiliy of the basic arithmetic operations described by the axioms. Whether this approach will turn out to be a good one or not depends on future work.

## Acknowledgements

Discussions with Murray Peshkin on several points of this paper were much appreciated. This work is supported by the U.S. Department of Energy, Nuclear Physics Division, under contract W-31-109-ENG-38.

## Appendix: Definition of $`\times `$

The goal is to define a unitary times operator according to Eq. 9 based on efficient iteration of the $`+`$ operator. To this end define $`Q_j(2,3)`$ for $`j=1,\mathrm{},L`$ as operators on the second and third product states that convert $`|\underset{¯}{s},\underset{¯}{w},\underset{¯}{w0^{j1}},\underset{¯}{z}`$ to $`|\underset{¯}{s},\underset{¯}{w},\underset{¯}{w0^j},\underset{¯}{z}`$. It has the effect of multiplying $`|\underset{¯}{w0^j}`$ by $`k`$. An efficient reversible implementation of this, acting on the state $`|\underset{¯}{s},\underset{¯}{w},\underset{¯}{y},\underset{¯}{z}`$ is obtained by subtraction, $`modk`$, of the $`Lj+1st`$ component qubyte state of $`|\underset{¯}{w}`$ from the $`Lth`$ component state of $`|\underset{¯}{y}`$, shifting all the elements of $`|\underset{¯}{y}`$ by one site and putting the result of the subtraction at the newly opened first site. This works because, if $`|\underset{¯}{y}=|\underset{¯}{w0^{j1}}`$, then $`|\underset{¯}{y}_L=|\underset{¯}{w}_{Lj+1}`$. The result, $`|\underset{¯}{0}_L`$, of the subtraction is moved to the first site of $`|\underset{¯}{y}`$ after the shift. One has

$$Q_j(2,3)|\underset{¯}{s},\underset{¯}{w},\underset{¯}{y},\underset{¯}{z}=|\underset{¯}{s},\underset{¯}{w},\underset{¯}{y^{}},\underset{¯}{z}$$
(20)
where $`|\underset{¯}{y_{j+1}^{}}=|\underset{¯}{y}_j`$ for $`1jL1`$ and $`|\underset{¯}{y_1^{}}=|\underset{¯}{y}_L|\underset{¯}{w}_{Lj+1}`$. Here $``$ denotes subtraction $`modk`$. Note that $`Q_j(2,3)`$ is unitary.

The operator $`\times `$ is defined from the $`Q_j(2,3)`$ and $`+`$ by

$`\times |\underset{¯}{s},\underset{¯}{w},\underset{¯}{y},\underset{¯}{z}=Q_L(2,3)(+_{3,4})^{s_L}Q_{L1}(2,3)(+_{3,4})^{s_{L1}}`$
$`\mathrm{},(+_{3,4})^{s_2}Q_1(2,3)(+_{3,4})^{s_1}+_{2,3}|\underset{¯}{s},\underset{¯}{w},\underset{¯}{y},\underset{¯}{z}`$
Here $`+_{m,n}`$ carries out the action defined in Eq. 8 on the $`mth`$ and $`nth`$ product state. The $`mth`$ state remains unchanged in this action. $`s_h`$ is the number $`\underset{¯}{s}(h)`$ in the state component $`|\underset{¯}{s}(h),h`$ of $`|\underset{¯}{s}`$. Note that since each operator in the righthand product of the equation is unitary, so is $`\times `$.

To see that $`\times `$ as defined above does carry out the intended multiplication operation on initial states of the form $`|\underset{¯}{s},\underset{¯}{w},\underset{¯}{0},\underset{¯}{0}`$ one carries out the action of the $`2L+1`$ operators shown above. The steps give

$`|\underset{¯}{s},\underset{¯}{w},\underset{¯}{0},\underset{¯}{0}\begin{array}{c}+_{2,3}\hfill \\ \hfill \end{array}|\underset{¯}{s},\underset{¯}{w},\underset{¯}{w},\underset{¯}{0}\begin{array}{c}(+_{3,4})^{s_1}\\ \end{array}|\underset{¯}{s},\underset{¯}{w},\underset{¯}{w},\underset{¯}{s_1w}`$ (25)
$`\begin{array}{c}Q_1(2,3)\\ \end{array}|\underset{¯}{s},\underset{¯}{w},\underset{¯}{w0},\underset{¯}{s_1w}\begin{array}{c}(+_{3,4})^{s_2}\\ \end{array}|\underset{¯}{s},\underset{¯}{w},\underset{¯}{w0},\underset{¯}{s_1t+s_2t0}`$ (30)
$`\mathrm{}\begin{array}{c}Q_L(2,3)\\ \end{array}|\underset{¯}{s},\underset{¯}{w},\underset{¯}{0},\underset{¯}{s_1w+s_2t0+\mathrm{}+s_Lt0^{L1}}`$ (33)
Note that $`Q_L(2,3)`$ acting on $`|,\underset{¯}{w},\underset{¯}{w0^{L1}},`$ gives $`|,\underset{¯}{w},\underset{¯}{0},`$ in accordance with Eq. 9 as $`|\underset{¯}{w0^L}=|\underset{¯}{0}`$. Here $`|\underset{¯}{s_1w}`$ denotes $`s_1`$ iterations of adding $`|\underset{¯}{w}`$ to $`|\underset{¯}{0}`$; also $`s_jw0^{j1}`$ denotes the result of $`s_j`$ additions of $`|\underset{¯}{w0^{j1}}`$ to the $`4th`$ product state.


format: text

text:
# Sunyaev-Zel’dovich constraints from black hole-seeded proto-galaxies

## 1 Introduction

Most theories of hierarchical structure formation are based on the study of the evolution of density perturbations under their own gravity. A density fluctuation, which represents an over- (or under-) density with respect to the mean matter distribution, contains both baryonic and dark matter (DM). The baryonic component sinks into the gravitational potential of the DM halo. It collapses and cools, resulting in star formation. In these scenarios, after the gravitational collapse of the DM halo, stars are assumed to be the first objects to form. A structure will thus end up as an emitting object after virialisation has occurred.

An alternative picture involves the formation of a super-massive black hole (BH) that powers the central regions of galaxies Lynden-Bell (1969). Numerous studies have been performed that relate the quasar luminosity function to galaxy formation scenarios by assuming that the formation of quasars (i.e., BH) in the potential well of the DM halos constitutes one of the phases in the galaxy formation process Efstathiou & Rees (1988); Haehnelt & Rees (1993); Nusser & Silk (1993); Haiman & Loeb (1997). Recent observations even suggest that a super-massive BH may be present in the centres of all galaxies with spheroidal components Kormendy & Richstone (1995).

Several authors have looked at several consequences of the presence of massive BHs on galaxy formation and evolution Haiman & Loeb (1997); Natarajan et al. (1998); Silk & Rees (1998). In this paper, we investigate the cosmological implications of such an alternative scenario for the Cosmic Microwave Background (CMB) anisotropies and spectral distortions. More specifically, we study the effects of the outflows, driven by the BH activity, on the gas within the seeded proto-galaxy. In fact, the outflow expands and shock-heats the ambient medium (proto-galactic gas), and then interacts with the inter-galactic medium (IGM). Three regimes of interest may be considered: 1) the high density region of the proto-galaxy, 2) the low density IGM and 3) the thin compressed layer (four times denser than the IGM) induced by the front shock. The second and third regimes give results very similar to those computed in Aghanim et al. (1996). We thus focus on the first regime, i.e. the localised effects of the BH-driven shock on the gas within the seeded proto-galaxy. This shock-heated gas will Compton scatter the CMB photons and induce spectral distortions and temperature anisotropies through the so-called Sunyaev-Zel’dovich effect Sunyaev & Zel’dovich (1980). The thermal SZ effect depresses the CMB brightness in the Rayleigh-Jeans region and increases it above a frequency of about 219 GHz. Its amplitude represents the integral along the line of sight of the electron pressure. It is proportional to the electron density $`n_e`$ and is characterised by the Compton parameter $`y`$ defined by:

$$y=2_0^R\frac{kT}{m_ec^2}\sigma _Tn_e(l)𝑑l,$$
(1)
where $`T`$ is the temperature of the gas, $`R`$ the physical size of the structure, $`m_e`$ the electron mass, $`k`$ the Boltzmann constant, $`c`$ the speed of light and $`\sigma _T`$ the Thomson cross section. An additional secondary anisotropy arises due to the first-order Doppler effect of the CMB photons when they scatter on a structure moving with respect to the Hubble flow, with radial peculiar velocity $`v_r`$. This interaction is called the SZ kinetic effect. It generates an anisotropy, with no specific spectral signature, whose amplitude is given by:

$$\frac{\delta T}{T}=\frac{v_r}{c}\times \left(2_0^R\sigma _Tn_e(l)𝑑l\right).$$
(2)
Previous work on galaxy formation has evaluated the global distortion of a population of galaxies in the virialised regime. The global Compton parameter was found to be much smaller than the constraints set by the FIRAS instrument (Far InfraRed Absolute Spectro-photometer) on board COBE (COsmic Background Explorer) Fixsen et al. (1996) on the global SZ distortion of the universe. By contrast, our model focuses on a regime in which proto-galaxies undergo a BH formation phase that induces larger distortions. The paper is organised as follows: in §2, we model the shock in an individual structure and give its physical characteristics (size and temperature). In §3, we compute the predicted number density of primordial galaxies, using the Press & Schechter (1974) mass function. In §4, we generalise the description of the shock to the whole population of proto-galaxies and we simulate maps of the induced secondary anisotropies. We estimate this contribution to the CMB anisotropies. We also compare our predicted global $`y`$ parameter to the COBE-FIRAS value and derive constraints on the model. Conclusions are given in the last section.

## 2 Modelling the shock

In the galaxy formation canonical scenario, a galaxy forms in the gravitational potential well of a DM halo of mass $`M_{halo}`$. Following Silk & Rees (1998), we consider that each forming galaxy, which is fully described by the mass $`M_{halo}`$, hosts a super-massive BH. The fraction of seeded proto-galaxies is thus 100%. For the sake of simplicity, we assume that all proto-galaxies are spheroids. A more refined and accurate description would take into account morphological segregation Balland et al. (1998). However, these effects do not introduce significant differences. We assume that the BH radiates during its lifetime $`t_{BH}`$ a fraction $`ϵ_E=0.1\mathrm{\hspace{0.17em}0.2}`$ Natarajan & Sigurdsson (1999) of its Eddington luminosity ($`L_{BH}=ϵ_EL_{edd}`$). The latter is fixed by the BH mass, $`M_{BH}`$:

$$L_{edd}=\frac{4\pi M_{BH}m_pGc}{\sigma _T},$$
(3)
where $`m_p`$ is the proton mass and $`G`$ the gravitational constant. The mass of the BH should be directly related to the mass of the proto-galaxy it seeds, and thus to the fraction of baryonic matter locked up in the spheroid in which the central BH collapses. We assume a simple relation of proportionality ($`M_{BH}=ϵ_{BH}M_{sph}`$) between the mass of the BH and the mass of the spheroid $`M_{sph}`$. Haehnelt & Rees (1993) give $`ϵ_{BH}10^3`$ and they assume that $`ϵ_{BH}`$ declines with mass. However, observations of galactic nuclei Kormendy et al. (1997); Magorrian et al. (1998) indicate that $`ϵ_{BH}`$ is relatively constant. Here, we take the value $`ϵ_{BH}=2.10^3`$ as advocated by Magorrian et al. (1998) and Silk & Rees (1998). We assume that the medium is instantaneously ionised, which is very likely due to the intense radiation emitted by the central BH Voit (1996). We therefore study the propagation of a strong shock driven by a mechanical energy which represents some fraction of the BH luminosity. The first analytic solutions of spherically symmetric explosions were given by Taylor (1950) and Sedov (1959) and applied to several astrophysical problems such as stellar winds and supernovae explosions Ikeuchi et al. (1983); Bertschinger (1986); Koo & McKee (1992a, b); Voit (1996). Following Voit (1996), we study the expansion of the shock and its effects on the gas within the seeded proto-galaxy. We characterise the shock in an expanding universe by a set of physical properties (its radius, velocity and temperature). Adapting Voit’s solutions to our study, the shock at a redshift $`z<z_{}`$, where $`z_{}`$ is the redshift at which the BH switches on, has a radius $`R_s`$ which reads as:

$$R_s\left(\frac{\pi GE_0}{H_0^4\delta \mathrm{\Omega }_0^3}\right)^{1/5}\frac{(1+\mathrm{\Omega }_0z_{})^{1/5}}{(1+z_{})^{2/5}}\times $$

$$\left[1\left(\frac{1+\mathrm{\Omega }_0z}{1+\mathrm{\Omega }_0z_{}}\right)^{1/2}\right]^{2/5}(1+z)^1.$$
(4)
It propagates at a velocity

$$v_s=\frac{2}{5}\left[\frac{\pi E_0H_0G}{3\delta \mathrm{\Omega }_b}\frac{\mathrm{\Omega }_0^2(1+z_{})^3}{(1+\mathrm{\Omega }_0z_{})^{3/2}}\right]^{1/5}\times $$

$$\left[1\left(\frac{1+\mathrm{\Omega }_0z}{1+\mathrm{\Omega }_0z_{}}\right)^{1/2}\right]^{3/5}\left(\frac{1+z}{1+z_{}}\right).$$
(5)
In the two previous equations, $`E_0=ϵL_{BH}t_{BH}`$ represents the mechanical energy which drives the shock. Very little is known about the fraction $`ϵ`$ which can be on the order of 0.5 or even higher Natarajan & Sigurdsson (1999). For the lifetime of the BH in the bright phase, we choose the recent value derived by Haiman & Loeb (1997): $`t_{BH}=10^6`$ years (our results, however, are not very sensitive to the exact value of $`t_{BH}`$). $`\delta `$ is the mean over-density of the proto-galaxy (assumed to be spherical), $`H_0`$ is the Hubble constant, $`\mathrm{\Omega }_0`$ is the density parameter and $`\mathrm{\Omega }_b`$ is the baryon density in the universe. Zero subscripts denote present day values. In the following and throughout the paper, we use $`h=H_0/(100\text{km/Mpc/s})=0.5`$ and $`\mathrm{\Omega }_b=0.06`$ Walker et al. (1991) and give the results as a function of $`\mathrm{\Omega }_0`$, for $`\mathrm{\Omega }_0=1`$ and $`\mathrm{\Omega }_0=0.3`$.

Following Natarajan & Sigurdsson (1999), we assume that the BH radiates 10% of its Eddington luminosity, i.e. $`ϵ_E=0.1`$ and that half of the corresponding energy is mechanical. Furthermore, we consider that galaxies form at sufficiently high redshifts ($`>5`$) so that only hydrogen and helium are present in substantial amounts. We compute both the size and velocity of the shock and find that the host proto-galaxy is always embedded in the shocked region.

### 2.1 Cooling mechanisms

The temperature of the shocked medium can be directly derived from the equipartition of energy:

$$Tv_s^2\mu m_p/k.$$
(6)
Here, $`\mu =0.6`$ is the mean molecular weight of a plasma with primordial abundances. The galactic matter can be shock-heated up to very high temperatures. For the most massive galaxies, we find that the matter is heated up to a few $`10^8`$ K, a value comparable to the temperature of the intracluster medium in galaxy clusters. For these temperatures and redshifts ($`>5`$), the main cooling process at play is bremsstrahlung. Therefore, the shocked gas looses heat with a cooling rate given by a temperature-dependent cooling function $`\mathrm{\Lambda }(T)`$. We have compared three different cooling functions Bertschinger (1986); Koo & McKee (1992a); Voit (1996) given in the literature for temperatures between a few $`10^5`$ and $`10^8`$ K. We find that the condition required for efficient cooling is always satisfied in our redshift range. This means that the cooling time, given by $`t_{cool}=5kT/n_H\mathrm{\Lambda }(T)`$ with $`n_H`$ the hydrogen number density, is always smaller than the age of Universe. Cooling is thus very efficient in our picture. The comparison between the three cooling functions shows that they all give essentially the same final temperature after cooling. We follow Bertschinger (1986) and we find that the shocked matter cools down to $`T10^5`$ K at $`z5`$.

## 3 Number counts of primordial galaxies

In order to quantify the global effect of the formation of primordial galaxies on the CMB, we apply our formalism to a synthetic population of galaxies with masses $`10^9M_{\mathrm{}}M10^{12}M_{\mathrm{}}`$.

We first assume that the galaxy number density traces, within a linear bias, the abundance of collapsed DM halos, as predicted by the Press–Schechter (PS) mass function Press & Schechter (1974). We use an initial power-law spectrum with an effective spectral index $`n=2`$ on galaxy scales. We express the amplitude of primordial matter fluctuations in terms of the rms variance in spheres of 8$`h^1`$ Mpc, $`\sigma _8=0.6`$ (as cluster-normalised, e.g. Viana & Liddle (1996), which corresponds to a bias factor $`b1.67`$. For $`\mathrm{\Omega }=1`$, the set of parameters corresponds to the “standard” biased cold DM model, which does fit neither small- and large-scale velocities Vittorio et al. (1986) nor COBE normalisation. However, we take it as a study case for the computations, our second model is the low density cosmological model with $`\mathrm{\Omega }=0.3`$. In our picture (no stars are formed yet), the spheroid is gaseous. Its mass is related to the mass of the DM halo via $`M_{sph}=\frac{1}{3}M_{halo}`$. The mass and luminosity of the central BH and thus the predicted SZ distortions are therefore inferred from $`M_{sph}`$ ($`M_{BH}=ϵ_{BH}M_{sph}`$, and $`ϵ_{BH}=\mathrm{2.\hspace{0.17em}10}^3`$; cf §2).

To compute the kinetic SZ term of a population of proto-galaxies, we need an estimate of their peculiar velocities with respect to the reference frame. As suggested by numerical simulations Bahcall et al. (1994); Moscardini et al. (1996), we assume that velocities follow a Gaussian distribution. The peculiar velocity of each proto-galaxy is drawn from a Gaussian which is completely defined by its rms value $`\sigma _v`$. In the range of redshifts we have adopted, the structures are in the linear regime, so that $`\sigma _v(z)=\sigma _0f(z)`$, where the redshift dependence of the velocities is given by $`f(z)`$Peebles (1980, 1993) as a function of the cosmological parameters. In this equation, $`\sigma _0`$ is the present-day rms peculiar velocity. It is related to the mass variance on mass scale $`M`$, $`\sigma (M)=(1.19\mathrm{\Omega }_0)^{(n+3)/6}\sigma _8M^{(n+3)/6}`$ Mathiesen & Evrard (1998), where $`n`$ is the index of the power spectrum. The rms velocity can thus be computed for each mass scale.

## 4 Results and discussion

The shock-heated gas within proto-galaxies interacts with the CMB photons through the SZ effect (thermal and kinetic). These interactions generate secondary temperature anisotropies and spectral distortions. We simulate maps of the secondary anisotropies generated by a population of seeded proto-galaxies formed between redshift 5 and 10. The maps have a resolution of about $`0.2`$ arcseconds to resolve the galaxies and contain $`600\times 600`$ pixels. The number of sources of mass $`M`$ at redshift $`z`$ is derived from the PS mass function. Their positions are drawn at random in the map. The $`y`$ and $`\delta T/T`$ profiles for, respectively, the thermal and the kinetic effects are directly derived from the integration of the gas profile $`n_e(R)`$ along the line of sight (Eqs. 1 and 2) assuming spherical symmetry.

Similarly to the case of galaxy clusters, we assume that in the early stages of formation the gas settles into a hydrostatic equilibrium within the DM potential. A universal density profile is motivated by Navarro et al. (1996). However, the gas profile may be softer than that of the DM, and moreover the existence of a central cusp is “unobserved” Kravtsov et al. (1998).We thus conservatively adopt the following parametrised profile for the gas distribution:

$$n_e(R)=n_0\left[1+\left(\frac{R}{R_c}\right)^2\right]^\alpha ,$$
(7)
where $`n_0`$ is the central density. $`\alpha `$ is left as a free parameter describing the steepness of the profile, whereas $`R_c`$ is identified with a core radius as in galaxy clusters. On cluster scales, $`R_c`$ is typically 10 to 30 times smaller than the cluster virial radius $`R_{vir}`$. In our model we introduce the parameter $`p=R_{vir}/R_c`$ which we vary, similarly to clusters, between 10 and 30. The central density $`n_0`$ can be derived from the gas mass of the proto-galaxy using the following equation:

$$M_{sph}\left(\frac{\mathrm{\Omega }_b}{\mathrm{\Omega }_0}\right)=m_p\mu _0^{R_{vir}}n_e(R)\mathrm{\hspace{0.17em}4}\pi R^2𝑑R,$$
(8)
where the virial radius of the structure is given by:

$$R_{vir}=\frac{(GM)^{1/3}}{(3\pi H_0)^{2/3}}\frac{1}{1+z_{coll}},$$
(9)
for a critical universe. It is fixed solely by the mass and the collapse redshift $`z_{coll}`$.

We will give the results for a flat model with no cosmological constant ($`\mathrm{\Omega }_0=1`$) and an open model ($`\mathrm{\Omega }_0=0.3`$). Varying the cosmological parameters will vary the number of proto-galaxies along the line of sight as well as their peculiar velocities. It will also modify their physical properties, i.e. the size and velocity of the shock and thus the gas temperature. The two cosmological models represent the upper and lower bounds between which all other cosmological models involving a non-zero cosmological constant fall.

### 4.1 Compton distortion

The CMB photons, scattering off the electrons of the ionised hot gas, induce a spectral distortion whose amplitude is given by Eq. 1. The FIRAS experiment has measured the mean Compton parameter resulting from all the interactions undergone by the photons. The result is $`\overline{y}_{FIRAS}=\mathrm{1.5\hspace{0.17em}10}^5`$ Fixsen et al. (1996). This stringent observational limit incorporates the (negligible) contribution of the rather cold intergalactic medium and that of all other extragalactic signals. Among these signals, there is the contribution of the hot ionised gas in galaxy clusters. The global distortion induced by intra-cluster gas has been computed De Luca et al. (1995); Barbosa et al. (1996), and found to be of the order of a few $`10^6`$. In addition to galaxy clusters, one has to take into account the contribution of the proto-galaxy population in terms of the overall Compton distortion, $`\overline{y}_{PG}`$, induced by the scattering of CMB photons on the shock-heated gas.

Based on simulated maps, we predict $`\overline{y}_{PG}`$ and we compare it to the limit set by COBE-FIRAS. Among all the parameters of the model, there are four major quantities that substantially affect the predictions of the mean Compton parameter. Two of them, $`\alpha `$ and $`p`$, are related to the gas distribution (Eq. 7). The two others are the fraction $`f`$ of BH-seeded proto-galaxies and the BH-to-spheroid mass ratio $`ϵ_{BH}`$. We compare our predicted overall distortion to the COBE-FIRAS limit and look for the combinations of parameters for which our predictions fit the observations. This allows us to constrain the assumptions of our model.

For $`\alpha =1/2`$, $`f=100`$%, $`ϵ_{BH}=\mathrm{2.\hspace{0.17em}10}^3`$ and both cosmological models, we find $`\overline{y}_{PG}10^4`$ which exceeds the observational value. In order for our prediction to be reconciled with the COBE-FIRAS limit, $`f`$ must be only a few percent. This constraint on $`f`$ strongly violates the actual observations Magorrian et al. (1998); Richstone et al. (1998). $`\alpha =1/2`$ is thus excluded by the limit on the global distortion whatever value we choose for $`p=R_{vir}/R_c`$.

For $`\alpha =1`$ (i.e. an isothermal profile), an $`\mathrm{\Omega }_0=1`$ model, $`f=100`$% and $`ϵ_{BH}=\mathrm{2.\hspace{0.17em}10}^3`$, we find $`\overline{y}_{PG}>\overline{y}_{FIRAS}`$ whatever we adopt for $`p`$. The fraction $`f`$ must be smaller than 75% for the prediction to be compatible with the observational limit. Again, this fraction is significantly smaller than the 95% advocated by Magorrian et al. (1998). Such a constraint could rule out the isothermal profile. However, up to now, $`ϵ_{BH}`$ was assumed to be constant and equal to $`\mathrm{2.\hspace{0.17em}10}^3`$. If we now use the lower limit of Magorrian et al. (1998), that is $`ϵ_{BH}=10^3`$, together with $`f=95`$% or higher there is only a marginal agreement for $`p30`$ between the predicted and measured distortions. In the open model case ($`\mathrm{\Omega }_0=0.3`$), we find approximately the same results. For $`\overline{y}_{PG}`$ to be compatible with $`\overline{y}_{FIRAS}`$ if $`p=10`$, the fraction of BH seeded proto-galaxies should be smaller than 80% if $`ϵ_{BH}=\mathrm{2.\hspace{0.17em}10}^3`$ or $`f<95\%`$ if $`ϵ_{BH}=10^3`$. The predictions for $`p=30`$ agree with observations in all the cases.

For $`\alpha =3/2`$ (i.e. the gas profile approximates a King profile) and for both cosmological models, we find $`\overline{y}_{PG}`$ of about $`10^6`$ to a few $`10^6`$, a prediction compatible with $`\overline{y}_{FIRAS}`$. This result remains valid for all values of $`p`$ between 10 and 30 including the highest boundaries of $`f`$ and $`ϵ_{BH}`$, respectively, 100% and $`\mathrm{2.\hspace{0.17em}10}^3`$.

### 4.2 Predicting the angular power spectrum

We choose the set of parameters associated with the isothermal profile which agrees with the COBE-FIRAS limit: $`\alpha =1`$, $`p=30`$, $`f=95`$% and $`ϵ_{BH}=\mathrm{2.\hspace{0.17em}10}^3`$. Within this context, we predict the upper limit on the contribution to secondary temperature anisotropies induced by the SZ, thermal and kinetic effects, of the proto-galactic gas. We express this contribution in terms of an angular power spectrum plotted in figure 1 together with the main other well-known secondary anisotropies.
At very small scales ($`l`$ a few $`10^5`$) corresponding to galactic scales, the kinetic SZ contribution of the shock-heated gas (Fig. 1, thick solid line for $`\mathrm{\Omega }_0=1`$ and thick dashed line for $`\mathrm{\Omega }_0=0.3`$) is very large. It is interesting to note the good agreement between our results and those obtained by Peebles & Juszkiewicz (1998) for the scattering of the CMB photons by the cloudy proto-galactic plasma. The power spectrum of the kinetic SZ anisotropies for the $`\mathrm{\Omega }_0=0.3`$ model is significantly larger than the $`\mathrm{\Omega }_0=1`$ model. This is mainly due to the higher number of sources per unit comoving volume in open models. In all other flat cosmological models involving a non-zero cosmological constant, the power spectrum will lie between the two curves. The expected power spectrum due to the thermal SZ effect is not plotted in this figure. It is more than one order of magnitude smaller than the kinetic effect contribution. This is due to the efficiency of bremsstrahlung which lowers the temperature down to a few $`10^5`$ K.

We compare the contribution of the proto-galaxies due to their SZ kinetic effect to the major sources of secondary temperature anisotropies. In each case, we choose the most extreme cases for the comparison with our upper limit prediction. The power spectra displayed in figure 1 are taken from the literature. The dotted line represents the upper limit of the contribution of the inhomogeneous reionisation as computed by Aghanim et al. (1996) for a quasar lifetime of $`10^7`$ yrs. The dot-dashed line represents the Rees-Sciama effect Rees & Sciama (1968) taken from Seljak (1996) ($`\sigma _8=1`$, $`\mathrm{\Omega }_0h=0.25`$). The dashed line represents the galaxy cluster contribution due to kinetic SZ effect from Aghanim et al. (1998) with a cut-off mass of $`10^{14}M_{\mathrm{}}`$. The triple-dot-dashed line represents the Vishniac-Ostriker effect Ostriker & Vishniac (1986); Vishniac (1987) computed by Hu & White (1996) with a total reionisation occurring at $`z_i=10`$. Finally, the solid thin line represents the power spectrum of the primary CMB anisotropies in a standard CDM model computed using the CMBFAST code Seljak & Zaldarriaga (1996). The primary CMB anisotropies dominate at all scales larger than the damping around 5 arcminutes. At intermediate scales, several effects take place among which the inhomogeneous reionisation, the Ostriker-Vishniac and the SZ effect. In figure 1, we do not plot the power spectra of the thermal SZ effect of galaxy clusters. It is about one order of magnitude larger than the kinetic SZ effect. At very small scales, the anisotropies are totally dominated by the proto-galactic contribution.

## 5 Conclusions

Previous studies on galaxy formation have evaluated the global distortion of a population of galaxies in the virialised regime. In these studies, the global Compton parameter was found to be very small, and smaller than the COBE-FIRAS value. In contrast, our model focuses on a regime in which proto-galaxies undergo a BH formation phase. During this phase, the proto-galactic matter is shock-heated up to a few $`10^8`$ K and cools down to $`10^5`$ K. CMB photons undergo inverse Compton scattering on the heated gas. In addition, galaxy peculiar motions induce temperature anisotropies through the SZ kinetic effect. We have estimated the global Compton parameter due to a population of proto-galaxies and the expected power spectrum of the induced secondary anisotropies. We find that there are four main parameters that control our model: the fraction $`f`$ of BH-seeded proto-galaxies, the fraction $`ϵ_{BH}`$ of the spheroid mass in the BH, the steepness of the density profile $`\alpha `$ and the gas core radius $`p=R_{vir}/R_c`$. The comparison between our predictions and the COBE-FIRAS observation constrains these parameters. Given the observed fraction of seeded galaxies, $`f=95`$%, our results put rather strong constraints on the density profile and on $`ϵ_{BH}`$. Indeed, our predictions agree with the observations whatever $`p`$ if the density profile is an approximation to a King profile. On the contrary, if the density profile is isothermal, then the core radius must be at least 30 times smaller than the virial radius and the BH-to-spheroid mass ratio has to be small, of the order of $`10^3`$. The computations in the two extreme cosmological models show that the global Compton parameter due to proto-galaxies is not very sensitive to $`\mathrm{\Omega }_0`$.

We compare the power spectra of the different contributions to the temperature anisotropies. Our results show that the SZ effect of the very early shock-heated proto-galaxies could constitute the major source of CMB distortions on very small scales (arcsecond and sub-arcsecond scales). The anisotropies are likely to be detected and measured by future long baseline interferometers such as ALMA. The shock heating is likely to contribute to the re-heating of the proto-galactic gas, which plays a role in galaxy formation theory. Blanchard et al. (1992) used preheating to modify the galaxy luminosity function, suppressing and finally delaying dwarf galaxy formation. We do not take into account this effect in our model, therefore, our results should be taken as an upper limit to the proto-galaxy contribution in terms of secondary anisotropies.

###### Acknowledgements.

This work was initiated while C.B. was at the Center for Particle Astrophysics and while N.A. was at the Astronomy Department of the University of Berkeley (U.S.A.). N.A. acknowledges partial funding from the Centre National d’Études Spatiales. During this work, J.S. was partially supported by a Blaise Pascal professorship. The authors thank O. Forni, G. Lagache and J.-L. Puget for discussions and careful reading of the manuscript. They also wish to thank R. Juszkiewicz for his comments that helped to improve the final version of the paper.