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

Dianzi xuebao

Divide and Conquer Algorithms for Quantum Circuit Simulation

Zhiqiang Li

Published Jan 1, 2010• 1 citation
OpenAlex

Abstract

Quantum circuits are divided into two classes,and unitary operator expressions for two kinds of circuits in each class are offered.Transformation of unitary operators between two classes is presented according to tensor product transposition similarity theory.Besides,direct sum operation of matrices is adopted and expanded to vectors to elegantly represent the functions of quantum circuits on input vectors.On the basis of abstracting quantum circuits as controlled unitary operations,divide and conquer algorithms are proposed to simulate quantum circuits.In contrast to other algorithms based on state vector,our algorithms avoid generating matrix operators by tensor product,thus are considerably economy of memory space;and we also show that they are more time-efficient while simulating nontrivial quantum circuits.

Related papers

Quantum Circuit Implementation of Two Matrix Product Operations and Elementary Column Transformations

Yu-Hang Liu, Yuan-Hong Tao, Jing-Run Lan +1 more

This paper focuses on quantum algorithms for three key matrix operations: Hadamard (Schur) product, Kronecker (tensor) product, and elementary column transformations each. By designing specific unitary transformations and auxiliary quantum measurement, efficient quantum schemes with circuit diagrams are proposed. Their computational depths are: O(1) for Kronecker product; O(max(m,n)) for Hadamard product (linked to matrix dimensions); and O(m) for elementary column transformations of (2^n X 2^m) matrices (dependent only on column count).Notably, compared to traditional column transformation via matrix transposition and row transformations, this scheme reduces computation steps and quantum gate usage, lowering quantum computing energy costs.

quant-pharXiv:2511.02413•Nov 5, 2025•0 citations

A Fast Quantum Simulation Algorithm Based on State Vector

Zhiqiang Li

We introduce symbolic representation for quantum circuit,and show how n-qubit circuit can be described as a control qubit symbolic vector and a lower-order controlled gate,instead of the representation of higher-order unitary matrix.We extend the loopless Gray code binary generation algorithm and propose n elements k position binary generation algorithm.Besides,a fast quantum simulation algorithm(FQSA) is presented,it divides a qubit state vector into several operand groups,each group is multiplied by the same unitary matrix,and then the output can be given quickly.In contrast to any other state vector based algorithm,FQSA requires less memory,and has an optimal time complexity.The experimental result of QFT indicates that FQSA is more time-efficient and it can provide more qubits circuit simulation under the same condition.

Dianzi xuebao•Jan 1, 2011•0 citations

Quantum computing and a unified approach to fast unitary transforms

Sos С. Agaian, Andreas Klappenecker

A quantum computer directly manipulates information stored in the state of quantum mechanical systems. The available operations have many attractive features but also underly severe restrictions, which complicate the design of quantum algorithms. We present a divide-and-conquer approach to the design of various quantum algorithms. The class of algorithm includes many transforms which are well-known in classical signal processing applications. We show how fast quantum algorithms can be derived for the discrete Fourier transform, the Walsh-Hadamard transform, the Slant transform, and the Hartley transform. All these algorithms use at most O(log^2 N) operations to transform a state vector of a quantum computer of length N.

arXiv:quant-ph/0201120•Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•May 23, 2002•6 citations

Quantum circuit design methods and applications

Ammar Daskin

Simulating quantum mechanical evolutions in general is difficult on classical computers because the size of the Hilbert space grows exponentially with the number of particles involved in the simulations. However, a quantum computer, which obeys the laws of quantum mechanics, is believed to perform such simulations more efficiently. The time evolution operator, a unitary matrix, of a quantum system acts as a quantum gate changing the state of the system in time. Therefore, any computation on quantum computers can be interpreted as a unitary transformation on quantum state vectors. Generally, quantum gates are sufficiently simple operations so as to avoid difficulty in the physical implementation. The implementation of a general given computation represented by a unitary matrix on quantum computers requires finding an array of elementary quantum gates describing the desired computation. This describes a matrix decomposition problem known as the quantum circuit design problem. In this dissertation, we address the following questions concerning quantum circuit designs: How hard is it to find suitable quantum circuits for a given computation? What are the possible circuit design methods? How do we apply these to simulations of quantum problems, in particular quantum chemistry problems? To answer these questions, we categorize methods for designing quantum circuits as evolutionary algorithms and deterministic methods. We apply our developed group leaders optimization algorithm, an evolutionary algorithm, to find quantum circuits for known quantum algorithms and the simulation of molecular Hamiltonians. Then, we present a deterministic circuit design approach to produce universal circuits, which can be programmable. Moreover, we show how to use these programmable circuit designs within the quantum phase estimation algorithm to find eigenvalues of nonunitary matrices and study resonances in quantum systems. Finally, the quantum phase estimation algorithm is employed to efficiently solve ranking problems: in particular, multiple network alignment is considered to find the similarities between protein-protein interaction networks and molecular networks.

•Jan 1, 2014•2 citations

A divide-and-conquer algorithm for quantum state preparation

Israel F. Araujo, Daniel K. Park, Francesco Petruccione +1 more

Advantages in several fields of research and industry are expected with the rise of quantum computers. However, the computational cost to load classical data in quantum computers can impose restrictions on possible quantum speedups. Known algorithms to create arbitrary quantum states require quantum circuits with depth O(N) to load an N-dimensional vector. Here, we show that it is possible to load an N-dimensional vector with exponential time advantage using a quantum circuit with polylogarithmic depth and entangled information in ancillary qubits. Results show that we can efficiently load data in quantum devices using a divide-and-conquer strategy to exchange computational time for space. We demonstrate a proof of concept on a real quantum device and present two applications for quantum machine learning. We expect that this new loading strategy allows the quantum speedup of tasks that require to load a significant volume of information to quantum devices.

arXiv:2008.01511•Scientific Reports•Mar 18, 2021•169 citations

An efficient method for improving the performance of quantum boolean circuit synthesis algorithms

Shiou-An Wang, Chin-Yung Lu

So far there are no synthesis algorithms that can find all the optimal quantum boolean circuits except an exhaustive algorithm. In this paper, we propose a method based on the divide and conquer approach which can significantly improve the performance of the existing synthesis algorithms to synthesize quantum boolean circuits. A quantum boolean circuit is first divided into two subcircuits. The subcircuit with fewer gates will input all possible combinations of m gates excluding those with the same function specification. The other subcircuit can be synthesized by using the existing algorithm. The two subcircuits are combined and then we can choose the most simplified quantum boolean circuit. According to the experimental results of all the 3-variable functions, we can see that the performance of the existing algorithms can be significantly improved by using our method. Therefore the synthesized quantum boolean circuits are much more simplified than previous results.

International Conference on Multimedia Technology (ICMT)•Jul 1, 2011•0 citations
Quantum circuits are divided into two classes,and unitary operator expressions for two kinds of circuits in each class are offered.Transformation of unitary operators between two classes is presented according to tensor product transposition similarity theory.Besides,direct sum operation of matrices is adopted and expanded to vectors to elegantly represent the functions of quantum circuits on input vectors.On the basis of abstracting quantum circuits as controlled unitary operations,divide and conquer algorithms are proposed to simulate quantum circuits.In contrast to other algorithms based on state vector,our algorithms avoid generating matrix operators by tensor product,thus are considerably economy of memory space;and we also show that they are more time-efficient while simulating nontrivial quantum circuits.
This paper focuses on quantum algorithms for three key matrix operations: Hadamard (Schur) product, Kronecker (tensor) product, and elementary column transformations each. By designing specific unitary transformations and auxiliary quantum measurement, efficient quantum schemes with circuit diagrams are proposed. Their computational depths are: O(1) for Kronecker product; O(max(m,n)) for Hadamard product (linked to matrix dimensions); and O(m) for elementary column transformations of (2^n X 2^m) matrices (dependent only on column count).Notably, compared to traditional column transformation via matrix transposition and row transformations, this scheme reduces computation steps and quantum gate usage, lowering quantum computing energy costs.
We introduce symbolic representation for quantum circuit,and show how n-qubit circuit can be described as a control qubit symbolic vector and a lower-order controlled gate,instead of the representation of higher-order unitary matrix.We extend the loopless Gray code binary generation algorithm and propose n elements k position binary generation algorithm.Besides,a fast quantum simulation algorithm(FQSA) is presented,it divides a qubit state vector into several operand groups,each group is multiplied by the same unitary matrix,and then the output can be given quickly.In contrast to any other state vector based algorithm,FQSA requires less memory,and has an optimal time complexity.The experimental result of QFT indicates that FQSA is more time-efficient and it can provide more qubits circuit simulation under the same condition.
A quantum computer directly manipulates information stored in the state of quantum mechanical systems. The available operations have many attractive features but also underly severe restrictions, which complicate the design of quantum algorithms. We present a divide-and-conquer approach to the design of various quantum algorithms. The class of algorithm includes many transforms which are well-known in classical signal processing applications. We show how fast quantum algorithms can be derived for the discrete Fourier transform, the Walsh-Hadamard transform, the Slant transform, and the Hartley transform. All these algorithms use at most O(log^2 N) operations to transform a state vector of a quantum computer of length N.
Simulating quantum mechanical evolutions in general is difficult on classical computers because the size of the Hilbert space grows exponentially with the number of particles involved in the simulations. However, a quantum computer, which obeys the laws of quantum mechanics, is believed to perform such simulations more efficiently. The time evolution operator, a unitary matrix, of a quantum system acts as a quantum gate changing the state of the system in time. Therefore, any computation on quantum computers can be interpreted as a unitary transformation on quantum state vectors. Generally, quantum gates are sufficiently simple operations so as to avoid difficulty in the physical implementation. The implementation of a general given computation represented by a unitary matrix on quantum computers requires finding an array of elementary quantum gates describing the desired computation. This describes a matrix decomposition problem known as the quantum circuit design problem. In this dissertation, we address the following questions concerning quantum circuit designs: How hard is it to find suitable quantum circuits for a given computation? What are the possible circuit design methods? How do we apply these to simulations of quantum problems, in particular quantum chemistry problems? To answer these questions, we categorize methods for designing quantum circuits as evolutionary algorithms and deterministic methods. We apply our developed group leaders optimization algorithm, an evolutionary algorithm, to find quantum circuits for known quantum algorithms and the simulation of molecular Hamiltonians. Then, we present a deterministic circuit design approach to produce universal circuits, which can be programmable. Moreover, we show how to use these programmable circuit designs within the quantum phase estimation algorithm to find eigenvalues of nonunitary matrices and study resonances in quantum systems. Finally, the quantum phase estimation algorithm is employed to efficiently solve ranking problems: in particular, multiple network alignment is considered to find the similarities between protein-protein interaction networks and molecular networks.
Advantages in several fields of research and industry are expected with the rise of quantum computers. However, the computational cost to load classical data in quantum computers can impose restrictions on possible quantum speedups. Known algorithms to create arbitrary quantum states require quantum circuits with depth O(N) to load an N-dimensional vector. Here, we show that it is possible to load an N-dimensional vector with exponential time advantage using a quantum circuit with polylogarithmic depth and entangled information in ancillary qubits. Results show that we can efficiently load data in quantum devices using a divide-and-conquer strategy to exchange computational time for space. We demonstrate a proof of concept on a real quantum device and present two applications for quantum machine learning. We expect that this new loading strategy allows the quantum speedup of tasks that require to load a significant volume of information to quantum devices.
So far there are no synthesis algorithms that can find all the optimal quantum boolean circuits except an exhaustive algorithm. In this paper, we propose a method based on the divide and conquer approach which can significantly improve the performance of the existing synthesis algorithms to synthesize quantum boolean circuits. A quantum boolean circuit is first divided into two subcircuits. The subcircuit with fewer gates will input all possible combinations of m gates excluding those with the same function specification. The other subcircuit can be synthesized by using the existing algorithm. The two subcircuits are combined and then we can choose the most simplified quantum boolean circuit. According to the experimental results of all the 3-variable functions, we can see that the performance of the existing algorithms can be significantly improved by using our method. Therefore the synthesized quantum boolean circuits are much more simplified than previous results.