Talk:Quantum walk

Untitled

I can't believe someone put quantum random walks on wikipedia. First I should say that I'm really impressed that this is even here, but it has some substantial shortcomings.

First of all, this article only mentions discrete quantum walk. Continuous quantum walks are very specific as well.

This discussion of quantum random walks is from a very mathematical perspective. I think it could help to add in more of a physical perspective (e.g. as the discretization of the Schrodinger/Dirac equation http://arxiv.org/abs/quant-ph/9604003) and significantly in terms of their algorithmic applications for quantum computer (see, for instance, http://arxiv.org/abs/quant-ph/0403120).

In particular, the definition of a discrete quantum random walk should be rewritten in the language of quantum mechanics. This means in terms of unitary shift and coin operators acting on Hilbert spaces. This is how it will make sense to physicists.

Also, quantum walks becoming classical walk in the limit of continuous measurement is a way to define them as well.

(I'm an undergrad who spent last summer researching algorithmic applications of quantum walks.)

--shoyer (talk) 05:41, 21 November 2007 (UTC)

The recent (anonymous) rewriting of the summary was mine -- I plan to return and rewrite the remainder of the article as I find the time. shoyer (talk) 23:08, 29 November 2007 (UTC)

Requested move

Quantum random walk → Quantum walk — "Quantum walk" is more commonly used than "Quantum random walk." - Robin (talk) 23:50, 7 July 2009 (UTC)

I have just moved it, doesn't seem to be controversial, article introduces subject as "Quantum walk". Pahari Sahib 17:46, 8 July 2009 (UTC)

Survey

Feel free to state your position on the renaming proposal by beginning a new line in this section with *'''Support''' or *'''Oppose''', then sign your comment with ~~~~. Since polling is not a substitute for discussion, please explain your reasons, taking into account Wikipedia's naming conventions.

Discussion

Any additional comments:

A survey article added by the author of the survey

User:Salvador.venegas, who is the author of the book "Quantum walks for computer scientists" added it as a reference under survey articles recently ([1]). I removed this, due to reasons mentioned below. User:Salvador.venegas then requested explanation for this action on my talk page, thus I am posting my reply here, to get comments from other editors.

First, User:Salvador.venegas, you are right, no one owns a Wikipedia page. Wikipedia works on the basis of establishing consensus. In particular, this means that if there is a difference of opinions, then we should discuss it on this talk page, and come to an agreement. Moreover, since you wish to add something that wasn't there before, you need to justify why it belongs on the wikipedia article. (The burden of proof is on the person adding the new material.)

Second, you stated on my talk page "I have the right to advertise my publications." No you don't. Of course no one has such rights on Wikipedia. Also, please read WP:COI. You have a conflict of interest, since you are citing material written by yourself.

Anyway, my reason for removing User:Salvador.venegas's addition:

• Non-notability: I can't find a third-party source referring a reader to your book for an introduction to the field. The other two surveys have third-party sources referring readers to them. Moreover, Kempe and Ambainis were both instrumental in founding the field of quantum walks, and as such their surveys are undoubtedly notable. If you provide evidence of notability, I will not object on these grounds.
• Non-free: Your book is a paid book, and is not available freely. The other two references are. There is no need to link to a non-free survey when there are multiple free surveys available. Wikipedia is not your advertiser.

I wait for your response to these objections. If your arguments are convincing, I will be more than happy to agree with the inclusion of your book in this article. For now, I will keep the reference, but if I don't get a response I'll remove it again after a while. Robin (talk) 14:39, 1 November 2009 (UTC)

Here is my answer:

1. You say that I have no right to cite material written by myself. To support your statement, you have cited [WP:COI]

That link states that: "Editing in an area in which you have professional or academic expertise is not, in itself, a conflict of interest. Using material you yourself have written or published is allowed within reason, but only if it is notable and conforms to the content policies. Excessive self-citation is strongly discouraged. When in doubt, defer to the community's opinion.".

So:

1.1) Of course citing oneself is OK as for Wikipedia policies. I have cited a verifiable and reliable scientific source, it is notable (more on that below) and I am not citing myself excessively.

1.2) Your statement about not citing oneself is, with all respect, non-sensical. Of course one has the right to cite oneself if sources are relevant, that is common practice in all scientific manuscripts and you should know that.

2. You say that my book is non-notable because you did not find any third party source citing my work. Well, that is truly surprising and I am afraid that your inability to find a third party is due to the fact that you did not take a look at scientific articles!

For example, check the following recent papers: http://arxiv.org/PS_cache/arxiv/pdf/0904/0904.0392v3.pdf and http://jpsj.ipap.jp/link?JPSJ/78/064004/

Now, you cannot expect that a book that was published in October 2008 has the same number of citations as Kempe's and Ambainis' articles. I am not comparing the "relevance" or "notability" of my book with respect to theirs as Science is a serious AND objective subject, not a popularity contest. I just won't get into such a discussion about comparing relevance or notability as I truly respect my scientific colleagues: my book has been reviewed and published by a serious editorial company, that is all that counts.

So, I included a reference to my book because, I insist, it is a reliable, peer-reviewed book on the subject.

3. Finally, as for my book being a paid book:

3.1) I did not know that Wikipedia was against economic development and capitalism! Sorry if I misunderstand, but I see nothing wrong with citing a book that you have to pay for if you want to read it. That is called the right to receive economic stimulus for your work. Science is not begging, it is a professional activity and everybody has the right to be paid for their hard work.

3.2) The other two references are NOT free sources. If you want to read only a preprint, then of course that information is free. However, the papers you have cited are not free sources, those are articles published in journals for which you have to pay a (high, much higher that my book price) subscription fee. —Preceding unsigned comment added by Salvador.venegas (talk • contribs)

Please justify why this source should be added to the further reading section, what does it offer that the two existing sources, which are openly available, do not? Please do not add it yourself, due to your WP:COI, but provide justification and convince other editors here that it deserves to be added. Perhaps you could propose expanding the article, with one of your publications as a source (assuming it is an RS, etc). Verbal chat 16:16, 1 November 2009 (UTC)

My answer to Verbal:

Thanks for your contribution, Verbal. Please find my answer in the following lines:

1. I am an advocate of open access, so I am NOT against preprints. Of course, I do visit the Arxiv everyday, looking for new contributions and benefiting from them. Moreover, I do take part in that effort by putting my own papers in the Arxiv as well as by providing free access, in my web site (http://www.mindsofmexico.org/sva), to my scientific and non-scientific manuscripts, presentations, etc.

2. I also believe that paying for reading an article or a book is a fair and honorable practice. As a matter of fact, I spend a good amount of my own money paying subscriptions/pay-per-article fees to Science, Nature, APS journals and others (I work for a Mexican University, so you may well imagine how difficult it is to get money for paying subscriptions to relevant journals.) I believe in paying as a way to show respect to both authors and editorial companies.

3. I think that the relevance of a scientific source is independent from that source being either available for free or by paying a fee to read it.

4. Sources provided in quantum walk article are not openly available. Try downloading any paper from IEEE, ACM or the International Journal for Quantum Information. Payment is due, of course. Preprints are openly available, but nobody can assure the reader that preprints have the same quality as peer-reviewed journals or books.

5. Now, an important remark: I know very well Kempe's and Ambainis' papers cited in this quantum walk article (in fact, I cited both authors and these two papers in my book). I also know that the preprints they have placed in both the Arxiv and their webpages have the same information as the corresponding journal versions, and I know it because I paid the fee to read the journal versions!

So, my complain has nothing to do with my opinion about Kempe's and Ambainis' papers. I highly regard both authors for their seminal contributions to quantum walks. Please let us understand this point as clearly as possible as I am profoundly respectful of both authors and their work. Kempe and Ambainis do deserve a place not only in a Wikipedia article but also in any work that seriously reviews the field of quantum walks, as I did in my book: I cited all their quantum walk papers either published in a journal or the Arxiv.

6. As for what my book has to offer:

6.1 First of all, my book contains several (and very relevant) topics and developments on both discrete and continuos quantum walks that have come up after the publication of Kempe's and Ambainis' papers:

6.1.1 For example, I have addressed the question of what is really quantum about a quantum walk, a controversial question posed by Knight et al and Kendon et al, among others, in the following articles:

- "Quantum walk on the line as an interference phenomenon". PL Knight, E. Roldan, and J.E. Sipe. Physical Review A, vol. 69, 012310, 2004.

- "Complementarity and quantum walks". V. Kendon and B.C. Sanders. Physical Review A, vol. 71, 022307, 2005.

6.1.2 I have also pointed at new applications of quantum walks in the field of quantum simulation: "Environment-assisted quantum walks in energy transfer of photosynthetic complexes". M. Mohseni, P. Rebentrost, S. Lloyd, and A. Aspuru-Guzik. J Chem Phys. 2008 Nov 7;129(17):174106.

6.1.3 I have also addressed a fundamental contribution of A. Childs about the computational universality of quantum walks: "Universal Computation by Quantum Walk". A. Childs. Physical Review Letters, vol. 102, 180501, 2009. I have actually cited the preprint version that A. Childs placed in the Arxiv in 2008, as the peer-reviewed version did not exist at the time of my book release.

6.2 Of course, one may say that all papers mentioned in 6.1 may be found in the Arxiv, but then again, the value of a book in which a comprehensive review of a field is developed is to provide the reader with a succinct and verifiable summary of that field. Such a review provides the reader with a ready-to-use source that may shorten the learning curve required to enter a field. Consequentely, providing Wikipedia readers with a serious and reliable source that may empower them to quickly learn about quantum walks is, in my opinion, a good idea that deserves to be supported.

6.2 The purpose of my book is to provide a concise yet comprehensive introduction to quantum walks. My approach in the development of this work has been to study those concepts of quantum mechanics and quantum computation relevant to the computational aspects of quantum walks. Thus, in the history of cross-fertilization between physics and computation, this book is meant to be situated as a novel contribution within the field of quantum computation from the perspective of a computer scientist.

It has been my intention to write a book from which computer scientists with no background in physics may obtain a succinct guide to the concepts of quantum mechanics needed to be initiated in the field of quantum walks. To the best of my knowledge, this is the first book ever published on the topic of quantum walks, and its approach may allow not only theoretical computer scientists but also applied computer scientists and engineers to learn the foundations and algorithmic applications of quantum walks.

6.3 I provide, in the following lines, the contents of my book:

1. Introduction

2. Quantum Mechanics

2.1 Mathematical Preliminaries

2.2 Postulates of Quantum Mechanics

2.2.1 State Space

2.2.2 Evolution of a Closed Quantum System

2.2.3 Quantum Measurements

2.2.4 Composite Quantum Systems

2.3 Entanglement

2.3.1 Measure of Entanglement

2.3.2 Bell Inequalities

3. Theory of Computation

3.1 What is the Theory of Computation?

3.2 The Birth of the Theory of Computation: Alan Turing and His Machines

3.3 Deterministic and Nondeterministic Computation

3.4 A Quick Tour on Algorithmic Complexity and NP-Completeness

3.4.1 Algorithmic Complexity for DTMs

3.4.2 Algorithmic Complexity for NTMs

3.4.3 P ?= NP and NP-complete Problems

3.5 Physics and the Theory of Computation

4. Classical Random Walks

4.1 Probability Theory and Stochastic Processes

4.1.1 Discrete Random Variables and Distributions

4.1.2 Moments and Generating Functions

4.1.3 Markov Chains

4.2 Classical Discrete RandomWalks: Results and Applications

4.2.1 Classical Discrete Random Walks on a Line

4.2.2 Classical Discrete Random Walks on a Graph

4.3 Stochastic Algorithms Based on Classical Discrete Random Walks

4.3.1 2-SAT

4.3.2 3-SAT

4.4 Classical Continuous Random Walks

5. Quantum Walks

5.1 Quantum Walk on a Line

5.1.1 Structure of a Coined DQWL

5.1.2 Analysis of Quantum Walks on an Infinite Line

5.1.3 Discrete Quantum Walk With Boundaries

5.2 Quantum Walks on Graphs

5.3 More Considerations on Classical and Quantum Walks

5.3.1 Are Quantum Walks Really Quantum?

5.4 Continuous Quantum Walks

5.5 Whether Discrete or Continuous: Is It Quantum Random Walks or Just Quantum Walks?

5.6 How Are Continuous and Discrete Quantum Walks Connected?

6. Computer Science and Quantum Walks

6.1 Algorithmic Applications of Quantum Walks

6.1.1 Algorithms Based on Discrete Quantum Walks

6.1.2 Algorithms Based on Continuous Quantum Walks

6.2 Universality of Quantum Walks

7. Conclusions

8. References

7. I sense that my request to have my book among relevant surveys to the field may have been taken as an opportunistic move. If my sense is wrong, please accept my apologies for what I just said, but I think it is beneficial to everybody to openly talk about this.

I am not an opportunist and I do not mean, as Robink said, to have Wikipedia as my advertiser. Morgan and Claypool, my publisher, does the advertising and this company pays a fair amount of money to promote books published by them. I insist on having my book among relevant surveys because of the scientific contents of my work and also because both graduate and undergraduate students, as well as established scientists interested in entering the field of quantum walks, may benefit from reading it.

Please, do not think that I am becoming rich by selling my book. I am not, as any science book author knows (had I wanted to become rich by means of my writing, I would have become a mainstream novel writer.) I wrote Quantum Walks for Computer Scientists because I wanted to provide the scientific community with a reliable and comprehensive summary of the field of quantum walks, not because I wanted to get hundreds of dollars for every sold copy.

Moreover, given the policies of Morgan and Claypool, it is likely that several scientists and students already have access to my book without paying a fee, as many University and research centres have access to electronic editions (i.e. pdf files) of Morgan and Claypool books.

8. I do not have any conflict of interest as, according to Wikipedia policies on this topic (WP:COI) "Editing in an area in which you have professional or academic expertise is not, in itself, a conflict of interest. Using material you yourself have written or published is allowed within reason, but only if it is notable and conforms to the content policies. Excessive self-citation is strongly discouraged. When in doubt, defer to the community's opinion."

9. Finally, I would be more than happy to expand this Wikipedia quantum walk article. Now, I would not want you to take my willingness to contribute as a quid pro quo offer, i.e. I will contribute independently of whether my book is cited in this quantum walk article. So, please let us go step by step.

These are my two cents. Now, please let me know your thoughts.

Salvador.venegas (talk) 06:32, 2 November 2009 (UTC)

I took an in-depth look at the book, and it seems decent. Of course, my previous objections have nothing to do with the quality of the book, and they still stand. The surveys in the article do a good job, but the book is newer and hence mentions stuff that wasn't known at the time of publication of the other surveys. The non-free nature of the book, and the fact that I haven't seen this book cited significantly make me hesitant to add the book back in under the "further reading" section. So I'm going to change my opinion to being neutral about the inclusion of the book. Moreover, as Verbal said, if you were to add information to the article and reference it by citing the book, that would be acceptable. (Furthermore, if I do see this book being cited often in the future, I'll add it to the article myself.) --Robin (talk) 23:44, 3 November 2009 (UTC)

OK, my answer and one question:

a) The book has been cited in the following articles:

1. Decoherence in Two-Dimensional Quantum Random Walks with Traps. Meltem Gonulol, Ekrem Aydiner, Ozgur E. Mustecaplioglu. Phys. Rev. A 80, 022336 (2009).

2. Localization of an inhomogeneous discrete-time quantum walk on the line. Norio Konno. Accepted for publication in Quantum Information Processing (2009).

3. Quantum stochastic walks: A generalization of classical random walks and quantum walks. César A. Rodríguez-Rosario, James D. Whitfield, Alán Aspuru-Guzik. arXiv:0905.2942.

4. One-dimensional discrete-time quantum walks on random environments. Norio Konno. Quantum Information Processing, Volume 8 , Issue 5, pp. 387-399, DOI 10.1007/s11128-009-0116-y (October 2009)

5. Orthogonal polynomials induced by discrete-time quantum walks in one dimension. Masatoshi Hamada, Norio Konno, Wojciech Mlotkowski. arXiv:0903.4047

6. Ballistic Quantum Walk in a Discrete One-Dimensional System. Takasi Endo, Shin'ichi Osano, Kouichi Toyoshima, and Yutaka Hirayoshi. Journal of the Physical Society of Japan, vol. 78, 064004 (2009).

b) Now, should I understand that, if I expand the article then I can cite my book? If so, should I cite it not under the survey section but under the reference section?

Cheers,

S.

Salvador.venegas (talk) 06:45, 4 November 2009 (UTC)

Yes, I understand that there are some papers which cite the book. I was just pointing out that I haven't seen any in my reading through the literature. This just means that the papers I have read don't seem to cite it. Which means that I would be hesitant to add the survey myself. This doesn't mean that I'll object to its addition by another editor.

To answer your second question, yes. When you state a fact in the article which requires citation, which is perhaps explained in some paper, but you feel that your book has a more in depth explanation of the fact, you could cite your book (and perhaps the original paper?) next to that fact. When you cite something using the "ref" tags, the citation automatically appears in the references section of the article. For instance, see how the article says "Continuous-time quantum walks provide a model for universal quantum computation." Now the reference to Andrew Childs' paper will appear in the references section. If you need any help with editing, I'm happy to help out. Moreover, if you can add information to the article, but you don't know how to format it correctly, or some such technical issue, just go ahead and add the information. Someone (like me) will come and fix up the technical and formatting issues. --Robin (talk) 13:12, 4 November 2009 (UTC)

References

Including a new review paper on quantum walks as a reference

Dear Editors,

I hope these words find you well. Some time ago I wanted to add my book "Quantum Walks for Computer Scientists" as a reference on this page. Unfortunately, I found strong opposition as my book was not a free source (which is indeed true) and, according to one Wikipedia editor, it was non-notable (which was and is a false statement.)

Now, I have written a review paper entitled "Quantum walks: a comprehensive review" which has been recently accepted for publication at the Quantum Information Processing Journal (DOI: 10.1007/s11128-012-0432-5 (2012)) and is freely available at http://arxiv.org/abs/1201.4780v2. This paper has already been cited in the following articles:

1. Quantum walk as a generalized measuring device. P. Kurzyński and A. Wójcik. ArXiv:1208.1800v1 (2012).

2. The square and cube of the transition of the discrete-time quantum walk on a graph. N. Konno and I. Sato. ArXiv:1207.4987v1 (2012).

3. High-level Structures for Quantum Computing. Jarosław Adam Miszczak. Synthesis Lectures on Quantum Computing, Morgan and Claypool Publishers (2012).

4. Decoherence on Quantum Markov Chains. R.A.M. Santos, R. Portugal, and M.D. Fragoso. ArXiv:1204.6238v2 (2012).

5. Increasing the dimensionality of quantum walks using multiple walkers. P.P. Rohde, Andreas Schreiber, M. Stefanak, I. Jex, A. Gilchrist, and C. Silberhorn. arXiv:1205.1850v1 [quant-ph] (2012).

I think that my review paper does fulfill the criteria needed to be included as a reference on this page. Consequently, I would like to add my review paper as a reference under the Further reading section but I really do not want to go through the same bitter arguments we had last time as I think that is truly unnecessary. Please let me know whether I can do it.

Best regards,

Salvador E. Venegas-Andraca. Salvador.venegas (talk) 23:41, 21 August 2012 (UTC)

"Oracular problems"

Should the redlink to "oracular problems" in the Motivation section actually point to oracle problems? It seems likely to me, as a computer scientist, but I don't want to make the edit as I'm not an expert on anything with "quantum" in its name. Dricherby (talk) 13:00, 10 May 2019 (UTC)