Geometric quantum machine learning of BQP$^A$ protocols and latent graph
  classifiers
Chukwudubem Umeano Vincent E. Elfving Oleksandr Kyriienko
Geometric quantum machine learning (GQML) aims to embed problem symmetries
for learning efficient solving protocols. However, the question remains if
(G)QML can be routinely used for constructing protocols with an exponential
separation from classical analogs. In this Letter we consider Simon's problem
for learning properties of Boolean functions, and show that this can be related
to an unsupervised circuit classification problem. Using the workflow of
geometric QML, we learn from first principles Simon's algorithm, thus
discovering an example of BQP$^A\neq$BPP protocol with respect to some dataset
(oracle $A$). Our key findings include the development of an equivariant
feature map for embedding Boolean functions, based on twirling with respect to
identified bitflip and permutational symmetries, and measurement based on
invariant observables with a sampling advantage. The proposed workflow points
to the importance of data embeddings and classical post-processing, while
keeping the variational circuit as a trivial identity operator. Next,
developing the intuition for the function learning, we visualize instances as
directed computational hypergraphs, and observe that the GQML protocol can
access their global topological features for distinguishing bijective and
surjective functions. Finally, we discuss the prospects for learning other
BQP$^A$-type protocols, and conjecture that this depends on the ability of
simplifying embeddings-based oracles $A$ applied as a linear combination of
unitaries.