{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T07:30:31Z","timestamp":1784359831781,"version":"3.55.0"},"update-to":[{"DOI":"10.1371\/journal.pcbi.1011033","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2023,4,24]],"date-time":"2023-04-24T00:00:00Z","timestamp":1682294400000}}],"reference-count":40,"publisher":"Public Library of Science (PLoS)","issue":"4","license":[{"start":{"date-parts":[[2023,4,12]],"date-time":"2023-04-12T00:00:00Z","timestamp":1681257600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000024","name":"Canadian Institutes of Health Research","doi-asserted-by":"publisher","award":["PJT-159750"],"award-info":[{"award-number":["PJT-159750"]}],"id":[{"id":"10.13039\/501100000024","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["www.ploscompbiol.org"],"crossmark-restriction":false},"short-container-title":["PLoS Comput Biol"],"abstract":"<jats:p>Protein design is a technique to engineer proteins by permuting amino acids in the sequence to obtain novel functionalities. However, exploring all possible combinations of amino acids is generally impossible due to the exponential growth of possibilities with the number of designable sites. The present work introduces circuits implementing a pure quantum approach, Grover\u2019s algorithm, to solve protein design problems. Our algorithms can adjust to implement any custom pair-wise energy tables and protein structure models. Moreover, the algorithm\u2019s oracle is designed to consist of only adder functions. Quantum computer simulators validate the practicality of our circuits, containing up to 234 qubits. However, a smaller circuit is implemented on real quantum devices. Our results show that using<jats:inline-formula id=\"pcbi.1011033.e001\"><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" id=\"pcbi.1011033.e001g\" mimetype=\"image\" position=\"anchor\" xlink:href=\"info:doi\/10.1371\/journal.pcbi.1011033.e001\" xlink:type=\"simple\"\/><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" id=\"M1\"><mml:mi mathvariant=\"script\">O<\/mml:mi><mml:mo>(<\/mml:mo><mml:msqrt><mml:mi>N<\/mml:mi><\/mml:msqrt><mml:mo>)<\/mml:mo><\/mml:math><\/jats:alternatives><\/jats:inline-formula>iterations, the circuits find the correct results among all<jats:italic>N<\/jats:italic>possibilities, providing the expected quadratic speed up of Grover\u2019s algorithm over classical methods (i.e.,<jats:inline-formula id=\"pcbi.1011033.e002\"><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" id=\"pcbi.1011033.e002g\" mimetype=\"image\" position=\"anchor\" xlink:href=\"info:doi\/10.1371\/journal.pcbi.1011033.e002\" xlink:type=\"simple\"\/><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" display=\"inline\" id=\"M2\"><mml:mi mathvariant=\"script\">O<\/mml:mi><mml:mo>(<\/mml:mo><mml:mi>N<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:math><\/jats:alternatives><\/jats:inline-formula>).<\/jats:p>","DOI":"10.1371\/journal.pcbi.1011033","type":"journal-article","created":{"date-parts":[[2023,4,12]],"date-time":"2023-04-12T17:41:19Z","timestamp":1681321279000},"page":"e1011033","update-policy":"https:\/\/doi.org\/10.1371\/journal.pcbi.corrections_policy","source":"Crossref","is-referenced-by-count":21,"title":["Gate-based quantum computing for protein design"],"prefix":"10.1371","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1340-1087","authenticated-orcid":true,"given":"Mohammad Hassan","family":"Khatami","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Udson C.","family":"Mendes","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nathan","family":"Wiebe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3683-152X","authenticated-orcid":true,"given":"Philip M.","family":"Kim","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"340","published-online":{"date-parts":[[2023,4,12]]},"reference":[{"key":"pcbi.1011033.ref001","doi-asserted-by":"crossref","first-page":"779","DOI":"10.1093\/protein\/15.10.779","article-title":"Protein design is NP-hard","volume":"15","author":"NA Pierce","year":"2002","journal-title":"Protein Eng"},{"key":"pcbi.1011033.ref002","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1145\/1008304.1008305","article-title":"Postscript about NP-hard problems","volume":"6","author":"DE Knuth","year":"1974","journal-title":"ACM SIGACT News"},{"key":"pcbi.1011033.ref003","volume-title":"Quantum computation and quantum information","author":"MA Nielsen","year":"2010"},{"key":"pcbi.1011033.ref004","doi-asserted-by":"crossref","first-page":"1501","DOI":"10.1021\/bi00327a032","article-title":"Theory for the folding and stability of globular proteins","volume":"24","author":"KA Dill","year":"1985","journal-title":"Biochemistry"},{"key":"pcbi.1011033.ref005","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1093\/protein\/7.9.1059","article-title":"The protein threading problem with sequence amino acid interaction preferences is NP-complete","volume":"7","author":"RH Lathrop","year":"1994","journal-title":"Protein Engineering, Design and Selection."},{"key":"pcbi.1011033.ref006","doi-asserted-by":"crossref","DOI":"10.1201\/b14835","volume-title":"Markov chain Monte Carlo in practice","author":"WR Gilks","year":"1995"},{"key":"pcbi.1011033.ref007","doi-asserted-by":"crossref","DOI":"10.1201\/9781482296426","volume-title":"Markov chain Monte Carlo: stochastic simulation for Bayesian inference","author":"D Gamerman","year":"2006"},{"key":"pcbi.1011033.ref008","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1109\/TCBB.2008.124","article-title":"Protein design by sampling an undirected graphical model of residue constraints","volume":"6","author":"J Thomas","year":"2008","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"key":"pcbi.1011033.ref009","doi-asserted-by":"crossref","first-page":"e1005722","DOI":"10.1371\/journal.pcbi.1005722","article-title":"Data driven flexible backbone protein design.","volume":"13","author":"MGF Sun","year":"2017","journal-title":"PLoS Comput Biol"},{"key":"pcbi.1011033.ref010","article-title":"De novo protein design by deep network hallucination.","author":"I Anishchenko","year":"2020","journal-title":"bioRxiv."},{"key":"pcbi.1011033.ref011","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/srep00571","article-title":"Finding low-energy conformations of lattice protein models by quantum annealing.","volume":"2","author":"A Perdomo-Ortiz","year":"2012","journal-title":"Sci Rep."},{"key":"pcbi.1011033.ref012","article-title":"others. Coarse-grained lattice protein folding on a quantum annealer.","author":"T Babej","year":"2018","journal-title":"arXiv preprint arXiv:181100713."},{"key":"pcbi.1011033.ref013","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41534-021-00368-4","article-title":"Resource-efficient quantum algorithm for protein folding.","volume":"7","author":"A Robert","year":"2021","journal-title":"npj Quantum Inf."},{"key":"pcbi.1011033.ref014","article-title":"others. A quantum alternating operator ansatz with hard and soft constraints for lattice protein folding","author":"M Fingerhuth","year":"2018","journal-title":"arXiv preprint arXiv:181013411."},{"key":"pcbi.1011033.ref015","article-title":"A quantum approximate optimization algorithm.","author":"E Farhi","year":"2014","journal-title":"arXiv preprint arXiv:14114028."},{"key":"pcbi.1011033.ref016","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/ncomms5213","article-title":"A variational eigenvalue solver on a photonic quantum processor.","volume":"5","author":"A Peruzzo","year":"2014","journal-title":"Nat Commun"},{"key":"pcbi.1011033.ref017","article-title":"Quantum annealing.","author":"F Ruiz A de la","year":"2014","journal-title":"arXiv"},{"key":"pcbi.1011033.ref018","first-page":"752485","article-title":"Designing peptides on a quantum computer","author":"VK Mulligan","year":"2020","journal-title":"bioRxiv"},{"key":"pcbi.1011033.ref019","doi-asserted-by":"crossref","first-page":"e32637","DOI":"10.1371\/journal.pone.0032637","article-title":"Incorporation of noncanonical amino acids into Rosetta and use in computational protein-peptide interface design","volume":"7","author":"PD Renfrew","year":"2012","journal-title":"PLoS One"},{"key":"pcbi.1011033.ref020","doi-asserted-by":"crossref","unstructured":"Grover LK. A fast quantum mechanical algorithm for database search. Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. 1996; 212\u2013219.","DOI":"10.1145\/237814.237866"},{"key":"pcbi.1011033.ref021","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1038\/nature03347","article-title":"Experimental one-way quantum computing","volume":"434","author":"P Walther","year":"2005","journal-title":"Nature"},{"key":"pcbi.1011033.ref022","article-title":"A quantum algorithm for finding the minimum.","author":"C Durr","year":"1996","journal-title":"arXiv preprint quant-ph\/9607014."},{"key":"pcbi.1011033.ref023","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1109\/SFCS.1994.365700","article-title":"Algorithms for quantum computation: discrete logarithms and factoring","author":"PW Shor","year":"1994","journal-title":"Proceedings 35th annual symposium on foundations of computer science."},{"key":"pcbi.1011033.ref024","doi-asserted-by":"crossref","first-page":"553","DOI":"10.1098\/rspa.1992.0167","article-title":"Rapid solution of problems by quantum computation","volume":"439","author":"D Deutsch","year":"1992","journal-title":"Proc R Soc Lond A Math Phys Sci"},{"key":"pcbi.1011033.ref025","article-title":"Study of Decoherence in Quantum Computers: A Circuit-Design Perspective.","author":"AA Saki","year":"2019","journal-title":"arXiv preprint arXiv:190404323."},{"key":"pcbi.1011033.ref026","doi-asserted-by":"crossref","first-page":"3031","DOI":"10.1021\/acs.jctc.7b00125","article-title":"The Rosetta all-atom energy function for macromolecular modeling and design.","volume":"13","author":"RF Alford","year":"2017","journal-title":"J Chem Theory Comput"},{"key":"pcbi.1011033.ref027","article-title":"Quantum algorithms and circuits for scientific computing","author":"MK Bhaskar","year":"2015","journal-title":"arXiv preprint arXiv:151108253"},{"key":"pcbi.1011033.ref028","doi-asserted-by":"crossref","first-page":"147902","DOI":"10.1103\/PhysRevLett.91.147902","article-title":"Efficient classical simulation of slightly entangled quantum computations","volume":"91","author":"G. Vidal","year":"2003","journal-title":"Phys Rev Lett"},{"key":"pcbi.1011033.ref029","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/srep38095","article-title":"Quantum error correction protects quantum search algorithms against decoherence.","volume":"6","author":"P Botsinis","year":"2016","journal-title":"Sci Rep"},{"key":"pcbi.1011033.ref030","article-title":"A new quantum ripple-carry addition circuit.","author":"SA Cuccaro","year":"2004","journal-title":"arXiv preprint quant-ph\/0410184."},{"key":"pcbi.1011033.ref031","doi-asserted-by":"crossref","first-page":"74","DOI":"10.22331\/q-2018-06-18-74","article-title":"Halving the cost of quantum addition","volume":"2","author":"C. Gidney","year":"2018","journal-title":"Quantum."},{"key":"pcbi.1011033.ref032","first-page":"74","article-title":"A layered software architecture for quantum computing design tools.","volume":"39","author":"KM Svore","year":"2006","journal-title":"Computer (Long Beach Calif)."},{"key":"pcbi.1011033.ref033","doi-asserted-by":"crossref","first-page":"032328","DOI":"10.1103\/PhysRevA.100.032328","article-title":"Validating quantum computers using randomized model circuits","volume":"100","author":"AW Cross","year":"2019","journal-title":"Phys Rev A (Coll Park)."},{"key":"pcbi.1011033.ref034","doi-asserted-by":"crossref","unstructured":"Chia N-H, Chung K-M, Lai C-Y. On the need for large quantum depth. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. 2020. pp. 902\u2013915.","DOI":"10.1145\/3357713.3384291"},{"key":"pcbi.1011033.ref035","author":"R Li","year":"2018","journal-title":"Quantum Supremacy Circuit Simulation on Sunway TaihuLight"},{"key":"pcbi.1011033.ref036","article-title":"Quantum lower bound for recursive fourier sampling","author":"S. Aaronson","year":"2002","journal-title":"arXiv preprint quant-ph\/0209060."},{"key":"pcbi.1011033.ref037","author":"H Abraham","year":"2019","journal-title":"Qiskit: An Open-source Framework for Quantum Computing"},{"key":"pcbi.1011033.ref038","unstructured":"Cedar cluster: https:\/\/docs.computecanada.ca\/wiki\/Cedar (accessed: 06.02.2022)."},{"key":"pcbi.1011033.ref039","unstructured":"Ibm real quantum devices: https:\/\/quantum-computing.ibm.com\/services?services=systems (last accessed: 06.02.2022)."},{"key":"pcbi.1011033.ref040","article-title":"Introduction to the Theory of Computation","author":"M. Sipser","year":"2012","journal-title":"Cengage learning;"}],"updated-by":[{"DOI":"10.1371\/journal.pcbi.1011033","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2023,4,24]],"date-time":"2023-04-24T00:00:00Z","timestamp":1682294400000}}],"container-title":["PLOS Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1011033","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,10]],"date-time":"2023-12-10T16:09:54Z","timestamp":1702224594000},"score":1,"resource":{"primary":{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1011033"}},"subtitle":[],"editor":[{"given":"Nir","family":"Ben-Tal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2023,4,12]]},"references-count":40,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2023,4,12]]}},"URL":"https:\/\/doi.org\/10.1371\/journal.pcbi.1011033","relation":{"new_version":[{"id-type":"doi","id":"10.1371\/journal.pcbi.1011033","asserted-by":"object"}]},"ISSN":["1553-7358"],"issn-type":[{"value":"1553-7358","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,4,12]]}}}