Gram-Schmidt Orthogonalization on Encrypted Vectors

P. K. Majumdar

This Python/NumPy program generates a reproducible, normalised random quantum state and constructs its rank-one projection operator. It then generates a second complex state and applies the Gram–Schmidt procedure to remove every component parallel to the first state, producing a normalised orthogonal vector. The program verifies the inner-product orthogonality, confirms that the projector is Hermitian and idempotent, and demonstrates that applying the projector to the orthogonal state produces a vector whose norm is numerically zero within a declared floating-point tolerance. This illustrates, computationally, how a projector completely filters out a state that lies in its orthogonal complement.

Manoj Prabhakaran, Mike Rosulek

Zi-Ming Li, Yu-xi Liu

Vector set orthogonal normalization and matrix QR decomposition are fundamental problems in matrix analysis with important applications in many fields. We know that the Gram-Schmidt process is a widely used method to solve these two problems. However, existing methods, including the Gram-Schmidt process, have problems of high complexity, scaling $O({N}^{3})$ in the system dimension $N$, which leads to difficulties when calculating large-scale or ill-conditioned problems. With the development of quantum information processing, a series of quantum algorithms have been proposed, providing advantages and speedups over classical algorithms in many fields. In this paper we propose quantum algorithms to solve these two problems based on the idea of the Gram-Schmidt process and quantum phase estimation. The complexity of proposed quantum algorithms is theoretically and numerically analyzed. We find that our algorithms provide polynomial acceleration over the best-known quantum algorithms and a potential polynomial acceleration over the best-known classical algorithms on these two problems, scaling $O({N}^{2}\mathrm{poly}(logN))$ in the dimension $N$ of the system when ignoring the complexity of state readout or $O({N}^{2}\mathrm{poly}(logN))$ when considering the complexity of state readout.

Ilya I. Dumer

Yaozong Zhang, Dabin Zheng, Xiaoqiang Wang

Hans Havlicek, Karl Svozil

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.