As stated in the question, I have found in several papers (e.g. 1, 2) that in order to perform a quantum walk on a given tree it is necessary to add some nodes to the root $r$, say $r^{'}$ and $r^{"}$. Why are they needed?


  1. Farhi E., "Quantum computation and decision trees". https://arxiv.org/abs/quant-ph/9706062

  2. Ambainis A., "Any AND-OR formula of size N can be evaluated in time $N^{1/2+o(1)}$ on a quantum computer". http://www.ucw.cz/~robert/papers/andor-siamjc.pdf

  • $\begingroup$ In Farhi and Gutman, the tail is added to aid the analysis of the algorithm. The tree with an infinite tail is easy to analyse because most of it is one dimensional. They have mentioned this at the end of page 12. $\endgroup$ – biryani Jun 14 '18 at 14:35
  • $\begingroup$ The problem is that the authors add the semi-infinite line in order to prove the penetrability of the tree, stating that afterwards it is possible to cut such line at a sufficient distance such that the quantum penetrability is not affected. My point is: once I proved that the tree is penetrable, why can't I get rid of the line and implement the algorithm? In Ambainis there is no mention about penetrability, so I assume that it is implied, so what is the purpose of the tail nodes? $\endgroup$ – FSic Jun 14 '18 at 14:55
  • $\begingroup$ @F.Siciliano - Previously you accepted my answer but the answer was deleted. You may still be able to access it with this link if you found it helpful: quantumcomputing.stackexchange.com/a/2362/278 $\endgroup$ – Rob Jul 13 '18 at 19:18
  • 1
    $\begingroup$ @Rob Are you sure? Because I do not recall ever having seen an answer to this question, nor the link shows anything! $\endgroup$ – FSic Jul 14 '18 at 21:17
  • 1
    $\begingroup$ Yes, it was chosen as the preferred answer shortly after posting it. Then gIS made a comment and wanted to chat, then two downvotes, a while later Heather deleted it. The short version is: It uses the Quantum Scattering Algorithm, the nodes are used to physically repair the reflection that would otherwise contaminate the tuning of the quantum mechanical system. ... - Unfortunate that the link doesn't work for you, it would be bad form for me to repost an answer that was deleted with no reason offered. You could ask the other two Mods or a diamond if you want it back. $\endgroup$ – Rob Jul 14 '18 at 21:26

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.