Linear Depth Stabilizer and Quantum Fourier Transformation Circuits with no Auxiliary Qubits in Finite Neighbor Quantum Architectures

In this paper, we investigate how quantum architectures affect the efficiency of the execution of the quantum Fourier transform (QFT) and linear transformations, which are essential parts of the stabilizer/Clifford group circuits. In particular, we show that in most common and realistic physical architectures including the linear nearest neighbor, two-dimensional lattice, and bounded degree graph (containing a chain of length n), n-qubit QFT and n-qubit stabilizer circuits can be parallelized to linear depth using no auxiliary qubits. We construct lower bounds that show the efficiency of our approach.

I. INTRODUCTION
Quantum computation has attracted attention because it appears to reduce the computational complexity of certain calculations, see, for example, [1,2]. For the quantum circuit model of computation, there exists a number of physical quantum information processing implementations, such as liquid NMR (up to 12 qubits at a time) [3], and trapped ions (8 qubits) [4]. Generally, a large number of qubits is required for computational purposes. In this work, we do not allow for any auxiliary qubits to be used in order to reflect the apparent hardness of scaling up quantum information processing devices.
Quantum circuits have been optimized to require less space, fewer gates and smaller depth. This is important from the point of view of the efficient potential realization of the quantum algorithms. As discussed in the first paragraph, we address the issue of space minimization by restricting the number of auxiliary qubits to zero. Our next focus is on depth minimization. This is because a small depth circuit does not only mean a fast computation, but also helps reduce the effect of decoherence. For instance, it is possible to construct realistic examples in which a smaller depth circuit will require fewer levels of error correction, and each error correction code concatenation step is a very expensive operation [5].
In this paper, the depth of a circuit is defined as the number of logic levels in it. Each logic level is a set of non-intersecting "elementary" gates. It is generally accepted that in a practical quantum information processing approach, it should be possible to execute independent gates in parallel. The gate libraries considered in the relevant literature include a set of single-qubit and CNOT gates (which is most likely an artifact of the well known result showing the completeness of this gate set, however, CNOT may not necessarily be a natural gate for some quantum information processing proposals), and any two-qubit operation. Indeed, given a Hamiltonian, any two-qubit operation can be efficiently implemented [6]. For the sake of completeness, this paper discusses how the results apply to both gate sets. Circuit depth, as defined above, upper bounds a possibly lower circuit runtime in cases when next logic level can be executed based upon the availability of qubits and before execution of the gates from the previous level has completed. Practically, this means that some of our upper bounds may not be tight (which is advantageous in the sense that the implementation we construct may in fact have a smaller runtime than predicted by the formulas evaluating depth).
Quantum algorithms and their circuits are usually formulated without considering the physical limitations imposed by different architectures. We believe that circuit and algorithm designs need to be modified to account for possible architectures. In particular, in realistic architectures, it is not possible to establish direct interactions between every pair of qubits [3,4,7]. A study of quantum computing architectures for the existing and emerging quantum technologies shows that the fastest possible direct interactions form a bounded degree graph (e.g., liquid NMR quantum information processing), and 1D or 2D (sub)lattices [8]. A mixed architecture, where values of stationary qubits may be teleported with the help of flying qubits to where they are desired was studied in [9]. In this work, the role of stationary qubits is played by the spins of phosphorus atoms embedded in silicon, known as the Kane proposal [10], and the flying qubits are photons, with the information being teleported via EPR states. Other proposals for state transfer between either stationary or both flying and stationary qubits, and discussions of mixed architectures, can be found, for example, in [11,12,13] and the references therein. However, an architecture that allows interconversion between stationary and flying qubits cannot in general be realized in any technology. In addition, it was shown that teleportation of a single value (simultaneous teleportation of many qubits may be less efficient) in the Kane architecture is only efficient if compared to more than 2-4 levels of SWAPs [9]. A similar effect is likely to take place in other mixed architecture proposals. The latter is important for this work since we are only using depth-1 swapping of multiple qubits via SWAP gates.
Generally speaking, due to the spatial constraints it seems unrealistic to believe that a direct scalable implementation of the unrestricted (where every two qubits are neighbors) architecture, or, more generally, unbounded neighbor architecture, will ever be found. Furthermore, in classical computation the number of neighbors is limited, and there is no obvious reason to believe that the quantum world is different. Thus, the complexity of the circuit designs must be refined to take it into account the limitations of possible quantum computing architectures.
The linear nearest neighbor (LNN) architecture, also known as chain nearest neighbor, is often considered as a good (and, in fact, very restrictive) approximation to what a scalable quantum architecture may be. Mathematically, in an LNN architecture with n qubits q 1 , q 2 , . . . , q n , two-qubit gates are allowed between any qubits whose subscript values differ by one. The LNN architecture describes 1D lattices. It misses possible direct interactions in 2D lattices and may restrict the number of useful interactions in connected graphs. However, if one can show that a circuit can be efficiently reorganized to be executed in the LNN architecture, such a circuit could be run efficiently in many other architectures.
The Quantum Fourier Transformation (QFT) is an analogue of the classical discrete Fourier transformation, however, in the quantum case the transformation is applied to the amplitudes. The QFT serves as a basis for a number of efficient quantum algorithms. Most notably, it is at the heart of integer factorization and the discrete logarithm polynomial time quantum algorithms [2]. Therefore, efficient implementation of the QFT is important. This is why this topic has been studied extensively [14,15,16]. Researchers presented linear and logarithmic depth circuits using a number of auxiliary qubits. Known circuits for the QFT have a regular structure [5,16]. However, they require direct interaction between every two qubits, which makes such circuits especially inconvenient for quantum architectures where only a finite number of neighbors is allowed. In an architecture with a finite number of neighbors, such as LNN, state transfer down the chain may require up to (n − 1) SWAP gates. We refer to the this observation as the locality constraint in the discussions involving lower bound arguments. A linear depth QFT circuit implemented in the LNN architecture has been reported in [17]. We reconstruct this circuit with our generalized technique and we also study lower bounds.
Stabilizer circuits (also known as unitary stabilizer circuits or Clifford group circuits) were introduced and studied for their use in the encoding, decoding and error detection stages of quantum error-correction codes [18,19]. They can be defined as arbitrary quantum circuits composed with singlequbit Hadamard and Phase gates and two-qubit controlled-NOT gates. It turns out that stabilizer circuits can be efficiently simulated [20] as an 11-stage sequence of Hadamard (H), Phase (P) and linear reversible circuits (C) as H-C-P-C-P-C-H-P-C-P-C. Each P and H stage is a depth-1 computation composed with single-qubit gates. The depth of stabilizer circuits is, thus, defined by the depth of a circuit realizing some linear reversible function. Efficient circuits for linear functions are, therefore, of great importance. In this paper we show that every stage C can be parallelized to linear depth in the LNN architecture. Thus, the entire stabilizer circuit requires at most linear time to be executed.
A very recent study shows that a size s stabilizer circuit in an unrestricted architecture can be parallelized to a depth O(log n) circuit, but requires O(s 3 + n) auxiliary qubits [21], Proposition 8.9. Combining the results of [20,21,22] this gives a depth O(log n) circuit in unrestricted architectures using O( n 6 log 3 n ) auxiliary qubits to realize any stabilizer circuit. Since a depth d circuit built on q qubits in unrestricted architectures may become as large as depth O(qd) in the LNN architecture (every depth-2 computation can be adversary made to define the complete interaction pattern of the LNN architecture, and two depth-2 non-commuting stages can be defined such as to require a linear depth qubit permutation between them), the benefit of logarithmic depth quickly disappears. However, a large amount of auxiliary qubits remains.
Out approach thus appears more practical.
The remainder of the paper is organized as follows. We start by introducing a concept of skeleton circuits and studying their properties. In Subsections II A and II B the lessons learned are applied to show that QFT and linear reversible/stabilizer circuits can be parallelized to linear depth in the LNN architecture. Section III reports lower bounds for a class of skeleton circuits which appears to be very important. Concluding remarks can be found in Section IV.

II. SKELETON CIRCUITS
Any quantum circuit composed with single-qubit and twoqubit gates can be thought of as a circuit composed of generic two-qubit operations each of which consists of a two-qubit gate of the initial circuit with the surrounding gates absorbed into it (the trivial case when only single-qubit gates are applied to a specific qubit throughout an entire computation is ignored as not interesting). We call this a skeleton circuit. Obviously, the complexity of a skeleton circuit defines the complexity of the initial circuit (assuming that any two-qubit gate has a finite cost) and vice versa. We next study skeleton circuits of a certain type and apply the lessons learned to construct circuits for QFT and linear reversible/stabilizer circuits of linear depth in the LNN architecture.
The basic skeleton circuit we consider is illustrated in Fig.  1(a). Mathematically, the skeleton circuit SC is defined as where G * ( * is reserved to represent any possible existing value of subscript) is a two-qubit gate that operates on the qubits indicated in brackets, i * take Boolean values, and for a gate G, G 1 is the gate G itself, whereas G 0 = Id (identity, i.e., this gate is not applied). In other words, i * are used to indicate whether a gate is present or not. Since all quantum gates that operate on non-intersecting sets of qubits commute, the SC circuit can be executed in parallel in (2n−3) computational stages L 1 , L 2 , . . . , L 2n−3 defined as follows: 2n−2 , . . . , L 2n−3 := G i n(n−1)/2 n(n−1)/2 . This is illustrated in Fig. 1(b) in the case n = 5. S : q 5 q 3 q 2 q 4 q 3 q 5 q 1 q 2 q 3 q 4 q 5 q 3 q 4 q 5 q 1 q 2 q 3 q 4 q 1 q 2 q 5 q 4 q 2 q 5 q 1 q 3 q 4 q 5 q 3 q 1 q 2 Next, the circuit can be adapted to the LNN architecture through inserting SWAP gates SWAP(q s , q t ) after each gate G i k k (q s , q t ). This is illustrated in Fig. 1(c) and (d) in the case n = 5. In the gate library containing all possible 2-qubit unitaries, the upper bound for depth is (2n − 3). We next use this result to achieve linear depth circuits for QFT and stabilizer circuits. These are fairly tight upper bounds. With the best known asymptotic result requiring Θ(n 2 ) gates for the QFT, it can be shown that QFT cannot be computed in less than linear depth even in an unrestricted architecture. A counting argument applied to linear circuits [22] shows that there exists a stabilizer circuit that requires at least Θ( n 2 log n ) gates, meaning that it is impossible to find a circuit for it with depth less than Θ( n log n ) even if the architecture is unrestricted. Lower bounds in restricted architectures (all of which turn out to be linear, and thus having the same asymptotic as the upper bound that follows from our construction) are studied in Section III.
Let us note that the skeleton circuit that we consider can be parallelized to linear depth in the LNN architecture for any initial permutation of the input and return the output in any desired order. For that, at most a linear depth swapping stage before and after the circuit is required, which does not change the overall linearity of the depth. The circuit illustrated in Fig. 1(c) not only allows execution in the LNN architecture, it also does not change the LNN connectivity pattern (q 1 − q 2 − . . . − q n ), and thus such circuits can be applied one after the other with no swapping in between. This observation will be used in Subsection II B. If the circuit in Fig. 1(c) is the last computational stage before the measurement is done, the last SWAP need not be applied.

A. QFT in the LNN architecture
A circuit that realizes the QFT and requires no ancilla qubits is illustrated in Fig. 2 FIG. 2: (a) Circuit for n-qubit QFT [5], page 219, illustrated for n = 6. The two-qubit gates are controlled-Z rotations with parameter 1/2 k , where k is the subscript in the gate notation. The single-qubit gates are Hadamard gates. (b) Skeleton circuit of the QFT circuit in (a) composed of generic two-qubit gates.
2(b)) is obviously of the type considered in the previous section with all i * = 1. Therefore, the QFT can be parallelized to linear depth. This is, however, a known result, as [17] reports a construction that is equivalent to ours. It can also be observed that the approximate QFT circuit, where controlled rotations of the QFT circuit with small parameters are ignored, may be executed in linear depth in the LNN architecture. Lower bounds are discussed in Section III, and they apply directly to the QFT circuit.

B. Stabilizer/linear circuits
Synthesis of efficient linear circuits has been studied in [22]. The authors report a synthesis algorithm capable of pro-ducing a circuit with O( n 2 log n ) CNOT gates. It was also proven that their synthesis is asymptotically optimal in that there exists a linear function that requires Θ( n 2 log n ) CNOT gates. In this paper, the goal is different. We target minimization of the depth as opposed to the number of gates used. The depth of our circuit is linear in the number of qubits n, and it is upper bounded by 18n + O(1) CNOTs (assuming every SWAP is substituted with a suitable 3-CNOT implementation) or 6n + O(1) generic two-qubit gates. We also prove asymptotic optimality, which in our case is straightforward.
Every reversible linear function of n variables q = (q 1 , q 2 , . . . , q n ) t can be written as matrix multiplication A q, where A is an n × n Boolean non-singular matrix. Synthesizing such a function is equivalent to composing a sequence of gate operations that transforms matrix A into its reduced echelon form. Due to reversibility, the reduced echelon form of A is the identity matrix. A standard technique for transforming a matrix A to the identity is to apply the Gauss-Jordan elimination algorithm. In the following, we illustrate the application of the Gauss-Jordan elimination algorithm and then modify its circuit to allow it be executed with a linear number of computational stages. Parameters i * and p * take Boolean values and they are used to indicate whether the gate has been applied (1) or not (0). Parameters p * are reserved for the gates applied to update values of the diagonal elements of the matrix A during Gauss-Jordan elimination.
• Step n(n+1) 2 − 1. Transform each a n,n−1 to 0 through application (if needed) of the gate CNOT(q n−1 , q n ). If the gate was applied set i n(n+1) 2 −1 := 1, otherwise, i n(n+1) 2 −1 := 0. At this point, the set of applied transformations reduced matrix A to the upper triangular form with ones on diagonal. The remainder of the algorithm eliminates non-zero elements above the diagonal. • Steps s = n(n+1) 2 ..(n 2 − 1). If a k,l = 0, apply CNOT(q l , q k ) for k = l..1 inside for l = n..2 and set i s to one iff a gate has been applied.
We next use the gate commutation rule (two CNOT gates commute iff target of one gate is not equal to the control of the other) and circuit identity CNOT(a, c)CNOT(c, b) = CNOT(c, b)CNOT(a, b)CNOT(a, c) to move all (n − 1) gates CNOT(a, c) with parameter p * to the front of the network. Note, that every time commutation rule is used, the gates just change their position and every time the circuit identity is applied we introduce a new gate CNOT (a, b). However, such a gate can always be commuted to the closest on the left CNOT(a, b), and this is accounted for by the updates to the i * gate presence indicator. The circuit gets transformed to the one illustrated in Fig. 4. Parameters i * are changed through XORing each i j , j < n(n+1) 2 with p k , for k < n such that q k is the target of the gate used at step j. The constructed circuit consists of three parts marked I-III in Fig. 4. The skeleton of each of these parts is described by equation (1), which is obvious for parts II and III and requires a short explanation for part I. Divide the skeleton circuit (Fig. 1a) into (n − 1) parts with the first containing first (n − 1) gates, the second containing next (n − 2) gates, and so on, the last, (n − 1) st part containing one last gate. Then, gate G i for i = 1..n − 1 from part I of the circuit in Fig. 4 can be matched (via "skeletonization") to some gate in the i th part of the skeleton circuit SC. Thus, every linear reversible function can be computed as a maximal depth 3(2n − 3) = 6n + O(1) circuit. Furthermore, since each SWAP-CNOT pair can be rewritten as two CNOTs (Fig. 5) and SWAP requires no more than 3 CNOT gates, the overall depth in terms of CNOTs can be upper bounded by the expression 18n + O (1). We note that in some quantum information processing proposals pair CNOT-SWAP can be executed more efficiently than a single CNOT or a single SWAP, such as in [23], Fig. 1. Due to the locality constraint our upper bound has the same asymptotic as a lower bound, and thus our circuits are asymptotically optimal. Using H-C-P-C-P-C- H-P-C-P-C decomposition for stabilizer circuits [20] these upper bounds directly translate to at most depth 30n + O(1) circuit composed with generic two-qubit gates, or at most depth 90n + O(1) circuit in the library with single-qubit and CNOT gates.

Encoding and error syndrome circuits for CSS codes
Encoding and error syndrome circuits for CSS codes are of a great practical importance due to the clever error correcting properties of the CSS codes. Such circuits include those illustrated in Fig. 6(a) (encoding; [24]) and Fig. 6(b) (error syndrome; [5]), where single-qubit Hadamard gates are not illustrated since their contribution to the total depth is only a constant, and the controlled gates, each of which may or may not be present (which is defined by the form of the parity check matrices of the corresponding classical codes), are either controlled-NOT or controlled-Z. Our circuit parallelization technique described in the previous subsection applies directly to such circuits since each of them has skeleton as described by the Eq. (1) with n = s + t + 1 for the encoding circuit and n = s + t for the error syndrome circuit. This allows us to execute the encoding circuit in (2s + 2t − 1) stages and the error syndrome circuit in (2s + 2t − 3) (in both cases, s,t ≥ 1) stages composed of generic two-qubit gates. However, a better approach is possible. The following construction is, essentially, a part of the algorithm used to execute SC.
Consider encoding circuit ( Fig. 6(a)). Prepare the qubits in the following LNN connectivity pattern At each level i apply gates whose targets intersect with the sloping lines marked "level i" shown in Fig. 6(a). Each such level is followed by the level of SWAPs applied to the same qubits as the gates from the previous level to allow for the next set of gates to get executed in the LNN architecture. For example, for s = 3 and t = 4  G(b, c 2 ), G(a 3 , c 3 ), and G(a 2 , c 4 ), followed by the swaps SWAP(b, c 2 ), SWAP(a 3 , c 3 ), and SWAP(a 2 , c 4 ). Thus, the total depth of the encoding circuit executable in the LNN architecture will be equal to (s +t + 1) if it is allowed to be composed of generic two-qubit gates. This is almost half of what was expected if this circuit were matched to the SC first. This translates to a depth 2(s + t + 1) circuit with controlled-NOT, controlled-Z and SWAP gates. Similarly, the depth of the error syndrome circuit composed with generic gates and executable in the LNN architecture is (s + t − 1). Application of the technique described in this subsection to executing the error syndrome circuit for Steane's code ( [5], Fig. 10.16) in the LNN architecture shows that this can be done in 12 stages composed of generic two-qubit gates or 26(= 2 * 12 + 2) stages composed of Hadamard, controlled-NOT, controlled-Z, and SWAP gates. We can show that the encoding circuit of [24], Fig. 8b, can be executed in 23 stages composed of generic two-qubit gates or, alternatively, 68 (= 3 * 23 + 1 − 2: pairs CNOT-SWAP must be combined, we need an extra level for Hadamard gates, but do not need to apply last SWAP) stages composed of CNOT and Hadamard gates in the LNN architecture. Our result for the depth, 68, is notably better than 177 found by the automated procedure of [24].

III. LOWER BOUNDS
In this section we study lower bounds on the depth of skeleton circuit SC defined in equation (1) assuming all gates are present (i.e., each i * = 1). We further assume that a pair of gates G(q i , q j )SWAP(q i , q j ) requires two units of the execution time, one for each of the gates. In practice, a direct implementation of pair G(q i , q j )SWAP(q i , q j ) may be more efficient [6], but the particulars of such a construction depend on the specific Hamiltonian, which is unknown in the general case. The depth of circuit illustrated in Fig. 1(c) is thus (4n − 6). The lower bounds achieved below are directly applicable to the QFT circuit.
To prove lower bounds, we need to restrict the set of possible computations. We define two circuit type quantum com-putational models A and B. We require that for each of them in order to compute the SC (equation (1)) all n(n−1) 2 two-qubit gates need to be executed, and no ancilla qubits may be used. Furthermore, • in model A we assume that the gates required to be executed in SC cannot be commuted (other than triviallya pair of gates operating on non-intersecting sets of qubits always commutes); • in model B we allow possibility of the execution of gates in any order (i.e., this lets us obtain bounds that allow commuting gates through the circuit, without worrying about which gates actually commute, and what kind of corrections are needed in case they do not commute).
The architectures considered in this paper are LNN, 2D square lattice, and bounded degree graph with the degree of each vertex no more than k. We next prove a number of lower bounds, refer to Table I.

LNN 2D square lattice bounded degree graph
First, denote each depth-1 computational stage (logic level) by L and each depth-1 swapping stage by S. Every three stages of the SC have a single fixed qubit that interacts with three other qubits. This is either q 1 , q 2 , or q n . Thus, every three logic levels have to be separated by a round of SWAPs, each having depth at least 1, i.e. each sequence LLL must be replaced by LSLL or LLSL to be able to run the circuit in the LNN architecture. We call this 3L → 1S requirement. With the 3L → 1S requirement, the total depth must be at least 2n − 3 + ⌈ 1 2 (2n − 5)⌉ = 3n + O(1) logic levels. Therefore, using just the 3L → 1S requirement proves that our circuit is at most factor 4 3 off the optimum. We now improve this bound to 10n 3 + O(1) by showing that every 4 computational stages must be separated by at least depth-2 swapping stage (4L → 2S requirement). 4L → 2S is slightly more restrictive than 3L → 1S. The difference between the two is that in one LLSLL is allowed, but not in the other. We next prove that depth-1 level does not suffice in separating some two computational stages from the following two by exploring the properties of SC and the LNN architecture.
Assume all 4 computational stages L i , L i+1 , L i+2 , and L i+3 are solely in the first half of SC. The second half is symmetric to the first half and thus a similar proof holds for it. We do not prove the boundary case (where one part of the 4stage computation is in the first half of the SC and the other part is in the second half) because its contribution to the final figure is only a constant. Next, assume i is odd. The proof for even values i is analogous. Name the qubits q 1 , q 2 , . . . , q n top to bottom. The computational stages L i and L i+1 use which in the LNN architecture can only be aligned as follows: The computational stages L i+2 and L i+3 use interactions q i+4 − q 1 , q 1 − q i+3 , q i+3 − q 2 , . . . , q i+3 2 − q i+5 2 . In particular, stages L i+2 and L i+3 require interaction q i+3 2 − q i+7 2 , and qubit q i+7 2 is used both in L i+2 and L i+3 . However, we know that after completion of stages L i and L i+1 , the architecture allows interactions in the following order q i+3 The LNN architecture distance between q i+3 2 and q i+7 2 is 4. A depth-1 swapping reduces the architectural distance between these qubits by at most 2, which is not enough for the desired interaction to be allowed. Thus, the depth of swapping must be at least 2. This concludes the proof of the 4L → 2S requirement.
We finalize the proof of 10n 3 + O(1) lower bound by observing that for a circuit with 2n + O(1) stages L we need to have at least 4n 3 + O(1) stages S to satisfy 4L → 2S requirement. Thus, the total number of stages required to execute SC in LNN is 10n 3 + O(1). This implies that the circuit we constructed explicitly ( Fig. 1(c)) must be within factor of 6 5 from optimum.
3n + O(1) lower bound in 2D square lattice, model A. We prove that every three computational stages L i−2 , L i−1 , and L i , where i = 2k + 1 and k = 1..⌈ n−2 2 ⌉ (this means that all computational stages are in the first part of SC; the proof for the symmetric second part is similar) must contain at least one swapping stage if ran in 2D square lattice architecture. We prove this by finding three interactions that form a loop. Vertices in such loop cannot be isomorphically mapped to the vertices of 2D square lattice. The interactions that form such a loop, assuming qubits are named q 1 , q 2 , . . . , q n top to bottom, in L i . This proves that for every possible value k it is required to have at least one swapping stage, which results in the construction of 3n + O(1) lower bound.
The lower bound that we just proved may be interesting to those experimentalists working on implementing 2D architectures for quantum information processing. The lower bound shows that, with certain restrictions, the QFT in 2D square lattices cannot in principle be parallelized any more efficiently than to a depth at least 3 4 of the depth of QFT circuit executable in the LNN architecture. and they all require different qubit-to-qubit interactions to be available. Next, note that in the LNN architecture application of a single SWAP may make at most two new interactions become available for a gate to be applied on. Thus, the total number of SWAPs that one must execute in a circuit to go through all n(n−1) ⌉. This means that the total number of gates to be executed in the LNN architecture to compute SC must be at least n(n−1) 2 + ⌈ (n−1)(n−2) 4 ⌉ = ⌈ (3n−2)(n−1) 4 ⌉. At most ⌊ n 2 ⌋ gates can be executed in paral-lel. Thus, the depth of the circuit is at least the minimum total number of gates to be executed divided by the maximum number of gates that can be executed simultaneously, i.e. 3n 2 + O(1). This lower bound is constructed based on the assumption that all gates in SC need to be executed, and does not take into account that the order they are executed in is important. Thus, the restriction on the form of the computation is significantly weaker than that for model A, and the proven lower bound is looser.
Generalizing the above techniques, it can be shown that in an architecture where each qubit has a finite number of neighbors bounded by number k: • the lower bound for executing SC is (2 + 2 k )n + O(1) in model A; • the lower bound for executing SC is (1 + 1 k )n + O(1) in model B.

The 5n
4 + O(1) lower bound announced in Table I follows from the second of these two statements. Given the linearity of proven lower and upper bounds, we have just shown the asymptotic optimality of the depth of our skeleton circuit in the restricted architectures considered in this paper.

IV. CONCLUSION
In this paper we studied the complexity of the execution of the quantum Fourier transformation and stabilizer circuits in restricted architectures.
We reconstructed the depth 4n + O(1) circuit (composed with SWAP and controlled-Z gates) for QFT initially reported in [17] which is implemented in the LNN architecture. With the application of our generalized technique we showed how the approximate QFT circuit can be executed in linear depth in the LNN architecture. We proved a number of lower bounds for the depth of QFT circuit, which are all a constant factor away (ranging from 1 4 to 5 6 , and depending on the computational model and assumptions made) from the above upper bound. Some of our lower bounds can be used by experimentalists working on implementing advanced architectures as a guide to how complex architectures may need to be for particular types of computations. For instance, we proved that, with certain restrictions, the QFT circuit in 2D square lattices cannot in principle be parallelized more than to the depth equal to More importantly, we presented a constructive algorithm for synthesizing linear depth stabilizer circuits in the LNN architecture. In particular, we showed that any stabilizer circuit can be executed in at most 30n + O(1) stages each composed with generic two-qubit gates, which in the library with CNOT and single-qubit gates translates to at most depth 90n + O (1) circuit. This upper bound is asymptotically optimal. We considered specific stabilizer circuits and showed how these circuits can be executed faster than reported by previous researchers [24].


extfieldsofstudy:
Computer Science
Mathematics

text:
Neighbor Discovery in Wireless Networks:A Multiuser-Detection Approach

We examine the problem of determining which nodes are neighbors of a given one in a wireless network. We consider an unsupervised network operating on a frequency-flat Gaussian channel, where $K+1$ nodes associate their identities to nonorthogonal signatures, transmitted at random times, synchronously, and independently. A number of neighbor-discovery algorithms, based on different optimization criteria, are introduced and analyzed. Numerical results show how reduced-complexity algorithms can achieve a satisfactory performance.

Introduction
Of late, wireless networks, and in particular sensor networks, have been the object of a good deal of interest, also spurred by the manifold applications they can be associated with (see, for exam-if its amplitude, received by the latter, exceeds a preassigned activity threshold, say τ A . 2 Moreover, nodes cannot transmit and receive simultaneously on the same channel, 3 and the maximum number of active nodes is fixed and finite. We clarify that a neighbor relation between two nodes need not be bidirectional, since each node discovers those nodes it can receive from.
The organization of this paper is the following. In Section 2 we provide a model for the physical aspects of the networks, and we formulate our problem. ND algorithms are introduced in Section 3, and analyzed in Section 4. Section 5 shows some numerical results, while Section 6 concludes the paper.

Signal model and problem formulation
Our scenario is based on the transmission scheme illustrated in Fig. 1, which corresponds to node 0 searching its own neighbors among four other nodes. 4 In every time interval ("slot"), each node i, i = 0, 1, . . . , K, transmits its own signature, independently of the other nodes, with probability ε i , while otherwise (and hence with probability 1 − ε i ) it senses the channel. This probability is actually designed as a part of the algorithm, and it influences the ND algorithm performance, as we shall examine in our analysis.
The ND algorithm runs in a finite period, called a discovery session, whose duration is denoted T D . During T D , every active node transmits a number of signals containing one or more copies of than running ND periodically as an application program. 2 Note that this definition can be generalized: for example, one may define a neighbor as one whose power-tointerference plus noise ratio exceeds a given threshold. In this paper we stick to a more restrictive definition, which allows simpler algorithms. In general, any information gleaned through ND will help scheduling, or medium-access control, or routing algorithms to be more efficient, because they will be armed with neighbor information. 3 For simplicity, we disregard the more general case of nodes that can be in an idle state, i.e., they are neither receiving nor transmitting. 4 We consider node 0 to be the reference node. Since all nodes are at the same hierarchical level, the same analysis applies to any node. its signature. Each signal has duration T = T D /N, with N the number of slots in the discovery session. The network is assumed to be unsupervised, which implies that all nodes are independent and at the same hierarchical level: as a consequence, the ND algorithm is run in parallel by all nodes. Under the assumptions made in Section 1, the baseband representation of the signal received by node 0 in the time interval (n − 1)T, nT , n ∈ {1, 2, . . . , N}, is where α k denotes the channel gain, i.e., the complex amplitude of the signal received from node k and assumed to be constant during all the discovery session, s k (·) is the kth node signature, ψ k,n is a random variable taking value 1 if node k is transmitting at time n, and value 0 otherwise (so that P(ψ k,n = 1) = ε k ), and z(t) is additive white complex Gaussian noise having spectral density 2N 0 . We assume α k to be modeled by a complex circularly symmetric Gaussian random variable with variance 2σ 2 k . The signatures can be expressed as where s l,k ∈ {−1, +1} is the lth chip of the kth signature, L is the processing gain, T c = T /L is the chip duration, and φ(·) is the (unit-energy) chip waveform. 5 The slots devoted to channel sensing need not be adjacent: however, due to our flat-fading assumption, we may assume, without any loss of generality, a sensing phase of consecutive slots with intermittent other-users activity, with ν 0 the number of slots where node "0" is transmitting. Notice that M 0 is random (N is assumed fixed and node 0 has its own activity factor ε 0 ), but the value it takes is known to node 0. Hence, in all subsequent derivations we refer 5 The signatures are assumed to have unit energy.
Our problem is now reduced to determining the indexes k such that {|α k |} K k=1 exceed an "activity threshold" τ A , based on model (4).
Since z(t) is white Gaussian noise, the components of y(t) orthogonal to the subspace spanned by the signatures are irrelevant to our detection problem [8]. As a consequence, we might in principle adopt the signatures themselves, and their delayed versions, as an expansion basis for such a subspace. Alternatively, we may use the L−dimensional orthonormal basis to expand the signal in the interval (p − 1)T, pT . The two approaches are obviously equivalent, but the latter is mandatory in situations where the discovering node has no prior information as to the signatures of other users: although we do not deal blind ND in this paper, we choose this one due to its inherent flexibility.
Defining the scalar products with * denoting conjugation, we obtain a vector representation y p [y 1,p , y 2,p , . . . , y L,p ] T 7 of the signal received in (p − 1)T, pT : 6 Notice that the index n refers to consecutive time slots, while p refers to the time scale defined by the silent phase of node "0". 7 The symbol T denotes transposition operation The ND problem now consists of assessing, after observing the set of M 0 vectors y 1:M 0 {y 1 , . . . , y M 0 }, which ones, among |α 1 |, . . . , |α K |, exceed the "activity threshold" τ A .

ND algorithms
A sensible criterion for the selection of a ND algorithm consists of minimizing the probability of choosing, among the K network nodes under scrutiny, an erroneous set of neighbors of node 0.
Since there are 2 K such sets, each corresponding to one hypothesis H, this error probability is minimized by the maximum a posteriori (MAP) decision rule: where P (H) is the a priori probability of hypothesis H, and p(y 1:M 0 |H) is the probability density of the observations given H. As an example, if K = 2, the 4 hypotheses are shown in Table 1.
which has a complexity that grows exponentially with KM 0 .
To overcome this complexity obstacle, the decision on the neighbor set works as follows. We first obtain estimates of the instantaneous powers |α i | 2 of all nodes, next we decide that a node is a neighbor by comparing each of them with a threshold, i.e., where H 1 : The received instantaneous power exceeds τ 2 A .
H 0 : The received instantaneous power is below τ 2 A .
The performance of this test can be expressed through its probability P (i) F of a false-alarm and its probability P (i) M of a miss, defined as: These are related to the overall error probability through 8 Now, the maximum-likelihood (ML) estimators of the instantaneous powers can be obtained by jointly estimating α and the matrix sequence with † denoting Hermitian operation. Computing with α i the solution corresponding to Ψ 1:M 0 ,i , and recalling that ML estimates commute under nonlinear transformations, test (10) can be implemented by using Even with this receiver, implementation complexity would be unrealistic, and hence a further simplification is called for. Instead of dealing with the receive/transmit pattern related to the whole discovery session, we rather obtain estimates based on a single T -interval observation, which are then combined according to a suitable integration strategy.

Suboptimum ND algorithms
Consider again model (7). The ML estimate of Ψ p α, based upon the observation y p available in slot p, is where S + denotes the pseudo-inverse of the tall matrix S.
A closer look at this solution reveals that, since the interference from the other users is completely eliminated, at the price of some noise enhancement, reflecting the increase of the variance of its ith compo- It is interesting to notice that this estimate is noise-limited, but not interference-limited, implying that any receiver based on (15) is asymptotically efficient [10]; likewise, near-far resistance is granted [10].
Since there are M 0 sensing phases, the M 0 estimates resulting from repeated application of (15) should be combined to yield the final test statistic. Borrowing techniques from radar detection theory, reasonable combination criteria are coherent integration (CI), wherein an estimate of the instantaneous power is obtained as and incoherent integration (II) Notice that implying that both |α i | 2 II and |α i | 2 CI can be interpreted as biased estimators of the instantaneous power received in each slot from node i: biases can however be absorbed in the detection thresholds τ i , while what matters here is that they are both consistent in the mean square sense, a property that will be exploited later on. Inserting (17) and (18) into (10), and skipping factors that can be absorbed in the detection thresholds, we obtain the coherent detector (CD) and the Incoherent Detector (ID): DA, EB, ML: Neighbor Discovery in Wireless Networks February 5, 2008 Notice how the CD can also be interpreted in a different way. Indeed, it may be obtained by first pre-processing the observations so as to form the cumulative sum: and V diag(ν 1 , . . . , ν K ), then multiplying the new observation by S + and finally extracting the ith component to form the test statistic (21). Rewriting equation (23) in the form: , where I L is the L × L identity matrix, the CD is easily seen to be a member of the family of linear ND tests (LNDT), wherein a decision on the proximity of user i is made based on the rule: Thus, the CD (21) can be also interpreted as the zero-forcing (ZF) member of the family (26), obtained as the unique solution to the constrained minimization problem: with β = 0, which yields 9 where S i is the L × (K − 1) matrix obtained skipping the i−th column from S and P i denotes the projector onto the orthogonal complement of the column span of S i . For future reference we 9 Notice from (28) that the parameter β 2 has been set to where s i,⊥ denotes the projection of s i on the above orthogonal complement: needless to say, since , the noise power is enhanced by a factor (S † S) −1 i,i . The vector c i can be designed according to a number of different criteria. For example, in [12] an LNDT based on conventional matched filtering (MF), i.e., assuming has been proposed and analyzed for ND [12]. MF is indeed simple, but it results into interferencelimited performance, as we shall prove soon, nor does it retain the near-far resistance property granted by ML-based detectors.
A possible alternative to the ZF criterion is offered by the minimum-mean-output-energy (MMOE) strategy, first introduced in [11], wherein the vector c i is obtained as the unique solution to the following constrained minimization problem: namely: Due to the invariance of the decision rule to any positive scaling of the test statistic, an equivalent detector relies upon setting It might be worth recalling here that, since MMOE is itself asymptotically efficient. Likewise, it retains the near-far resistance property since the projection direction c i,M M OE tends to become orthogonal to those signatures whose amplitudes become increasingly large [11]. The advantage of (33) over ZF is that it easily lends itself to adaptive implementations in situations where the signatures of the active users are unknown. Even though we do not deal with adaptive ND in this paper, we anticipate that a number of reduced complexity algorithms, ranging from the O(L)-complex Least Mean Squares to the O(L 2 )-complex Recursive Least Squares, can be easily applied for adaptive MMOE implementation.

Analysis
From now on we assume that the node to be detected is node "1". Consider first the ID. The conditional false-alarm and miss probabilities in assessing the proximity of node 1 can be written as: with χ 1 M 0 p=1 |(S + y p ) 1 | 2 . Given |α 1 | and Ψ 1:M 0 , χ 1 is noncentral chi-square distributed with 2M 0 degrees of freedom and parameters ν 1 |α 1 | 2 and σ 2 n,1 = (S † S) −1 1,1 N 0 , implying where Q M 0 (·, ·) is the Marcum function of order M 0 . Using the series expansion of modified Bessel functions we obtain are the upper incomplete Gamma function and its regularized version, respectively, while ρ 1 is the signal-to-noise ratio after decorrelation, i.e.: We thus obtain the conditional measure: which should be averaged over ν 1 to yield the conditional probability of a miss given M 0 . Similar developments hold for P F , yielding are the lower incomplete Gamma function and its regularized version, respectively. Finally, from (43) we easily obtain: Consider now the test family (26). Notice that, since |g 1 | 2 is conditionally chi-square with two degrees of freedom, given α 1 , whereby, reproducing the same steps leading to (42) and (45), we obtain: where ρ eq represents the signal-to-interference-plus-noise ratio (SINR) at the output of the linear filter, i.e.: Relationships (48) and (49) are quite reminiscent of (42) and (45), respectively, one major difference being the dependency of the performance on ν 2 1 ρ eq , rather than ν 1 ρ 1 . Of course, the quadratic factor in ν 1 stems from the fact that linear detectors operate on a coherent combination of the observations, while ID combines the slot-by-slot estimates incoherently. Notice, however, that the above relationships represent conditional measures, given M 0 (i.e., given ν 0 ) and {ν i } K i=1 . If the discovery session is long enough, so that the matrix sequence Ψ 1:M 0 may exhibit its typical behavior, namely, if N(1−ε 0 ) ≫ 1, then the ν k 's tend in probability to M 0 ε k , whereby the unconditional performances may be obtained by averaging the corresponding conditional measures on the typical set of values of {ν k } K k=1 and M 0 only, implying: In this limiting situation, it is interesting to notice the relationship between the "cumulated" SNR's for ID and CD (i.e., the ZF of (28)), i.e. (see also (29) and subsequent comments): Thus, in terms of cumulated signal-to-noise ratio and for large N, ID seems to be preferable to CD, even though a global superiority cannot be claimed due to the different forms assumed by the respective false-alarm and miss probabilities.
So far no criterion has been given to select the decision threshold τ 1 . Notice, however, that the consistency of the estimates (17) and (18) allows devising the asymptotically optimum thresholds (those achieving minimum error probability for large N) from (19) and (20) in the form: For short discovery sessions, and under known activity factors of nodes to be discovered, optimum detection thresholds can be obtained by evaluating numerically the unconditional error probability, and then determining the points where it has a minimum.

Results
We consider here a fully loaded network with K + 1 = 7, each node being assigned a length-7 m-sequence. As in the previous section, we assume that node "0" has to decide on the proximity of node 1. Figure 2 assumes SNR 1 σ 2 1 /N 0 = 0 dB, N = 100, a power-controlled scenario wherein all nodes are received with the same average power, uniform activity factor (ε k = ε = 0.5), and an activity threshold equal to the median of the fading amplitude distribution, i.e., such that P(|α 1 | > τ A ) = 0.5. The figure represents the pair P M , P F for the various receivers examined so far. Interestingly, "conventional" MF suffers from the presence of the other nodes even in this rather benign situation, while MMOE, ZF (which coincides with CD rule) take advantage of their asymptotic efficiency: from now on, conventional MF will not be considered any longer. The interested reader is deferred to [12] for a fairly thorough performance assessment.
The reliability of the asymptotic approximation for long discovery sessions can be assessed through figures 3-5 for the CD, and through figures 6-8 for the ID, which refer to the same scenario as in Fig. 2. The curves of these figures represent: -The unconditional false alarm and miss probabilities obtained by simulation.
-The same pair obtained by a semi-analytical method, i.e., by estimating the averages of their conditional counterparts.
From the plots, it is evident that the asymptotic approximation tends to overestimate the performances in the interesting region of low error probabilities, while coming closer and closer to the true performance as N increases: notice that the approximation is extremely tight for N = 500, a realistic value indeed in real applications, which, for ǫ 0 = 0.5, corresponds to M 0 ≃ 250. However, it should be kept in mind that, for larger activity factors of the discovering node, the minimum value of N for the asymptotic behavior to be reached inevitably increases.
The validity of the approximations (52) and (53), yielding the asymptotically optimal thresholds for CD and ID, respectively, can be verified through Figs. 9 and 10, showing P (e) versus τ 1 for CD and ID, respectively, for some values of SNR 1 , ε=0.5, N = 500 and τ A such that P(|α 1 | > τ A ) = 0.5. These plots, obtained numerically, show that the error probability admits a unique minimum; moreover, the optimal values of τ 1 are surprisingly close to those resulting from an optimum value is practically independent of SNR 1 for CD, while being strongly tied to SNR 1 for ID. Fig. 11 is aimed at comparing CD and ID. It represents the error probability versus the signalto-noise ratio SNR 1 using the optimal thresholds for both receivers, and assuming again ε = 0.5, N = 500, and τ A as before. It is interesting to notice that CD outperforms ID for small signal-tonoise ratios, while ID is preferable for medium-to-large values of SNR 1 .

Conclusions
We have examined the problem of discovery which nodes are neighbors in a wireless network operating over a fading channel. The optimum Bayesian decision rule has been derived, showing that its complexity is practically prohibitive. Two suboptimum neighbor-discovery algorithms have been introduced, based on standard techniques of coherent and incoherent integration. We show how coherent integration may be viewed as a particular case of a family of algorithm akin to Linear Neighbor Discovery Tests (LNDT). Theoretical analysis allows one to understand the design of a system employing such algorithms according to constraints on error rate, signal-to-noise ratio and discovery session duration. Finally, algorithm optimization was considered, and formulas were derived for asymptotical optimum threshold.


s2fieldsofstudy:
Computer Science
Linguistics

text:
Mutaphrase: Paraphrasing with FrameNet

We describe a preliminary version of Mutaphrase, a system that generates paraphrases of semantically labeled input sentences using the semantics and syntax encoded in FrameNet, a freely available lexicosemantic database. The algorithm generates a large number of paraphrases with a wide range of syntactic and semantic distances from the input. For example, given the input "I like eating cheese", the system outputs the syntactically distant "Eating cheese is liked by me", the semantically distant "I fear sipping juice", and thousands of other sentences. The wide range of generated paraphrases makes the algorithm ideal for a range of statistical machine learning problems such as machine translation and language modeling as well as other semantics-dependent tasks such as query and language generation.

Introduction
A central tenet of statistical natural language processing (NLP) is "there's no data like more data". One method for generating more data is to restate each phrase in a corpus, keeping similar semantics while changing both the words and the word sequence. The efficacy of this approach has been well-established in many areas, including automated evaluation of machine translation systems (Kauchak and Barzilay, 2006), text summarization (Kittredge, 2002), question answering (Rinaldi et al., 2003), document retrieval (Zukerman and Raskutti, 2002), and many others.
Most of the reported work on paraphrase generation from arbitrary input sentences uses machine learning techniques trained on sentences that are known or can be inferred to be paraphrases of each other (Bannard and Callison-Burch, 2005;Barzilay and Lee, 2003;Barzilay and McKeown, 2001;Callison-Burch et al., 2006;Ibrahim et al., 2003;Lin and Pantel, 2001;Pang et al., 2003;Shinyama et al., 2002). Mutaphrase instead generates paraphrases algorithmically using an input sentence and FrameNet, a freely available lexico-semantic resource (information regarding FrameNet, including relevant terminology, is presented in Section 2). Conceptually, the Mutaphrase algorithm takes a semantic specification of a sentence, provided by an automatic semantic parser such as Shalmaneser (Erk and Padó, 2006), and recursively replaces each semantically parsed phrase with a semantically similar phrase. To generate each new phrase, each of the semantic parts of the original phrase is mapped, using FrameNet data, onto a new word or phrase whose position and syntactic marking may be quite different.
The Mutaphrase algorithm outputs a large set of paraphrases with a variety of distances from the input in terms of both syntax and semantics; see Figure 1. Depending on the needs of the application, filtering can be applied to limit the distance to a desired range. For example, language modeling may benefit from a wider variety of semantic outputs, since if I like eating cheese is in-domain, then I like sipping juice is also likely in-domain. Other applications, e.g. Question Answering, require more stringent limits on semantic distance. See Section 4.

Current Limitations
The current implementation of Mutaphrase suffers from several limitations. Perhaps the most significant is that the input sentences must be semantically labeled using FrameNet annotations. Since no automated systems for FrameNet-specific annotation are currently incorporated into our algorithm, input is limited to hand-annotated sentences. Also, certain types of semantic ill-formedness are permitted (e.g. I like sipping meat), and some types of syntax are not well supported (e.g. conjunctions, relativeclauses). We believe all these factors can be addressed; they are covered briefly in Future Work (Section 4). We confine ourselves in other sections to describing the core Mutaphrase algorithm as currently implemented.

FrameNet
The primary resource used in Mutaphrase is FrameNet (Fontenelle, 2003;FrameNet, 2007b), a lexico-semantic database that describes concepts and their interrelations, wordform and wordsequence information, syntactic categories, and mappings between conceptual and lexical/syntactic information. All of these are grounded in handannotated examples of real-world sentences. At a slightly more abstract level, FrameNet can be described as providing a two-way mapping between meaning (semantics) and form (syntax, wordforms, sequences).

Semantics
The conceptual information is represented using frames, where a frame is a type of schema or scenario (e.g. Motion, Commercial transaction), and frame elements (FEs), which are the participants and parameters of the frames (e.g. Motion.Path, Commercial transaction.Buyer). Frames and their frame elements are related and mapped with a limited type of conceptual ontology involving Inheritance (i.e. subtype), Subframe (i.e. temporal subpart), Using (i.e. presupposition) and a few other relation types.

Syntax
On the form side, the representation is more minimal. Wordforms and word-sequences are represented so that words with multiple wordforms (e.g. take/took) and word sequences with wordforms (e.g. take/took off ) can be referred to as unitary objects. We have a category Support (and the more specific label 'Copula') for pieces of multi-word expressions that are optional for expressing the semantics of the whole (e.g. take in take a bath). FrameNet also represents a small but sufficiently rich set of syntactic categories of English (i.e. phrase types or PTs, such as 'Sfin', i.e. finite sentence) and syntactic relations (i.e. grammatical functions or GFs, e.g. 'Object').

Syntax-Semantics Bindings
The most vital part of the FrameNet data for our Mutaphrase algorithm is the mappings between semantics and syntax. There are several categories pertaining to this in the data. Lexical units (LUs) are a pairing of words/word sequences with the frame each evokes. The valences for each LU are sequences in which semantic and form information pertinent to phrases are paired. They are not stored in the database, so we have created a process that produces them entirely automatically (see 3.2). For example, for the LU hand in the Giving frame and possible in the Likelihood frame, we have the following annotated sentences: Example 1 above shows a typical valence, in which most of the positions are semantically labeled with a frame element which is paired with syntactic GF and PT information. The second annotation (2) is more complex, exemplifying each of the major categories that make up the positions of a valence. The categories are: 1. a Null element, with syntax but no semantics (usually there or it) 2. a Support or Copula with its wordforms 3. a Target (i.e. an LU or word that is part of an LU) with its wordforms, conceptually representing a frame 4. a frame-element/phrase-type/grammaticalfunction phrase description, which puts together semantic (FE) information with syntax (GF and PT); the PT also indicates fixed words (e.g. the word that in the example above) We can abstract away from the individual sentences, preserving only the sequences of positions with their features, as in the following representation of sentence 2 above:

Null(it), Copula, Target(possible), Hypothetical event/Dep/Sfin(that)
These abstract valences are the basis for the algorithm we present here. There are typically between two and ten basic patterns associated with each annotated lexical unit, encompassing alternations in the realization of FEs such as Active/Passive (I recommended her vs. She was recommended by me), the Dative Alternation (He handed the paper to Stephen vs. He handed Stephen the paper), optional elements (I ate dinner vs. I ate) and many more.
Basing our algorithm on rearranging the fillers of these FEs allows us to abstract away from syntax, since the FEs of a frame express the same relations regardless of the LU or syntax they occur with. Some meaning differences between LUs within the same frame (e.g. drink vs. eat) are not overtly modeled in FrameNet. Other resources, such as Word-Net, could provide added information in cases requiring finer granularity (see Section 4).

Mutaphrase Algorithm
At a very high level, the paraphrase algorithm that we use is as follows: we begin with a sentence with frame-semantic annotation, replace each lexical unit and its associated frame Elements with an alternative valence, then filter the output for its syntactic and semantic fit with the original sentence. The valences may be drawn from either the same LU, an LU of the same frame, or an LU of a related frame.  Figure 2 shows an example of one step of the algorithm. An input tree for the sentence I want your opinion is shown in Figure 2A. The particular valence for the Desiring frame in Figure 2B describes the relations between the word desire and its dependents in sentences like A meeting was desired. Because the phrase types and grammatical functions of the FEs between the input and the attested valence are compatible, it is possible to replace the input frame with the new valence. The output is shown in Figure 2C.
The remainder of this section describes in more detail how this algorithm is implemented.

Building a Syntax/Semantics Tree from FrameNet Data
Because the FEs of the original sentence are often filled by phrases with their own annotation, the initial syntactic/semantic annotation is (conceptually, at least) in the form of a graph. Typically, the graph is nearly a tree, with few or no non-tree edges 1 .
Hereafter, we will use the term 'tree' even for the cases where there are non-tree edges.
Since the data are not organized in this format in the FrameNet output, we have implemented a routine which can turn FrameNet data into a syntacticosemantic tree; tree examples can be seen in Figure 2A and Figure 2C.

Building Ordered Valences from FrameNet Data
As mentioned in Section 2.3, we have constructed a routine to parse FrameNet data to produce the valences for each LU of a frame. The basic output is an ordered list of syntactico-semantic elements, optional apositional features (e.g. passive +/-), and the frequency of the pattern. 2 One innovation of our algorithm is its ability to handle multiword LUs. It simply identifies each word of the LU as a separate element in the list, marking each with the label 'Target'. Thus the ordered valences of take off.v in the Undressing frame include, among others: • Wearer/NP/Ext, take/Target, off/Target, Clothing/NP/Obj; Frequency: 57/68 (e.g. I TOOK OFF my watch) • Wearer/NP/Ext, take/Target, Clothing/NP/Obj, 1 These non-tree edges are introduced when a phrase is an FE of more than one frame. In keeping with normal syntactic analysis, we treat the node as non-local to all but one parent.
2 Although frequency of a particular pattern in the FrameNet data is not strictly representative of the frequency of that pattern in the corpus, a close examination reveals that the rank order of patterns is largely identical, i.e. the most common pattern in FrameNet represents the most common pattern in the corpus. How useful this inexact statistical data will be is the subject of future research. off/Target; Frequency: 7/68 (e.g. You TAKE your shoes OFF) One way of thinking about the valence set is that it represents possible orderings of subparts of a phrase that is semantically a frame instance and syntactically a phrase headed by the Target (see, for example, Figure 2B). This semantic/syntactic information is detailed enough to build the syntax of a phrase, given FrameNet-style semantics.

Core algorithm
Once the input has been turned into a tree and there is a set of alternative ways of expressing each frame that is in the input, the algorithm then recurses downward and then, as it returns up, replaces each phrase/frame node with a set of alternative phrases. In the simplest case, these phrases are built from all the valences that are attested for the frame that the original phrase expressed 3 . In other words, our algorithm is a recursive tree-rewrite in which the current valence of the current LU is replaced by many alternate valences of many different LUs.
In the recursion, word and phrase nodes not headed by an LU are kept the same (except for pronouns, which are expanded to all their wordforms, e.g. me to I/me/my/mine). The child phrases of such an unparaphrased node, if they are headed by an LU or pronoun, can be paraphrased as long as the paraphrases match the phrase type and grammatical function of the original child phrase.
In Figure 2, the original sentence (represented in Figure 2A) has the phrase representing the Desiring frame replaced with an alternative phrase evoking the same frame ( Figure 2B) to produce a new, roughly semantically equivalent sentence (Figure 2C) by expressing the same set of frames in the same FE relations to each other.
In practice, we have to throw away at the outset many of the valences because they include FEs that are not in the input sentence 4 or because they have syntactic requirements of their child phrases which 3 Our algorithm will work just as well with related frames as long as the relevant FEs are mapped in the FrameNet data. Controlling the distance, direction, and relation-types of related frames that are included for paraphrase (if any) is one way to control the degree of semantic diversity of the paraphrase output. See further Section 3.4. 4 Thus attempting to use the valence Experiencer/NP/Ext, Degree/AVP/Dep, want/Target, Event/NP/Obj (e.g. I really cannot be filled by a paraphrase of the child phrases. For example, for the input sentence I gave presents to friends, the code can output 560 (unfiltered) paraphrases. A random selection from the output includes Presents bequeathed to friends, I handed in presents, and Presents donated by I. Of these, the first and last are filtered out as not filling the original sentential context and the last, in addition, is filtered out because of the mismatch between the pronoun wordform I and the non-subject grammatical function.
To further refine the paraphrases, we must eliminate examples that are not compatible with the input sentence. In our current implementation, our algorithm filters out incorrect syntax during the recursion over the tree. Ultimately, we will also filter out malformed semantics. The rest of this section is devoted to an explication of the details of this filtering.

Syntactic/Semantic Compatibility
For both syntax and semantics, the degree of viability of a paraphrase can be divided up into two components: well-formedness and similarity. Syntactic and semantic well-formedness is always desirable and the algorithm seeks to maximize it in ways that are outlined below. Similarity between the original sentence and its paraphrases (or among the paraphrases), however, may be more or less desirable depending on the task. Figure 1 shows an example of the various degrees of syntactic and semantic similarity of the paraphrase output. To maintain flexibility, we will need several control parameters to allow us to filter our output for syntactic/semantic similarity.

Syntactic Compatibility
Syntactic incompatibilities most commonly result from gross mismatches between the Phrase Type called for in a new valence and the Phrase Type possibilities available for the child phrase.
For example, if the initial sentence for paraphrase is I want your opinion as in 1 below (repeated from Figure 2), Valence 2 below represents a PT mismatch, since I, an NP filler of the Experiencer role want another chance) when paraphrasing the initial sentence in Figure 2 will not work, since there is nothing in the original to fill the Degree FE mentioned here. in the original sentence, is not modifiable into an adjective phrase (AJP). This filtering is vital, as otherwise valence 2 would yield the awful There is me desire for your opinion.
However, phrase types that are not exact matches may nevertheless be compatible with each other. Valence 3, for example, is compatible with the original valence, since the original Experiencer and Event FEs were filled by NPs, to which prepositions can be added to match the PP realizations required by Valence 3. This yields another paraphrase of the sentence in Figure 2: There is a desire in me for your opinion. Similarly, full sentential clauses can be modified to match VPs by truncation of the External (subject) argument, etc. A phrase from the original sentence may also be omitted to match an empty phrase in the paraphrase, as seen in the omission of the Experiencer in the paraphrase in Figure 2.
These alternations provide more variety in the potential phrase types of the paraphrases. Which syntactic modifications are allowed should be an externally controllable parameter, but this has not yet been implemented. In general, allowing fewer types of modification should move the average output leftward in the syntax/semantic similarity graph in Figure 1 (toward more syntactic similarity).
Although every annotated valence represents a grammatical structure, some of these structures will more likely be judged as well-formed than others; in particular, infrequent patterns are more likely illformed than frequent ones. An additional controllable parameter, allowing a trade-off between recall and precision, is a frequency cut-off for accepting a valence pattern based on the number of times the pattern is found in the FrameNet data. Our algorithm currently produces a ranked list of paraphrases based on exactly this frequency parameter, and downstream processing can choose a cut-off frequency or n-best to reduce the total output.

Semantic Filtering
Lexical units of the same frame are not necessarily synonyms; they may be antonyms or coordinate terms (i.e. co-hyponyms). For example, cheese and juice are both in the Food frame, but I like eating cheese and I like eating juice are certainly not a semantic match! In fact, the second is a semantically ill-formed modification of the first. Similarly, like and hate are both in the Experiencer subject frame. While I hate eating cheese is similar to I like eating cheese in describing an attitude toward eating cheese, they are not an exact semantic match either; in this case, however, the lack of semantic similarity does not lead to semantic ill-formedness.
For some tasks such as expanding a language model, exact semantic match is not necessary, but for tasks that require strict semantic match, there are several simple ways to increase robustness.
Tighter filtering, of whatever kind, will move the average output of the algorithm downward in the syntax/semantic similarity graph in Figure 1 (toward more semantic similarity).

Preliminary Results
We have implemented the above algorithm to the point that it is capable of producing paraphrases of arbitrary input sentences that have received proper FrameNet annotation. A large number of paraphrases with a variety of phrase types are produced, but the lack of semantic filtering occasionally leads to semantically ill-formed results. The output is ranked purely according to the frequency in the FrameNet data of the valences used to build the paraphrase.
For the sentence I like eating cheese, the paraphraser produced 8403 paraphrases, of which the following was top-ranked: I resented drinking cheese, which suffers from the semantic mismatch problems discussed in Section 3.4.2. Some other output at random: • I am interested in cheese devouring.
• I was nervous that cheese's ingested.
• I'm worried about gobbling down cheese.
• My regrets were that cheese was eaten by me.
Since most of the annotation in the Ingestion frame (the frame for eat, etc.) concerns eating rather than drinking, the majority of the output is semantically well-formed. The paraphrases generated from the Experiencer subject frame (the frame for like, interested, regret, etc.) are more uniformly felicitous, even if semantically quite divergent from the meaning of the original.
Both the infelicity of drinking cheese and the semantic divergence appear to be addressable by refining semantic tightness using Word-Net. Averaging over senses, words like gobble and ingest have lower WordNet-based semantic distance from eat than drink.
For the sentence Nausea seems a commonplace symptom, the paraphraser outputs 502 paraphrases, of which the following was top-ranked: It seems a commonplace sign. Other output at random: • Tiredness looks indicative.
• Queasiness smelt of a commonplace sign.
• Sleepiness appears a commonplace sign.
• Somnolence appears to be indicative.
Longer sentences (e.g. Locally elected school boards, especially in our larger cities, become the prey of ambitious, generally corrupt, and invariably demagogic local politicians or would-be politicians) currently take excessive amounts of time and memory to run, but typically produce 10,000+ paraphrases. Pruning earlier during paraphrase generation should help address this issue.

Future Work
Currently, Mutaphrase requires the input sentences to have been marked with FrameNet annotations prior to processing. Although automatic semantic parsing is a large and growing field (Moldovan et al., 2004;Litkowski, 2004;Baldewein et al., 2004), two problems present themselves. First, output from an automated parser is not typically compatible with FrameNet markup. Although this is mostly "a simple matter of programming", some linguistic tools must be developed to convert between formats (e.g. to infer FrameNet phrase types from part-of-speech tags). 5 Second, it is not yet clear how the inevitable errors introduced by the parser will affect the Mutaphrase algorithm 6 . We plan to use applicationdependent measures to judge the effects of parsing errors.
Certain types of semantic ill-formedness cannot be detected by the current version of Mutaphrase. A typical example is I like sipping beef as a paraphrase of I like eating cheese. We can guarantee semantic well-formedness by limiting paraphrases to morphologically related words (e.g. consume, consumption) and/or by choosing only the FrameNet LUs which are in the same WordNet (Fellbaum, 1998;Word-Net, 2006) synset or higher in the WN hierarchy than the original LU (e.g. eat to consume). Clearly this will exclude many well-formed paraphrases, so for tasks in which breadth is more important than accuracy of paraphrase, we anticipate experimenting with WordNet hierarchy distances between the original and paraphrase LUs as a quantitative measure of semantic similarity as a proxy for semantic well-formedness.
Currently, paraphrase scores are computed simply from the frequency of a particular valence in FrameNet data. We plan to significantly extend scoring to simultaneously rate each paraphrase on its WordNet similarity, syntactic edit distance 7 , and language model scores. We also plan to measure the correlation between these estimated scores and both human-judged paraphrase accuracy and application dependent metrics, e.g. extension of in-domain language models by paraphrase.
WordNet can also be used to provide additional paraphrases beyond the particular valences attested in FrameNet. For example, we plan to use WordNet 5 It is worth noting that the current SemEval competition (FrameNet, 2007a) should lead to more complete automatic FrameNet-style annotation. 6 An anecdotal example from a semantic parse of I was prepared for a hound, but not for such a creature as this. (Doyle, 1902) assigns prepared to the Cooking creation frame, leading to the interesting paraphrase I was tenderized for a hound.... 7 We plan to base the syntactic distance on the edit distance between the original and paraphrase syntactic valences. to generate synonyms of target words so that, for example, adore could be used anywhere like is used even if adore never appears in the FrameNet data.
Finally, the structure of the Mutaphrase algorithm makes multi-lingual paraphrase possible. This requires FrameNet-like data in other languages, and several projects are underway to provide just such a resource (FrameNet, 2007d;FrameNet, 2007c;SALSA, 2007). We plan to exploit these as they become available.

Conclusions
We have presented the Mutaphrase algorithm, a system for generating a large set of paraphrases of semantically marked input sentences using FrameNet. The generated sentences range widely in their similarity to the input sentence both in terms of syntax and semantics. Various methods of filtering the output for well-formedness and semantic and syntactic similarity were presented.
Although the current implementation suffers from a number of limitations, we believe these can be addressed, eventually providing a fully automated paraphrase system suitable for use in a variety of statistical natural language processing systems.


Towards multi-GPU support for visualization

At the Institute for Ultrascale Visualization, we are tackling the broad problem of building visualization solutions for the petascale age and beyond. As computing transitions into a new age where scalar solutions no longer improve in performance, and parallel solutions are the vehicle for future performance gains, one key challenge in our effort is to harness the power of emerging commodity data-parallel processors. One of the most promising new parallel processors is the graphics processing unit (GPU), whose recent gains in programmability and enormous arithmetic and memory bandwidth substantially outpace its CPU counterpart. The GPU's performance and programmability, together with its graphics capabilities, make it particularly well suited for demanding next-generation visualization applications. We face a number of important challenges in making the GPU a first-class citizen for computation in these visualization applications. In this paper, we describe how we are addressing these challenges: mapping GPUs to general-purpose tasks, fundamental algorithms for GPUs, visualization applications that use the GPU for general-purpose computation, and extending our applications to support multiple GPUs. We also describe trends in upcoming GPU designs and how they will impact our research moving forward.

Introduction
Ten years ago, the conventional wisdom held that the scalar microprocessor was the future of computation. Driven by smaller, faster transistors, and increasing transistor counts, microprocessors doubled in performance every 18-20 months, with an annual performance growth increase of over 50% [1]. Even the Top500 list of supercomputers, traditionally the domain of specialized parallel processors, gradually shifted towards machines whose cores were commodity scalar microprocessors.
Today, the picture has changed. The future of computation is parallel processing. Future microprocessors, due to thermal and architectural constraints, will no longer demonstrate increases in the performance of a single thread of execution. Instead, future processors will increase performance solely by exploiting data-and thread-level parallelism. This monumental shift in focus-Intel CEO Paul Otellini called it a "sea change in computing"-fundamentally changes the way we must think about computation going forward.
At the SciDAC Institute for Ultrascale Visualization (IUSV), we are targeting two of the largest challenges in computing today. The first challenge is the "too much data" problem: the computational demands of science and engineering produces an ever-increasing flood of data that only sophisticated data analysis methods-such as large-scale visualization-can handle. With big data comes big computation, and the second challenge is restructuring that computation dual-core quadcore Figure 1. Because of the parallel nature of computer graphics, the GPU has always been a highly parallel machine. The most recent NVIDIA GPU, for instance, features 128 parallel processors. With this parallelism, modern GPUs feature substantially larger floating-point performance than their CPU counterparts. GPU memory systems also sustain bandwidths of over 80 GB/s, while CPU memory systems are closer to 10 GB/s. for this new parallel age. While scalar algorithms continue to evolve over time, only parallel algorithms that match the capabilities of emerging parallel computer systems can match the rate at which data is generated. It is this challenge of parallelism that is the focus of this paper. At IUSV, we are pursuing a research agenda to make the high-performance, highly parallel graphics processing unit (GPU) an integral part of our petascale visualization solutions.

GPU Computing
The commodity GPU is a youngster in the family tree of processors. GPUs only entered the computing mainstream around 1995. At first, the GPU was best described as a fixed-function processor, but in 2001, it began to feature stages that were directly programmable by the user. These programmable stages were initially fairly limited in functionality but, motivated by the need for more flexible shading and lighting in graphics applications, rapidly gained both features and performance. Today's GPU is no longer a fixed-function processor with programmable stages. It has instead transmuted into a programmable processor with several fixed-function components. The programmable parts of the GPU are now the most important components in GPU performance and functionality, and are the primary focus of continued architectural innovation by GPU vendors.
With these new programmable features, researchers in the field of general-purpose programmability of GPUs (GPGPU), also known as GPU computing, have successfully mapped a broad range of computationally demanding problems to the GPU [2]. How does the GPU, a processor designed for graphics, perform non-graphics, general-purpose computation? Historically this has been a convoluted task: researchers would specify geometry that covered a large portion of the screen, which would then invoke a programmable pixel program at each pixel, and the resulting image held the result (and could be used in future computation). (Harris describes this process in detail [3].) This process was awkward because it used graphics metaphors and APIs to perform non-graphics computation. However, the newest programming environments/APIs-NVIDIA's CUDA [4] ("compute unified device architecture") and AMD's CTM [5] ("close to the metal") allow developers to access the programmable units directly without the need to go through graphics APIs or special-purpose graphics hardware. CUDA provides a C-like language and a compute driver to access the programmable units; CTM exposes lower-level memory accesses and CPU-GPU transfer control operations; both greatly ease the difficulty of writing, debugging, and optimizing GPU programs for general-purpose use.
So why GPU computing? In a word, performance ( Figure 1). For problems well-suited to the GPU, researchers in GPU computing have found order-of-magnitude or greater increases in performance over CPU implementations. For instance, a GPU implementation of the NAMD molecular dynamics package achieves a 20-fold speedup over a highly tuned CPU implementation [6]. Large-scale visualization is an ideal fit for GPU computing for several reasons: • Visualization is a data-intensive application, particularly as the problem size increases into the petascale. GPUs are well-suited for data-intensive tasks. • Visualization computations exhibit substantial parallelism, typically both object parallelism (many objects or parts of objects can be computed/viewed in parallel) and image parallelism (visualizations produce large images and image parts can be computed/viewed in parallel). Parallel computations are necessary for GPUs to be effective. • Visualization tasks should be closely coupled to the graphics system; even though much of overall visualization computation may not be graphics-centric, the final stage typically is, and so moving computation closer to the graphics device offers potential benefits in terms of interactivity and computational steering. • Finally, GPUs can offload computation from CPUs, permitting the entire application to run faster when GPUs are involved.

Fundamental primitives for GPUs
In developing code for CPUs, programmers often have access to a wealth of abstractions, tools, and libraries. For instance, a developer may incorporate linear algebra packages (like BLAS or ATLAS), visualization toolkits (like vtk), and data structure and algorithm libraries (like STL or Boost) into a particular application. The developer is responsible for stitching these parts into an application, but in any given application, the developer only writes a small fraction of the code. This is a "horizontal" method of program development, with the lower layers of abstraction already present in most CPU codes.
One of the major difficulties in programming GPUs is the lack of these established abstractions, tools, and libraries. Consequently GPU programmers are forced to use a more "vertical" model of development, where the application programmer must write all levels of the application. Code reuse is rare and productivity is thus low.
One of our main goals at IUSV is to support large-scale visualization applications by creating libraries of fundamental primitives-algorithms and data structures-to enable modular programs and more productive programmers. We are fortunate to have experts on both low-level GPU programming (who can write efficient, portable parallel primitives) and visualization (who can guide the choice of primitives for best use by visualization).
We have begun our efforts in this area by concentrating on the lowest level of GPU primitives and will build layers and libraries of primitives over the course of the next few years. Our notable initial success is a successful implementation of the scan primitives on GPUs [7,8], which in turn has led to efficient and novel implementations of GPU sorting, sparse matrix operations, depth of field calculations, and fluid simulation.
To leverage our parallel primitive development, we are concurrently pursuing two major research goals. The first is the integration of GPU computation in visualization applications. The second is extending single-GPU applications to multiple GPUs.

Applications
The emergence of parallel hardware will force application developers of all kinds to rethink the way in which they structure their programs. While some of these changes are more evolutionary (threading in multicore machines), moving to the massive parallelism of the GPU implies more substantial changes. One of our primary research goals is to solve complex, compute-heavy visualization applications using GPU computing and with those lessons, better learn how to use the GPU as a computing engine in these future systems. One fertile area for research is migrating demanding general-purpose tasks to the GPU. For instance, sorting large datasets is a common operation in visualization applications. The GPU's superior memory bandwidth and arithmetic capability make it well-suited to large sorting tasks [9]. Robert Hero and Professor Kwan-Liu Ma at IUSV are using GPU-based sorts in CUDA to accelerate unstructured-grid visualizations, in which cells must be sorted by distance from the eye.
A second research thrust is leveraging the special-purpose hardware of the GPU for visualization tasks. At IUSV, Eric Lengyel and Professor Nelson Max are using floating-point compositing GPU hardware to blend partially transparent samples together for a final image.
Finally, a third focus for our research is directly building GPU implementations of visualization primitives, with a long-term goal of building a library of open-source, GPUaccelerated primitives. For instance, GPU primitives for compaction [10] are a key component of visualization primitives such as isosurface extraction. At IUSV, Yuan Hong, Liya Li, and Processor Han-Wei Shen are pursuing GPU implementations of both marching cubes and raycasting, both important primitives for a broad class of visualization applications.

Multi-GPU support
We also are pursuing a research program to extend our single-GPU primitives to multiple GPUs in a multi-node system. As our primary interest in IUSV is petascale visualization, clustered systems with many GPUs are a must.
Multi-node GPU computing is still in its infancy-with many open research problems with single-node GPUs, multi-node vendor support has been a tricky task. Successful multi-GPU applications have traditionally taken two forms. The first is parallelizable problems that can be partitioned between GPUs. In these problems, the input is divided into parts and each part is sent to a separate GPU. The second is a pipeline, where each GPU executes part of the pipeline and forwards its results to the next GPU in the pipeline.
While many interesting problems may be well suited for one of these communication patterns, neither allows fully general communication. Instead, the communication patterns for both are essentially fixed at the outset of the program. We see two potential more flexible models for computation in an ideal system.
In the first, the GPUs are the primary processors: GPUs can share memory dynamically, and any GPU can request arbitrary data from any other GPU at any time. We advocate, and have built, a distributed-shared memory abstraction across multiple GPUs [11]. With this abstraction, each GPU's memory is part of a global memory space, and any GPU can request memory from any part of that global memory space at any time without knowing the details of where that memory is located in the system. Such a system can be made scalable. Our current implementation assumes one GPU per CPU but can be extended to have multiple GPUs per CPU. It is functional but not suitable for performance-critical applications; however, the necessary vendor support for making such a system efficient, such as per-element demand paging and more fine-grained memory management, is on vendor roadmaps and will allow highperformance implementations over the next few years.
In the second, GPUs are treated as coprocessors and CPUs are primarily responsible for scheduling and distributing work with them. In conjunction with Brian Budge and Professor Ken Joy (VACET), we are pursuing a hybrid out-of-core rendering solution that efficiently distributes work across multiple nodes and processors on those nodes to render large complex scenes with sophisticated shading. The lessons learned-how to distribute work and what kind of work is best suited for GPUs-are directly applicable to complex visualization applications.
Regardless of the eventual model for arbitrary memory sharing across multiple GPUs, the broad research problem of the design of multi-node memory models-balancing generality with performance, programmer efficiency with runtime efficiency-is a vital one for not only GPUs but also emerging parallel CPUs and hybrid CPU-GPU clusters.

Looking Forward
Both GPU vendors and application developers with demanding computation needs are embracing GPU computing as a first-class computing resource in tomorrow's systems. Perhaps the most important challenge is the development of a programming ecosystem around the GPU; two important aspects of such an ecosystem are the development of fundamental primitives and an efficient, powerful programming abstraction built around multiple GPUs that we describe above. Beyond these components are a strong need for programming tools (compilers, emulators, debuggers, and profilers) and abstractions (programming models, libraries, and APIs). These problems are not unique to the GPU but instead are important to all aspects of parallel programming, whether coarse-grained thread-parallel systems (like a multicore CPU) or finegrained data-parallel systems (like a GPU). The development of vendor-supported general-purpose programming environments like CUDA and CTM are vital to the continued development of GPU computing. Over the next few years we will see further vendor improvements that will continue to improve the prospects of GPU computing. For instance, both AMD and NVIDIA have announced that their GPUs will support double-precision arithmetic by the end of 2007, eliminating a major obstacle to their adoption in scientific computing. The next generation of device drivers (Windows Driver Device Model 2.1) will add more fine-grained memory and exception control, which will lead to more efficient multi-GPU shared-memory implementations. And an increased vendor focus on GPU computing in general-evidenced by boards and products that are designed and built specifically for GPU computing-paints a bright picture.
As one of the most complex and demanding applications, visualization is perfectly positioned to take advantage of the power of GPU computing. Visualization is a critical step in the processing of data into knowledge, and the high computational demands of visualization applications coupled with their real-time requirements make it imperative that as we move into the petascale and beyond, we use GPU computing and other innovative computing approaches to best support these applications.