{"data":{"id":"10.48550/arxiv.1412.6062","type":"dois","attributes":{"doi":"10.48550/arxiv.1412.6062","prefix":"10.48550","suffix":"arxiv.1412.6062","identifiers":[{"identifier":"1412.6062","identifierType":"arXiv"}],"alternateIdentifiers":[{"alternateIdentifierType":"arXiv","alternateIdentifier":"1412.6062"}],"creators":[{"name":"Farhi, Edward","nameType":"Personal","givenName":"Edward","familyName":"Farhi","affiliation":[],"nameIdentifiers":[]},{"name":"Goldstone, Jeffrey","nameType":"Personal","givenName":"Jeffrey","familyName":"Goldstone","affiliation":[],"nameIdentifiers":[]},{"name":"Gutmann, Sam","nameType":"Personal","givenName":"Sam","familyName":"Gutmann","affiliation":[],"nameIdentifiers":[]}],"titles":[{"title":"A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem"}],"publisher":"arXiv","container":{},"publicationYear":2014,"subjects":[{"lang":"en","subject":"Quantum Physics (quant-ph)","subjectScheme":"arXiv"},{"subject":"FOS: Physical sciences","subjectScheme":"Fields of Science and Technology (FOS)"},{"subject":"FOS: Physical sciences","schemeUri":"http://www.oecd.org/science/inno/38235147.pdf","subjectScheme":"Fields of Science and Technology (FOS)"}],"contributors":[],"dates":[{"date":"2014-12-18T20:38:18Z","dateType":"Submitted","dateInformation":"v1"},{"date":"2014-12-19T01:15:26Z","dateType":"Updated","dateInformation":"v1"},{"date":"2015-06-25T17:43:01Z","dateType":"Submitted","dateInformation":"v2"},{"date":"2015-06-26T00:12:19Z","dateType":"Updated","dateInformation":"v2"},{"date":"2014-12","dateType":"Available","dateInformation":"v1"},{"date":"2014","dateType":"Issued"}],"language":null,"types":{"ris":"GEN","bibtex":"misc","citeproc":"article","schemaOrg":"CreativeWork","resourceType":"Article","resourceTypeGeneral":"Preprint"},"relatedIdentifiers":[],"relatedItems":[],"sizes":[],"formats":[],"version":"2","rightsList":[{"rights":"arXiv.org perpetual, non-exclusive license","rightsUri":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/"}],"descriptions":[{"description":"We apply our recent Quantum Approximate Optimization Algorithm to the combinatorial problem of bounded occurrence Max E3LIN2. The input is a set of linear equations each of which contains exactly three boolean variables and each equation says that the sum of the variables mod 2 is 0 or is 1. Every variable is in no more than D equations. A random string will satisfy 1/2 of the equations. We show that the level one QAOA will efficiently produce a string that satisfies $\\left(\\frac{1}{2} + \\frac{1}{101 D^{1/2}\\, l n\\, D}\\right)$ times the number of equations. A recent classical algorithm achieved $\\left(\\frac{1}{2} + \\frac{constant}{D^{1/2}}\\right)$. We also show that in the typical case the quantum computer will output a string that satisfies $\\left(\\frac{1}{2}+ \\frac{1}{2\\sqrt{3e}\\, D^{1/2}}\\right)$ times the number of equations.","descriptionType":"Abstract"},{"description":"This version contains a tighter analysis that leads to stronger results on the performance of the quantum algorithm","descriptionType":"Other"}],"geoLocations":[],"fundingReferences":[],"xml":"PD94bWwgdmVyc2lvbj0iMS4wIiBlbmNvZGluZz0idXRmLTgiPz4KPHJlc291cmNlIHhtbG5zPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCIgeG1sbnM6eHNpPSJodHRwOi8vd3d3LnczLm9yZy8yMDAxL1hNTFNjaGVtYS1pbnN0YW5jZSIgeHNpOnNjaGVtYUxvY2F0aW9uPSJodHRwOi8vZGF0YWNpdGUub3JnL3NjaGVtYS9rZXJuZWwtNCBodHRwOi8vc2NoZW1hLmRhdGFjaXRlLm9yZy9tZXRhL2tlcm5lbC00LjMvbWV0YWRhdGEueHNkIj4KICA8aWRlbnRpZmllciBpZGVudGlmaWVyVHlwZT0iRE9JIj4xMC40ODU1MC9BUlhJVi4xNDEyLjYwNjI8L2lkZW50aWZpZXI+CiAgPGFsdGVybmF0ZUlkZW50aWZpZXJzPgogICAgPGFsdGVybmF0ZUlkZW50aWZpZXIgYWx0ZXJuYXRlSWRlbnRpZmllclR5cGU9ImFyWGl2Ij4xNDEyLjYwNjI8L2FsdGVybmF0ZUlkZW50aWZpZXI+CiAgPC9hbHRlcm5hdGVJZGVudGlmaWVycz4KICA8Y3JlYXRvcnM+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+RmFyaGksIEVkd2FyZDwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+RWR3YXJkPC9naXZlbk5hbWU+CiAgICAgIDxmYW1pbHlOYW1lPkZhcmhpPC9mYW1pbHlOYW1lPgogICAgPC9jcmVhdG9yPgogICAgPGNyZWF0b3I+CiAgICAgIDxjcmVhdG9yTmFtZSBuYW1lVHlwZT0iUGVyc29uYWwiPkdvbGRzdG9uZSwgSmVmZnJleTwvY3JlYXRvck5hbWU+CiAgICAgIDxnaXZlbk5hbWU+SmVmZnJleTwvZ2l2ZW5OYW1lPgogICAgICA8ZmFtaWx5TmFtZT5Hb2xkc3RvbmU8L2ZhbWlseU5hbWU+CiAgICA8L2NyZWF0b3I+CiAgICA8Y3JlYXRvcj4KICAgICAgPGNyZWF0b3JOYW1lIG5hbWVUeXBlPSJQZXJzb25hbCI+R3V0bWFubiwgU2FtPC9jcmVhdG9yTmFtZT4KICAgICAgPGdpdmVuTmFtZT5TYW08L2dpdmVuTmFtZT4KICAgICAgPGZhbWlseU5hbWU+R3V0bWFubjwvZmFtaWx5TmFtZT4KICAgIDwvY3JlYXRvcj4KICA8L2NyZWF0b3JzPgogIDx0aXRsZXM+CiAgICA8dGl0bGU+QSBRdWFudHVtIEFwcHJveGltYXRlIE9wdGltaXphdGlvbiBBbGdvcml0aG0gQXBwbGllZCB0byBhIEJvdW5kZWQgT2NjdXJyZW5jZSBDb25zdHJhaW50IFByb2JsZW08L3RpdGxlPgogIDwvdGl0bGVzPgogIDxwdWJsaXNoZXI+YXJYaXY8L3B1Ymxpc2hlcj4KICA8cHVibGljYXRpb25ZZWFyPjIwMTQ8L3B1YmxpY2F0aW9uWWVhcj4KICA8c3ViamVjdHM+CiAgICA8c3ViamVjdCB4bWw6bGFuZz0iZW4iIHN1YmplY3RTY2hlbWU9ImFyWGl2Ij5RdWFudHVtIFBoeXNpY3MgKHF1YW50LXBoKTwvc3ViamVjdD4KICAgIDxzdWJqZWN0IHN1YmplY3RTY2hlbWU9IkZpZWxkcyBvZiBTY2llbmNlIGFuZCBUZWNobm9sb2d5IChGT1MpIj5GT1M6IFBoeXNpY2FsIHNjaWVuY2VzPC9zdWJqZWN0PgogIDwvc3ViamVjdHM+CiAgPGRhdGVzPgogICAgPGRhdGUgZGF0ZVR5cGU9IlN1Ym1pdHRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAxNC0xMi0xOFQyMDozODoxOFo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iVXBkYXRlZCIgZGF0ZUluZm9ybWF0aW9uPSJ2MSI+MjAxNC0xMi0xOVQwMToxNToyNlo8L2RhdGU+CiAgICA8ZGF0ZSBkYXRlVHlwZT0iU3VibWl0dGVkIiBkYXRlSW5mb3JtYXRpb249InYyIj4yMDE1LTA2LTI1VDE3OjQzOjAxWjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJVcGRhdGVkIiBkYXRlSW5mb3JtYXRpb249InYyIj4yMDE1LTA2LTI2VDAwOjEyOjE5WjwvZGF0ZT4KICAgIDxkYXRlIGRhdGVUeXBlPSJBdmFpbGFibGUiIGRhdGVJbmZvcm1hdGlvbj0idjEiPjIwMTQtMTI8L2RhdGU+CiAgPC9kYXRlcz4KICA8cmVzb3VyY2VUeXBlIHJlc291cmNlVHlwZUdlbmVyYWw9IlByZXByaW50Ij5BcnRpY2xlPC9yZXNvdXJjZVR5cGU+CiAgPHZlcnNpb24+MjwvdmVyc2lvbj4KICA8cmlnaHRzTGlzdD4KICAgIDxyaWdodHMgcmlnaHRzVVJJPSJodHRwOi8vYXJ4aXYub3JnL2xpY2Vuc2VzL25vbmV4Y2x1c2l2ZS1kaXN0cmliLzEuMC8iPmFyWGl2Lm9yZyBwZXJwZXR1YWwsIG5vbi1leGNsdXNpdmUgbGljZW5zZTwvcmlnaHRzPgogIDwvcmlnaHRzTGlzdD4KICA8ZGVzY3JpcHRpb25zPgogICAgPGRlc2NyaXB0aW9uIGRlc2NyaXB0aW9uVHlwZT0iQWJzdHJhY3QiPldlIGFwcGx5IG91ciByZWNlbnQgUXVhbnR1bSBBcHByb3hpbWF0ZSBPcHRpbWl6YXRpb24gQWxnb3JpdGhtIHRvIHRoZSBjb21iaW5hdG9yaWFsIHByb2JsZW0gb2YgYm91bmRlZCBvY2N1cnJlbmNlIE1heCBFM0xJTjIuIFRoZSBpbnB1dCBpcyBhIHNldCBvZiBsaW5lYXIgZXF1YXRpb25zIGVhY2ggb2Ygd2hpY2ggY29udGFpbnMgZXhhY3RseSB0aHJlZSBib29sZWFuIHZhcmlhYmxlcyBhbmQgZWFjaCBlcXVhdGlvbiBzYXlzIHRoYXQgdGhlIHN1bSBvZiB0aGUgdmFyaWFibGVzIG1vZCAyIGlzIDAgb3IgaXMgMS4gRXZlcnkgdmFyaWFibGUgaXMgaW4gbm8gbW9yZSB0aGFuIEQgZXF1YXRpb25zLiBBIHJhbmRvbSBzdHJpbmcgd2lsbCBzYXRpc2Z5IDEvMiBvZiB0aGUgZXF1YXRpb25zLiBXZSBzaG93IHRoYXQgdGhlIGxldmVsIG9uZSBRQU9BIHdpbGwgZWZmaWNpZW50bHkgcHJvZHVjZSBhIHN0cmluZyB0aGF0IHNhdGlzZmllcyAkXGxlZnQoXGZyYWN7MX17Mn0gKyBcZnJhY3sxfXsxMDEgRF57MS8yfVwsIGwgblwsIER9XHJpZ2h0KSQgdGltZXMgdGhlIG51bWJlciBvZiBlcXVhdGlvbnMuIEEgcmVjZW50IGNsYXNzaWNhbCBhbGdvcml0aG0gYWNoaWV2ZWQgJFxsZWZ0KFxmcmFjezF9ezJ9ICsgXGZyYWN7Y29uc3RhbnR9e0ReezEvMn19XHJpZ2h0KSQuIFdlIGFsc28gc2hvdyB0aGF0IGluIHRoZSB0eXBpY2FsIGNhc2UgdGhlIHF1YW50dW0gY29tcHV0ZXIgd2lsbCBvdXRwdXQgYSBzdHJpbmcgdGhhdCBzYXRpc2ZpZXMgJFxsZWZ0KFxmcmFjezF9ezJ9KyBcZnJhY3sxfXsyXHNxcnR7M2V9XCwgRF57MS8yfX1ccmlnaHQpJCB0aW1lcyB0aGUgbnVtYmVyIG9mIGVxdWF0aW9ucy48L2Rlc2NyaXB0aW9uPgogICAgPGRlc2NyaXB0aW9uIGRlc2NyaXB0aW9uVHlwZT0iT3RoZXIiPlRoaXMgdmVyc2lvbiBjb250YWlucyBhIHRpZ2h0ZXIgYW5hbHlzaXMgdGhhdCBsZWFkcyB0byBzdHJvbmdlciByZXN1bHRzIG9uIHRoZSBwZXJmb3JtYW5jZSBvZiB0aGUgcXVhbnR1bSBhbGdvcml0aG08L2Rlc2NyaXB0aW9uPgogIDwvZGVzY3JpcHRpb25zPgo8L3Jlc291cmNlPg==","url":"https://arxiv.org/abs/1412.6062","contentUrl":null,"metadataVersion":0,"schemaVersion":"http://datacite.org/schema/kernel-4","source":"mds","isActive":true,"state":"findable","reason":null,"viewCount":0,"viewsOverTime":[],"downloadCount":0,"downloadsOverTime":[],"referenceCount":0,"citationCount":1,"citationsOverTime":[{"year":"2022","total":1}],"partCount":0,"partOfCount":0,"versionCount":0,"versionOfCount":0,"created":"2022-03-08T23:35:32.000Z","registered":"2022-03-08T23:35:33.000Z","published":"2014","updated":"2022-03-08T23:35:33.000Z"},"relationships":{"client":{"data":{"id":"arxiv.content","type":"clients"}},"provider":{"data":{"id":"arxiv","type":"providers"}},"media":{"data":{"id":"10.48550/arxiv.1412.6062","type":"media"}},"references":{"data":[]},"citations":{"data":[{"id":"10.1038/s42254-022-00440-8","type":"dois"}]},"parts":{"data":[]},"partOf":{"data":[]},"versions":{"data":[]},"versionOf":{"data":[]}}}}