Skip to content

Quantum signal processing / quantum singular value transformation

Rough overview (in words)

Quantum signal processing (QSP) and quantum singular value transformation (QSVT) are techniques for applying polynomial transformations to block-encoded operators. These techniques can be used to implement Hamiltonian simulation, given a block-encoding of the Hamiltonian. Both approaches have optimal scaling with \(t\) and \(\epsilon\) for time-independent Hamiltonians.

QSP was initially developed for the \(d\)-sparse access model [1]. Through the introduction of block-encodings and qubitization, it was made applicable in a standard form to Hamiltonians in a Pauli access model, \(d\)-sparse access model, or given as density matrices (where we are given access to a unitary that prepares a purification of the density matrix) [2]. QSVT was later developed as a more general and direct route to the results of QSP [3].

Hamiltonian simulation via QSP / QSVT is less well suited to time-dependent Hamiltonians, as the need to Trotterize the time-dependent evolution breaks the optimal dependence on the parameters.

Rough overview (in math)

Access to the Hamiltonian \(H\) is provided by an \((\alpha, m, 0)\)-block-encoding \(U_H\) (the case of approximate block-encodings can be treated using [3, Lemma 22]) such that

\[\begin{equation} \left(\bra{0}^{\otimes m} \otimes I \right) U_H \left(\ket{0}^{\otimes m} \otimes I \right) = H/\alpha \end{equation}\]

The Hamiltonian has a spectral decomposition of \(\sum_\lambda \lambda \ket{\lambda} \bra{\lambda}\). We seek to use \(U_H\) to implement an operator \(U(t)\) approximating

\[\begin{equation} \nrm{ U(t) - \sum_\lambda e^{i \lambda t} \ket{\lambda} \bra{\lambda}} \leq \epsilon. \end{equation}\]

Qubitization converts \(U_H\) into a more structured unitary \(W\) (which is also a block-encoding of the Hamiltonian). The eigenvalues of \(W\) are \(e^{\pm i \arccos(\lambda / \alpha)}\), directly related to those of \(H\). QSP then enables polynomial transformations to be applied to these eigenvalues, which defines the application of the polynomial to \(W\). This concept can be generalized via QSVT, which effectively unifies the qubitization and QSP step.

In both cases, our goal is to implement a block-encoding of \(U(t) \approx \sum_\lambda e^{i \lambda t} \ket{\lambda} \bra{\lambda}\), which defines Hamiltonian simulation. In QSVT we separately implement polynomials approximating \(\cos(\lambda t)\) and \(i\sin(\lambda t)\), combine them using a linear combination of block-encodings, and boost the success probability using 3-step oblivious amplitude amplification. Further details can be found in [3, 4]. Meanwhile, quantum signal processing implements \(\exp( i t H)\) directly but requires an additional ancilla qubit and controlled access to a Hermitian block-encoding \(U'_H\), which, when implemented via Eq. \(\eqref{eq:genQubitiz}\), uses both controlled \(U_H\) and \(U_H^\dagger\) resulting in a factor of \(\sim 4\) overhead [2]. Altogether these considerations suggest that the QSVT-based approach might have a slightly better complexity, particularly when controlled \(U_H\) is significantly more costly to implement than \(U_H\). If \(U_H\) is already Hermitian then quantum signal processing can have a lower complexity.

Dominant resource cost (gates/qubits)

Using either QSP or QSVT, block-encoding a degree-\(k\) polynomial \(f(H)\) is performed using \(\mathcal{O}\left( k \right)\) calls to the block-encoding \(U_H\) [2, 3]. Hence, the degree of the polynomial approximating the \(e^{iHt}\) determines the complexity of Hamiltonian simulation using these techniques. As noted in [3, Corollary 60], we can rigorously bound the resources for Hamiltonian simulation via QSVT for all values of \(t\) as using

\[\begin{equation} \mathcal{O}\left( \alpha t + \frac{\log(1/\epsilon)}{\log(e+ \log(1/\epsilon)/\alpha t)} \right) \end{equation}\]

calls to the \((\alpha, m, 0)\)-block-encoding \(U_H\). This query complexity is optimal [5, 3], although the block-encoding can hide additional complexities, in practice. In some cases, the dependence on norm parameters can be improved by exploiting details of the simulated system, see [6, 7].

For a Pauli access model the block-encoding is implemented using the linear combination of unitaries primitives PREPARE and SELECT. For a Hamiltonian with \(L\) terms \(\alpha = \nrm{H}_1\), \(m=\mathcal{O}\left( \log(L) \right)\), and two additional qubits are required for QSVT. The overall gate complexity depends on the exact implementation of PREPARE and SELECT, which can often be tailored to the Hamiltonian of interest. In the worst case, PREPARE uses \(\Theta(L)\) gates, and SELECT uses \(\Theta(nL)\) gates (although these can be significantly improved by exploiting structure in the Hamiltonian, see, e.g., [8, 9]). This yields an overall worst case gate complexity of

\[\begin{equation} \mathcal{O}\left( nL \left( \nrm{H}_1 t + \frac{\log(1/\epsilon)}{\log(e+ \log(1/\epsilon)/\nrm{H}_1 t)} \right) \right). \end{equation}\]

For a \(d\)-sparse access model, \(\alpha= d\nrm{H}_{\max}\) where \(\nrm{H}_{\mathrm{max}} = \mathrm{max}_{i,j} \lvert \bra{i}H\ket{j} \rvert\), \(m=\mathcal{O}\left( \log(d) \right)\), and two additional qubits are required for QSVT. The overall gate complexity depends on the cost of sparse access to elements of \(H\). Assuming a constant gate complexity circuit for sparse access, the overall gate complexity is

\[\begin{equation} \mathcal{O}\left( d\nrm{H}_{\max} t + \frac{\log(1/\epsilon)}{\log(e+ \log(1/\epsilon)/d\nrm{H}_{\max} t)} \right). \end{equation}\]

The density matrix access model seeks to perform time evolution under \(e^{i\rho t}\), given access to either multiple copies of \(\rho\) or a unitary \(U_\rho\) that prepares a purification of \(\rho\). Given \(U_\rho\), we can prepare a block-encoding of \(\rho\) [2] (see section on block-encodings for details) with \(\alpha=1\). If the gate complexity of \(U_\rho\) is \(C(U_\rho)\) then the overall gate complexity is

\[\begin{equation} \mathcal{O}\left( C(U_\rho) \left(t + \frac{\log(1/\epsilon)}{\log(e+ \log(1/\epsilon)/ t)} \right) \right). \end{equation}\]

Caveats

The method was found to perform competitively with Trotterization (and better than Taylor series) in concrete resource estimates for simulating spin chain Hamiltonians [10]. While that work had difficulty calculating the QSP phase factors, this issue has since been addressed with the development of classical algorithms for finding the phase factors [11, 12, 13, 14]. Nevertheless, this contributes a classical preprocessing cost to the algorithm.

It is currently unclear how to perform optimal time-dependent Hamiltonian simulation with these methods, without resorting to Trotterization. Some initial investigations have shown promising results using clock Hamiltonian constructions [15] or for time-periodic Hamiltonians [16, 17].

Example use cases

Further reading

  • Pedagogical overviews [4, 19].
  • Comparison of several Hamiltonian simulation algorithms [10].

Bibliography

  1. Guang Hao Low and Isaac L. Chuang. Optimal hamiltonian simulation by quantum signal processing. Physical Review Letters, 118(1):010501, 2017. arXiv: https://arxiv.org/abs/1606.02685. doi:10.1103/PhysRevLett.118.010501.

  2. Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by qubitization. Quantum, 3:163, 2019. arXiv: https://arxiv.org/abs/1610.06546. doi:10.22331/q-2019-07-12-163.

  3. András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics [full version]. arXiv: https://arxiv.org/abs/1806.01838, 2018.

  4. John M. Martyn, Zane M. Rossi, Andrew K. Tan, and Isaac L. Chuang. Grand unification of quantum algorithms. Physical Review X, 2(4):040203, 2021. arXiv: https://arxiv.org/abs/2105.02859. doi:10.1103/PRXQuantum.2.040203.

  5. Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders. Efficient quantum algorithms for simulating sparse hamiltonians. Communications in Mathematical Physics, 270(2):359–371, 2007. arXiv: https://arxiv.org/abs/quant-ph/0508139. doi:10.1007/s00220-006-0150-x.

  6. Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by uniform spectral amplification. arXiv: https://arxiv.org/abs/1707.05391, 2017.

  7. Guang Hao Low. Hamiltonian simulation with nearly optimal dependence on spectral norm. In Proceedings of the 51st ACM Symposium on the Theory of Computing (STOC), 491–502. 2019. arXiv: https://arxiv.org/abs/1807.03967. doi:10.1145/3313276.3316386.

  8. Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven. Encoding electronic spectra in quantum circuits with linear t complexity. Physical Review X, 8(4):041015, 2018. arXiv: https://arxiv.org/abs/1805.03662. doi:10.1103/PhysRevX.8.041015.

  9. Kianna Wan. Exponentially faster implementations of select(h) for fermionic hamiltonians. Quantum, 2021. arXiv: https://arxiv.org/abs/2004.04170. doi:10.22331/q-2021-01-12-380.

  10. Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su. Toward the first quantum simulation with quantum speedup. Proceedings of the National Academy of Sciences, 115(38):9456–9461, 2018. arXiv: https://arxiv.org/abs/1711.10980. doi:10.1073/pnas.1801723115.

  11. András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st ACM Symposium on the Theory of Computing (STOC), 193–204. 2019. arXiv: https://arxiv.org/abs/1806.01838. doi:10.1145/3313276.3316366.

  12. Jeongwan Haah. Product decomposition of periodic functions in quantum signal processing. Quantum, 3:190, 2019. arXiv: https://arxiv.org/abs/1806.10236. doi:10.22331/q-2019-10-07-190.

  13. Yulong Dong, Xiang Meng, K. Birgitta Whaley, and Lin Lin. Efficient phase-factor evaluation in quantum signal processing. Physical Review A, 103:042419, 2021. arXiv: https://arxiv.org/abs/2002.11649. doi:10.1103/PhysRevA.103.042419.

  14. Rui Chao, Dawei Ding, András Gilyén, Cupjin Huang, and Márió Szegedy. Finding angles for quantum signal processing with machine precision. arXiv: https://arxiv.org/abs/2003.02831, 2020.

  15. Jacob Watkins, Nathan Wiebe, Alessandro Roggero, and Dean Lee. Time-dependent hamiltonian simulation using discrete clock constructions. arXiv: https://arxiv.org/abs/2203.11353, 2022.

  16. Kaoru Mizuta and Keisuke Fujii. Optimal hamiltonian simulation for time-periodic systems. Quantum, 7:962, 3 2023. arXiv: https://arxiv.org/abs/2209.05048. URL: https://doi.org/10.22331/q-2023-03-28-962, doi:10.22331/q-2023-03-28-962.

  17. Kaoru Mizuta. Optimal/nearly-optimal simulation of multi-periodic time-dependent hamiltonians. arXiv: https://arxiv.org/abs/2301.06232, 2023.

  18. I. Novikau, E. A. Startsev, and I. Y. Dodin. Quantum signal processing for simulating cold plasma waves. Physical Review A, 105:062444, 6 2022. arXiv: https://arxiv.org/abs/2112.06086. URL: https://link.aps.org/doi/10.1103/PhysRevA.105.062444, doi:10.1103/PhysRevA.105.062444.

  19. Lin Lin. Lecture notes on quantum algorithms for scientific computation. arXiv: https://arxiv.org/abs/2201.08309, 2022.