Quantum Algorithms for Matrix Operations Based on Unitary Transformations and Ancillary State Measurements

• URL: http://arxiv.org/abs/2501.15137v1
• Date: Sat, 25 Jan 2025 08:51:00 GMT
• Title: Quantum Algorithms for Matrix Operations Based on Unitary Transformations and Ancillary State Measurements
• Authors: Yu-Hang Liu, Yuan-Hong Tao, Yi-Kun Lan, Shao-Ming Fei,
• Abstract summary: This paper presents quantum algorithms for several important matrix operations. By leveraging multi-qubit Toffoli gates and basic single-qubit operations, these algorithms efficiently carry out matrix row addition, row swapping, trace calculation and transpose.
• Score: 3.8622081658937093
• License:
• Abstract: Matrix operations are of great significance in quantum computing, which manipulate quantum states in information processing. This paper presents quantum algorithms for several important matrix operations. By leveraging multi-qubit Toffoli gates and basic single-qubit operations, these algorithms efficiently carry out matrix row addition, row swapping, trace calculation and transpose. By using the ancillary measurement techniques to eliminate redundant information, these algorithms achieve streamlined and efficient computations, and demonstrate excellent performance with the running time increasing logarithmically as the matrix dimension grows, ensuring scalability. The success probability depends on the matrix dimensions for the trace calculation, and on the matrix elements for row addition. Interestingly, the success probability is a constant for matrix row swapping and transpose, highlighting the reliability and efficiency.

Related papers

• Optimizing Quantum Transformation Matrices: A Block Decomposition Approach for Efficient Gate Reduction [5.453850739960517]
  The paper introduces an algorithm designed to approximate quantum transformation matrix with a restricted number of gates. Inspired by the Block Decompose algorithm, our approach processes transformation matrices in a block-wise manner. Simulations validate the effectiveness of the algorithm in approximating transformations with significantly fewer gates.
  arXiv  Detail & Related papers  (2024-12-18T14:54:45Z)
• Matrix manipulations via unitary transformations and ancilla-state measurements [46.13392585104221]
  We propose protocols for calculating inner product, matrix addition and matrix multiplication based on multiqubit Toffoli-type and the simplest one-qubit operations. The depth (runtime) of the addition protocol is $O(1)$ and that of other protocols logarithmically increases with the dimensionality of the considered matrices.
  arXiv  Detail & Related papers  (2023-11-19T14:06:25Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• DBA: Efficient Transformer with Dynamic Bilinear Low-Rank Attention [53.02648818164273]
  We present an efficient yet effective attention mechanism, namely the Dynamic Bilinear Low-Rank Attention (DBA) DBA compresses the sequence length by input-sensitive dynamic projection matrices and achieves linear time and space complexity. Experiments over tasks with diverse sequence length conditions show that DBA achieves state-of-the-art performance.
  arXiv  Detail & Related papers  (2022-11-24T03:06:36Z)
• A quantum algorithm for solving eigenproblem of the Laplacian matrix of a fully connected weighted graph [4.045204834863644]
  We propose an efficient quantum algorithm to solve the eigenproblem of the Laplacian matrix of a fully connected weighted graph. Specifically, we adopt the optimal Hamiltonian simulation technique based on the block-encoding framework. We also show that our algorithm can be extended to solve the eigenproblem of symmetric (non-symmetric) normalized Laplacian matrix.
  arXiv  Detail & Related papers  (2022-03-28T02:24:08Z)
• Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices [4.2389474761558406]
  We show how efficient quantum circuits can be explicitly constructed for some well-structured matrices. We also provide implementations of these quantum circuits in sparse strategies.
  arXiv  Detail & Related papers  (2022-03-19T03:50:16Z)
• Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
  We propose quantum algorithms for matrix operations using the "Sender-Receiver" model. These quantum protocols can be used as subroutines in other quantum schemes.
  arXiv  Detail & Related papers  (2022-02-10T08:12:20Z)
• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors [54.936314353063494]
  We provide recovery guarantees for a correlation-based optimization algorithm for robust 1-bit compressive sensing. We make use of a practical iterative algorithm, and perform numerical experiments on image datasets to corroborate our results.
  arXiv  Detail & Related papers  (2021-08-08T05:28:06Z)
• Quantum algorithms for powering stable Hermitian matrices [0.7734726150561088]
  Matrix powering is a fundamental computational primitive in linear algebra. We present two quantum algorithms that can achieve speedup over the classical matrix powering algorithms.
  arXiv  Detail & Related papers  (2021-03-15T12:20:04Z)
• Multi-View Spectral Clustering with High-Order Optimal Neighborhood Laplacian Matrix [57.11971786407279]
  Multi-view spectral clustering can effectively reveal the intrinsic cluster structure among data. This paper proposes a multi-view spectral clustering algorithm that learns a high-order optimal neighborhood Laplacian matrix. Our proposed algorithm generates the optimal Laplacian matrix by searching the neighborhood of the linear combination of both the first-order and high-order base.
  arXiv  Detail & Related papers  (2020-08-31T12:28:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.