{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:51:51Z","timestamp":1750308711119,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":38,"publisher":"ACM","license":[{"start":{"date-parts":[[2013,1,9]],"date-time":"2013-01-09T00:00:00Z","timestamp":1357689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2013,1,9]]},"DOI":"10.1145\/2422436.2422475","type":"proceedings-article","created":{"date-parts":[[2013,1,3]],"date-time":"2013-01-03T12:58:22Z","timestamp":1357217902000},"page":"329-352","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Stronger methods of making quantum interactive proofs perfectly complete"],"prefix":"10.1145","author":[{"given":"Hirotada","family":"Kobayashi","sequence":"first","affiliation":[{"name":"National Institute of Informatics, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fran\u00e7ois","family":"Le Gall","sequence":"additional","affiliation":[{"name":"The University of Tokyo, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Harumichi","family":"Nishimura","sequence":"additional","affiliation":[{"name":"Nagoya University, Nagoya, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,1,9]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_1_1_1","DOI":"10.1145\/1536414.1536472"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.1109\/FOCS.2011.91"},{"key":"e_1_3_2_1_3_1","volume-title":"On perfect completeness for QMA. Quantum Information and Computation, 9(1--2):0081--0089","author":"Aaronson Scott","year":"2009","unstructured":"Scott Aaronson . On perfect completeness for QMA. Quantum Information and Computation, 9(1--2):0081--0089 , 2009 . Scott Aaronson. On perfect completeness for QMA. Quantum Information and Computation, 9(1--2):0081--0089, 2009."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_4_1","DOI":"10.1109\/FOCS.2011.58"},{"key":"e_1_3_2_1_5_1","volume-title":"A simple proof that Toffoli and Hadamard are quantum universal. arXiv.org e-Print archive,arXiv:quant-ph\/0301040","author":"Aharonov Dorit","year":"2003","unstructured":"Dorit Aharonov . A simple proof that Toffoli and Hadamard are quantum universal. arXiv.org e-Print archive,arXiv:quant-ph\/0301040 , 2003 . Dorit Aharonov. A simple proof that Toffoli and Hadamard are quantum universal. arXiv.org e-Print archive,arXiv:quant-ph\/0301040, 2003."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_6_1","DOI":"10.1145\/276698.276708"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_7_1","DOI":"10.1145\/278298.278306"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_8_1","DOI":"10.1145\/273865.273901"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_9_1","DOI":"10.1145\/22145.22192"},{"key":"e_1_3_2_1_10_1","volume-title":"Efficient algorithm for a quantum analogue of 2-SAT. arXiv.org e-Print archive,arXiv:quant-ph\/0602108","author":"Bravyi Sergey","year":"2006","unstructured":"Sergey Bravyi . Efficient algorithm for a quantum analogue of 2-SAT. arXiv.org e-Print archive,arXiv:quant-ph\/0602108 , 2006 . Sergey Bravyi. Efficient algorithm for a quantum analogue of 2-SAT. arXiv.org e-Print archive,arXiv:quant-ph\/0602108, 2006."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.4086\/toc.2011.v007a007"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.1016\/0024-3795(75)90075-0"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_13_1","DOI":"10.1007\/s00220-007-0189-3"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_14_1","DOI":"10.1016\/S0019-9958(84)80056-X"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_15_1","DOI":"10.1145\/237814.237866"},{"key":"e_1_3_2_1_16_1","volume-title":"QMA variants with polynomially many provers. arXiv.org e-Print archive,arXiv:1108.0617 {quant-ph}","author":"Gharibian Sevag","year":"2011","unstructured":"Sevag Gharibian , Jamie Sikora , and Sarvagya Upadhyay . QMA variants with polynomially many provers. arXiv.org e-Print archive,arXiv:1108.0617 {quant-ph} , 2011 . Sevag Gharibian, Jamie Sikora, and Sarvagya Upadhyay. QMA variants with polynomially many provers. arXiv.org e-Print archive,arXiv:1108.0617 {quant-ph}, 2011."},{"key":"e_1_3_2_1_18_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1007\/978-3-642-22670-0_6","volume-title":"Studies in Complexity and Cryptography, Miscellanea on the Interplay between Randomness and Computation","author":"Goldreich Oded","year":"2011","unstructured":"Oded Goldreich and David Zuckerman . Another proof that BPP \u2286 \u00b6H (and more) . In Oded Goldreich, editor, Studies in Complexity and Cryptography, Miscellanea on the Interplay between Randomness and Computation , volume 6650 of Lecture Notes in Computer Science , pages 40 -- 53 . Springer-Verlag , 2011 . Electronic Colloquium on Computational Complexity, Report TR97-045, 1997. Oded Goldreich and David Zuckerman. Another proof that BPP \u2286 \u00b6H (and more). In Oded Goldreich, editor, Studies in Complexity and Cryptography, Miscellanea on the Interplay between Randomness and Computation, volume 6650 of Lecture Notes in Computer Science, pages 40--53. Springer-Verlag, 2011. Electronic Colloquium on Computational Complexity, Report TR97-045, 1997."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.1016\/0034-4877(72)90011-0"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_20_1","DOI":"10.1145\/2049697.2049704"},{"key":"e_1_3_2_1_21_1","volume-title":"Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems. Quantum Information and Computation, 12(5--6):0461--0471","author":"Jordan Stephen P.","year":"2012","unstructured":"Stephen P. Jordan , Hirotada Kobayashi , Daniel Nagaj , and Harumichi Nishimura . Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems. Quantum Information and Computation, 12(5--6):0461--0471 , 2012 . Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj, and Harumichi Nishimura. Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems. Quantum Information and Computation, 12(5--6):0461--0471, 2012."},{"key":"e_1_3_2_1_22_1","volume-title":"DePaul University","author":"Kitaev Yu.","year":"1999","unstructured":"Alexeirelax Yu. Kitaev . Quantum NP. Talk at the 2nd Workshop on Algorithms in Quantum Information Processing , DePaul University , Chicago , January 1999 . AlexeirelaxYu. Kitaev. Quantum NP. Talk at the 2nd Workshop on Algorithms in Quantum Information Processing, DePaul University, Chicago, January 1999."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_23_1","DOI":"10.1007\/s00037-009-0275-3"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_25_1","DOI":"10.1063\/1.2146188"},{"key":"e_1_3_2_1_26_1","series-title":"Graduate Studies in Mathematics","doi-asserted-by":"crossref","DOI":"10.1090\/gsm\/047","volume-title":"Classical and Quantum Computation","author":"Kitaev Yu.","year":"2002","unstructured":"Alexeirelax Yu. Kitaev , Alexander H. Shen , and Mikhail N. Vyalyi . Classical and Quantum Computation , volume 47 of Graduate Studies in Mathematics . American Mathematical Society , 2002 . AlexeirelaxYu. Kitaev, Alexander H. Shen, and Mikhail N. Vyalyi. Classical and Quantum Computation, volume 47 of Graduate Studies in Mathematics. American Mathematical Society, 2002."},{"key":"e_1_3_2_1_27_1","volume-title":"How hard is it to approximate the Jones polynomial? arXiv.org e-print archive,arXiv:0908.0512 {quant-ph}","author":"Kuperberg Greg","year":"2009","unstructured":"Greg Kuperberg . How hard is it to approximate the Jones polynomial? arXiv.org e-print archive,arXiv:0908.0512 {quant-ph} , 2009 . Greg Kuperberg. How hard is it to approximate the Jones polynomial? arXiv.org e-print archive,arXiv:0908.0512 {quant-ph}, 2009."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_28_1","DOI":"10.1145\/335305.335387"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_29_1","DOI":"10.1007\/s00037-005-0194-x"},{"key":"e_1_3_2_1_30_1","volume-title":"Quantum Computation and Quantum Information","author":"Nielsen Michael A.","year":"2000","unstructured":"Michael A. Nielsen and Isaac L. Chuang . Quantum Computation and Quantum Information . Cambridge University Press , 2000 . Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_31_1","DOI":"10.1103\/PhysRevA.67.012304"},{"key":"e_1_3_2_1_32_1","volume-title":"Fast amplification of QMA. Quantum Information and Computation, 9(11--12):1053--1068","author":"Nagaj Daniel","year":"2009","unstructured":"Daniel Nagaj , Pawel Wocjan , and Yong Zhang . Fast amplification of QMA. Quantum Information and Computation, 9(11--12):1053--1068 , 2009 . Daniel Nagaj, Pawel Wocjan, and Yong Zhang. Fast amplification of QMA. Quantum Information and Computation, 9(11--12):1053--1068, 2009."},{"issue":"1","key":"e_1_3_2_1_33_1","first-page":"084","article-title":"Both Toffoli and Controlled-NOT need little help to do universal quantum computing","volume":"3","author":"Shi Yaoyun","year":"2002","unstructured":"Yaoyun Shi . Both Toffoli and Controlled-NOT need little help to do universal quantum computing . Quantum Information and Computation , 3 ( 1 ): 084 -- 092 , 2002 . Yaoyun Shi. Both Toffoli and Controlled-NOT need little help to do universal quantum computing. Quantum Information and Computation, 3(1):084--092, 2002.","journal-title":"Quantum Information and Computation"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_34_1","DOI":"10.5555\/874062.875509"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_35_1","DOI":"10.1103\/PhysRevA.65.012310"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_37_1","DOI":"10.5555\/795666.796590"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_38_1","DOI":"10.1016\/S0304-3975(01)00375-9"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_39_1","DOI":"10.1007\/978-0-387-30440-3_428"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_40_1","DOI":"10.1137\/060670997"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_41_1","DOI":"10.5555\/36624.36655"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"ITCS '13","name":"ITCS '13: Innovations in Theoretical Computer Science","location":"Berkeley California USA"},"container-title":["Proceedings of the 4th conference on Innovations in Theoretical Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2422436.2422475","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2422436.2422475","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:14:14Z","timestamp":1750277654000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2422436.2422475"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,9]]},"references-count":38,"alternative-id":["10.1145\/2422436.2422475","10.1145\/2422436"],"URL":"https:\/\/doi.org\/10.1145\/2422436.2422475","relation":{},"subject":[],"published":{"date-parts":[[2013,1,9]]},"assertion":[{"value":"2013-01-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}