From calendar@csail.mit.edu Wed Jun 28 10:25:40 2017 From: calendar@csail.mit.edu To: aspuru-list@lists.fas.harvard.edu Subject: [Aspuru-Guzik Group List] [qip] TALK: Friday 06-30-2017 Adam Bouland: Thesis Defense: The space around BQP Date: Wed, 28 Jun 2017 10:22:09 -0400 Message-ID: <5953bb916806a_7be533196828263@calendar.mail> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="===============4080300471395520625==" --===============4080300471395520625== Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Adam Bouland: Thesis Defense: The space around BQP Speaker: Adam Bouland Host: Scott Aaronson =20 Date: Friday, June 30, 2017 Time: 3:00 PM to 4:30 PM Refreshments Time: 2:45 PM Location: G575 Abstract: This thesis explores the computational power of quantum devices from the pers= pective of complexity theory. Quantum computers hold the promise of solving m= any problems - such as factoring integers - exponentially faster than classic= al computers. The computational power of universal quantum devices is capture= d by the complexity class BQP, which stands for =E2=80=9Cbounded-error quantu= m polynomial time.=E2=80=9D We hope that quantum devices will be capable of t= he full power of BQP in the long term. However, quantum computers are very di= fficult to build, and therefore the experimental devices of the near future m= ay be incapable of universal quantum computation. As a result, a number of re= cent works have studied the computational power of =E2=80=9Cweak=E2=80=9D mod= els of quantum computers which lie =E2=80=9Cbelow BQP.=E2=80=9D =20 The first part of this thesis examines the space "below BQP=E2=80=9D and desc= ribes a number of sub-universal models of quantum computation which can never= theless perform sampling tasks which are difficult for classical computers. W= e show that prior models maintain hardness when their set of quantum operatio= ns is restricted, and describe two new models of =E2=80=9Cweak=E2=80=9D quant= um computation which also show advantage over classical devices. A major them= e in this work is that almost any weak device can perform hard sampling tasks= . We find that almost any model which is not universal, but not known to be e= fficiently classically simulable, admits a speedup over classical computing f= or sampling tasks under plausible assumptions. This work can be seen as progr= ess towards classifying the power of all restricted quantum gate sets. =20 On the other hand, recent developments in quantum gravity have opened up the = possibility of modifying quantum mechanics to resolve the black hole informat= ion paradox. Inspired by these debates, the second part of this thesis explor= es the space =E2=80=9Cabove BQP=E2=80=9D - i.e. the power of quantum computer= s in the presence of modified theories of quantum mechanics. We find that alm= ost all modifications allow for drastically more power than BQP, and find tha= t these speedups may be related to superluminal signaling in these models. Su= rprisingly, we find one model which is merely just a bit more powerful than B= QP. Inspired by this model =E2=80=9Cjust above=E2=80=9D BQP, we study and res= olve an open problem in classical complexity related to the power of statisti= cal-zero knowledge proof systems. =20 Members of committee: Scott Aaronson, Aram Harrow, Ryan Williams =20 Relevant URL:=20 For more information please contact: Deborah Goodwin, 617.324.7303, dlehto(a)csail.mit.edu _______________________________________________ qip mailing list qip(a)mit.edu http://mailman.mit.edu/mailman/listinfo/qip --===============4080300471395520625== Content-Type: text/html Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="attachment.htm" MIME-Version: 1.0 PGgzPkFkYW0gQm91bGFuZDogVGhlc2lzIERlZmVuc2U6IFRoZSBzcGFjZSBhcm91bmQgQlFQPC9o Mz4KCgo8cD48Yj5TcGVha2VyOjwvYj4gQWRhbSBCb3VsYW5kPC9wPgoKCjxwPjxiPkhvc3Q6PC9i PiBTY290dCBBYXJvbnNvbjwvcD4KCiAKPHA+PGI+RGF0ZTo8L2I+IEZyaWRheSwgSnVuZSAzMCwg MjAxNzwvcD4KCjxwPjxiPlRpbWU6PC9iPiAgMzowMCBQTSB0byA0OjMwIFBNPC9wPgoKPHA+PGI+ UmVmcmVzaG1lbnRzIFRpbWU6PC9iPiAyOjQ1IFBNPC9wPgoKPHA+PGI+TG9jYXRpb246PC9iPiBH NTc1PC9wPgoKPHA+PHA+QWJzdHJhY3Q6CjxiciAvPlRoaXMgdGhlc2lzIGV4cGxvcmVzIHRoZSBj b21wdXRhdGlvbmFsIHBvd2VyIG9mIHF1YW50dW0gZGV2aWNlcyBmcm9tIHRoZSBwZXJzcGVjdGl2 ZSBvZiBjb21wbGV4aXR5IHRoZW9yeS4gUXVhbnR1bSBjb21wdXRlcnMgaG9sZCB0aGUgcHJvbWlz ZSBvZiBzb2x2aW5nIG1hbnkgcHJvYmxlbXMgLSBzdWNoIGFzIGZhY3RvcmluZyBpbnRlZ2VycyAt IGV4cG9uZW50aWFsbHkgZmFzdGVyIHRoYW4gY2xhc3NpY2FsIGNvbXB1dGVycy4gVGhlIGNvbXB1 dGF0aW9uYWwgcG93ZXIgb2YgdW5pdmVyc2FsIHF1YW50dW0gZGV2aWNlcyBpcyBjYXB0dXJlZCBi eSB0aGUgY29tcGxleGl0eSBjbGFzcyBCUVAsIHdoaWNoIHN0YW5kcyBmb3Ig4oCcYm91bmRlZC1l cnJvciBxdWFudHVtIHBvbHlub21pYWwgdGltZS7igJ0gV2UgaG9wZSB0aGF0IHF1YW50dW0gZGV2 aWNlcyB3aWxsIGJlIGNhcGFibGUgb2YgdGhlIGZ1bGwgcG93ZXIgb2YgQlFQIGluIHRoZSBsb25n IHRlcm0uIEhvd2V2ZXIsIHF1YW50dW0gY29tcHV0ZXJzIGFyZSB2ZXJ5IGRpZmZpY3VsdCB0byBi dWlsZCwgYW5kIHRoZXJlZm9yZSB0aGUgZXhwZXJpbWVudGFsIGRldmljZXMgb2YgdGhlIG5lYXIg ZnV0dXJlIG1heSBiZSBpbmNhcGFibGUgb2YgdW5pdmVyc2FsIHF1YW50dW0gY29tcHV0YXRpb24u IEFzIGEgcmVzdWx0LCBhIG51bWJlciBvZiByZWNlbnQgd29ya3MgaGF2ZSBzdHVkaWVkIHRoZSBj b21wdXRhdGlvbmFsIHBvd2VyIG9mIOKAnHdlYWvigJ0gbW9kZWxzIG9mIHF1YW50dW0gY29tcHV0 ZXJzIHdoaWNoIGxpZSDigJxiZWxvdyBCUVAu4oCdPC9wPgoKPHA+IDwvcD4KCjxwPlRoZSBmaXJz dCBwYXJ0IG9mIHRoaXMgdGhlc2lzIGV4YW1pbmVzIHRoZSBzcGFjZSAiYmVsb3cgQlFQ4oCdIGFu ZCBkZXNjcmliZXMgYSBudW1iZXIgb2Ygc3ViLXVuaXZlcnNhbCBtb2RlbHMgb2YgcXVhbnR1bSBj b21wdXRhdGlvbiB3aGljaCBjYW4gbmV2ZXJ0aGVsZXNzIHBlcmZvcm0gc2FtcGxpbmcgdGFza3Mg d2hpY2ggYXJlIGRpZmZpY3VsdCBmb3IgY2xhc3NpY2FsIGNvbXB1dGVycy4gV2Ugc2hvdyB0aGF0 IHByaW9yIG1vZGVscyBtYWludGFpbiBoYXJkbmVzcyB3aGVuIHRoZWlyIHNldCBvZiBxdWFudHVt IG9wZXJhdGlvbnMgaXMgcmVzdHJpY3RlZCwgYW5kIGRlc2NyaWJlIHR3byBuZXcgbW9kZWxzIG9m IOKAnHdlYWvigJ0gcXVhbnR1bSBjb21wdXRhdGlvbiB3aGljaCBhbHNvIHNob3cgYWR2YW50YWdl IG92ZXIgY2xhc3NpY2FsIGRldmljZXMuIEEgbWFqb3IgdGhlbWUgaW4gdGhpcyB3b3JrIGlzIHRo YXQgYWxtb3N0IGFueSB3ZWFrIGRldmljZSBjYW4gcGVyZm9ybSBoYXJkIHNhbXBsaW5nIHRhc2tz LiBXZSBmaW5kIHRoYXQgYWxtb3N0IGFueSBtb2RlbCB3aGljaCBpcyBub3QgdW5pdmVyc2FsLCBi dXQgbm90IGtub3duIHRvIGJlIGVmZmljaWVudGx5IGNsYXNzaWNhbGx5IHNpbXVsYWJsZSwgYWRt aXRzIGEgc3BlZWR1cCBvdmVyIGNsYXNzaWNhbCBjb21wdXRpbmcgZm9yIHNhbXBsaW5nIHRhc2tz IHVuZGVyIHBsYXVzaWJsZSBhc3N1bXB0aW9ucy4gVGhpcyB3b3JrIGNhbiBiZSBzZWVuIGFzIHBy b2dyZXNzIHRvd2FyZHMgY2xhc3NpZnlpbmcgdGhlIHBvd2VyIG9mIGFsbCByZXN0cmljdGVkIHF1 YW50dW0gZ2F0ZSBzZXRzLjwvcD4KCjxwPiA8L3A+Cgo8cD5PbiB0aGUgb3RoZXIgaGFuZCwgcmVj ZW50IGRldmVsb3BtZW50cyBpbiBxdWFudHVtIGdyYXZpdHkgaGF2ZSBvcGVuZWQgdXAgdGhlIHBv c3NpYmlsaXR5IG9mIG1vZGlmeWluZyBxdWFudHVtIG1lY2hhbmljcyB0byByZXNvbHZlIHRoZSBi bGFjayBob2xlIGluZm9ybWF0aW9uIHBhcmFkb3guIEluc3BpcmVkIGJ5IHRoZXNlIGRlYmF0ZXMs IHRoZSBzZWNvbmQgcGFydCBvZiB0aGlzIHRoZXNpcyBleHBsb3JlcyB0aGUgc3BhY2Ug4oCcYWJv dmUgQlFQ4oCdIC0gaS5lLiB0aGUgcG93ZXIgb2YgcXVhbnR1bSBjb21wdXRlcnMgaW4gdGhlIHBy ZXNlbmNlIG9mIG1vZGlmaWVkIHRoZW9yaWVzIG9mIHF1YW50dW0gbWVjaGFuaWNzLiBXZSBmaW5k IHRoYXQgYWxtb3N0IGFsbCBtb2RpZmljYXRpb25zIGFsbG93IGZvciBkcmFzdGljYWxseSBtb3Jl IHBvd2VyIHRoYW4gQlFQLCBhbmQgZmluZCB0aGF0IHRoZXNlIHNwZWVkdXBzIG1heSBiZSByZWxh dGVkIHRvIHN1cGVybHVtaW5hbCBzaWduYWxpbmcgaW4gdGhlc2UgbW9kZWxzLiBTdXJwcmlzaW5n bHksIHdlIGZpbmQgb25lIG1vZGVsIHdoaWNoIGlzIG1lcmVseSBqdXN0IGEgYml0IG1vcmUgcG93 ZXJmdWwgdGhhbiBCUVAuIEluc3BpcmVkIGJ5IHRoaXMgbW9kZWwg4oCcanVzdCBhYm92ZeKAnSBC UVAsIHdlIHN0dWR5IGFuZCByZXNvbHZlIGFuIG9wZW4gcHJvYmxlbSBpbiBjbGFzc2ljYWwgY29t cGxleGl0eSByZWxhdGVkIHRvIHRoZSBwb3dlciBvZiBzdGF0aXN0aWNhbC16ZXJvIGtub3dsZWRn ZSBwcm9vZiBzeXN0ZW1zLgo8YnIgLz4gCjxiciAvPk1lbWJlcnMgb2YgY29tbWl0dGVlOiBTY290 dCBBYXJvbnNvbiwgQXJhbSBIYXJyb3csIFJ5YW4gV2lsbGlhbXMKPGJyIC8+IAo8L3A+PC9wPgoK PHA+UmVsZXZhbnQgVVJMOiA8L3A+Cgo8cD5Gb3IgbW9yZSBpbmZvcm1hdGlvbiBwbGVhc2UgY29u dGFjdDogRGVib3JhaCBHb29kd2luLCA2MTcuMzI0LjczMDMsIDxhIGhyZWY9Im1haWx0bzpkbGVo dG9AY3NhaWwubWl0LmVkdSI+ZGxlaHRvQGNzYWlsLm1pdC5lZHU8L2E+PC9wPgoKCg== --===============4080300471395520625== Content-Type: application/ics Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="event.ics" MIME-Version: 1.0 QkVHSU46VkNBTEVOREFSDQpWRVJTSU9OOjIuMA0KUFJPRElEOmljYWxlbmRhci1ydWJ5DQpDQUxT Q0FMRTpHUkVHT1JJQU4NCk1FVEhPRDpQVUJMSVNIDQpCRUdJTjpWVElNRVpPTkUNClRaSUQ6QW1l cmljYS9OZXdfWW9yaw0KQkVHSU46REFZTElHSFQNCkRUU1RBUlQ6MjAxNzAzMTJUMDMwMDAwDQpU Wk9GRlNFVEZST006LTA1MDANClRaT0ZGU0VUVE86LTA0MDANClJSVUxFOkZSRVE9WUVBUkxZO0JZ REFZPTJTVTtCWU1PTlRIPTMNClRaTkFNRTpFRFQNCkVORDpEQVlMSUdIVA0KQkVHSU46U1RBTkRB UkQNCkRUU1RBUlQ6MjAxNzExMDVUMDEwMDAwDQpUWk9GRlNFVEZST006LTA0MDANClRaT0ZGU0VU VE86LTA1MDANClJSVUxFOkZSRVE9WUVBUkxZO0JZREFZPTFTVTtCWU1PTlRIPTExDQpUWk5BTUU6 RVNUDQpFTkQ6U1RBTkRBUkQNCkVORDpWVElNRVpPTkUNCkJFR0lOOlZFVkVOVA0KRFRTVEFNUDoy MDE3MDYyOFQxNDIyMDhaDQpVSUQ6NmJjYTdjZWMtYjgzYi00ODM0LWIxMWEtZWU3MmI2MTY4OGZj DQpEVFNUQVJUO1RaSUQ9QW1lcmljYS9OZXdfWW9yazoyMDE3MDYzMFQxNTAwMDANCkRURU5EO1Ra SUQ9QW1lcmljYS9OZXdfWW9yazoyMDE3MDYzMFQxNjMwMDANCkNSRUFURUQ6MjAxNzA2MjZUMTAw NTEwDQpERVNDUklQVElPTjpBYnN0cmFjdDpcblRoaXMgdGhlc2lzIGV4cGxvcmVzIHRoZSBjb21w dXRhdGlvbmFsIHBvd2VyIG9mIHF1YW4NCiB0dW0gZGV2aWNlcyBmcm9tIHRoZSBwZXJzcGVjdGl2 ZSBvZiBjb21wbGV4aXR5IHRoZW9yeS4gUXVhbnR1bSBjb21wdXRlcnMgaG8NCiBsZCB0aGUgcHJv bWlzZSBvZiBzb2x2aW5nIG1hbnkgcHJvYmxlbXMgLSBzdWNoIGFzIGZhY3RvcmluZyBpbnRlZ2Vy cyAtIGV4cG8NCiBuZW50aWFsbHkgZmFzdGVyIHRoYW4gY2xhc3NpY2FsIGNvbXB1dGVycy4gVGhl IGNvbXB1dGF0aW9uYWwgcG93ZXIgb2YgdW5pdmUNCiByc2FsIHF1YW50dW0gZGV2aWNlcyBpcyBj YXB0dXJlZCBieSB0aGUgY29tcGxleGl0eSBjbGFzcyBCUVBcLCB3aGljaCBzdGFuZHMNCiAgZm9y IOKAnGJvdW5kZWQtZXJyb3IgcXVhbnR1bSBwb2x5bm9taWFsIHRpbWUu4oCdIFdlIGhvcGUgdGhh dCBxdWFudHVtIGRldmljZXMgDQogd2lsbCBiZSBjYXBhYmxlIG9mIHRoZSBmdWxsIHBvd2VyIG9m IEJRUCBpbiB0aGUgbG9uZyB0ZXJtLiBIb3dldmVyXCwgcXVhbnR1DQogbSBjb21wdXRlcnMgYXJl IHZlcnkgZGlmZmljdWx0IHRvIGJ1aWxkXCwgYW5kIHRoZXJlZm9yZSB0aGUgZXhwZXJpbWVudGFs IGRlDQogdmljZXMgb2YgdGhlIG5lYXIgZnV0dXJlIG1heSBiZSBpbmNhcGFibGUgb2YgdW5pdmVy c2FsIHF1YW50dW0gY29tcHV0YXRpb24uDQogIEFzIGEgcmVzdWx0XCwgYSBudW1iZXIgb2YgcmVj ZW50IHdvcmtzIGhhdmUgc3R1ZGllZCB0aGUgY29tcHV0YXRpb25hbCBwb3dlDQogciBvZiDigJx3 ZWFr4oCdIG1vZGVscyBvZiBxdWFudHVtIGNvbXB1dGVycyB3aGljaCBsaWUg4oCcYmVsb3cgQlFQ LuKAnVxuXG4gXG5cblRoZSANCiBmaXJzdCBwYXJ0IG9mIHRoaXMgdGhlc2lzIGV4YW1pbmVzIHRo ZSBzcGFjZSAiYmVsb3cgQlFQ4oCdIGFuZCBkZXNjcmliZXMgYSBudQ0KIG1iZXIgb2Ygc3ViLXVu aXZlcnNhbCBtb2RlbHMgb2YgcXVhbnR1bSBjb21wdXRhdGlvbiB3aGljaCBjYW4gbmV2ZXJ0aGVs ZXNzIA0KIHBlcmZvcm0gc2FtcGxpbmcgdGFza3Mgd2hpY2ggYXJlIGRpZmZpY3VsdCBmb3IgY2xh c3NpY2FsIGNvbXB1dGVycy4gV2Ugc2hvdw0KICB0aGF0IHByaW9yIG1vZGVscyBtYWludGFpbiBo YXJkbmVzcyB3aGVuIHRoZWlyIHNldCBvZiBxdWFudHVtIG9wZXJhdGlvbnMgaQ0KIHMgcmVzdHJp Y3RlZFwsIGFuZCBkZXNjcmliZSB0d28gbmV3IG1vZGVscyBvZiDigJx3ZWFr4oCdIHF1YW50dW0g Y29tcHV0YXRpb24gd2gNCiBpY2ggYWxzbyBzaG93IGFkdmFudGFnZSBvdmVyIGNsYXNzaWNhbCBk ZXZpY2VzLiBBIG1ham9yIHRoZW1lIGluIHRoaXMgd29yayANCiBpcyB0aGF0IGFsbW9zdCBhbnkg d2VhayBkZXZpY2UgY2FuIHBlcmZvcm0gaGFyZCBzYW1wbGluZyB0YXNrcy4gV2UgZmluZCB0aGEN CiB0IGFsbW9zdCBhbnkgbW9kZWwgd2hpY2ggaXMgbm90IHVuaXZlcnNhbFwsIGJ1dCBub3Qga25v d24gdG8gYmUgZWZmaWNpZW50bHkNCiAgY2xhc3NpY2FsbHkgc2ltdWxhYmxlXCwgYWRtaXRzIGEg c3BlZWR1cCBvdmVyIGNsYXNzaWNhbCBjb21wdXRpbmcgZm9yIHNhbXANCiBsaW5nIHRhc2tzIHVu ZGVyIHBsYXVzaWJsZSBhc3N1bXB0aW9ucy4gVGhpcyB3b3JrIGNhbiBiZSBzZWVuIGFzIHByb2dy ZXNzIHQNCiBvd2FyZHMgY2xhc3NpZnlpbmcgdGhlIHBvd2VyIG9mIGFsbCByZXN0cmljdGVkIHF1 YW50dW0gZ2F0ZSBzZXRzLlxuXG4gXG5cbk8NCiBuIHRoZSBvdGhlciBoYW5kXCwgcmVjZW50IGRl dmVsb3BtZW50cyBpbiBxdWFudHVtIGdyYXZpdHkgaGF2ZSBvcGVuZWQgdXAgdGgNCiBlIHBvc3Np YmlsaXR5IG9mIG1vZGlmeWluZyBxdWFudHVtIG1lY2hhbmljcyB0byByZXNvbHZlIHRoZSBibGFj ayBob2xlIGluZm8NCiBybWF0aW9uIHBhcmFkb3guIEluc3BpcmVkIGJ5IHRoZXNlIGRlYmF0ZXNc LCB0aGUgc2Vjb25kIHBhcnQgb2YgdGhpcyB0aGVzaXMNCiAgZXhwbG9yZXMgdGhlIHNwYWNlIOKA nGFib3ZlIEJRUOKAnSAtIGkuZS4gdGhlIHBvd2VyIG9mIHF1YW50dW0gY29tcHV0ZXJzIGluIHRo DQogZSBwcmVzZW5jZSBvZiBtb2RpZmllZCB0aGVvcmllcyBvZiBxdWFudHVtIG1lY2hhbmljcy4g V2UgZmluZCB0aGF0IGFsbW9zdCBhDQogbGwgbW9kaWZpY2F0aW9ucyBhbGxvdyBmb3IgZHJhc3Rp Y2FsbHkgbW9yZSBwb3dlciB0aGFuIEJRUFwsIGFuZCBmaW5kIHRoYXQgDQogdGhlc2Ugc3BlZWR1 cHMgbWF5IGJlIHJlbGF0ZWQgdG8gc3VwZXJsdW1pbmFsIHNpZ25hbGluZyBpbiB0aGVzZSBtb2Rl bHMuIFN1DQogcnByaXNpbmdseVwsIHdlIGZpbmQgb25lIG1vZGVsIHdoaWNoIGlzIG1lcmVseSBq dXN0IGEgYml0IG1vcmUgcG93ZXJmdWwgdGhhDQogbiBCUVAuIEluc3BpcmVkIGJ5IHRoaXMgbW9k ZWwg4oCcanVzdCBhYm92ZeKAnSBCUVBcLCB3ZSBzdHVkeSBhbmQgcmVzb2x2ZSBhbiBvcA0KIGVu IHByb2JsZW0gaW4gY2xhc3NpY2FsIGNvbXBsZXhpdHkgcmVsYXRlZCB0byB0aGUgcG93ZXIgb2Yg c3RhdGlzdGljYWwtemVybw0KICBrbm93bGVkZ2UgcHJvb2Ygc3lzdGVtcy5cbiBcbk1lbWJlcnMg b2YgY29tbWl0dGVlOiBTY290dCBBYXJvbnNvblwsIEFyYW0gSA0KIGFycm93XCwgUnlhbiBXaWxs aWFtc1xuIFxuDQpMQVNULU1PRElGSUVEOjIwMTcwNjI4VDEwMjIwNA0KTE9DQVRJT046RzU3NQ0K U1VNTUFSWTpBZGFtIEJvdWxhbmQ6IFRoZXNpcyBEZWZlbnNlOiBUaGUgc3BhY2UgYXJvdW5kIEJR UA0KRU5EOlZFVkVOVA0KRU5EOlZDQUxFTkRBUg0K --===============4080300471395520625==--