5
$\begingroup$

I was listening to an advanced lecture about quantum computing, when the professor introduced a chapter called "Qubitization and the quantum singular value transform", but never really cared to define what qubitization means. After some research I came across the term in it's first usage by Chuang in 2016 I believe in this paper https://arxiv.org/pdf/1610.06546.pdf. However, I can't seem to see where the authors actually give a proper definition in the above paper. Any help on what is commonly referred to as qubitization is much apprectiated.

$\endgroup$

2 Answers 2

6
$\begingroup$

It just means that you block encode the matrix $A$ into a larger unitary matrix, $U_A$. That is,

$$ U_A = \begin{pmatrix} A & *\\ * & *\end{pmatrix}$$

where $*$ indicate arbitrary matrix elements. Note that each unitary matrix is already a trivial block encoding of itself. Once this is done, you can implement $$ U = \begin{pmatrix} P(A) & *\\ * & *\end{pmatrix}$$ where $P(A)$ is a polynomial (usually Chebyshev) approximation of some function you want to implement. For instance, if you want to find $A^{-1}$ so that you can solve the linear system of equations $Ax =b$ then $P(A)$ is the polynomial (usually Chebyshev)approximation of $f(x) = 1/x$. This implementation can be done through a quantum circuit of the form enter image description here

The key point is that the Quantum Signal Processing theorem tells us that the above sequence can approximate rich space of functions by modifying the sequence $\{\varphi_i \}_{i=0}^d$. Furthermore, this can be done efficiently as well as noted in the paper "Efficient phase-factor evaluation in quantum signal processing" by Dong et al.

$\endgroup$
3
  • $\begingroup$ Thank you for your answer - in the context of my lecture, this does make a lot of sense now! One further question: So as far as I can see there's no restrictions on the operator A we want to block encode and what do you mean by "information of your system"? Also the $\phi$ should be $\varphi$ and start from the index 0 as far as I am concerned. $\endgroup$
    – Lagrange
    Commented Jul 17, 2023 at 10:28
  • $\begingroup$ @Lagrange What I meant to say is that $A$ represents the problem you are trying to solve. For instance, it could be the electronic Hamiltonian of a chemical system. Sorry if I have worded it confusingly. And yes, φ ranging from $0$ to $d$ is correct. $\endgroup$
    – KAJ226
    Commented Jul 17, 2023 at 13:32
  • 2
    $\begingroup$ The answer is not correct as it addresses the question "what block encoding is". $\endgroup$
    – mavzolej
    Commented Dec 23, 2023 at 2:40
4
$\begingroup$

Qubitization is a way to assemble a very specific block encoding $W_A$ (also known as Szegedy quantum walk operator). It was introduced in Chapter 4 of the original paper. A friendly introduction can be found in Section II of the Linear T complexity paper or in Section II.B of this lattice paper. (More precisely, Fig 1 in the Linear T complexity paper provides an extremely efficient implementation of $W_A$ based on the same ingredients, PREPARE and SELECT, which one would use to construct $U_A$ using the Linear Combination of Unitaries; Fig 3 in the lattice paper explains how $W_A$ can be made out of an arbitrary $U_A$.)

BASICS

$U_A$ is a block encoding of $A$ if $$ A/\alpha = ({\langle 0|}_a\otimes 1_s) U_A (|0\rangle_a\otimes 1_s) \,, $$ where $|0\rangle_a$ is the ancillary qubit register and $1_s$ is the identity operator on the system register. From now on assume for simplicity that $\alpha=1$.

This imples that $$ U_A |0\rangle_a|\psi\rangle_s = |0\rangle_a (A |\psi\rangle_s) - |\bot\rangle_{as}\,, $$ where the state $|\bot\rangle_{as}$ is "perpendicular" to $|0\rangle_a$ in the sense that $({\langle 0|}_a\otimes 1_s)|\bot\rangle_{as}=0$, and the minus sign is conventional.

Now, let's consider a particular case of the equation above and choose $|\psi\rangle_s$ to be $|\lambda\rangle_s$, the eigenvector of $A$:

$$ U_A |0\rangle_a|\lambda\rangle_s = \lambda\,|0\rangle_a|\lambda\rangle_s - \sqrt{1-\lambda^2} |\bot^\lambda\rangle_{as} \,, $$ where the superscript in $|\bot^\lambda\rangle_{as}$ indicates that the vector $|\bot\rangle_{as}$ corresponds to the case $|\psi\rangle_s=|\lambda\rangle_s$.

Note that if one further applies $U_A$ to any of the two equations above, the RHS will generally contain more than two terms, since it is not obvious how $U_A$ acts on the perpendicular vector. (It would be more fruitful to act on these equations with $U_A^\dagger$, as described in Section 7.4 here, and this would eventually lead to the construction described below.)

QUBITIZATION

As was stated above, Qubitization allows one, starting from $U_A$, to obtain another block encoding $W_A$, possessing the following extra property: $$ \begin{aligned} W_A |0\rangle_a|\lambda\rangle_s &= \lambda\,|0\rangle_a|\lambda\rangle_s - \sqrt{1-\lambda^2} |\bot^\lambda\rangle_{as} \\&= \left( \lambda\, |0\rangle_a - \sqrt{1-\lambda^2} |\bot^\lambda\rangle_a \right)|\lambda\rangle_s \,, \end{aligned} $$ where $$ |\bot^\lambda\rangle_{as} = |\bot^\lambda\rangle_{a}|0\rangle_{s} = (1_a\otimes\langle\lambda|_s)\frac{\lambda 1_{as} - W_A }{\sqrt{1-\lambda^2}}|0\rangle_a|\lambda\rangle_s\,. $$

Here for simplicity I keep the convention that the ancillary qubit is in the all-zero state. In fact, starting from $U_A$ which assumes all zero ancillas, leads to $W_A$ which has one ancilla in the $|+\rangle$ state. Also here I am overall not very careful about the dimension of ancillary register.

The significance of this construction is given by equations above: while consecutive applications of $U_A$ generally mess up the structure of the state it acts upon, the consecutive action of $W_A$ is simple. When acting on the state $|0\rangle_a|\lambda\rangle_s$, the block encoding $W_A$ only induces a 2D rotation in the ancillary space but does not affect $|\lambda\rangle_s$. This implies that for a fixed $\lambda$ the action of $W_A$ is given by a $2\times2$ matrix acting on $\{|0\rangle_a,|\bot^\lambda\rangle_{a}\}$: $$ \left(1_a \otimes \langle\lambda'|_s\right) W_A \left(1_a \otimes |\lambda\rangle_s\right) = W_A^{(\lambda)} \delta_{\lambda \lambda'}\,, $$ where $$ W_A = \begin{pmatrix} \lambda & - \sqrt{1-\lambda^2} \\ \sqrt{1-\lambda^2} & \lambda \end{pmatrix}\,. $$

Finally, the action of $W_A$ on arbitrary state of the form $|0\rangle_a|\psi\rangle_s$ is given by a block-diagonal matrix, with blocks of size $2\times2$, each corresponding to different eigenvalues $\lambda$.

ADDITIONAL DISCLAIMER

In the quantum simulation literature / community, Qubitization is, quite confusingly, also used for two other things:

  • Simulating time evolution via Quantum Signal Processing, with the walk operator being constructed as discussed above. (The confusion arose from the title of the original paper.)

  • More generally, any technique for simulating time evolution which relies on the usage of block encoding. For example, someone may easily say that "simulating time evolution using Truncated Taylor / Dyson Series is an example of Qubitization", despite that these algorithms neither use the walk operator nor rely on the concept of Quantum Signal Processing.

$\endgroup$
1
  • $\begingroup$ This is the more correct answer. Qubitization is a consequence of Jordan's lemma: mathoverflow.net/questions/328574/…. The surprising bit (to me anyways) is that these two-dimensional invariant subspaces correspond exactly to the eigensystem of the block encoded matrix. $\endgroup$
    – Cuhrazatee
    Commented Apr 24 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.