Counting abelian squares efficiently for a problem in quantum computing

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.

Keywords

abelian squares, quantum computing, quantum circuit expressiveness, variational methods

2010 Mathematics Subject Classification

05A05, 68Q12

Full Text (PDF format)

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