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.
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.
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.
Among matrix decomposition methods, the two factorized matrices obtained by Non-negative matrix factorization (NMF) generally yield a more natural and interpretable representations. It is computationally expensive to find the two factorized matrices W and H with a fixed rank r from a non-negative matrix X∈Rn⇥m by minimizing ||X-WH^Τ ||^2. Even if the proposed separability assumption enables polynomial separable NMF (SNMF) algorithms, the computational cost is not affordable for the continuously growing big data. As a powerful technique to deal with high dimensional data, quantum computing possesses quantum advantages for solving machine learning problems, at which the quantum advantages include both an exponential speedup and a more efficient learning ability with respect to the classical counterparts. In this research, based on the divide-and-conquer anchoring (DCA) scheme, quantum DCA (QDCA) is devised to solve SNMF problems. Benefiting from the linear algebraic nature of quantum mechanics and the convenience that statistical distribution is natively available in quantum mechanics with a superset, QDCA achieves an exponential speedup with respect to the classical counterpart. The runtime complexity is O(poly log(n + m)), where n x m is the size of the input matrix. In addition, the proposed QDCA can naturally generalize to solve near-separable NMF under a polynomial logarithmic runtime. Specifically, the time consuming divide step can be completed by a quantum algorithm for linear operations with an exponential speedup. In the conquer step, considering that reading out quantum data into classical forms is exponential expensive and attributing to that anchors can be sampled with a high probability from a probability distribution in the resulting quantum states, the proposed heuristic post-selection method enables QDCA to extract information from quantum states efficiently, which also maintains the quantum speedup after measurements. Under a plausible assumption, QDCA performs efficiently, achieves the exponential speedup, and is beneficial for high dimensional problems. The QDCA is a hybrid quantum and classical algorithm that maintains the quantum speedup after measurements, which provides a new way to develop quantum machine learning algorithms.
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.
One of the challenges of quantum computers in the near- and mid- term is the limited number of qubits we can use for computations. Finding methods that achieve useful quantum improvements under size limitations is thus a key question in the field. In this vein, it was recently shown that a hybrid classical-quantum method can help provide polynomial speed-ups to classical divide-and-conquer algorithms, even when only given access to a quantum computer much smaller than the problem itself. In this work, we study the hybrid divide-and-conquer method in the context of tree search algorithms, and extend it by including quantum backtracking, which allows better results than previous Grover-based methods. Further, we provide general criteria for polynomial speed-ups in the tree search context, and provide a number of examples where polynomial speed ups, using arbitrarily smaller quantum computers, can be obtained. We provide conditions for speedups for the well known algorithm of DPLL, and we prove threshold-free speed-ups for the PPSZ algorithm (the core of the fastest exact Boolean satisfiability solver) for well-behaved classes of formulas. We also provide a simple example where speed-ups can be obtained in an algorithm-independent fashion, under certain well-studied complexity-theoretical assumptions. Finally, we briefly discuss the fundamental limitations of hybrid methods in providing speed-ups for larger problems.
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.