Quantum Advantages and End-to-end Complexity

By Lin Lin

Rapid advancements in quantum computing offer unparalleled opportunities for the scientific computing community. However, it is quite difficult to fully harness the potential of quantum computers and outperform classical computers in scientific computing. It may be tempting to think that \(n\) quantum bits (qubits) can encode \(2^n\) complex amplitudes—which would suggest exponential quantum speedups—but the reality is more subtle. Every quantum algorithm must interact with classical processing systems, which means that we need to thoughtfully consider input-output models and the specific requirements of quantum algorithms when evaluating quantum complexities. Due to the inherent constraints of quantum devices, we can only achieve significant quantum advantages for problems that have a limited amount of input and output data.

Let us divide the quantum cost into three main categories: input, output, and running costs. A quantum algorithm typically begins with a standard state such as \(|0^n\rangle\); a unitary matrix then transforms this state to prepare the input state. The input cost is the quantum gate complexity that is required to implement this unitary matrix, and the output cost pertains to the quantum measurement process — which is generally performed on one or more qubits at the end of the algorithm. The number of necessary repetitions to carry out the quantum algorithm determines the output cost. Finally, the running cost refers to the expense that is incurred by executing the quantum algorithm a single time (excluding the cost of preparing the input state). In order to conduct a comprehensive end-to-end analysis of quantum advantage, we must consider all three of these costs. We also have to compare the quantum algorithm’s performance with that of the best available classical algorithms. A recent survey systematically investigated this end-to-end complexity for a wide range of quantum applications [5].

Shor’s algorithm serves as a great example of end-to-end quantum advantage because it effectively tackles the prime factorization problem, which challenges classical computers. This algorithm excels at end-to-end complexity in multiple ways: (i) It has minimal input and output costs since it only involves integers; (ii) it maintains a running cost that is polynomial in relation to the integer’s bit length; and (iii) it significantly surpasses the best classical algorithm for the task, which has a superpolynomial cost in the number of bits.

Hamiltonian simulation—which finds numerous applications in quantum physics and chemistry—is another method that could achieve a quantum advantage. During this process, an initial state \(|\psi_0\rangle\) evolves over time \(t\) to \(|\psi_t\rangle =e^{-iHt} |\psi_0\rangle\). For a system with \(n\) qubits, the size of the Hamiltonian matrix \(H\) is \(2^n\) but the amount of information in \(H\) is typically only polynomial in \(n\). We begin with simple initial states that are prepared at a polynomial cost in \(n\); the best algorithm for simulating quantum dynamics up to time \(t\) with precision \(\epsilon\) only queries the unitary encoding of \(H\) (known as a block encoding) \(\mathcal{O}(\|H\|_2t+\log(1/\epsilon))\) times [7, 10]. The output emphasizes accurate approximations of observables that are associated with \(|\psi_t\rangle\)—i.e., \(\langle\psi_t|O|\psi_t\rangle\)—rather than reconstructions of all of the information in \(|\psi_t\rangle\). The cost of measuring these observables is again polynomial in \(n\) and \(1/\epsilon\). Given these parameters, classical algorithms cannot reliably and accurately compute such dynamical properties over an extended duration \(t\) at a polynomial cost in \(n\). This shortcoming sets a strong foundation for the potential of quantum speedups during the simulation of quantum dynamics.

Does quantum computing demonstrate a clear, end-to-end advantage in other domains besides prime factorization and quantum dynamics simulation? While many applications still lack a solid foundational basis, rapid progress is certainly occurring across various areas.

Consider a seemingly simple variation of the simulation of quantum dynamics, where \(iH\) is replaced with a general matrix \(A\) that acts on \(n\) qubits. Such problems appear when simulating certain open quantum systems. The goal is to simulate \(|\psi_t\rangle=e^{-At}|\psi_0\rangle\) and subsequently measure an observable \(\langle\psi_t|O|\psi_t\rangle\). We can always decompose a general matrix \(A\) (through a Cartesian decomposition) as \(A=L+iH\), where \(L=(A+A^{\dagger})/2\), \(H=(A-A^{\dagger})/(2i)\), and \(A^{\dagger}\) represents the Hermitian conjugate of \(A\). Both \(L\) and \(H\) are Hermitian matrices. If \(L\) is positive semidefinite, the matrix 2-norm satisfies \(\|e^{-At}\|_2\le 1\) and the norm of the final state satisfies \(\| |\psi_t\rangle\|_2\le 1\). The input can still be a simple state that is prepared at a polynomial cost in \(n\). When \(\|L\|_2\) is small, the dynamics only differ slightly from the Hamiltonian simulation problem, thus suggesting that the general task of estimating the observable \(\langle \psi_t|O|\psi_t\rangle\) could be hard for classical computers. But if the norm \(\| |\psi_t\rangle\|_2\) decreases rapidly with respect to \(t\), estimating \(\langle \psi_t|O|\psi_t\rangle\) with a multiplicative accuracy of \(\epsilon\) requires an increased number of repetitions — thereby raising the output cost. To establish a quantum advantage over this non-Hermitian simulation problem, we must find a duration \(t\) that is sufficiently demanding for classical computers yet feasible for quantum computers. The lack of current knowledge about the difficulty of practically relevant non-Hermitian Hamiltonians calls for further research in this area.

We have discussed input cost, output cost, and the potential difficulties that classical solvers face. The remaining aspect of end-to-end analysis is the running cost — specifically, the simulation \(e^{-At}\) on a quantum computer. This task is actually quite challenging. One significant advancement in quantum algorithms from the past decade is the development of the quantum singular value transformation (QSVT) [7]. Consider the singular value decomposition of \(A=U\Sigma W^{\dagger}\). Since \(U\) and \(W\) are unitary matrices, implementing a singular value transformation like \(U f(\Sigma) W^{\dagger}\) mainly requires that we address the non-unitarity of \(f(\Sigma)\). This notion is a key innovation in both QSVT and quantum signal processing [10]. When \(A=iH\), the singular value decomposition directly relates to the eigenvalue decomposition \(A=V D V^{\dagger}\) in which \(V\) is also unitary, thus allowing QSVT to perform the Hamiltonian simulation \(e^{-iHt}\). But for a more general \(A\), the eigenvalue decomposition becomes \(A=VDV^{-1}\) and \(V\) is simply an invertible matrix. Because the simulation task \(e^{-At}=V e^{-Dt} V^{-1}\) is intrinsically an eigenvalue decomposition problem, techniques such as QSVT are not applicable.

Given this restriction, how do we prepare the state \(|\psi_t\rangle=e^{-At} |\psi_0\rangle\) on a quantum computer? The leading approach is somewhat complex and perhaps counterintuitive. It begins by treating the problem like an ordinary differential equation (ODE): \(\frac{\text{d} |\psi(s)\rangle}{\text{d}s}=-A|\psi(s)\rangle\), \(\psi(0)=|\psi_0\rangle\) on \(0\le s \le t\). We then discretize this ODE over time and convert it into a large linear system of equations. We solve the resulting linear system with a quantum linear system solver, such as the renowned Harrow-Hassidim-Lloyd algorithm [8] or a more recent near-optimal solver [3, 4, 9]. The ODE itself is solvable via a traditional time-marching strategy, similar to the type that is employed in standard numerical ODE solvers. Although direct implementation leads to an excessively high output cost due to diminishing success probability, we developed a time-marching strategy that can partially mitigate this issue [6].

One timely advancement was a significant simplification of the simulation of non-unitary quantum dynamics [2]. If \(L\) is positive semidefinite, then

\[e^{-At} = \int_{\mathbb{R}} \frac{1}{\pi(1+k^2)} e^{-i(kL+H)t} \text{d} k. \tag1\]

This formula generalizes the scalar identity \(e^{-|x|}= \int_{\mathbb{R}} \frac{1}{\pi(1+k^2)} e^{-ikx} \text{d} k\) to the matrix setting. Since the matrices \(H,L\) do not commute in general, the proof of \((1)\) is not based on the spectral mapping theorem, which evaluates a matrix function \(f(A)=Vf(D)V^{-1}\) via the eigendecomposition \(A=VDV^{-1}\) [2]. This identity expresses \(e^{-At}\) as a linear combination of Hamiltonian simulation (LCHS) problems of the form \(e^{-i(kL+H)t}\). We can even generalize LCHS to time-dependent \(A(t)\), where the time-ordered propagator \(\mathcal{T} e^{-\int_0^t A(s)\text{d} s}\) replaces \(e^{-At}\) (see Figure 1). The LCHS approach both streamlines the simulation process and achieves optimal query complexity with respect to the initial state preparation, which reduces the input cost. A recent study generalized the LCHS formalism to a family of identities that can express linear non-unitary evolution operators as a linear combination of unitary evolution operators [1]. This work is the first approach to solve linear differential equations with both optimal state preparation cost and near-optimal scaling in matrix queries on all parameters.

To fully harness the potential of quantum computers and achieve a quantum advantage in the coming years, we must develop innovative methods to map various problems into suitable quantum frameworks. We thus welcome both theoretical and empirical discussions of the end-to-end complexities of these solutions. Problems that already exhibit some degree of “quantumness” may have a head start, as classical hardness is easier to argue. At the same time, significant advancements might arise as we apply quantum computers to classical problems — much like the revolution in prime number factoring and cryptography due to Shor’s algorithm in the 1990s.

---

References
[1] An, D., Childs, A.M., & Lin, L. (2023). Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters. Preprint, arXiv:2312.03916.
[2] An, D., Liu, J.-P., & Lin, L. (2023). Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost. Phys. Rev. Lett., 131(15), 150603.
[3] Childs, A.M., Kothari, R., & Somma, R.D. (2017). Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM J. Comput., 46(6), 1920-1950.
[4] Costa, P.C.S., An, D., Sanders, Y.R., Su, Y., Babbush, R., & Berry, D.W. (2022). Optimal scaling quantum linear-systems solver via discrete adiabatic theorem. PRX Quantum, 3(4), 040303.
[5] Dalzell, A.M., McArdle, S., Berta, M., Bienias, P., Chen, C.-F., Gilyén, A., … Brandão, F.G.S.L. (2023). Quantum algorithms: A survey of applications and end-to-end complexities. Preprint, arXiv:2310.03011.
[6] Fang, D., Lin, L., & Tong, Y. (2023). Time-marching based quantum solvers for time-dependent linear differential equations. Quantum, 7, 955.
[7] Gilyén, A., Su, Y., Low, G.H., & Wiebe, N. (2019). Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics. In STOC 2019: Proceedings of the 51st annual ACM SIGACT symposium on theory of computing (pp. 193-204). Phoenix, AZ: Association for Computing Machinery.
[8] Harrow, A.W., Hassidim, A., & Lloyd, S. (2009). Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 103(15), 150502.
[9] Lin, L., & Tong, Y. (2020). Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems. Quantum, 4, 361.
[10] Low, G.H., & Chuang, I.L. (2017). Optimal Hamiltonian simulation by quantum signal processing. Phys. Rev. Lett., 118(1), 010501.

Lin Lin is a professor in the Department of Mathematics at the University of California, Berkeley, and a faculty scientist in the Mathematics Group at Lawrence Berkeley National Laboratory.