The book I am reading is suggesting the following:

Suppose I have two vectors $v, w$ and $P(n)$ matrices $U_1, U_2, \ldots, U_{P(n)}$. Then performing an inner product of $v$ with $U_1U_2\ldots U_{P(n)} w$ is more complex in terms of space complexity than some trick which they use in order to create an expression of the form $$\sum_{j=1}^{P(n)} \langle v, U_1x_j\rangle \langle v, U_2x_j\rangle, \ldots, \langle v, U_{P(n)}x_j\rangle$$ for some vectors $x_j$.

Basically they say that $\langle v, U_1U_2\ldots U_{P(n)}w\rangle$ is not linear in space, as opposed to the same expression written this way by adding many $x$ vectors which render the expression equal but written differently as above.

How come the latter is better than the former? In both of them you have a vector which has to be stored in memory. They claim that in the latter you just add to the running total. But inside the inner product you still have to store a vector just the size of the first method. What's the difference?

  • $\begingroup$ Welcome to Computer Science! I suggest editing your question to show the exact expression or formula they use. I recommend you use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. I can't tell what VUX or VU1X refers to. $\endgroup$ – D.W. Mar 3 '19 at 19:06
  • $\begingroup$ I was also unable to decipher your notation. Perhaps some details are missing. $\endgroup$ – Yuval Filmus Mar 3 '19 at 19:12
  • $\begingroup$ What else do you want to know? Basically the question is why is this ⟨V,U1U2…UP(n)w⟩ not linear in space??? $\endgroup$ – bilanush Mar 3 '19 at 20:10
  • $\begingroup$ Can you provide a full citation for the book you are reading? (Book title, authors, the chapter/section and page numbers you are reading.) Can you provide any additional context? It's hard for me to tell what might be going on based on just the information here, so I'm hoping that maybe providing additional context might help us guess what's going on. $\endgroup$ – D.W. Mar 4 '19 at 21:55
  • $\begingroup$ It will require some syntax knowledge of quantum mechanics. But sure, it's in QCQI by Chuang and Nielsen. Page 202 . $\endgroup$ – bilanush Mar 4 '19 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.