Riemannian geometry of quantum computation

A review is given of some recent developments in the differential geometry of quantum computation for which the quantum evolution is described by the special unitary unimodular group, SU(2ⁿ). Using the Lie algebra su(2ⁿ), detailed derivations are given of a useful Riemannian geometry of SU(2ⁿ), including the connection and the geodesic equation for minimal complexity quantum computations.     

Subnormal structure of non-stable unitary groups over rings

Let R be a commutative ring with identity in which 2 is invertible. Let H denote a subgroup of the unitary group U(2n,R,Λ) with n≥4. H is normalized by EU(2n,J,Γ^J) for some form ideal (J,Γ^J) of the form ring (R,Λ). The purpose of the paper is to prove that H satisfies a “sandwich” property, i.e. there exists a form ideal (I,Γ^I) such that

EU(2n,IJ⁸Γ^J,Γ)⊆H⊆CU(2n,I,Γ^I).     

A theorem of the Wiener—Tauberian type forL 1(H n)

The Heisenberg motion groupHM(n), which is a semi-direct product of the Heisenberg group Hⁿ and the unitary group U(n), acts on Hⁿ in a natural way. Here we prove a Wiener-Tauberian theorem for L¹ (Hⁿ) with this HM(n)-action on Hⁿ i.e. we give conditions on the “group theoretic” Fourier transform of a functionf in L¹ (Hⁿ) in order that the linear span of^gf : g∈HM(n) is dense in L¹(Hⁿ), where^gf(z, t) =f(g·(z, t)), forg ∈ HM(n), (z,t)∈Hⁿ.     

Semidefinite descriptions of low-dimensional separable matrix cones

Let K⊂E, K^′⊂E^′ be convex cones residing in finite-dimensional real vector spaces. An element y in the tensor product E⊗E^′ is K⊗K^′-separable if it can be represented as finite sum , where x_l∈K and for all l. Let S(n), H(n), Q(n) be the spaces of n×n real symmetric, complex Hermitian and quaternionic Hermitian matrices, respectively. Let further S₊(n), H₊(n), Q₊(n) be the cones of positive semidefinite matrices in these spaces. If a matrix A∈H(mn)=H(m)⊗H(n) is H₊(m)⊗H₊(n)-separable, then it fulfills also the so-called PPT condition, i.e. it is positive semidefinite and has a positive semidefinite partial transpose. The same implication holds for matrices in the spaces S(m)⊗S(n), H(m)⊗S(n), and for m?2 in the space Q(m)⊗S(n). We provide a complete enumeration of all pairs (n,m) when the inverse implication is also true for each of the above spaces, i.e. the PPT condition is sufficient for separability. We also show that a matrix in Q(n)⊗S(2) is Q₊(n)⊗S₊(2)- separable if and only if it is positive semidefinite.     

On squares in Lucas sequences

Let P and Q be non-zero integers. The Lucas sequence {Un(P,Q)} is defined by U₀=0, U₁=1, Un=PUn−1−QUn−2 (n?2). The question of when Un(P,Q) can be a perfect square has generated interest in the literature. We show that for n=2,…,7, Un is a square for infinitely many pairs (P,Q) with gcd(P,Q)=1; further, for n=8,…,12, the only non-degenerate sequences where gcd(P,Q)=1 and Un(P,Q)=□, are given by U₈(1,−4)=²¹², U₈(4,−17)=⁶²⁰², and U₁₂(1,−1)=¹²².     

The Combinatorics of a Class of Representation Functions

In the study of the irreducible representations of the unitary groupU(n), one encounters a class of polynomials defined onn²indeterminatesz_ij, 1i, jn, which may be arranged into ann×nmatrix arrayZ=(z_ij). These polynomials are indexed by double Gelfand patterns, or equivalently, by pairs of column strict Young tableaux of the same shape. Using the double labeling property, one may define a square matrixD(Z), whose elements are the double-indexed polynomials. These matrices possess the remarkable “group multiplication property”D(XY)=D(X) D(Y) for arbitrary matricesXandY, even though these matrices may be singular. ForZ=UU(n), these matrices give irreducible unitary representations ofU(n). These results are known, but not always fully proved from the extensive physics literature on representation of the unitary groups, where they are often formulated in terms of the boson calculus, and the multiplication property is unrecognized. The generality of the multiplication property is the key to understanding group representation theory from the purview of combinatorics. The combinatorial structure of the general polynomials is expected to be intricate, and in this paper, we take the first step to explore the combinatorial aspects of a special class which can be defined in terms of the set of integral matrices with given row and column sums. These special polynomials are denoted byL_{α, β}(Z), whereαandβare integral vectors representing the row sums and column sums of a class of integral matrices. We present a combinatorial interpretation of the multiplicative properties of these polynomials. We also point out the connections with MacMahon's Master Theorem and Schwinger's inner product formula, which is essentially equivalent to MacMahon's Master Theorem. Finally, we give a formula for the double Pfaffian, which is crucial in the studies of the generating function of the 3n−jcoefficients in angular momentum theory. We also review the background of the general polynomials and give some of their properties.     

Brauer groups and Amitsur cohomology for general commutative ring extensions

Exact couples are interconnected families of long exact sequences extending the short exact sequences usually derived from spectral sequences. This is exploited to give a long exact sequence connecting Amitsur cohomology groups $\text{H>}{}^{\mathrm{n}}\text{(}\text{S}\text{R}\text{, U)}$ (where U means the multiplicative group) and $\text{H}{}^{\mathrm{n}}\text{(}\text{S}\text{R}\text{, Pic)}$ and a third sequence of groups Hⁿ(J), for every faithfully flat commutative R-algebra S. This same sequence is derived in another way without assuming faithful flatness and Hⁿ(J) is identified explicitly as a certain subquotient of a group of isomorphism classes of pairs (P, α) with P a rank one, projective Sⁿ-module and α an isomorphism from the coboundary of P (inPicS^{n + 1}) toS^{n + 1}. (Here Sⁿ denotes repeated tensor product of S over R.) This last formulation allows us to construct a homomorphism of the relative Brauer group $\text{B(}\text{S}\text{R}\text{)}$ to H²(J) which is a monomorphism when S is faithfully flat over R, and an isomorphism when some S-module is faithfully projective over R. The first approach also identifies H²(J) with Ker[H²(R, U)→H²(S, U)], where H²(R, U) denotes the ordinary, Grothendieck cohomology (in the étale topology, for example).     

The problem of harmonic analysis on the infinite-dimensional unitary group

The goal of harmonic analysis on a (noncommutative) group is to decompose the most “natural” unitary representations of this group (like the regular representation) on irreducible ones. The infinite-dimensional unitary group U(∞) is one of the basic examples of “big” groups whose irreducible representations depend on infinitely many parameters. Our aim is to explain what the harmonic analysis on U(∞) consists of.We deal with unitary representations of a reasonable class, which are in 1-1 correspondence with characters (central, positive definite, normalized functions on U(∞)). The decomposition of any representation of this class is described by a probability measure (called spectral measure) on the space of indecomposable characters. The indecomposable characters were found by Dan Voiculescu in 1976.The main result of the present paper consists in explicitly constructing a 4-parameter family of “natural” representations and computing their characters. We view these representations as a substitute of the nonexisting regular representation of U(∞). We state the problem of harmonic analysis on U(∞) as the problem of computing the spectral measures for these “natural” representations. A solution to this problem is given in the next paper (Harmonic analysis on the infinite-dimensional unitary group and determinantal point processes, math/0109194, to appear in Ann. Math.), joint with Alexei Borodin.We also prove a few auxiliary general results. In particular, it is proved that the spectral measure of any character of U(∞) can be approximated by a sequence of (discrete) spectral measures for the restrictions of the character to the compact unitary groups U(N). This fact is a starting point for computing spectral measures.     

Average running time of the fast Fourier transform

We compare several algorithms for computing the discrete Fourier transform of n numbers. The number of “operations” of the original Cooley-Tukey algorithm is approximately 2nA(n), where A(n) is the sum of the prime divisors of n. We show that the average number of operations satisfies $\text{1}\text{x}\text{)∑}{}_{\mathrm{n\le x}}\text{2n A(n) ～ (}\text{π}{}^2\text{9}\text{)(}\text{x}{}^2\text{log}\text{x}\text{)}$. The average is not a good indication of the number of operations. For example, it is shown that for about half of the integers n less than x, the number of “operations” is less than n^1.61. A similar analysis is given for Good's algorithm and for two algorithms that compute the discrete Fourier transform in O(n log n) operations: the chirp-z transform and the mixed-radix algorithm that computes the transform of a series of prime length p in O(p log p) operations.     

ADMISSIBLE WAVELETS ASSOCIATED WITH THE TRANSFORM GROUP ON R

Let p be the transform group on R, then P has a natural unitary representation U onL2 (R^n). Decompose L2(R^n) into the direct sum of irreducible invariant closed subspace,s. The re-striction of U on these suhspaces is square-intagrable. In this paper the characterization of admissi-ble condition in tarrns of the Fourier transform is given. The wavelet transform is defined, and theorthogorml direct sum decomposition of function space L2 (P,du1) is obtained.     

On a conjecture of Kippenhahn about the characteristic polynomial of a pencil generated by two Hermitian matrices. I

Let A be an n × n complex matrix, and write A = H + iK, where i² = ?1 and H and K are Hermitian matrices. The characteristic polynomial of the pencil xH + yK is f(x, y, z) = det(zI ? xH ? yK). Suppose f(x, y, z) is factored into a product of irreducible polynomials. Kippenhahn [5, p. 212] conjectured that if there is a repeated factor, then there is a unitary matrix U such that U^?1AU is block diagonal. We prove that if f(x, y, z) has a linear factor of multiplicity greater than n?3, then H and K have a common eigenvector. This may be viewed as a special case of Kippenhahn’s conjecture.     

Cohomology for infinitesimal unipotent algebraic and quantum groups

In this paper we study the structure of cohomology spaces for the Frobenius kernels of unipotent and parabolic algebraic group schemes and of their quantum analogs. Given a simple algebraic group G, a parabolic subgroup P _J , and its unipotent radical U _J , we determine the ring structure of the cohomology ring H^?((U _J )₁, k). We also obtain new results on computing H^?((P _J )₁, L(??)) as an L _J -module where L(??) is a simple G-module with highest weight ?? in the closure of the bottom p-alcove. Finally, we provide generalizations of all our results to small quantum groups at a root of unity.     

The sum of unitary similarity orbits containing only special operators

Let B(H) be the algebra of bounded linear operator acting on a Hilbert space H (over the complex or real field). Characterization is given to A₁,…,A_k∈B(H) such that for any unitary operators is always in a special class S of operators such as normal operators, self-adjoint operators, unitary operators. As corollaries, characterizations are given to A∈B(H) such that complex, real or nonnegative linear combinations of operators in its unitary orbit U(A)={U^∗AU:Uunitary} always lie in S.     

Linear preservers and quantum information science

In this article, a brief survey of recent results on linear preserver problems and quantum information science is given. In addition, characterization is obtained for linear operators φ on mn?×?mn Hermitian matrices such that φ(A???B) and A???B have the same spectrum for any m?×?m Hermitian A and n?×?n Hermitian B. Such a map has the form A???B???U(?₁(A)????₂(B))U* for mn?×?mn Hermitian matrices in tensor form A???B, where U is a unitary matrix, and for j?∈?{1,?2}, ? _j is the identity map?X???X or the transposition map?X???X ^t . The structure of linear maps leaving invariant the spectral radius of matrices in tensor form A???B is also obtained. The results are connected to bipartite (quantum) systems and are extended to multipartite systems.     

Two-parameter families of quantum symmetry groups

We introduce and study natural two-parameter families of quantum groups motivated on one hand by the liberations of classical orthogonal groups and on the other by quantum isometry groups of the duals of the free groups. Specifically, for each pair (p,q) of non-negative integers we define and investigate quantum groups O⁺(p,q), B⁺(p,q), S⁺(p,q) and H⁺(p,q) corresponding to, respectively, orthogonal groups, bistochastic groups, symmetric groups and hyperoctahedral groups. In the first three cases the new quantum groups turn out to be related to the (dual free products of ) free quantum groups studied earlier. For H⁺(p,q) the situation is different and we show that , where the latter can be viewed as a liberation of the classical isometry group of the p-dimensional torus.     

On the Blum-Hanson theorem for quantum quadratic processes

In this paper an analog of the Blum-Hanson theorem for quantum quadratic processes on the von Neumann algebra is proved, i.e., it is established that the following conditions are equivalent:

Matching Realization of Uq（sln＋1） of Higher Rank in the Quantum Weyl Algebra Wq（2n）

In the paper, we further realize the higher rank quantized universal enveloping algebra Uq（sln＋1） as certain quantum differential operators in the quantum Weyl algebra Wq （2n） defined over the quantum divided power algebra Sq（n） of rank n. We give the quantum differential operators realization for both the simple root vectors and the non-simple root vectors of Uq（sln＋1）. The nice behavior of the quantum root vectors formulas under the action of the Lusztig symmetries once again indicates that our realization model is naturally matched.     

New Techniques for the Computation of Linear Recurrence Coefficients

The n coefficients of a fixed linear recurrence can be expressed through its m≤2n terms or, equivalently, the coefficients of a polynomial of a degree n can be expressed via the power sums of its zeros—by means of a polynomial equation known as the key equation for decoding the BCH error-correcting codes. The same problem arises in sparse multivariate polynomial interpolation and in various fundamental computations with sparse matrices in finite fields. Berlekamp's algorithm of 1968 solves the key equation by using order of n² operations in a fixed field. Several algorithms of 1975–1980 rely on the extended Euclidean algorithm and computing Padé approximation, which yields a solution in O(n(log n)² log log n) operations, though a considerable overhead constant is hidden in the “O” notation. We show algorithms (depending on the characteristic c of the ground field of the allowed constants) that simplify the solution and lead to further improvements of the latter bound, by factors ranging from order of log n, for c=0 and c>n (in which case the overhead constant drops dramatically), to order of min (c, log n), for 2≤c≤n; the algorithms use Las Vegas type randomization in the case of 2<c≤n.     

Unitary part of a contraction

For a contraction A on a Hilbert space H, we define the index j(A) (resp., k(A)) as the smallest nonnegative integer j (resp., k) such that ker(I−Aj∗Aj) (resp., ker(I−Ak*Ak)∩ker(I−AkAk∗)) equals the subspace of H on which the unitary part of A acts. We show that if , then j(A)?n (resp., k(A)?⌈n/2⌉), and the equality holds if and only if A is of class Sn (resp., one of the three conditions is true: (1) A is of class Sn, (2) n is even and A is completely nonunitary with ‖An−2‖=1 and ‖An−1‖<1, and (3) n is even and A=U⊕A^′, where U is unitary on a one-dimensional space and A^′ is of class Sn−1).