2

The HHL algorithm prepares the output state $|x\rangle$. However, we cannot efficiently measure the state directly to get its components. Instead, we can construct an operator $M$ to find $\langle x|M|x\rangle$ (the expectation value of $M$ on $|x\rangle$). There's been some discussion on this site on what information can be extracted from $|x\rangle$ and how the operator $M$ can be constructed so that $\langle x|M|x\rangle$ yields the desired quantity and the operator is measurable.

See

My question is this:

Can a diagonal matrix $M$ with only one non-zero element (e.g. $1$) be implemented as a measurable observable?

One example of such a matrix would be $$M=\begin{pmatrix}1 & 0 & \cdots & 0 \\ 0 & 0 & \cdots & 0 \\ \vdots & \vdots & \ddots &\vdots \\ 0 & 0 & \cdots & 0 \\ \end{pmatrix}$$

If $M$ is usable as an observable, could we not use that to extract individual components of $|x\rangle$? (Obviously extracting all or linearly many components would destroy the computational speedup of HHL)

Adam Zalcman
  • 25,260
  • 3
  • 40
  • 95
Dominik Vereno
  • 63
  • 3

1 Answers1

5

TL;DR: We can implement a simple experimental procedure to estimate $\langle x|M|x\rangle$ for every normal complex matrix $M$.

Background

A normal matrix $M$ can be written as $$ M=\sum_k\lambda_k |x_k\rangle\langle x_k|\tag1 $$ where the complex numbers $\lambda_k\in\mathbb{C}$ are the eigenvalues and $|x_k\rangle$ form an orthonormal basis of eigenvectors. Using $(1)$, we can write $$ \langle x|M|x\rangle=\sum_k\lambda_k|\langle x|x_k\rangle|^2=\sum_k\lambda_k p(k|x)\tag2 $$ where $p(k|x)=|\langle x|x_k\rangle|^2$ is the probability of obtaining the $k$th measurement outcome in a measurement in the basis $|x_k\rangle$. The key observation is that the right hand side of $(2)$ is the average of the eigenvalues $\lambda_k$ in the probability distribution $p(k|x)$.

Algorithm

Thus, we can estimate $\langle x|M|x\rangle$ to arbitrary accuracy using the following algorithm:

  1. Initialize $\lambda=0$.
  2. Repeat $N$ times the steps $3$ to $5$.
  3. Prepare $|x\rangle$.
  4. Measure in the basis $|x_k\rangle$.
  5. Using the outcome $k$ from the step $4$ select $\lambda_k$ and add it into $\lambda$.
  6. Return $\frac{\lambda}{N}$.

Accuracy

The standard deviation of the value returned by the above algorithm is $$ \sigma(M)=\sqrt{\frac{\langle x|M\overline{M}|x\rangle-|\langle x|M|x\rangle|^2}{N}}.\tag3 $$ In particular, if $M=|y\rangle\langle y|$ and $p=|\langle x|y\rangle|^2$, then $\sigma(M)=\sqrt{\frac{p(1-p)}{N}}$.

Note on non-Hermitian $M$

By convention, only Hermitian matrices are used to represent observables. This reflects the fact that people tend to label measurement outcomes using real numbers. However, this is a choice. We could use the imaginary axis to label measurement outcomes and then the anti-Hermitian matrices$^1$ would be our observables. More generally, if we choose to use complex numbers to label measurement outcomes then any normal matrix is a valid observable.

In any case, the quantity $\langle x|M|x\rangle$ is clearly accessible experimentally via the procedure above for any complex diagonal matrix $M$.

$^1$ In the theory of Lie groups and Lie algebras unitary operators are sometimes written as $e^A$ where $A\in\mathfrak{u}(n)$ is anti-Hermitian. However, in quantum mechanics unitary evolution under Hamiltonian $H$ is usually written as $e^{-iHt}$. Thus, in physics we need to add an explicit imaginary unit, because we insist that energy should be a real, rather than an imaginary, number.

Adam Zalcman
  • 25,260
  • 3
  • 40
  • 95