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:1812.03454

Duality Quantum Computing with Subwave Projections

Fangjun Hu, Gui‐Lu Long

Published Dec 9, 2018• 0 citations
arXivHTMLPDF

Abstract

Duality quantum computing (DQC) offers the use of linear combination of unitaries (LCU), or generalized quantum gates, in designing quantum algorithms. DQC contains wave divider and wave combiner operations. The wave function of a quantum computer is split into several subwaves after the wave division operation. Then different unitary operations are performed on different subwaves in parallel. A quantum wave combiner combines the subwaves into a final wave function, so that a linear combination of the unitaries are performed on the final state. In this paper, we study of the properties of duality quantum computer with projections on subwaves. In subwave-projection DQC (SWP-DQC), we can realize the linear combinations of non-unitaries, and this not only gives further flexibility for designing quantum algorithms, but also offers additional speedup in the expected time complexity. Specifically, SWP-DQC offers an O(M) acceleration over DQC with only final-wave-projection in the mean time complexity, where M is the number of projections. As an application, we show that the ground state preparation algorithm recently proposed by Ge, Tura, and Cirac is actually an DQC algorithm, and we further optimized the algorithm using SWP-DQC, which can save up to $\log_2 N$ qubits compared DQC without subwave projection, where N is the dimension of the system's Hilbert Space.

DOI
10.48550/arxiv.1812.03454

Related papers

Quantum Computing

Dong Ruan, Gui‐Lu Long, Shi-Jie WEI +1 more

Quantum computing exploits quantum mechanical properties to perform computations. It enables quantum parallelism and provides much more powerful data processing capabilities than classical computers. With a quantum computer, one can exponentially accelerate quantum system simulation and accelerate some important classical algorithms. Traditional quantum algorithms use unitary evolution to process information. A quantum computing process is the product of a series of unitary operators. In 1994, Shor invented a quantum prime factorization algorithm that exponentially accelerates the factorization of an integer. In 1996, Grover proposed a quantum search algorithm that accelerates the search of an unsorted database using square-root steps. Afterwards, the development of quantum algorithms slowed down, leading to a subsequent query by Shor in 2003 regarding why no more significant quantum algorithms have been found. Since 2009, many important new quantum algorithms have been proposed, such as a quantum algorithm for solving linear equations with the capability of exponential acceleration, a quantum algorithm for sparse Hamiltonian simulation using linear combinations of unitary operators, and a novel algorithm for Hamiltonian simulation, which provides exponential improvements in precision. In this paper, we first describe the basic principles of quantum computation. We then describe the Shor algorithm and Grover/Long search algorithm. These quantum algorithms are the general quantum algorithms that use unitary operations in their computational processes. Next, we introduce the basic principles of duality quantum computing, which was proposed in 2002. In contrast to traditional quantum computing, duality quantum computing allows the use of linear combinations of unitary operators in the computation process, meaning the multiplication, division, addition, and subtraction of unitary operators are all possible in duality quantum computing. Thus, duality quantum computing provides more flexibility for constructing quantum algorithms and the techniques used in classical algorithm design can be directly used to construct quantum algorithms. We then review recent work regarding newer quantum algorithms that enable the linear combination of unitary operators, which are actually duality quantum algorithms. Additionally, a duality quantum simulation algorithm for open quantum systems is introduced. This algorithm not only reduces computational complexity, but also improves accuracy exponentially. Finally, a summary and the future prospects of quantum algorithms are provided.

Scientia Sinica Informationis•Sep 25, 2017•8 citations

Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers

Shantanav Chakraborty

We develop three new methods to implement any Linear Combination of Unitaries (LCU), a powerful quantum algorithmic tool with diverse applications. While the standard LCU procedure requires several ancilla qubits and sophisticated multi-qubit controlled operations, our methods consume significantly fewer quantum resources. The first method ( Single-Ancilla LCU ) estimates expectation values of observables with respect to any quantum state prepared by an LCU procedure while requiring only a single ancilla qubit, and no multi-qubit controlled operations. The second approach ( Analog LCU ) is a simple, physically motivated, continuous-time analogue of LCU, tailored to hybrid qubit-qumode systems. The third method ( Ancilla-free LCU ) requires no ancilla qubit at all and is useful when we are interested in the projection of a quantum state (prepared by the LCU procedure) in some subspace of interest. We apply the first two techniques to develop new quantum algorithms for a wide range of practical problems, ranging from Hamiltonian simulation, ground state preparation and property estimation, and quantum linear systems. Remarkably, despite consuming fewer quantum resources they retain a provable quantum advantage. The third technique allows us to connect discrete and continuous-time quantum walks with their classical counterparts. It also unifies the recently developed optimal quantum spatial search algorithms in both these frameworks, and leads to the development of new ones that require fewer ancilla qubits. Overall, our results are quite generic and can be readily applied to other problems, even beyond those considered here.

arXiv:2302.13555•Quantum•Oct 10, 2024•64 citations

Universal quantum simulation of single-qubit nonunitary operators using duality quantum algorithm

Chao Zheng

Quantum information processing enhances human's power to simulate nature in quantum level and solve complex problem efficiently. During the process, a series of operators is performed to evolve the system or undertake a computing task. In recent year, research interest in non-Hermitian quantum systems, dissipative-quantum systems and new quantum algorithms has greatly increased, which nonunitary operators take an important role in. In this work, we utilize the linear combination of unitaries technique for nonunitary dynamics on a single qubit to give explicit decompositions of the necessary unitaries, and simulate arbitrary time-dependent single-qubit nonunitary operator F(t) using duality quantum algorithm. We find that the successful probability is not only decided by F(t) and the initial state, but also is inversely proportional to the dimensions of the used ancillary Hilbert subspace. In a general case, the simulation can be achieved in both eight- and six-dimensional Hilbert spaces. In phase matching conditions, F(t) can be simulated by only two qubits. We illustrate our method by simulating typical non-Hermitian systems and single-qubit measurements. Our method can be extended to high-dimensional case, such as Abrams-Lloyd's two-qubit gate. By discussing the practicability, we expect applications and experimental implementations in the near future.

Scientific Reports•Feb 17, 2021•58 citations

Trade-offs between Quantum and Classical Resources in the Linear Combination of Unitaries

Kaito Wada, Hiroyuki Harada, Yasunari Suzuki +3 more

The randomized linear combination of unitaries (LCU) method with many applications to early fault-tolerant quantum computing algorithms has been proposed. This quantum algorithm computes the same expectation values as the original, fully coherent LCU algorithm using a shallower quantum circuit with a single ancilla qubit, at the cost of a quadratically larger sampling overhead. In this work, we propose a quantum algorithm intermediate between the original and randomized LCU that manages the trade-off between the sampling overhead and circuit complexity. Our algorithm divides the set of unitary operators into several groups and then randomly samples LCU circuits from these groups to evaluate the target expectation value. Notably, we reveal that across all grouping strategies, the mechanism of the sampling overhead reduction can be solely characterized by a metric we call the reduction factor. Moreover, we analytically prove an underlying monotonicity of the reduction factor in the group size: larger group sizes entail smaller sampling overhead. Finally, our framework enables a more flexible algorithmic design by systematically yielding intermediate implementations of LCU-based algorithms; we provide intermediate implementations of non-Hermitian dynamics simulation, ground-state property estimation, and quantum error detection. Besides, we demonstrate this principle by deriving intermediate trade-off scaling in sample complexity and ancillary space for quantum linear system solver.

quant-pharXiv:2512.06260•Dec 9, 2025•5 citations

From linear combination of quantum states to Grover's searching algorithm

Changpeng Shao

Linear combination of unitaries (LCU for short) is one of the most important techniques in designing quantum algorithms. In this paper, we propose a new quantum algorithm in three different forms to achieve LCU. Different from previous algorithms [Childs-linear-system,Clader,Long11], the complexity now only depends on the number of the unitaries and the precision. So it will play more important role in the design of quantum algorithms when the number of unitaries is small, such as quantum iteration algorithms. %Since in iteration algorithms, $m$ often refers to the iteration steps, which is small if the iteration algorithms are efficient. Moreover, as an application of the new LCU, three new quantum algorithms to the searching problem will be proposed, which will provide us new insights into Grover's searching algorithm. We also show that the problem of LCU is closely related to the problem of if we can efficiently implement $U^t$ for $0

arXiv:1807.09693•Jul 22, 2018•8 citations

Efficient simulation of open quantum system in duality quantum computing

Shi-Jie Wei, Gui‐Lu Long

Practical quantum systems are open systems due to interactions with their environment. Understanding the evolution of open systems dynamics is important for quantum noise processes , designing quantum error correcting codes, and performing simulations of open quantum systems. Here we proposed an efficient quantum algorithm for simulating the evolution of an open quantum system on a duality quantum computer. In contrast to unitary evolution in a usual quantum computer, the evolution operator in a duality quantum computer is a linear combination of unitary operators. In this duality algorithm, the time evolution of open quantum system is realized by using Kraus operators which is naturally realized in duality quantum computing. Compared to the Lloyd's quantum algorithm [Science.273, 1073(1996)] , the dependence on the dimension of the open quantum system in our algorithm is decreased. Moreover, our algorithm uses a truncated Taylor series of the evolution operators, exponentially improving the performance on the precision compared with existing quantum simulation algorithms with unitary evolution operations.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Nov 3, 2016•3 citations
Duality quantum computing (DQC) offers the use of linear combination of unitaries (LCU), or generalized quantum gates, in designing quantum algorithms. DQC contains wave divider and wave combiner operations. The wave function of a quantum computer is split into several subwaves after the wave division operation. Then different unitary operations are performed on different subwaves in parallel. A quantum wave combiner combines the subwaves into a final wave function, so that a linear combination of the unitaries are performed on the final state. In this paper, we study of the properties of duality quantum computer with projections on subwaves. In subwave-projection DQC (SWP-DQC), we can realize the linear combinations of non-unitaries, and this not only gives further flexibility for designing quantum algorithms, but also offers additional speedup in the expected time complexity. Specifically, SWP-DQC offers an O(M) acceleration over DQC with only final-wave-projection in the mean time complexity, where M is the number of projections. As an application, we show that the ground state preparation algorithm recently proposed by Ge, Tura, and Cirac is actually an DQC algorithm, and we further optimized the algorithm using SWP-DQC, which can save up to log⁡2N\log_2 Nlog2​N qubits compared DQC without subwave projection, where N is the dimension of the system's Hilbert Space.
Quantum computing exploits quantum mechanical properties to perform computations. It enables quantum parallelism and provides much more powerful data processing capabilities than classical computers. With a quantum computer, one can exponentially accelerate quantum system simulation and accelerate some important classical algorithms. Traditional quantum algorithms use unitary evolution to process information. A quantum computing process is the product of a series of unitary operators. In 1994, Shor invented a quantum prime factorization algorithm that exponentially accelerates the factorization of an integer. In 1996, Grover proposed a quantum search algorithm that accelerates the search of an unsorted database using square-root steps. Afterwards, the development of quantum algorithms slowed down, leading to a subsequent query by Shor in 2003 regarding why no more significant quantum algorithms have been found. Since 2009, many important new quantum algorithms have been proposed, such as a quantum algorithm for solving linear equations with the capability of exponential acceleration, a quantum algorithm for sparse Hamiltonian simulation using linear combinations of unitary operators, and a novel algorithm for Hamiltonian simulation, which provides exponential improvements in precision. In this paper, we first describe the basic principles of quantum computation. We then describe the Shor algorithm and Grover/Long search algorithm. These quantum algorithms are the general quantum algorithms that use unitary operations in their computational processes. Next, we introduce the basic principles of duality quantum computing, which was proposed in 2002. In contrast to traditional quantum computing, duality quantum computing allows the use of linear combinations of unitary operators in the computation process, meaning the multiplication, division, addition, and subtraction of unitary operators are all possible in duality quantum computing. Thus, duality quantum computing provides more flexibility for constructing quantum algorithms and the techniques used in classical algorithm design can be directly used to construct quantum algorithms. We then review recent work regarding newer quantum algorithms that enable the linear combination of unitary operators, which are actually duality quantum algorithms. Additionally, a duality quantum simulation algorithm for open quantum systems is introduced. This algorithm not only reduces computational complexity, but also improves accuracy exponentially. Finally, a summary and the future prospects of quantum algorithms are provided.
We develop three new methods to implement any Linear Combination of Unitaries (LCU), a powerful quantum algorithmic tool with diverse applications. While the standard LCU procedure requires several ancilla qubits and sophisticated multi-qubit controlled operations, our methods consume significantly fewer quantum resources. The first method ( Single-Ancilla LCU ) estimates expectation values of observables with respect to any quantum state prepared by an LCU procedure while requiring only a single ancilla qubit, and no multi-qubit controlled operations. The second approach ( Analog LCU ) is a simple, physically motivated, continuous-time analogue of LCU, tailored to hybrid qubit-qumode systems. The third method ( Ancilla-free LCU ) requires no ancilla qubit at all and is useful when we are interested in the projection of a quantum state (prepared by the LCU procedure) in some subspace of interest. We apply the first two techniques to develop new quantum algorithms for a wide range of practical problems, ranging from Hamiltonian simulation, ground state preparation and property estimation, and quantum linear systems. Remarkably, despite consuming fewer quantum resources they retain a provable quantum advantage. The third technique allows us to connect discrete and continuous-time quantum walks with their classical counterparts. It also unifies the recently developed optimal quantum spatial search algorithms in both these frameworks, and leads to the development of new ones that require fewer ancilla qubits. Overall, our results are quite generic and can be readily applied to other problems, even beyond those considered here.
Quantum information processing enhances human's power to simulate nature in quantum level and solve complex problem efficiently. During the process, a series of operators is performed to evolve the system or undertake a computing task. In recent year, research interest in non-Hermitian quantum systems, dissipative-quantum systems and new quantum algorithms has greatly increased, which nonunitary operators take an important role in. In this work, we utilize the linear combination of unitaries technique for nonunitary dynamics on a single qubit to give explicit decompositions of the necessary unitaries, and simulate arbitrary time-dependent single-qubit nonunitary operator F(t) using duality quantum algorithm. We find that the successful probability is not only decided by F(t) and the initial state, but also is inversely proportional to the dimensions of the used ancillary Hilbert subspace. In a general case, the simulation can be achieved in both eight- and six-dimensional Hilbert spaces. In phase matching conditions, F(t) can be simulated by only two qubits. We illustrate our method by simulating typical non-Hermitian systems and single-qubit measurements. Our method can be extended to high-dimensional case, such as Abrams-Lloyd's two-qubit gate. By discussing the practicability, we expect applications and experimental implementations in the near future.
The randomized linear combination of unitaries (LCU) method with many applications to early fault-tolerant quantum computing algorithms has been proposed. This quantum algorithm computes the same expectation values as the original, fully coherent LCU algorithm using a shallower quantum circuit with a single ancilla qubit, at the cost of a quadratically larger sampling overhead. In this work, we propose a quantum algorithm intermediate between the original and randomized LCU that manages the trade-off between the sampling overhead and circuit complexity. Our algorithm divides the set of unitary operators into several groups and then randomly samples LCU circuits from these groups to evaluate the target expectation value. Notably, we reveal that across all grouping strategies, the mechanism of the sampling overhead reduction can be solely characterized by a metric we call the reduction factor. Moreover, we analytically prove an underlying monotonicity of the reduction factor in the group size: larger group sizes entail smaller sampling overhead. Finally, our framework enables a more flexible algorithmic design by systematically yielding intermediate implementations of LCU-based algorithms; we provide intermediate implementations of non-Hermitian dynamics simulation, ground-state property estimation, and quantum error detection. Besides, we demonstrate this principle by deriving intermediate trade-off scaling in sample complexity and ancillary space for quantum linear system solver.
Linear combination of unitaries (LCU for short) is one of the most important techniques in designing quantum algorithms. In this paper, we propose a new quantum algorithm in three different forms to achieve LCU. Different from previous algorithms [Childs-linear-system,Clader,Long11], the complexity now only depends on the number of the unitaries and the precision. So it will play more important role in the design of quantum algorithms when the number of unitaries is small, such as quantum iteration algorithms. %Since in iteration algorithms, mmm often refers to the iteration steps, which is small if the iteration algorithms are efficient. Moreover, as an application of the new LCU, three new quantum algorithms to the searching problem will be proposed, which will provide us new insights into Grover's searching algorithm. We also show that the problem of LCU is closely related to the problem of if we can efficiently implement UtU^tUt for $0
Practical quantum systems are open systems due to interactions with their environment. Understanding the evolution of open systems dynamics is important for quantum noise processes , designing quantum error correcting codes, and performing simulations of open quantum systems. Here we proposed an efficient quantum algorithm for simulating the evolution of an open quantum system on a duality quantum computer. In contrast to unitary evolution in a usual quantum computer, the evolution operator in a duality quantum computer is a linear combination of unitary operators. In this duality algorithm, the time evolution of open quantum system is realized by using Kraus operators which is naturally realized in duality quantum computing. Compared to the Lloyd's quantum algorithm [Science.273, 1073(1996)] , the dependence on the dimension of the open quantum system in our algorithm is decreased. Moreover, our algorithm uses a truncated Taylor series of the evolution operators, exponentially improving the performance on the precision compared with existing quantum simulation algorithms with unitary evolution operations.