Variational quantum algorithms have found success in the noisy intermediate-scale quantum era owing to their hybrid quantum-classical approach which mitigate the problems of noise in quantum computers. In our paper, we introduce the dynamic ansatz in the variational quantum linear solver for a system of linear algebraic equations. In this improved algorithm, the number of layers in the hardware efficient ansatz circuit is evolved, starting from a small and gradually increasing until convergence of the solution is reached. We demonstrate the algorithm advantage in comparison to the standard static ansatz by utilizing fewer quantum resources and with a smaller quantum depth on average in the presence and absence of quantum noise and in cases when the number of qubits or condition number of the system matrices are increased. The numbers of iterations and layers can be altered by a switching parameter. The performance of the algorithm in using quantum resources is quantified by a newly defined metric.
Variational quantum algorithms have found success in the noisy intermediate-scale quantum era owing to their hybrid quantum-classical approach which mitigate the problems of noise in quantum computers. In our paper, we introduce the dynamic ansatz in the variational quantum linear solver for a system of linear algebraic equations. In this improved algorithm, the number of layers in the hardware efficient ansatz circuit is evolved, starting from a small and gradually increasing until convergence of the solution is reached. We demonstrate the algorithm advantage in comparison to the standard static ansatz by utilizing fewer quantum resources and with a smaller quantum depth on average in the presence and absence of quantum noise and in cases when the number of qubits or condition number of the system matrices are increased. The numbers of iterations and layers can be altered by a switching parameter. The performance of the algorithm in using quantum resources is quantified by a newly defined metric.
Combinatorial optimization is a promising application for near-term quantum computers, however, identifying performant algorithms suited to noisy quantum hardware remains as an important goal to potentially realizing quantum computational advantages. To address this we present a variational quantum algorithm for solving combinatorial optimization problems with linear-depth circuits. Our algorithm uses an ansatz composed of Hamiltonian generators designed to control each term in the target combinatorial function, along with parameter updates following a modified version of quantum imaginary time evolution. We evaluate this ansatz in numerical simulations that target solutions to the MAXCUT problem. The state evolution is shown to closely mimic imaginary time evolution, and its optimal-solution convergence is further improved using adaptive transformations of the classical Hamiltonian spectrum. With these innovations, the algorithm consistently converges to optimal solutions, with interesting highly-entangled dynamics along the way. We further demonstrate the success of this approach by performing optimization of a truncated version of our ansatz with up to 32 qubits in a trapped-ion quantum computer, using measurements from the quantum computer to train the ansatz and prepare optimal solutions with high fidelity in the majority of cases we consider. The success of these large-scale quantum circuit optimizations, in the presence of realistic hardware constraints and without error mitigation, mark significant progress on the path towards solving combinatorial problems using quantum computers. We conclude our performant and resource-minimal approach is a promising candidate for potential quantum computational advantages.
Previously proposed quantum algorithms for solving linear systems of equations cannot be implemented in the near term due to the required circuit depth. Here, we propose a hybrid quantum-classical algorithm, called Variational Quantum Linear Solver (VQLS), for solving linear systems on near-term quantum computers. VQLS seeks to variationally prepare | x ⟩ such that A | x ⟩ ∝ | b ⟩ . We derive an operationally meaningful termination condition for VQLS that allows one to guarantee that a desired solution precision ϵ is achieved. Specifically, we prove that C ⩾ ϵ 2 / κ 2 , where C is the VQLS cost function and κ is the condition number of A . We present efficient quantum circuits to estimate C , while providing evidence for the classical hardness of its estimation. Using Rigetti's quantum computer, we successfully implement VQLS up to a problem size of 1024 × 1024 . Finally, we numerically solve non-trivial problems of size up to 2 50 × 2 50 . For the specific examples that we consider, we heuristically find that the time complexity of VQLS scales efficiently in ϵ , κ , and the system size N .
Finding the solution to linear systems is at the heart of many applications in science and technology. Over the years, a number of algorithms have been proposed to solve this problem on a digital quantum device, yet most of these are too demanding to be applied to the current noisy hardware. In this work, an original algorithmic procedure to solve the quantum linear system problem (QLSP) is presented, which combines ideas from variational quantum algorithms and the framework of classical shadows. The result is the shadow quantum linear solver (SQLS), a quantum algorithm solving the QLSP while avoiding the need for large controlled unitaries and requiring a number of qubits that is logarithmic in the system size. In particular, our heuristics show an exponential advantage of the SQLS in circuit execution per cost function evaluation when compared with other notorious variational approaches to solving linear systems of equations. We test the convergence of the SQLS on a number of linear systems, and the results highlight how the theoretical bounds on the number of resources used by the SQLS are conservative. Finally, we apply this algorithm to a physical problem of practical relevance by leveraging decomposition theorems from linear algebra to solve the discretized Laplace equation in a two-dimensional grid.
Abstract Variational quantum algorithms are promising methods with the greatest potential to achieve quantum advantage, widely employed in the era of noisy intermediate-scale quantum computing. This study presents an advanced variational hybrid algorithm (EVQLSE) that leverages both quantum and classical computing paradigms to address the solution of linear equation systems. Initially, an innovative loss function is proposed, drawing inspiration from the similarity measure between two quantum states. This function exhibits a substantial improvement in computational complexity when benchmarked against the variational quantum linear solver. Subsequently, a specialized parameterized quantum circuit structure is presented for small-scale linear systems, which exhibits powerful expressive capabilities. Through rigorous numerical analysis, the expressiveness of this circuit structure is quantitatively assessed using a variational quantum regression algorithm, and it obtained the best score compared to the others. Moreover, the expansion in system size is accompanied by an increase in the number of parameters, placing considerable strain on the training process for the algorithm. To address this challenge, an optimization strategy known as quantum parameter sharing is introduced, which proficiently minimizes parameter volume while adhering to exacting precision standards. Finally, EVQLSE is successfully implemented on a quantum computing platform provided by IBM for the resolution of large-scale problems characterized by a dimensionality of 220.
Solving linear systems of equations is central to many engineering and
scientific fields. Several quantum algorithms have been proposed for linear
systems, where the goal is to prepare ∣x⟩ such that A∣x⟩∝∣b⟩. While these algorithms are promising, the time horizon for their
implementation is long due to the required quantum circuit depth. In this work,
we propose a variational hybrid quantum-classical algorithm for solving linear
systems, with the aim of reducing the circuit depth and doing much of the
computation classically. We propose a cost function based on the overlap
between ∣b⟩ and A∣x⟩, and we derive an operational meaning for
this cost in terms of the solution precision ϵ. We also introduce a
quantum circuit to estimate this cost, while showing that this cost cannot be
efficiently estimated classically. Using Rigetti's quantum computer, we
successfully implement our algorithm up to a problem size of 32×32.
Furthermore, we numerically find that the complexity of our algorithm scales
efficiently in both 1/ϵ and κ, with κ the condition
number of A. Our algorithm provides a heuristic for quantum linear systems
that could make this application more near term.
Quantum computing is an emerging topic in engineering that promises to enhance supercomputing using fundamental physics. In the near term, the best candidate algorithms for achieving this advantage are variational quantum algorithms (VQAs). We design and numerically evaluate a novel ansatz for VQAs, focusing in particular on the variational quantum eigen-solver (VQE). As our ansatz is inspired by classical multigrid hierarchy methods, we call it “multigrid” ansatz. The multigrid ansatz creates a parameterized quantum circuit for a quantum problem onnqubits by successively building and optimizing circuits for smaller qubit countsj<n, reusing optimized parameter values as initial solutions to next level hierarchy atj+1. We show through numerical simulation that the multigrid ansatz outperforms the standard hardware-efficient ansatz in terms of solution quality for the Laplacian eigensolver as well as for a large class of combinatorial optimization problems with specific examples for MaxCut and Maximum k-Satisfiability. Our studies establish the multi-grid ansatz as a viable method for improving the performance of variational quantum eigensolvers.