2
$\begingroup$

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)

$\endgroup$
3
  • 1
    $\begingroup$ The matrix $M$ is just a projector, $M= |0 \ldots0 \rangle \langle 0 \ldots 0|$. This is equivalent to making a measurement on all qubits. $\endgroup$
    – MonteNero
    Commented Feb 2, 2023 at 22:56
  • $\begingroup$ To expand on MonteNero's answer, as long as there is just a single 1 on the diagonal, $M$ is projector of that corresponding basis state. Eg., a $1$ on $M_{3, 3}$ (1-based) is the projector of $|0010\rangle\langle0010|$. $\endgroup$
    – rhundt
    Commented Feb 3, 2023 at 1:24
  • 1
    $\begingroup$ "Is a diagonal matrix with one non-zero element a measurable observable?" Is the one non-zero element a real number? If so, then yes. $\endgroup$
    – hft
    Commented Feb 3, 2023 at 1:44

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Does Eq. (3) for the standard deviation really make sense in the case of a non-Hermitian $M$? $\endgroup$
    – forky40
    Commented Feb 3, 2023 at 19:47
  • 1
    $\begingroup$ @forky40 Good catch! Thank you! Fixed by using stddev for complex random variable. N.B. this is equivalent to the sqrt of the sum of variances of the real and imaginary parts, but I didn't expand on this since the whole accuracy part is already a bit beyond the scope of the original question. I included it only because if M has high dimension one might worry that they will never obtain a result other than zero. The short accuracy discussion is meant to bring up the right ideas to think about this. $\endgroup$ Commented Feb 3, 2023 at 22:14

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.