User talk:RobinK

This is RobinK's talk page, where you can send them messages and comments.

Put new text under old text. Click here to start a new topic.
New to Wikipedia? Welcome! Learn to edit; get help.

Archives: 1: 30 days

Welcome to my talk page. Please adhere to the talk page guidelines and particularly the following:

Please post your new topic at the bottom of this page.
Please sign and date your entry by inserting "~~~~" at the end.
Please specify a descriptive "Subject/headline" for a new topic and separate subtopics by ===heading=== lines, if needed.
Please indent your posts with one more ":" than what you are replying to, i.e. begin with ":" if replying to an existing topic and "::" if replying to a reply.

I will generally respond here to comments that are posted here, rather than replying via your Talk page (or the article Talk page, if you are writing to me here about an article), so you may want to watch this page until you are responded to, or specifically let me know where you'd prefer the reply.

⇒ Start a new Talk topic.

File:Decision Problem.png listed for deletion

A file that you uploaded or altered, File:Decision Problem.png, has been listed at Wikipedia:Files for deletion. Please see the discussion to see why this is (you may have to search for the title of the image to find its entry), if you are interested in it not being deleted. Thank you. $The Haz talk$ 04:10, 2 January 2012 (UTC)[reply]

Simon's algorithm

We have a random oracle relative to which BPP and BQP are separated. This is an improvement over the Deutsch-Jozsa algorithm separating P from EQP. The oracle needs to be quantum and nondecohering.

I think what this is saying is that given a quantum oracle (running in BQP time?), the classic algorithm can't solve the problem as efficiently as quantum algorithm. It's a stronger example of the power of QC than the Deutsch-Jozsa algorithm. I don't quite understand the sentence either, but if you have another idea about how to capture this concept, it would be helpful. I don't know enough about quantum complexity to craft a sentence myself. Skippydo (talk) 14:43, 19 August 2012 (UTC)[reply]

The first sentence is vague, but a fairly common interpretation of it would be that there is a random oracle separation between BQP and BPP. This is not known to be true, and conjectured to be false. The second sentence is OK, so I didn't remove it -- although I'll try to reword it to make it clearer. The last one about the oracle being quantum and decohering makes very little sense to me. If it just means that the oracle has to allow the quantum computer to make queries in quantum superposition, then that's part of the definition of what it means to give BQP oracle access. --Robin (talk) 15:07, 19 August 2012 (UTC)[reply]

Thank you for the explanation and the edits. You've been very helpful. Skippydo (talk) 20:29, 19 August 2012 (UTC)[reply]