{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,6]],"date-time":"2022-04-06T01:27:51Z","timestamp":1649208471361},"reference-count":21,"publisher":"Wiley","license":[{"start":{"date-parts":[[2010,2,1]],"date-time":"2010-02-01T00:00:00Z","timestamp":1264982400000},"content-version":"unspecified","delay-in-days":1492,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["LMS J. Comput. Math."],"published-print":{"date-parts":[[2006]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>H\u00f8yer has given a generalisation of the Deutsch\u2013Jozsa algorithm which uses the Fourier transform on a group <jats:italic>G<\/jats:italic> which is (in general) non-Abelian. His algorithm distinguishes between functions which are either perfectly balanced (<jats:italic>m<\/jats:italic>-to-one) or constant, with certainty, and using a single quantum query. Here, we show that this algorithm (which we call the Deutsch\u2013Jozsa\u2013H\u00f8yer algorithm) can in fact deal with a broader range of promises, which we define in terms of the irreducible representations of <jats:italic>G<\/jats:italic>.<\/jats:p>","DOI":"10.1112\/s1461157000001182","type":"journal-article","created":{"date-parts":[[2013,8,6]],"date-time":"2013-08-06T07:41:55Z","timestamp":1375774915000},"page":"40-63","source":"Crossref","is-referenced-by-count":2,"title":["Extending the Promise of the Deutsch\u2013Jozsa\u2013H\u00f8yer Algorithm for Finite Groups"],"prefix":"10.1112","volume":"9","author":[{"given":"Michael","family":"Batty","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew J.","family":"Duncan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samuel L.","family":"Braunstein","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2010,2,1]]},"reference":[{"key":"S1461157000001182_ref020","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"},{"key":"S1461157000001182_ref004","volume-title":"An Approximate Fourier transform useful for quantum factoring","author":"Coppersmith","year":"1994"},{"key":"S1461157000001182_ref021","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626265"},{"key":"S1461157000001182_ref014","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511565755"},{"key":"S1461157000001182_ref002","article-title":"Quantum algorithms revisited","volume":"454","author":"Cleve","year":"1998","journal-title":"Proc. Royal Soc. London, Sen. A"},{"key":"S1461157000001182_ref019","unstructured":"19. R\u00f6tteler M. and Beth T. , \u2018Polynomial-time solution to the hidden subgroup problem for a class of non-Abelian groups\u2019, vl, 1998, http:\/\/lanl.arxiv.org\/abs\/quant-ph\/9812070."},{"key":"S1461157000001182_ref005","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1985.0070"},{"key":"S1461157000001182_ref011","unstructured":"11. H\u00f8yer P. , \u2018Efficient quantum transforms\u2019, 1997, http:\/\/lanl.arxiv.org\/abs\/quant-ph\/9702028."},{"key":"S1461157000001182_ref016","first-page":"778","volume-title":"Proc. Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Moore","year":"2004"},{"key":"S1461157000001182_ref008","volume-title":"Representation theory","volume":"129","author":"Fulton","year":"1991"},{"key":"S1461157000001182_ref001","first-page":"48","article-title":"Quantum computation of Fourier transforms over the symmetric groups","author":"Beals","year":"1997","journal-title":"Proc. 29th Annual ACM Symposium on Theory of Computing"},{"key":"S1461157000001182_ref010","first-page":"627","volume-title":"Proc. 32nd Annual ACM Symposium on Theory of Computing","author":"Hallgreen","year":"2000"},{"key":"S1461157000001182_ref003","unstructured":"3. Constantini G. and Smeraldi F. , \u2018A generalisation of Deutsch's example\u2019, 1997, http:\/\/lanl.arxiv.org\/abs\/quant-ph\/9702020."},{"key":"S1461157000001182_ref015","first-page":"183","volume-title":"Proc. 1995 DIMACS Workshop in Groups and- Computation","volume":"28","author":"Maslen","year":"1997"},{"key":"S1461157000001182_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-004-0009-8"},{"key":"S1461157000001182_ref013","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-1779-2"},{"key":"S1461157000001182_ref007","doi-asserted-by":"publisher","DOI":"10.1006\/aama.2000.0699"},{"key":"S1461157000001182_ref006","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1992.0167"},{"key":"S1461157000001182_ref012","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.59.3280"},{"key":"S1461157000001182_ref017","volume-title":"Quantum computation and quantum information","author":"Nielsen","year":"2000"},{"key":"S1461157000001182_ref018","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46796-3_15"}],"container-title":["LMS Journal of Computation and Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1461157000001182","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T19:49:33Z","timestamp":1559936973000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1461157000001182\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"references-count":21,"alternative-id":["S1461157000001182"],"URL":"https:\/\/doi.org\/10.1112\/s1461157000001182","relation":{},"ISSN":["1461-1570"],"issn-type":[{"value":"1461-1570","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}