Abstract structure of unitary oracles for quantum algorithms

William Zeng
(University of Oxford)
Jamie Vicary
(University of Singapore and University of Oxford)

We show that a pair of complementary dagger-Frobenius algebras, equipped with a self-conjugate comonoid homomorphism onto one of the algebras, produce a nontrivial unitary morphism on the product of the algebras. This gives an abstract understanding of the structure of an oracle in a quantum computation, and we apply this understanding to develop a new algorithm for the deterministic identification of group homomorphisms into abelian groups. We also discuss an application to the categorical theory of signal-flow networks.

In Bob Coecke, Ichiro Hasuo and Prakash Panangaden: Proceedings of the 11th workshop on Quantum Physics and Logic (QPL 2014), Kyoto, Japan, 4-6th June 2014, Electronic Proceedings in Theoretical Computer Science 172, pp. 270–284.
Published: 28th December 2014.

ArXived at: https://dx.doi.org/10.4204/EPTCS.172.19 bibtex PDF

Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org