Efficient Ancilla-Free Reversible and Quantum Circuits for the Hidden Weighted Bit Function.
Saved in:
| Title: | Efficient Ancilla-Free Reversible and Quantum Circuits for the Hidden Weighted Bit Function. |
|---|---|
| Authors: | Bravyi, Sergey1 (AUTHOR) sbravyi@us.ibm.com, Yoder, Theodore J.1 (AUTHOR) ted.yoder@ibm.com, Maslov, Dmitri1 (AUTHOR) dmitri.maslov@ibm.com |
| Source: | IEEE Transactions on Computers. May2022, Vol. 71 Issue 5, p1170-1180. 11p. |
| Subjects: | Circuit complexity, Quantum computing, Computer science, Hamming weight, Logic circuits |
| Abstract: | The Hidden Weighted Bit function plays an important role in the study of classical models of computation. A common belief is that this function is exponentially hard to implement using reversible ancilla-free circuits, even though introducing a small number of ancillae allows a very efficient implementation. In this paper, we refute the exponential hardness conjecture by developing a polynomial-size reversible ancilla-free circuit computing the Hidden Weighted Bit function. Our circuit has size $O(n^{6.42})$ O (n 6. 42) , where $n$ n is the number of input bits. We also show that the Hidden Weighted Bit function can be computed by a quantum ancilla-free circuit of size $O(n^2)$ O (n 2) . The technical tools employed come from a combination of Theoretical Computer Science (Barrington's theorem) and Physics (simulation of fermionic Hamiltonians) techniques. [ABSTRACT FROM AUTHOR] |
| Copyright of IEEE Transactions on Computers is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 156273023 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Efficient Ancilla-Free Reversible and Quantum Circuits for the Hidden Weighted Bit Function. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Bravyi%2C+Sergey%22">Bravyi, Sergey</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> sbravyi@us.ibm.com</i><br /><searchLink fieldCode="AR" term="%22Yoder%2C+Theodore+J%2E%22">Yoder, Theodore J.</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> ted.yoder@ibm.com</i><br /><searchLink fieldCode="AR" term="%22Maslov%2C+Dmitri%22">Maslov, Dmitri</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> dmitri.maslov@ibm.com</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22IEEE+Transactions+on+Computers%22">IEEE Transactions on Computers</searchLink>. May2022, Vol. 71 Issue 5, p1170-1180. 11p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Circuit+complexity%22">Circuit complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Quantum+computing%22">Quantum computing</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+science%22">Computer science</searchLink><br /><searchLink fieldCode="DE" term="%22Hamming+weight%22">Hamming weight</searchLink><br /><searchLink fieldCode="DE" term="%22Logic+circuits%22">Logic circuits</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: The Hidden Weighted Bit function plays an important role in the study of classical models of computation. A common belief is that this function is exponentially hard to implement using reversible ancilla-free circuits, even though introducing a small number of ancillae allows a very efficient implementation. In this paper, we refute the exponential hardness conjecture by developing a polynomial-size reversible ancilla-free circuit computing the Hidden Weighted Bit function. Our circuit has size $O(n^{6.42})$ O (n 6. 42) , where $n$ n is the number of input bits. We also show that the Hidden Weighted Bit function can be computed by a quantum ancilla-free circuit of size $O(n^2)$ O (n 2) . The technical tools employed come from a combination of Theoretical Computer Science (Barrington's theorem) and Physics (simulation of fermionic Hamiltonians) techniques. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of IEEE Transactions on Computers is the property of IEEE and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=156273023 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1109/TC.2021.3076435 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 11 StartPage: 1170 Subjects: – SubjectFull: Circuit complexity Type: general – SubjectFull: Quantum computing Type: general – SubjectFull: Computer science Type: general – SubjectFull: Hamming weight Type: general – SubjectFull: Logic circuits Type: general Titles: – TitleFull: Efficient Ancilla-Free Reversible and Quantum Circuits for the Hidden Weighted Bit Function. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Bravyi, Sergey – PersonEntity: Name: NameFull: Yoder, Theodore J. – PersonEntity: Name: NameFull: Maslov, Dmitri IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 05 Text: May2022 Type: published Y: 2022 Identifiers: – Type: issn-print Value: 00189340 Numbering: – Type: volume Value: 71 – Type: issue Value: 5 Titles: – TitleFull: IEEE Transactions on Computers Type: main |
| ResultId | 1 |
