Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1607.07149

Efficient quantum circuits for dense and non-unitary operators

Sisi Zhou, J. B. Wang

Published Jul 25, 2016• 2 citations
arXivHTMLPDF

Abstract

Circulant matrices are an important family of operators, which have a wide range of applications in science and engineering related fields. They are in general non-sparse and non-unitary. In this paper, we present efficient quantum circuits to implement circulant operators using fewer resources and with lower complexity than existing methods. Moreover, our quantum circuits can be readily extended to the implementation of Toeplitz, Hankel, and block circulant matrices. Efficient quantum algorithms to implement the inverses and products of circulant operators are also provided.

DOI
10.48550/arxiv.1607.07149

Related papers

Efficient quantum circuits for dense circulant and circulant like operators

Sisi Zhou, Jingbo B. Wang

Circulant matrices are an important family of operators, which have a wide range of applications in science and engineering-related fields. They are, in general, non-sparse and non-unitary. In this paper, we present efficient quantum circuits to implement circulant operators using fewer resources and with lower complexity than existing methods. Moreover, our quantum circuits can be readily extended to the implementation of Toeplitz, Hankel and block circulant matrices. Efficient quantum algorithms to implement the inverses and products of circulant operators are also provided, and an example application in solving the equation of motion for cyclic systems is discussed.

Royal Society Open Science•May 1, 2017•22 citations

Efficient quantum circuits for Toeplitz and Hankel matrices

Anuradha Mahasinghe, J B Wang

Abstract Toeplitz and Hankel matrices have been a subject of intense interest in a wide range of science and engineering related applications. In this paper, we show that quantum circuits can efficiently implement sparse or Fourier-sparse Toeplitz and Hankel matrices. This provides an essential ingredient for solving many physical problems with Toeplitz or Hankel symmetry in the quantum setting with deterministic queries.

arXiv:1605.07710•Journal of Physics A Mathematical and Theoretical•May 24, 2016•11 citations

Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices

Daan Camps, Lin Lin, Roel Van Beeumen +1 more

Abstract. Many standard linear algebra problems can be solved on a quantum computer by using recently developed quantum linear algebra algorithms that make use of block encodings and quantum eigenvalue/singular value transformations. A block encoding embeds a properly scaled matrix of interest [Formula: see text] in a larger unitary transformation [Formula: see text] that can be decomposed into a product of simpler unitaries and implemented efficiently on a quantum computer. Although quantum algorithms can potentially achieve exponential speedup in solving linear algebra problems compared to the best classical algorithm, such a gain in efficiency ultimately hinges on our ability to construct an efficient quantum circuit for the block encoding of [Formula: see text], which is difficult in general, and not trivial even for well structured sparse matrices. In this paper, we give a few examples on how efficient quantum circuits can be explicitly constructed for some well structured sparse matrices and discuss a few strategies used in these constructions. We also provide implementations of these quantum circuits in MATLAB.

arXiv:2203.10236•SIAM Journal on Matrix Analysis and Applications•Mar 11, 2024•78 citations

Efficient quantum walk on a quantum processor

Xiaogang Qiang, T. Loke, Ashley Montanaro +5 more

The random walk formalism is used across a wide range of applications, from modelling share prices to predicting population genetics. Likewise, quantum walks have shown much potential as a framework for developing new quantum algorithms. Here we present explicit efficient quantum circuits for implementing continuous-time quantum walks on the circulant class of graphs. These circuits allow us to sample from the output probability distributions of quantum walks on circulant graphs efficiently. We also show that solving the same sampling problem for arbitrary circulant quantum circuits is intractable for a classical computer, assuming conjectures from computational complexity theory. This is a new link between continuous-time quantum walks and computational complexity theory and it indicates a family of tasks that could ultimately demonstrate quantum supremacy over classical computers. As a proof of principle, we experimentally implement the proposed quantum circuit on an example circulant graph using a two-qubit photonics quantum processor.

arXiv:1510.08657•Nature Communications•May 5, 2016•108 citations

Quantum circuits from non-unitary sparse binary matrices

Krishnageetha Karuppasamy, Varun Puram, K. M. George +1 more

Quantum computing leverages unitary matrices to perform reversible computations while preserving probability norms. However, many real-world applications involve non-unitary sparse matrices, posing a challenge for quantum implementation. This paper introduces a novel method for transforming a class of non-unitary sparse binary matrices into higher-dimensional permutation matrices, ensuring unitarity. Our approach is efficient in both space and time, ensuring practical applicability to large-scale problems. We demonstrate the utility of this transformation in constructing quantum gates and apply the method to model quantum finite state machines (QFSMs) derived from classical deterministic finite automata (DFAs). This work offers a practical pathway for integrating non-unitary transformations into quantum systems, with implications for the many applications that are based on sparse, non-unitary matrices. The significance of this work for automata theory and quantum computation is outlined.

Scientific Reports•Jul 1, 2025•2 citations

A quantum algorithm for Toeplitz matrix-vector multiplication

Shang Gao, Yu-Guang 宇光 Yang 杨

Toeplitz matrix-vector multiplication is widely used in various fields, including optimal control, systolic finite field multipliers, multidimensional convolution, etc. In this paper, we first present a non-asymptotic quantum algorithm for Toeplitz matrix-vector multiplication with time complexity O ( κ polylog n ) , where κ and 2n are the condition number and the dimension of the circulant matrix extended from the Toeplitz matrix, respectively. For the case with an unknown generating function, we also give a corresponding non-asymptotic quantum version that eliminates the dependency on the L 1-norm ρ of the displacement of the structured matrices. Due to the good use of the special properties of Toeplitz matrices, the proposed quantum algorithms are sufficiently accurate and efficient compared to the existing quantum algorithms under certain circumstances.

Chinese Physics B•Feb 6, 2023•4 citations
Circulant matrices are an important family of operators, which have a wide range of applications in science and engineering related fields. They are in general non-sparse and non-unitary. In this paper, we present efficient quantum circuits to implement circulant operators using fewer resources and with lower complexity than existing methods. Moreover, our quantum circuits can be readily extended to the implementation of Toeplitz, Hankel, and block circulant matrices. Efficient quantum algorithms to implement the inverses and products of circulant operators are also provided.
Circulant matrices are an important family of operators, which have a wide range of applications in science and engineering-related fields. They are, in general, non-sparse and non-unitary. In this paper, we present efficient quantum circuits to implement circulant operators using fewer resources and with lower complexity than existing methods. Moreover, our quantum circuits can be readily extended to the implementation of Toeplitz, Hankel and block circulant matrices. Efficient quantum algorithms to implement the inverses and products of circulant operators are also provided, and an example application in solving the equation of motion for cyclic systems is discussed.
Abstract. Many standard linear algebra problems can be solved on a quantum computer by using recently developed quantum linear algebra algorithms that make use of block encodings and quantum eigenvalue/singular value transformations. A block encoding embeds a properly scaled matrix of interest [Formula: see text] in a larger unitary transformation [Formula: see text] that can be decomposed into a product of simpler unitaries and implemented efficiently on a quantum computer. Although quantum algorithms can potentially achieve exponential speedup in solving linear algebra problems compared to the best classical algorithm, such a gain in efficiency ultimately hinges on our ability to construct an efficient quantum circuit for the block encoding of [Formula: see text], which is difficult in general, and not trivial even for well structured sparse matrices. In this paper, we give a few examples on how efficient quantum circuits can be explicitly constructed for some well structured sparse matrices and discuss a few strategies used in these constructions. We also provide implementations of these quantum circuits in MATLAB.
The random walk formalism is used across a wide range of applications, from modelling share prices to predicting population genetics. Likewise, quantum walks have shown much potential as a framework for developing new quantum algorithms. Here we present explicit efficient quantum circuits for implementing continuous-time quantum walks on the circulant class of graphs. These circuits allow us to sample from the output probability distributions of quantum walks on circulant graphs efficiently. We also show that solving the same sampling problem for arbitrary circulant quantum circuits is intractable for a classical computer, assuming conjectures from computational complexity theory. This is a new link between continuous-time quantum walks and computational complexity theory and it indicates a family of tasks that could ultimately demonstrate quantum supremacy over classical computers. As a proof of principle, we experimentally implement the proposed quantum circuit on an example circulant graph using a two-qubit photonics quantum processor.
Quantum computing leverages unitary matrices to perform reversible computations while preserving probability norms. However, many real-world applications involve non-unitary sparse matrices, posing a challenge for quantum implementation. This paper introduces a novel method for transforming a class of non-unitary sparse binary matrices into higher-dimensional permutation matrices, ensuring unitarity. Our approach is efficient in both space and time, ensuring practical applicability to large-scale problems. We demonstrate the utility of this transformation in constructing quantum gates and apply the method to model quantum finite state machines (QFSMs) derived from classical deterministic finite automata (DFAs). This work offers a practical pathway for integrating non-unitary transformations into quantum systems, with implications for the many applications that are based on sparse, non-unitary matrices. The significance of this work for automata theory and quantum computation is outlined.
Toeplitz matrix-vector multiplication is widely used in various fields, including optimal control, systolic finite field multipliers, multidimensional convolution, etc. In this paper, we first present a non-asymptotic quantum algorithm for Toeplitz matrix-vector multiplication with time complexity O ( κ polylog n ) , where κ and 2n are the condition number and the dimension of the circulant matrix extended from the Toeplitz matrix, respectively. For the case with an unknown generating function, we also give a corresponding non-asymptotic quantum version that eliminates the dependency on the L 1-norm ρ of the displacement of the structured matrices. Due to the good use of the special properties of Toeplitz matrices, the proposed quantum algorithms are sufficiently accurate and efficient compared to the existing quantum algorithms under certain circumstances.