The most trivial theorem I’ve ever written up
Theorem: Suppose NP-complete problems are efficiently solvable by quantum computers. Then either the polynomial hierarchy collapses, or else BQP ⊄ AM (that is, quantum computations can’t be efficiently simulated by Arthur-Merlin protocols).
Proof: Suppose NP ⊆ BQP and BQP ⊆ AM. Then coNP ⊆ BQP ⊆ AM, and hence the polynomial hierarchy collapses to the second level by a result of Boppana, Håstad, and Zachos.
Note: If only we could delete the weasel phrase “or else BQP ⊄ AM” from my Most Trivial Theorem, we would’ve achieved a long-sought breakthrough in quantum computing theory. In particular, we would’ve shown that any fast quantum algorithm to solve NP-complete problems would imply an unlikely collapse of classical complexity classes. But while the weasel phrase is weaselly enough to make the Most Trivial Theorem a triviality, I don’t think it’s infinitely weaselly. The reason is my growing suspicion that BQP ⊆ AM in the unrelativized world.
Second Note: When I call this my “Most Trivial Theorem,” obviously I’m excluding homework exercises.
Follow
Comment #1 May 2nd, 2007 at 1:35 pm
I have to bite. Why do you think BQP is inside AM in the unrelativized world?
Comment #2 May 2nd, 2007 at 2:12 pm
Why do you think BQP is inside AM in the unrelativized world?
Because every attempt to construct a candidate problem in BQP\AM has — unexpectedly to me! — been such a total failure. Whenever we find an efficient quantum algorithm — for example, for HSP, for walking on two conjoined binary trees, for the problems recently considered by Harrow & Hallgren, for various combinations of the last three — we also seem to find global structure that can be detected using approximate counting. Why does the one property always seem to go with the other?
To be clear, I do think we’re likely to succeed eventually in showing BQP⊄AM relative to an oracle. Probably Recursive Fourier Sampling already gives a suitable oracle, though it could only lead to an nlog n versus n separation, not an exponential one. If not, Greg Kuperberg and I have an alternative proposal based on “pseudorandom unitaries” (see here for more), which could lead to an exponential separation. However, both types of oracle are so contrived — in contrast (for example) to the oracles relative to which P≠BQP and NP⊄BQP — that I don’t know if anything can be learned from them about the unrelativized case.
Alright, let me be more conservative: I see strong reasons to believe P≠NP, P≠BQP, and NP⊄BQP. I expected to find similarly strong reasons to believe BQP⊄AM, and haven’t found any yet.
Comment #3 May 2nd, 2007 at 6:03 pm
I disagree with Scott. It is possible that BQP is in AM, unrelativized. But of course, everyone believes that NP = AM, unrelativized, so that would imply that BQP is in NP. I see no strong evidence that it has to be so. I have no strong evidence that it is false, either, but to me it more indicates our primitive understanding of BQP. The apparent size of a complexity class typically changes as you understand it better, and I still think that BQP will look larger in the future.
Of course some oracle separations should still be taken seriously as evidence for the unrelativized world. The question is whether the oracle can reasonably be replaced by an instance.
Comment #4 May 3rd, 2007 at 12:50 am
Scott, just for your info, the “subset” character isn’t appearing properly in IE.
Oh, and nice theorem etc.
Comment #5 May 3rd, 2007 at 4:13 am
This is actually just the first of the “Wary Weasel” theorems. As I recall, the second is something like this:
Wary Weasel theorem 2. There is an infinite series of propositions of the following form –
Proposition N: Suppose NP-complete theorems are efficiently solvable by quantum computers, and that (Escape Clause N-1) is not true; then the polynomial hierarchy collapses, or else (Escape Clause N).
– such that:
(i) for N>1, the Escape Clause refers to properties of the series of propositions;
(ii) for N=1,2, proposition N implies the truth of Wary Weasel theorem N;
(iii) for N>=3, the shortest possible statement of the Escape Clause grows as fast as a Nabutovsky-Weinberger number.
Comment #6 May 3rd, 2007 at 4:15 am
That should be NP-complete problems, of course.
Comment #7 May 3rd, 2007 at 9:59 am
Greg: While I believe that P = BPP, I’m much more wary about AM = NP. So your statement that everybody believes it has an exception.
Scot: How about a weaker conjecture: BQP is in IP(log n). That is, interactive proofs with log n rounds of communication. Does this avoid even the potential recursive Fourier sampling counterexample?
Peter
Comment #8 May 3rd, 2007 at 10:20 am
Peter: Yes, BQP in IP[log] avoids even the RFS counterexample, and I correspondingly attach a greater probability to its truth.
Regarding AM=NP, I wouldn’t have believed it either before the Klivans-van Melkebeek paper. But I certainly believe there are languages in NE that require exponential-size nondeterministic circuits.
Comment #9 May 3rd, 2007 at 3:06 pm
So your statement that everybody believes it has an exception.
Well, I am not sure that it was a particularly informed statement that NP = AM is so likely. But I can point to what Scott said.
I have thought some about trying to prove that AM contains BQP. Given the examples such as IP = PSPACE, even a non-relativizing inclusion may not be as hard as P vs NP. But it seemed hopeless, although I concede that it deserves another try. In fact, the mechanics of showing that AM contains BQP was one of the motivations of the oracle that Scott and I propose to place BQP outside of AM (and do other things). Namely, as Scott said, we think that you can make a “limited randomness” quantum oracle from a random classical oracle, post-conditioned on the promise that it gives bounded-error answers. I think that such an oracle would be incomprehensible to an AM computer.
But on the other hand, it is possible that such an oracle would be unrealistic for the same reason that the random oracle is unrealistic for the question of IP vs PSPACE.
Comment #10 May 4th, 2007 at 12:58 pm
I also tried to show that BQP was in IP(log n), but there didn’t seem to be any promising avenues of attack.
Comment #11 May 4th, 2007 at 8:37 pm
BQP related: you can play integer factorization online:
http://87zero.com/SCT/hanamarugame.html
Comment #12 October 2nd, 2007 at 5:53 pm
sound good, respect!
i like ur blog, write more..
Comment #13 November 21st, 2007 at 8:55 am
In prayer, it is better to have a heart without words than words without heart.
Comment #14 September 23rd, 2008 at 10:13 pm
I am getting more and more worried about the economy and global meltdown.
The more things change the more they remain the same. The fundamental challenges we face today have changed little since Chaucer penned his observations on life and distilled them in a set of tales. In the modern city of Canterbury University Students analyse and dissect the meanings conveyed in texts set in that very locale in the 1300’s.
Youngsters face today’s Jekyll and Hyde society not knowing that the Constants remain; love, betrayal, desire, fear. Each story conveys a lesson as we study for our degree in the University of Life, the big diploma mill of which we are all Alumni. We sit grinning like Cheshire cats, thinking we have all the answers.
We call it a success when we pollute our atmosphere shooting down our own Satellite USA 193, Market Street Credibility is our preferred accreditation and recognition from our peers and fellow consumers, we Poison our Planet for Profit. Banks have crashed before and remember – you can’t eat money.
Globalization has consequences. Everything we do has consequences, even something simple like buying firewood. The Oregon ODA advises not to obtain anything from out-of-state because of all the insects and diseases it might carry. That is just a relatively local issue. Imagine all the things that are carried around the world each day – each hour. We must protect our future, just as we should remember our past. All over the world, From the UK to the USA and the Seychelles to Egypt, still, yes, STILL, there is no REAL alternative to fossil fuels.
Are we all going to purgatory in a wheelbarrow telling each other stories to pass the time? Sometimes I wonder!
Sorry guys, I had a long day and feel sick of the world. Rant Over!
Comment #15 October 9th, 2008 at 10:03 am
porta vidro box visa sexy asian bride honda civic vtec
Comment #16 November 28th, 2008 at 11:45 am
Hello Id Like to shove up you this tottering talk someone into something !
How with proposeion to we try something a teeny-weeny foetid this without detain-up ?
as the casing may be something like this ?
http://www.lovepicspoint.com
Comment #17 December 6th, 2008 at 2:12 pm
Check out Online Diet programs
The best online weight loss programs of 2008!
Comment #18 December 18th, 2008 at 6:54 pm
Hi people
As newly registered user i just want to say hi to everyone else who uses this board
Comment #19 December 18th, 2008 at 7:19 pm
Hi all!
As a fresh scottaaronson.com user i only want to say hi to everyone else who uses this board 😀
Comment #20 February 16th, 2009 at 5:49 pm
Оглянись и посмотри на других женщин.
Ты видишь: они не так молоды, умны, стройны, красивы, образованны или материально обеспечены, как ты.
Но с некоторыми из этих женщин рядом находятся такие мужчины, о которых тебе можно только мечтать.
Ты можешь думать, что эти женщины совсем не симпатичны, но они пользуются успехом у мужчин.
Почему же они замужем, а ты все еще одна? Долгое время я тоже была в категории одиноких женщин,
пока не создала анкету на сайте http://zamuz-blog.freehostia.com – выхожу замуж где сразу же познакомилась с 2 мужчинами. Один из европы,
второй из Америки. Я безумно счастлива, через неделю уезжаю в Америку
Comment #21 February 17th, 2009 at 4:48 pm
Новый способ давления на кандидата на пост Главы г. Химки
Новый способ “наказать” тех, кто посмел участвовать в выборной кампании не на стороне действующей власти изобрели правоохранительные органы г.о. Химки.
Руководствуясь не нормой закона, а чьей-то “волей” сотрудники милиции решили “проверить” все фирмы, внесшие денежные средства в избирательный фонд неудобных кандидатов.
Начались “проверки” с телефонных звонков – где директор, сколько человек работает на фирме. После чего последовали “письма счастья” с просьбой предоставить всю бухгалтерскую документацию, учредительные документы фирмы, и даже, план экспликации БТИ.
Такие запросы химкинским фирмам рассылает 1 отдел Оперативно-розыскной части № 9 Управления по налоговым преступлениям ГУВД Московской области за подписью начальника подполковника милиции Д.В. Языкова.
И всё это в то время, когда Президент дал прямое указание правоохранительным органам о прекращении всех незаконных проверок малого и среднего бизнеса. С это целью внесены изменения в Федеральный закон “О милиции” – из статьи 11 этого закона исключены пункты 25 и 35, на основании которых ранее правоохранительные органы имели право проверять финансово-хозяйственную деятельность предприятий.
Видно, об изменениях действующего законодательства местные правоохранительные органы не уведомлены. И не смотрят телепередачи с выступлениями Президента.
Может быть, эта публикация подвигнет их к исполнению указаний Президента, а также к изучению и соблюдению действующего законодательства