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.

21 Responses to “The most trivial theorem I’ve ever written up”

  1. Peter Shor Says:

    I have to bite. Why do you think BQP is inside AM in the unrelativized world?

  2. Scott Says:

    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.

  3. Greg Kuperberg Says:

    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.

  4. mick Says:

    Scott, just for your info, the “subset” character isn’t appearing properly in IE.

    Oh, and nice theorem etc.

  5. Mustela nivalis Says:

    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.

  6. Mustela nivalis Says:

    That should be NP-complete problems, of course.

  7. Peter Shor Says:

    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

  8. Scott Says:

    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.

  9. Greg Kuperberg Says:

    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.

  10. Peter Shor Says:

    I also tried to show that BQP was in IP(log n), but there didn’t seem to be any promising avenues of attack.

  11. almaya Says:

    BQP related: you can play integer factorization online:

    http://87zero.com/SCT/hanamarugame.html

  12. female free nudist photo Says:

    sound good, respect!
    i like ur blog, write more..

  13. christmas music download Says:

    In prayer, it is better to have a heart without words than words without heart.

  14. dwerfeide Says:

    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!

  15. Cakskeyloassy Says:

    porta vidro box visa sexy asian bride honda civic vtec

  16. engegaikacinc Says:

    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

  17. online diet plans Says:

    Check out Online Diet programs
    The best online weight loss programs of 2008!

  18. TogAlcogs Says:

    Hi people

    As newly registered user i just want to say hi to everyone else who uses this board

  19. TogAlcogs Says:

    Hi all!

    As a fresh scottaaronson.com user i only want to say hi to everyone else who uses this board :D

  20. Elena_zamuzh Says:

    Оглянись и посмотри на других женщин.
    Ты видишь: они не так молоды, умны, стройны, красивы, образованны или материально обеспечены, как ты.
    Но с некоторыми из этих женщин рядом находятся такие мужчины, о которых тебе можно только мечтать.
    Ты можешь думать, что эти женщины совсем не симпатичны, но они пользуются успехом у мужчин.
    Почему же они замужем, а ты все еще одна? Долгое время я тоже была в категории одиноких женщин,
    пока не создала анкету на сайте http://zamuz-blog.freehostia.com – выхожу замуж где сразу же познакомилась с 2 мужчинами. Один из европы,
    второй из Америки. Я безумно счастлива, через неделю уезжаю в Америку

  21. osobo Says:

    Новый способ давления на кандидата на пост Главы г. Химки

    Новый способ “наказать” тех, кто посмел участвовать в выборной кампании не на стороне действующей власти изобрели правоохранительные органы г.о. Химки.
    Руководствуясь не нормой закона, а чьей-то “волей” сотрудники милиции решили “проверить” все фирмы, внесшие денежные средства в избирательный фонд неудобных кандидатов.
    Начались “проверки” с телефонных звонков – где директор, сколько человек работает на фирме. После чего последовали “письма счастья” с просьбой предоставить всю бухгалтерскую документацию, учредительные документы фирмы, и даже, план экспликации БТИ.
    Такие запросы химкинским фирмам рассылает 1 отдел Оперативно-розыскной части № 9 Управления по налоговым преступлениям ГУВД Московской области за подписью начальника подполковника милиции Д.В. Языкова.
    И всё это в то время, когда Президент дал прямое указание правоохранительным органам о прекращении всех незаконных проверок малого и среднего бизнеса. С это целью внесены изменения в Федеральный закон “О милиции” – из статьи 11 этого закона исключены пункты 25 и 35, на основании которых ранее правоохранительные органы имели право проверять финансово-хозяйственную деятельность предприятий.
    Видно, об изменениях действующего законодательства местные правоохранительные органы не уведомлены. И не смотрят телепередачи с выступлениями Президента.
    Может быть, эта публикация подвигнет их к исполнению указаний Президента, а также к изучению и соблюдению действующего законодательства