Dimensional Lifting through the Generalized Gram–Schmidt Process

Abstract

A new way of orthogonalizing ensembles of vectors by “lifting” them to higher dimensions is introduced. This method can potentially be utilized for solving quantum decision and computing problems.

The celebrated Gram–Schmidt algorithm allows the construction of a system of orthonormal vectors from an (ordered) system of linearly independent vectors. Let us mention that there exist a wide variety of proposals to “generalize” the Gram–Schmidt process [1] serving many different purposes. In contrast to these generalizations, we construct a system of orthogonal vectors from an (ordered) system of arbitrary vectors, which may be linearly dependent. (Even repeated vectors are allowed.) This task is accomplished by what will be called “dimensional lifting”.

Some quantum computation tasks require the orthogonalization of previously non-orthogonal vectors. This might be best understood in terms of mutually exclusive outcomes of generalized beam splitter experiments, where the entire array of output ports corresponds to an ensemble of mutually orthogonal subspaces, or, equivalently, mutually orthogonal perpendicular projection operators [2].

Of course, by definition (we may define a unitary transformation in a complex Hilbert space by the requirement that it preserves the scalar product [3] (§ 73)), any transformation or mapping of non-orthogonal vectors into mutually orthogonal ones will be non-unitary. However, we may resort to requiring that some sort of angles or distances (e.g., in the original Hilbert space) remain unchanged.

Suppose, for the sake of demonstration, two non-orthogonal vectors, and suppose further that somehow one could “orthogonalize” them while at the same time retaining structural elements, such as the angles between projections of the new, mutually orthogonal vectors onto the subspace spanned by the original vectors. For instance, the two non-orthogonal vectors could be transformed into vectors of some higher-dimensional Hilbert space satisfying the following properties with respect to the original vectors: (i) the new vectors are orthogonal, and (ii) the orthogonal projection along the new, extra dimension(s) of the two vectors render the original vectors. A straightforward three-dimensional construction with the desired outcome can be given as follows: suppose the original vectors are unit vectors denoted by $|{\mathbf{e}}_1\rangle$ and $|{\mathbf{e}}_2\rangle$; and $0<|\langle {\mathbf{e}}_1|{\mathbf{e}}_2\rangle |<1$. Suppose further a two-dimensional coordinate frame in which $|{\mathbf{e}}_1\rangle$ and $|{\mathbf{e}}_2\rangle$ are planar; thus, we can write in terms of some orthonormal basis $|{\mathbf{e}}_1\rangle =\left(\begin{array}{c}{x}_{1,1},x_{1,2}\end{array}\right)$ as well as $|{\mathbf{e}}_2\rangle =\left(\begin{array}{c}{x}_{2,1},x_{2,2}\end{array}\right)$. Suppose we “enlarge” the vector space to include an additional dimension, and suppose a Cartesian basis system in that greater space that includes the two vectors of the old basis (and an additional unit vector that is orthogonal with respect to the original plane spanned by the original basis vectors).

Ad hoc, it is rather intuitive how two (not necessarily unit) vectors can be found that project onto the original vectors, and which are orthogonal: “create” a three-dimensional vector space with one extra dimension, assign a non-zero extra coordinate (such as 1) associated with this dimension for the first vector, and use the extra coordinate of the second vector for compensating any nonzero value of the scalar product of the two original vectors— in particular, whose coordinates with respect to the new basis are

$$\begin{array}{cc}\hfill |{\mathbf{f}}_1\rangle =& \left(\begin{array}{c}{x}_{1,1},x_{1,2},1\end{array}\right),\hfill \\ \hfill |{\mathbf{f}}_2\rangle =& \left(\begin{array}{c}{x}_{2,1},x_{2,2},-\left(x_{1,1}{x}_{2,1}+x_{1,2}{x}_{2,2}\right)\end{array}\right),\hfill \end{array}$$

(1)

which are orthogonal by construction.

It is not too difficult to find explicit constructions for the more general case of k vectors $|{\mathbf{e}}_1\rangle ,\dots ,|{\mathbf{e}}_k\rangle$ in ${\mathbb{R}}^n$ (cf. Ref. [2] for a rather inefficient method).

In the following, for the sake of construction, we shall embed ${\mathbb{R}}^n$ into ${\mathbb{R}}^{n+k}$, such that we fill all additional vector coordinates of $|{\mathbf{e}}_1\rangle ,\dots |{\mathbf{e}}_k\rangle$ with zeroes. For the new, mutually orthogonal, vectors we make the following Ansatz by defining

$$\begin{array}{cc}\hfill |{\mathbf{f}}_1\rangle =& \left(\begin{array}{c}{\mathbf{e}}_1,1,0,\dots ,0\end{array}\right),\hfill \\ \hfill |{\mathbf{f}}_2\rangle =& \left(\begin{array}{c}{\mathbf{e}}_2,x_{2,1},1,0,\dots ,0\end{array}\right),\hfill \\ \hfill \dots & \\ \hfill |{\mathbf{f}}_k\rangle =& \left(\begin{array}{c}{\mathbf{e}}_k,x_{k,1},x_{k,2},\dots ,x_{k,k-1},1\end{array}\right),\hfill \end{array}$$

(2)

with yet to be determined coordinates $x_{i,j}$. (The symbols ${\mathbf{e}}_i$ stand for all the n coordinates of $|{\mathbf{e}}_1\rangle$.)

The unit coordinates 1 ensure that the new vectors are linearly independent. By construction, the orthogonal projection of $|{\mathbf{f}}_i\rangle$ onto ${\mathbb{R}}^n$ renders $|{\mathbf{e}}_i\rangle$ for all $1\le i\le k$.

What remains is the recursive determination of the unknown coordinates $x_{i,j}$. Note that all $|{\mathbf{f}}_j\rangle$ must satisfy the following relations: for $j>1$, orthogonality demands that $\langle {\mathbf{f}}_1|{\mathbf{f}}_j\rangle =0$, and therefore $\langle {\mathbf{e}}_1|{\mathbf{e}}_j\rangle +1·x_{j,1}=0$, and therefore

$$x_{j,1}=-\langle {\mathbf{e}}_1|{\mathbf{e}}_j\rangle .$$

(3)

In this way, all unknown coordinates $x_{2,1},\dots ,x_{k,1}$ can be determined.

Similar constructions yield the remaining unknown coordinates in $|{\mathbf{f}}_2\rangle ,\dots ,|{\mathbf{f}}_k\rangle$. For $j>2$, $\langle {\mathbf{f}}_2|{\mathbf{f}}_j\rangle =0$, and therefore $\langle {\mathbf{e}}_2|{\mathbf{e}}_j\rangle +x_{2,1}{x}_{j,1}+x_{j,2}=0$, yielding

$$x_{j,2}=-\langle {\mathbf{e}}_2|{\mathbf{e}}_j\rangle -x_{2,1}{x}_{j,1}.$$

(4)

In this way, all unknown coordinates $x_{3,2},\dots ,x_{k,2}$ can be determined.

This procedure is repeated until one arrives at $j=k-1$, and therefore at the orthogonality of $|{\mathbf{f}}_{k-1}\rangle$ and $|{\mathbf{f}}_k\rangle$, encoded by the condition $\langle {\mathbf{f}}_{k-1}|{\mathbf{f}}_k\rangle =0$, and hence

$$\begin{array}{c}\hfill x_{k,k-1}=-\left(\langle {\mathbf{e}}_{k-1}|{\mathbf{e}}_k\rangle +\right.\\ \hfill \left.+x_{k-1,1}{x}_{k,1}+\cdots +x_{k-1,k-2}{x}_{k,k-2}\right).\end{array}$$

(5)

The approach has the advantage that, at each stage of the recursive construction, there is only a single unknown coordinate per equation. This situation is well known from Gaussian elimination. The Ansatz also works if one of the original vectors is the zero vector, and if some of the original vectors are equal.

The resulting system of orthogonal vectors is not the only solution of the initial problem—to find an orthogonal vector that projects onto the original ones—which can be explicitly demonstrated by multiplying all vectors $|{\mathbf{f}}_1\rangle ,\dots ,|{\mathbf{f}}_k\rangle$ with the matrix

$$\mathrm{diag}\left(\begin{array}{c}{\mathbb{I}}_n,c\mathbf{T}\end{array}\right),$$

(6)

whereby ${\mathbb{I}}_n$ stands for the n-dimensional unit matrix, c can be a real nonzero constant, and $\mathbf{T}$ is a k-dimensional orthogonal matrix. (For complex Hilbert space, the orthogonal matrix needs to be substituted by a unitary matrix, and by a complex constant $c\ne 0$.)

On the other hand, we may reinterpret our procedure as follows: Let $|{\mathbf{e}}_1\rangle ,\dots ,|{\mathbf{e}}_k\rangle$ be a system of vectors in ${\mathbb{R}}^n$, not necessarily spanning ${\mathbb{R}}^n$, and not necessarily being linearly independent. (The ordering of the vectors in this system will be essential throughout.) We embed ${\mathbb{R}}^n$ in ${\mathbb{R}}^{n+k}$ as we did above and denote the orthogonal complement of ${\mathbb{R}}^n$ by $C\cong {\mathbb{R}}^k$. Therefore, the first n coordinates of all vectors in C vanish, and ${\mathbb{R}}^{n+k}$ can be represented by a direct sum ${\mathbb{R}}^{n+k}={\mathbb{R}}^n\oplus {\mathbb{R}}^k$. Additionally, we choose some (ordered) orthonormal basis of C, say, $|{\mathbf{g}}_1\rangle ,\dots ,|{\mathbf{g}}_k\rangle$.

Then, there is a unique system of orthogonal vectors $|{\mathbf{f}}_1\rangle ,\dots ,|{\mathbf{f}}_k\rangle$ in ${\mathbb{R}}^{n+k}$ such that the following conditions are satisfied:

• For all $1\le i\le k$, the orthogonal projection of ${\mathbb{R}}^{n+k}$ onto ${\mathbb{R}}^n$ sends $|{\mathbf{f}}_i\rangle$ to $|{\mathbf{e}}_i\rangle$.
• The orthogonal projection of ${\mathbb{R}}^{n+k}$ onto C sends $|{\mathbf{f}}_1\rangle ,\dots ,|{\mathbf{f}}_k\rangle$ to some (ordered) basis of the subspace C. Applying the Gram–Schmidt process to this (ordered) basis gives the orthonormal basis $|{\mathbf{g}}_1\rangle ,\dots ,|{\mathbf{g}}_k\rangle$.

Indeed, in our previous Ansatz, we tacitly assumed the orthonormal basis $|{\mathbf{g}}_1\rangle ,\dots ,|{\mathbf{g}}_k\rangle$ of C to comprise the orthogonal projections of the last k vectors of the standard basis $|{\mathbf{b}}_1\rangle ,\dots ,|{\mathbf{b}}_{n+k}\rangle$ of ${\mathbb{R}}^{n+k}$ onto C. Condition 2 enforces the presence of all the 1s and 0s in Formula (2), since the Gram–Schmidt process, applied to the vectors

$$|{\mathbf{f}}_1\rangle -|{\mathbf{e}}_1\rangle ,\dots ,|{\mathbf{f}}_k\rangle -|{\mathbf{e}}_k\rangle ,$$

has to result in $|{\mathbf{b}}_{n+1}\rangle ,\dots ,|{\mathbf{b}}_{n+k}\rangle$. Notice that the usual Gram–Schmidt process gives merely an orthogonal basis, whose vectors can be normalized in a second step in order to obtain an orthonormal basis. In our setting, however, such a second step is not allowed. As we saw above, now Condition 1 guarantees that $|{\mathbf{f}}_1\rangle ,\dots ,|{\mathbf{f}}_k\rangle$ are uniquely determined.

Besides uniqueness, this construction has the additional advantage that the dot product in ${\mathbb{R}}^{n+k}$ “decays” into the sum of dot products in ${\mathbb{R}}^n$ and in ${\mathbb{R}}^k$: any basis vector ${\mathbf{f}}_i\in {\mathbb{R}}^{n+k}$ can be uniquely written as ${\mathbf{f}}_i={\mathbf{e}}_i+{\mathbf{h}}_i$, where ${\mathbf{e}}_i$ and ${\mathbf{h}}_i$ represent the projection of ${\mathbf{f}}_i$ along ${\mathbf{h}}_i$ onto the original subspace ${\mathbb{R}}^n$, and the projection of ${\mathbf{f}}_i$ along ${\mathbf{e}}_i$ onto C, respectively. Since ${\mathbf{e}}_i$ is orthogonal to ${\mathbf{h}}_i$, for $i\ne j$, ${\mathbf{f}}_i·{\mathbf{f}}_j={\mathbf{e}}_i·{\mathbf{e}}_j+{\mathbf{h}}_i·{\mathbf{h}}_j=0,$ and thus

$$\begin{array}{c}\hfill {\mathbf{e}}_i·{\mathbf{e}}_j=-{\mathbf{h}}_i·{\mathbf{h}}_j.\end{array}$$

(7)

Let us, for the sake of a physical example, study configurations associated with decision problems that can be efficiently (that is, with some speedup with respect to purely classical means [2]) encoded quantum mechanically. The inverse problem is the projection of orthogonal systems of vectors onto lower dimensions. This method renders a system of non-orthogonal rays, also called eutactic stars [4,5,6,7,8], which can be effectively levied to mutually exclusive outcomes in a generalized beam splitter configurations [9,10] reflecting the higher dimensional Hilbert space.

One instance of such a quantum computation involving the reduction to ensembles of orthogonal vectors (and their associated span or projection operators) is the Deutsch–Jozsa algorithm, as reviewed in Ref. [2]. Another, somewhat contrived, problem can be constructed in three dimensions from a eutactic star

$$\begin{array}{c}\hfill \frac{1}{\sqrt{3}}\left\{\left(\begin{array}{c}1,1\end{array}\right),\left(\begin{array}{c}\frac{1}{2}\left[\sqrt{3}i-1\right],\frac{1}{2}\left[-\sqrt{3}i-1\right]\end{array}\right),\right.\\ \hfill \left.\left(\begin{array}{c}\frac{1}{2}\left[-\sqrt{3}i-1\right],\frac{1}{2}\left[\sqrt{3}i-1\right]\end{array}\right)\right\},\end{array}$$

(8)

which is the projection onto the plane formed by the first two coordinates of a three-dimensional orthormal basis

$$\begin{array}{c}\hfill {\mathfrak{B}}_3=\frac{1}{\sqrt{3}}\left\{\left(\begin{array}{c}1,1,1\end{array}\right),\right.\\ \hfill \left(\begin{array}{c}\frac{1}{2}\left[\sqrt{3}i-1\right],\frac{1}{2}\left[-\sqrt{3}i-1\right],1\end{array}\right),\\ \hfill \left.\left(\begin{array}{c}\frac{1}{2}\left[-\sqrt{3}i-1\right],\frac{1}{2}\left[\sqrt{3}i-1\right],1\end{array}\right)\right\},\end{array}$$

(9)

which, together with the Cartesian standard basis, forms a pair of unbiased bases [11].

Still another decision configuration is the eutactic star

$$\begin{array}{c}\hfill \frac{1}{2}\left\{\left(\begin{array}{c}1,1,1\end{array}\right),\left(\begin{array}{c}1,1,-1\end{array}\right),\right.\\ \hfill \left(\begin{array}{c}1,-1,1\end{array}\right),\left.\left(\begin{array}{c}1,-1,-1\end{array}\right)\right\},\end{array}$$

(10)

which is the projection onto the subspace formed by the first three coordinates of a four-dimensional orthormal basis

$$\begin{array}{c}\hfill {\mathfrak{B}}_4=\frac{1}{2}\left\{\left(\begin{array}{c}1,1,1,1\end{array}\right),\left(\begin{array}{c}1,1,-1,-1\end{array}\right),\right.\\ \hfill \left.\left(\begin{array}{c}1,-1,1,-1\end{array}\right),\left(\begin{array}{c}1,-1,-1,1\end{array}\right)\right\}.\end{array}$$

(11)

More concretely, suppose some, admittedly construed, function f, and some quantum encoding $\left|xf\right(y)\rangle$, where x and y stand for (sequences of) auxiliary and input bits, respectively, would yield one of the basis systems ${\mathfrak{B}}_3$ or ${\mathfrak{B}}_4$. By reducing the auxiliary bits x, one might end up with the eutactic stars introduced above. Alas, so far, no candidate of this kind has been proposed.

In summary, a new method of orthogonalizing ensembles of vectors has been introduced. Thereby, the original vectors are “lifted” to or “completed” in higher dimensions. This method could be utilized for solving quantum decision and computing problems if the original problem does not allow an orthogonal encoding, and if extra bits can be introduced that render the equivalent of the extra dimensions in which the original state vectors can be lifted and orthogonalized.

Compared with methods that were introduced [12,13,14] previously to optimally differentiate between two non-orthogonal states, the scheme suggested here is similar in the sense that, in order to obtain a better resolution, the effective dimensionality of the problem is increased. However, our scheme is not limited to the differentiation between two states, as it uses arbitrary dimensionality. More importantly, whereas our scheme is capable of separating different states precisely, but in general is non-unitary—indeed, the original vectors are not mutually orthogonal, but the lifted vectors are, thereby changing the angles among vectors, resulting in transformations that cannot be unitary—the former methods are unitary and probabilistic.