Skip to content

Quantum signal processing

Rough overview (in words)

Quantum signal processing (QSP) [1] describes a method for nonlinear transformations of a signal parameter encoded in a single-qubit gate, using a structured sequence that interleaves the "signal gate" with fixed parametrized "modulation" gates. The technique was originally motivated by the desire to characterize pulse sequences used in nuclear magnetic resonance [1]. Remarkably, it has been shown [1, 2] that there is a rich family of polynomial transformations that are in one-to-one correspondence with appropriate modulation sequences, moreover given such a polynomial one can efficiently compute the corresponding modulation parameters.

Even more remarkably, this analysis holds not just for single-qubit "signal gates" but can be extended for multiqubit operators that act like single-qubit rotations when restricted to appropriate two-dimensional subspaces [3]. This insight enables the implementation of block-encodings of polynomials of Hermitian/normal matrices when used in conjunction with qubitization. The two-step process of qubitization

Rough overview (in math)

We follow the "Wx convention" of QSP [4, 5]. We define the single-qubit signal operator

\[\begin{equation} W(x) := \begin{pmatrix} x & i \sqrt{1-x^2} \\ i \sqrt{1-x^2} & x \end{pmatrix} = e^{i \arccos(x) X} \end{equation}\]

which is a single-qubit \(X\) rotation. We can verify that

\[\begin{align} W(x)^2 & = \begin{pmatrix} 2x^2 - 1 & \cdot \\ \cdot & \cdot \end{pmatrix}, \\ W(x)^3 & = \begin{pmatrix} 4x^3 - 3x & \cdot \\ \cdot & \cdot \end{pmatrix}, \\ & \vdots \\ W(x)^n & = \begin{pmatrix} T_n(x) & \cdot \\ \cdot & \cdot \end{pmatrix}, \\ \end{align}\]

where \(T_n(x)\) is the \(n\)-th Chebyshev polynomial of the first kind, showcasing that even a simple sequence of the signal unitaries can implement a rich family of polynomials of the signal \(x\).

More complex behavior is obtained by interleaving \(W(x)\) with parametrized single-qubit \(Z\) rotations \(e^{i \phi_j Z}\). We define a QSP sequence

\[\begin{equation} U_{\mathrm{QSP}}(\Phi) := e^{i \phi_0 Z} \prod_{j=1}^d W(x) e^{i \phi_j Z}. \end{equation}\]

where \(\Phi\) denotes the vector of angles \((\phi_0,\phi_1,\ldots,\phi_d)\). The QSP sequence implements the following unitary

\[\begin{equation} \label{eq:UQSP(Phi)} U_{\mathrm{QSP}}(\Phi) = \begin{pmatrix} P(x) & i Q(x) \sqrt{1-x^2} \\ i Q^*(x) \sqrt{1-x^2} & P^*(x) \end{pmatrix} \end{equation}\]

where \(P(x), Q(x)\) are complex polynomials obeying a number of constraints (see below), and \(P^*(x)\), \(Q^*(x)\) denote their complex conjugates.

Dominant resource cost (gates/qubits)

A QSP circuit that implements a degree \(d\) polynomial in the signal parameter requires \(d\) uses of \(W(x)\) and \(d+1\) fixed angle \(Z\) rotations. There are efficient classical algorithms to determine the angles for a given target polynomial, either using high-precision arithmetic with \(\sim d\log(d)\) bits of precision [2] (or more [4]—though this can be mitigated using heuristic techniques [6]) or in some regimes using more efficient optimization-based algorithms [7]. Although these procedures are efficient in theory, in practice it may still be nontrivial to find the angles. Nevertheless, researchers reportedly computed angle sequences corresponding to various degree \(d = \mathcal{O}\left( 10^4 \right)\) polynomials.

Caveats

As discussed above, not all polynomials can be implemented by a QSP sequence. Implementable polynomials must obey a number of constraints, which can be somewhat restrictive. For the standard QSP circuit \(U_{\mathrm{QSP}}(\Phi)\) given above, the achievable polynomials pairs \(P(x), Q(x) \in \mathbb{C}\) can be characterized by the following three conditions:

  • \(\mathrm{Deg}(P) \leq d\), \(\mathrm{Deg}(Q) \leq d-1\).
  • \(\mathrm{Parity}(P) = \mathrm{Parity}(d)\), \(\mathrm{Parity}(Q) = \mathrm{Parity}(d-1)\).
  • \(\forall~x \in [-1, 1]: |P(x)|^2 + (1-x^2) |Q(x)|^2 = 1\) (required for Eq. \(\eqref{eq:UQSP(Phi)}\) to be unitary).

This last requirement can be particularly limiting. A useful way to circumvent this for real functions is to encode the polynomial in the matrix element \(\bra{+} U_{\mathrm{QSP}}(\Phi) \ket{+}\) rather than in \(\bra{0} U_{\mathrm{QSP}}(\Phi) \ket{0}\), where \(\ket{+} = \smash{(\ket{0}+\ket{1})/\sqrt{2}}\). This matrix element evaluates to

\[\begin{equation} \bra{+} U_{\mathrm{QSP}}(\Phi) \ket{+} = \operatorname{Re}[P(x)] + i\sqrt{1-\smash{x^2}} \operatorname{Re}[Q(x)]\,. \end{equation}\]

Given a real target polynomial \(f(x)\) with parity equal to \(\mathrm{Parity}(d)\), we can guarantee that the matrix element evaluates to \(f(x)\) by choosing \(\operatorname{Re}[P(x)] = f(x)\) and \(\operatorname{Re}[Q(x)] = 0\). The third condition above then reduces to \(1-f(x)^2 = \lvert \operatorname{Im}[P(x)]\rvert^2 + (1-x^2)\lvert \operatorname{Im}[Q(x)]\rvert^2\). By [4, Lemma 6], there exist choices for \(\operatorname{Im}[P(x)]\) and \(\operatorname{Im}[Q(x)]\) that satisfy this identity as well as the first two conditions above, provided \(|f(x)| \leq 1~\forall~x \in [-1, 1]\). In summary, we may implement any real polynomial \(f(x)\) satisfying the requirements [4, Corollary 10]:

  • \(\mathrm{Deg}(f) = d\).
  • \(\mathrm{Parity}(f) = \mathrm{Parity}(d)\).
  • \(\forall~x \in [-1, 1]: |f(x)| \leq 1\).

There are several related conventions considered in the literature for the explicit form of the single qubit operators used in QSP; a thorough discussion is given in [5, Appendix A]. One common form that links closely to qubitization and QSVT is the reflection convention, which replaces \(W(x)\) by the reflection

\[\begin{equation} \label{eq:QSPR} R(x) = \begin{pmatrix} x & \sqrt{1-x^2} \\ \sqrt{1-x^2} & -x \end{pmatrix} \,, \end{equation}\]

and adjusts the parameters \(\{ \phi_j \}\) accordingly [4].

Example use cases

Further reading

  • A pedagogical discussion of QSP [5].
  • Detailed proofs of the key results of QSP [1, 4].
  • Lecture notes on QSP [9, Sec. 7.6].

Bibliography

  1. Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang. Methodology of resonant equiangular composite quantum gates. Physical Review X, 6(4):041067, 2016. arXiv: https://arxiv.org/abs/1603.03996. doi:10.1103/PhysRevX.6.041067.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. Yulong Dong, Jonathan Gross, and Murphy Yuezhen Niu. Beyond heisenberg limit quantum metrology through quantum signal processing. arXiv: https://arxiv.org/abs/2209.11207, 2022.

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