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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 at 21:26

1 Answer 1


Following up on and inspired by the comments from Rob, I sense that there's a bit of a similarity between, on the one hand, the boolean tree evaluation of Farhi and Gutmann (and of Ambainis et al.), and on the other hand, time-domain reflectometry (TDR) which is used to identify cracks/open circuits/short circuits/other faults on electrical cables.

For example, in TDR one may send a wave packet down a copper wire; if the wire is properly terminated, a fault along the wire will cause the wave packet to be reflected while a defect-free line may enable transmission. Similarly in the tree evaluation algorithms, one may partially flatten the tree.

In the tree evaluation algorithms, one may partially flatten the tree. One may also may add extra nodes to the root.

enter image description here

See, e.g., FIGS. 2 and 4 of Farhi and Gutmann, reproduced above.

Much as in TDR, if the tree evaluates to $0$ then a quantum wave packet will reflect back out from whence it came, whereas if the tree evaluates to $1$ then the wave packet will transit through the line.

If you didn't create your line by adding extra nodes to the root/flattening the tree, you would not have a way to send a wave-packet through the tree.


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.