Journal of Combinatorics
Volume 14 (2023)
Counting abelian squares efficiently for a problem in quantum computing
Pages: 445 – 459
I describe how the number of abelian squares of given length relates to a certain problem in theoretical quantum computing, and I present a recursive formula for calculating the number of abelian squares of length $t + t$ over an alphabet of size $d$. The presented formula is similar to a previously known formula but has substantially lower complexity for large $d$, a key improvement resulting in a practical solution to the original application.
abelian squares, quantum computing, quantum circuit expressiveness, variational methods
2010 Mathematics Subject Classification
This manuscript has been authored by UT-Battelle, LLC, under contract DEAC05-00OR22725 with the US Department of Energy (DOE). The US government retains and the publisher, by accepting the article for publication, acknowledges that the US government retains a nonexclusive, paid-up, irrevocable, worldwide license to publish or reproduce the published form of this manuscript, or allow others to do so, for US government purposes. DOE will provide public access to these results of federally sponsored research in accordance with the DOE Public Access Plan (http://energy.gov/downloads/doe-public-access-plan).
Received 16 September 2021
Accepted 29 July 2022
Published 14 April 2023