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

Quantum solvability of noisy linear systems of equations by divide-and-conquer strategy.

Wooyeong Song, Youngrong Lim, Kabgyun Jeong, Yun-Seong Ji, Jinhyoung Lee, Jaewan Kim, M. S. Kim, Jeongho Bang

Published Aug 17, 2019• 0 citations
OpenAlex

Abstract

Noisy linear problems have been studied in various science and engineering disciplines. A class of hard noisy linear problems can be formulated as follows: Given a matrix $\hat{A}$ and a vector $\mathbf{b}$ constructed using a finite set of samples, a hidden vector or structure involved in $\mathbf{b}$ is obtained by solving a noise-corrupted linear equation $\hat{A}\mathbf{x} \approx \mathbf{b} + \boldsymbol\eta$, where $\boldsymbol\eta$ is a noise vector that cannot be identified. For solving such a noisy linear problem, we consider a quantum algorithm based on a divide-and-conquer strategy, wherein a large core process is divided into smaller subprocesses. The algorithm appropriately reduces both the computational complexities and size of a quantum sample. More specifically, if a quantum computer can access a particular reduced form of the quantum samples, polynomial quantum-sample and time complexities are achieved in the main computation. The size of a quantum sample and its executing system can be reduced, e.g., from exponential to sub-exponential with respect to the problem length, which is better than other results we are aware. We analyse the noise model conditions for such a quantum advantage, and show when the divide-and-conquer strategy can be beneficial for quantum noisy linear problems.

Related papers

Quantum solvability of noisy linear problems by divide-and-conquer strategy

Wooyeong Song, Youngrong Lim, Kabgyun Jeong +5 more

Abstract Noisy linear problems have been studied in various science and engineering disciplines. A class of ‘hard’ noisy linear problems can be formulated as follows: Given a matrix A ^ and a vector b constructed using a finite set of samples, a hidden vector or structure involved in b is obtained by solving a noise-corrupted linear equation A ^ x ≈ b + η , where η is a noise vector that cannot be identified. For solving such a noisy linear problem, we consider a quantum algorithm based on a divide-and-conquer strategy, wherein a large core process is divided into smaller subprocesses. The algorithm appropriately reduces both the computational complexities and size of a quantum sample. More specifically, if a quantum computer can access a particular reduced form of the quantum samples, polynomial quantum-sample and time complexities are achieved in the main computation. The size of a quantum sample and its executing system can be reduced, e.g., from exponential to sub-exponential with respect to the problem length, which is better than other results we are aware. We analyse the noise model conditions for such a quantum advantage, and show when the divide-and-conquer strategy can be beneficial for quantum noisy linear problems.

arXiv:1908.06229•Quantum Science and Technology•Feb 3, 2022•6 citations

Tangible Quantum Speedup in Learning-With-Errors Problem

Wooyeong Song, Youngrong Lim, Kabgyun Jeong +4 more

Very recently, one of the most biggest agenda issues is to provide the proof of quantum computational speedup, particularly with a prospect for near-term uses. However, many quantum algorithms are beyond the reach of noisy intermediate-scale quantum (NISQ) realization. This is mainly because of the requirement of excessively large superposition and massive quantum circuit. Hence, we propose a (say) ``NISQ-compatible'' algorithm for one of the crucial problems in computation and modern cryptography, the learning-with-errors (LWE) problem. We base an approach on the divide-and-conquer, wherein a large core process is subdivided into smaller subprocesses. For a specific error distribution and problem condition, it is shown that the proposed quantum LWE algorithm allows the use of exponentially less-superposed quantum samples and operation overheads are reduced, while achieving polynomial sample complexity.

•Aug 17, 2019•0 citations

Fault-Tolerant Quantum Solvability of Noisy Binary Linear Problem

Wooyeong Song, Youngrong Lim, Kabgyun Jeong +4 more

The noisy binary linear problem (NBLP) is a known computationally intractable problem. Thus, NBLP offers primitives for post-quantum cryptography. An efficient quantum NBLP algorithm that exhibits a polynomial quantum sample and time complexities has recently been proposed. However, a large number of samples should be loaded in a highly entangled state, and it is unclear whether such a precondition does not affect the quantum speedup obtained. Here, we analyse the quantum solvability of NBLP by considering the entire algorithm process, namely from the preparation of the quantum sample to the main computation. Assuming that the algorithm runs on fault-tolerant quantum circuitry, the cost is defined in terms of the overall number of layers of $T$ gates, often referred to as $T$-depth complexity. We show that the cost of solving the NBLP can be polynomial in the problem size, at the expense of an exponentially increasing number of logical qubits.

•Sep 23, 2021•0 citations

Polynomial T-depth quantum solvability of noisy binary linear problem: from quantum-sample preparation to main computation

Wooyeong Song, Youngrong Lim, Kabgyun Jeong +4 more

Abstract The noisy binary linear problem (NBLP) is known as a computationally hard problem, and therefore, it offers primitives for post-quantum cryptography. An efficient quantum NBLP algorithm that exhibits a polynomial quantum sample and time complexities has recently been proposed. However, the algorithm requires a large number of samples to be loaded in a highly entangled state and it is unclear whether such a precondition on the quantum speedup can be obtained efficiently. Here, we present a complete analysis of the quantum solvability of the NBLP by considering the entire algorithm process, namely from the preparation of the quantum sample to the main computation. By assuming that the algorithm runs on ‘fault-tolerant’ quantum circuitry, we introduce a reasonable measure of the computational time cost. The measure is defined in terms of the overall number of T gate layers, referred to as T-depth complexity. We show that the cost of solving the NBLP can be polynomial in the problem size, at the expense of an exponentially increasing logical qubits.

arXiv:2109.11186•New Journal of Physics•Sep 26, 2022•3 citations

Quantum algorithm for solving matrix equations of the form AX = B

Xu Li, Xiaoqi Liu, Jin‐Min Liang +3 more

Abstract Solving linear systems of equations is of vital importance in various fields of science. With the scale of calculation soaring, classical computers are intractable, and the advantage of quantum computing is reflected. Quantum algorithm has exponential acceleration in solving the linear systems A x ⃗ = b ⃗ for sparse and well-conditioned coefficient matrix A with dimension N × N . In this paper, we present a quantum algorithm to solve matrix equations of the form AX = B , where X = ( x ⃗ 1 , x ⃗ 2 , … , x ⃗ n ) , B = ( b ⃗ 1 , b ⃗ 2 , … , b ⃗ n ) , x ⃗ k and b ⃗ k are unit vectors. The problem can be intuitively treated as solving n linear systems simultaneously, which will needs O ( n log N ) complexity by the famous HHL algorithm. We demonstrate that in our algorithm the scale of complexity is O ( log n N ) . In the error analysis part, phase estimation is discussed in details.

Laser Physics Letters•Mar 21, 2022•10 citations

Deep Variational Quantum Eigensolver: A Divide-And-Conquer Method for Solving a Larger Problem with Smaller Size Quantum Computers

Keisuke Fujii, Kaoru Mizuta, Hiroshi Ueda +3 more

We propose a divide-and-conquer method for the quantum-classical hybrid algorithm to solve larger problems with small-scale quantum computers.Specifically, we concatenate a variational quantum eigensolver (VQE) with a reduction in the system dimension, where the interactions between divided subsystems are taken as an effective Hamiltonian expanded by the reduced basis.Then the effective Hamiltonian is further solved by the VQE, which we call deep VQE.Deep VQE allows us to apply quantum-classical hybrid algorithms on small-scale quantum computers to large systems with strong intrasubsystem interactions and weak intersubsystem interactions, or strongly correlated spin models on large regular lattices.As proof-of-principle numerical demonstrations, we use the proposed method for quasi-one-dimensional models, including one-dimensionally coupled 12-qubit Heisenberg antiferromagnetic models on kagome lattices as well as two-dimensional Heisenberg antiferromagnetic models on square lattices.The largest problem size of 64 qubits is solved by simulating 20-qubit quantum computers with a reasonably good accuracy approximately a few %.The proposed scheme enables us to handle the problems of > 1000 qubits by concatenating VQEs with a few tens of qubits.While it is unclear how accurate ground-state energy can be obtained for such a large system, our numerical results on a 64-qubit system suggest that deep VQE provides a good approximation (discrepancy within a few percent) and has room for further improvement.Therefore, deep VQE provides us a promising pathway to solve practically important problems on noisy intermediate-scale quantum computers.

arXiv:2007.10917•PRX Quantum•Mar 21, 2022•66 citations
Noisy linear problems have been studied in various science and engineering disciplines. A class of hard noisy linear problems can be formulated as follows: Given a matrix A^\hat{A}A^ and a vector b\mathbf{b}b constructed using a finite set of samples, a hidden vector or structure involved in b\mathbf{b}b is obtained by solving a noise-corrupted linear equation A^x≈b+η\hat{A}\mathbf{x} \approx \mathbf{b} + \boldsymbol\etaA^x≈b+η, where η\boldsymbol\etaη is a noise vector that cannot be identified. For solving such a noisy linear problem, we consider a quantum algorithm based on a divide-and-conquer strategy, wherein a large core process is divided into smaller subprocesses. The algorithm appropriately reduces both the computational complexities and size of a quantum sample. More specifically, if a quantum computer can access a particular reduced form of the quantum samples, polynomial quantum-sample and time complexities are achieved in the main computation. The size of a quantum sample and its executing system can be reduced, e.g., from exponential to sub-exponential with respect to the problem length, which is better than other results we are aware. We analyse the noise model conditions for such a quantum advantage, and show when the divide-and-conquer strategy can be beneficial for quantum noisy linear problems.
Abstract Noisy linear problems have been studied in various science and engineering disciplines. A class of ‘hard’ noisy linear problems can be formulated as follows: Given a matrix A ^ and a vector b constructed using a finite set of samples, a hidden vector or structure involved in b is obtained by solving a noise-corrupted linear equation A ^ x ≈ b + η , where η is a noise vector that cannot be identified. For solving such a noisy linear problem, we consider a quantum algorithm based on a divide-and-conquer strategy, wherein a large core process is divided into smaller subprocesses. The algorithm appropriately reduces both the computational complexities and size of a quantum sample. More specifically, if a quantum computer can access a particular reduced form of the quantum samples, polynomial quantum-sample and time complexities are achieved in the main computation. The size of a quantum sample and its executing system can be reduced, e.g., from exponential to sub-exponential with respect to the problem length, which is better than other results we are aware. We analyse the noise model conditions for such a quantum advantage, and show when the divide-and-conquer strategy can be beneficial for quantum noisy linear problems.
Very recently, one of the most biggest agenda issues is to provide the proof of quantum computational speedup, particularly with a prospect for near-term uses. However, many quantum algorithms are beyond the reach of noisy intermediate-scale quantum (NISQ) realization. This is mainly because of the requirement of excessively large superposition and massive quantum circuit. Hence, we propose a (say) ``NISQ-compatible'' algorithm for one of the crucial problems in computation and modern cryptography, the learning-with-errors (LWE) problem. We base an approach on the divide-and-conquer, wherein a large core process is subdivided into smaller subprocesses. For a specific error distribution and problem condition, it is shown that the proposed quantum LWE algorithm allows the use of exponentially less-superposed quantum samples and operation overheads are reduced, while achieving polynomial sample complexity.
The noisy binary linear problem (NBLP) is a known computationally intractable problem. Thus, NBLP offers primitives for post-quantum cryptography. An efficient quantum NBLP algorithm that exhibits a polynomial quantum sample and time complexities has recently been proposed. However, a large number of samples should be loaded in a highly entangled state, and it is unclear whether such a precondition does not affect the quantum speedup obtained. Here, we analyse the quantum solvability of NBLP by considering the entire algorithm process, namely from the preparation of the quantum sample to the main computation. Assuming that the algorithm runs on fault-tolerant quantum circuitry, the cost is defined in terms of the overall number of layers of TTT gates, often referred to as TTT-depth complexity. We show that the cost of solving the NBLP can be polynomial in the problem size, at the expense of an exponentially increasing number of logical qubits.
Abstract The noisy binary linear problem (NBLP) is known as a computationally hard problem, and therefore, it offers primitives for post-quantum cryptography. An efficient quantum NBLP algorithm that exhibits a polynomial quantum sample and time complexities has recently been proposed. However, the algorithm requires a large number of samples to be loaded in a highly entangled state and it is unclear whether such a precondition on the quantum speedup can be obtained efficiently. Here, we present a complete analysis of the quantum solvability of the NBLP by considering the entire algorithm process, namely from the preparation of the quantum sample to the main computation. By assuming that the algorithm runs on ‘fault-tolerant’ quantum circuitry, we introduce a reasonable measure of the computational time cost. The measure is defined in terms of the overall number of T gate layers, referred to as T-depth complexity. We show that the cost of solving the NBLP can be polynomial in the problem size, at the expense of an exponentially increasing logical qubits.
Abstract Solving linear systems of equations is of vital importance in various fields of science. With the scale of calculation soaring, classical computers are intractable, and the advantage of quantum computing is reflected. Quantum algorithm has exponential acceleration in solving the linear systems A x ⃗ = b ⃗ for sparse and well-conditioned coefficient matrix A with dimension N × N . In this paper, we present a quantum algorithm to solve matrix equations of the form AX = B , where X = ( x ⃗ 1 , x ⃗ 2 , … , x ⃗ n ) , B = ( b ⃗ 1 , b ⃗ 2 , … , b ⃗ n ) , x ⃗ k and b ⃗ k are unit vectors. The problem can be intuitively treated as solving n linear systems simultaneously, which will needs O ( n log N ) complexity by the famous HHL algorithm. We demonstrate that in our algorithm the scale of complexity is O ( log n N ) . In the error analysis part, phase estimation is discussed in details.
We propose a divide-and-conquer method for the quantum-classical hybrid algorithm to solve larger problems with small-scale quantum computers.Specifically, we concatenate a variational quantum eigensolver (VQE) with a reduction in the system dimension, where the interactions between divided subsystems are taken as an effective Hamiltonian expanded by the reduced basis.Then the effective Hamiltonian is further solved by the VQE, which we call deep VQE.Deep VQE allows us to apply quantum-classical hybrid algorithms on small-scale quantum computers to large systems with strong intrasubsystem interactions and weak intersubsystem interactions, or strongly correlated spin models on large regular lattices.As proof-of-principle numerical demonstrations, we use the proposed method for quasi-one-dimensional models, including one-dimensionally coupled 12-qubit Heisenberg antiferromagnetic models on kagome lattices as well as two-dimensional Heisenberg antiferromagnetic models on square lattices.The largest problem size of 64 qubits is solved by simulating 20-qubit quantum computers with a reasonably good accuracy approximately a few %.The proposed scheme enables us to handle the problems of > 1000 qubits by concatenating VQEs with a few tens of qubits.While it is unclear how accurate ground-state energy can be obtained for such a large system, our numerical results on a 64-qubit system suggest that deep VQE provides a good approximation (discrepancy within a few percent) and has room for further improvement.Therefore, deep VQE provides us a promising pathway to solve practically important problems on noisy intermediate-scale quantum computers.