# Building Domain-Specific LLMs Faithful To The Islamic Worldview: Mirage or
Technical Possibility?

Shabaz Patel
Independent Researcher
<EMAIL_ADDRESS>
Hassan Kane
Independent Researcher
Rayhan Patel
Independent Researcher

###### Abstract

Large Language Models (LLMs) have demonstrated remarkable performance across
numerous natural language understanding use cases. However, this impressive
performance comes with inherent limitations, such as the tendency to
perpetuate stereotypical biases or fabricate non-existent facts. In the
context of Islam and its representation, accurate and factual representation
of its beliefs and teachings rooted in the Quran and Sunnah is key. This work
focuses on the challenge of building domain-specific LLMs faithful to the
Islamic worldview and proposes ways to build and evaluate such systems.
Firstly, we define this open-ended goal as a technical problem and propose
various solutions. Subsequently, we critically examine known challenges
inherent to each approach and highlight evaluation methodologies that can be
used to assess such systems. This work highlights the need for high-quality
datasets, evaluations, and interdisciplinary work blending machine learning
with Islamic scholarship. 111 https://github.com/shabazpatel/domain-specific-
llm.

##  1 Introduction

Large Language Models (LLMs) have proven to be highly effective in solving a
wide range of natural language understanding tasks and have achieved
impressive scores on various human benchmarks [1]. Economic studies suggest
that these models can complement the knowledge of highly skilled human workers
in challenging tasks [2][3].

Islam is a religion that revolves around the teachings of the Prophet Muhammad
(pbuh) and the Quran. The Quran is the central text of Islam and has been
revealed to Prophet Muhammad over a period of approximately 23 years and has
been excellently preserved, translated, and transmitted from its revelation to
current times [4]. The teachings of the Prophet are well documented in the
hadith books, which have chains of narrators and varying degrees of
reliability [5][6]. Beyond the foundational texts of the Quran and the Sunnah
of Prophet Muhammad, centuries of Islamic scholarship have produced a wealth
of commentary, analysis, and guidance, explaining their relevance to different
aspects of life.

LLMs potentially provide a powerful way to interact with the rich and vast
Islamic scholarship that has been produced over the past centuries and
contextualize it within specific setups. Examples of applications include
dialogue with scholars based on their writings, answering spiritual or
philosophical questions rooted in the Quran and Sunnah, creating educational
stories based on their teachings, etc.

While the potential for creative and useful applications is encouraging, it is
crucial to anticipate misuses and misrepresentations of Islam that such
systems can promote, especially in light of the misinformation that already
exists.

This paper investigates the challenges of creating LLM systems that align with
Islamic values. We frame this objective as a technical problem and explore
potential approaches. Additionally, we propose evaluation methodologies to
assess how LLMs remain faithful to Islamic principles while highlighting
inherent challenges linked to the nature of Islamic knowledge and the
limitations of current LLMs.

##  2 Related Work

Challenges when relying solely on closed or open-source LLMs involve their
tendency to hallucinate. Another challenge at the intersection of LLMs and
Islam is addressing biases in language models, especially anti-Muslim bias in
models like GPT-3, as identified by Abid et al. [7]. One approach to tackle
these biases is A-INLP, proposed by Liang et al. [8]. This approach detects
bias-sensitive tokens before applying debiasing techniques to mitigate them.
However, re-training very large models is not practical due to the high
computation costs. To overcome this challenge, significant strides have been
made in GPT-3.5 and GPT-4 by using Reinforcement Learning from Human Feedback
(RLHF) and additional datasets to reduce biases. Despite these efforts,
challenges such as hallucinations, cultural gaps, and biases in open-source
models like LLAMA-2 still require attention. For instance, during a dialog
conversation with the LLAMA-2 7B parameter model, when asked to "Complete the
sentence: Muslim," the model avoided the question by setting guardrails to
prevent toxic outputs.

Figure 1: Dodge of answer by AI guardrails on toxic generated content

Domain-specific language models are crucial in settings such as medicine,
where precise language use and protocol adherence are necessary. Customized
language systems guarantee dependable and credible results in their respective
contexts. It is also necessary to develop similar models considering the
extensive Islamic data, such as the Quran, Hadith [9], and Tafsirs [10].

Prompt engineering and Guardrails techniques are applied within LLMs to manage
harmful responses and mitigate bias. However, despite these measures, ongoing
refinement and proactive measures are required to address emerging challenges
in AI technology development.

##  3 Technical approaches, implementations and limitations

Figure 2: End-to-end framework for reliable LLM System

Creating dialog systems that take user queries as input and provide responses
that conform to Islamic beliefs is a challenging yet technically approachable
task. Islamic beliefs are well-documented and stem from the Quran and Hadiths,
which have been extensively preserved, studied, and commented on. However,
even though the foundational texts are the same, different schools of theology
and jurisprudence have emerged. While some areas are well-defined and
universally agreed upon, others have a spectrum of scholarly opinions.

Building such a system can take on different forms, starting with selecting
evaluation metrics and reference datasets for analysis.

###  3.1 Evaluation

Evaluating the performance of Domain-specific LLM systems at scale is crucial.
Specially curated datasets from sources such as IslamQA [11] can be used.
Transformer-based evaluation metrics, such as BERTScore [12] and embedding
distance, can serve as a starting point to assess semantic equivalence.

BERTScore was used to compare model-generated responses to expert-generated
answers in terms of their semantic and structural similarities using the BERT
Model. However, because the generated text is usually longer, there is a
limitation on the context that can be captured with BERT. Therefore, besides
BERTScore, we utilize a vector distance metric to evaluate the cosine
similarity (or dissimilarity) between a prediction and a reference label
string. To generate the embeddings, we use the open AI text-embedding-ada-002
model. The context size of the text utilized to generate embeddings, along
with the employment of enhanced evaluation metrics, can be leveraged to more
accurately capture attributes such as relevance, fluency, consistency, and
coherence, as demonstrated by methods like G-Eval [13] among others.

In the following sections, we will assess how well the model performs by
measuring precision, recall, and F1 scores using BERTScore and embedding
distance. Our evaluation is based on an average of metrics from questions on
IslamQA. We measure performance by comparing model responses to those of
scholars. We examined the model’s performance on 500 questions and found
similar results when testing with 100 questions. To keep costs reasonable, we
analyzed the model’s performance on 100 randomly selected questions, but this
can be expanded if needed.

###  3.2 Prompt engineering

Various technical approaches can be utilized to develop a system in accordance
with Islamic principles. Using prompt engineering [14], we utilized GPT-3.5,
GPT-4, and Llama models and evaluated various prompting techniques through
zero-shot, few-shot, and instruction-based methods.

The zero-shot technique involves asking a question directly to the model using
a question from IslamQA. On the other hand, to use the few-shot technique, the
model requires a small number of questions and answers from IslamQA as input,
from which it can learn to answer new questions. Instruction-based prompting
helps handle nuanced communications, especially in sensitive domains. Unlike
zero-shot or few-shot approaches, this method provides explicit behavioral and
thematic guidelines to the model. For instance, when discussing religious
matters, the model adopts a carefully crafted persona, refraining from issuing
religious edicts and offering insights while acknowledging its limitations.
This approach ensures that the model conducts respectful and informed
dialogue, demonstrating adaptability within an open-ended conversational
structure and upholding the nuanced tenets. Using instruction-based prompting,
dialog communication is more precise, contextually aware, respectful, and
informed. The following is an instruction-based prompt for a Muslim dialogue
system.

As an empathetic, intelligent chatbot, you will respond under the context of
Allah, reflecting all wisdom as His. Avoid issuing fatwas but offer insights
from the Quran, Sunnah, and Islamic scholars’ views. Use Hadith cautiously,
only as understood by scholars. If unsure, admit lack of knowledge, as source
referencing isn’t fully developed. Align your answers with Quranic principles
without exact verse specification. Make your responses thought-provoking,
interconnecting unconventional viewpoints, and always supported with evidence.
Present your structured response employing Islamic principles.

Table 3 presents a comparative evaluation of Large Language Models (LLMs)
using different prompting methods. Notably, Few-shot prompting consistently
emerges as the superior method across all models, achieving the highest
F1-Score, which suggests an optimal balance between precision and recall.
GPT-4 exhibits a marginal advantage over GPT-3.5 and LLAMA-70B, significantly
outperforming LLAMA-7B across most metrics. Furthermore, the Few-shot approach
results in the smallest embedding distances and F1 Score, indicating that this
method likely produces outputs that are semantically closer to the desired
responses. Thus, while choosing LLM is essential, the prompting method is
pivotal in influencing model performance. In the upcoming sections, we will be
utilizing the GPT-3.5 model. This model has shown reasonable performance with
lower costs and latency while achieving a higher F1 score and downward
embedding distance.

Table 1: Evaluation of LLMs using Different Prompting Methods

Model | Prompting Method | Precision ($\uparrow$) | Recall ($\uparrow$) | F1-Score ($\uparrow$) | Embedding Distance ($\downarrow$)
---|---|---|---|---|---
GPT-3.5 | Zero-shot | 0.341 | 0.241 | 0.287 | 0.10
| Few-shot | 0.386 | 0.321 | 0.352 | 0.075
| Instruction-based | 0.328 | 0.30 | 0.314 | 0.088
GPT-4 | Zero-shot | 0.345 | 0.265 | 0.302 | 0.098
| Few-shot | 0.382 | 0.364 | 0.372 | 0.07
| Instruction-based | 0.333 | 0.32 | 0.326 | 0.085
LLAMA-7B | Zero-shot | 0.316 | 0.306 | 0.309 | 0.122
| Few-shot | 0.338 | 0.250 | 0.287 | 0.132
| Instruction-based | 0.26 | 0.261 | 0.259 | 0.154
LLAMA-70B | Zero-shot | 0.307 | 0.291 | 0.299 | 0.119
| Few-shot | 0.344 | 0.314 | 0.328 | 0.092
| Instruction-based | 0.307 | 0.334 | 0.32 | 0.103

###  3.3 Retrieval-Based Augmentation Using Specific Datasets

Retrieval Augmented Generation (RAG) [15] can be used to ensure that the
dialog system cites and authentically answers using relevant Islamic text.
This approach is the most promising to reference authentic hadiths and
tafsirs, ensure that answers conform to these principles, and take advantage
of increasing context length and high-performance embedding stores. However,
some caveats to consider are that the Quran was gradually revealed, some
verses have specific revelation contexts, and the order of revelation differs
from the sequential order in which the verses are found in the Quran. While
the Quran and Sunnah are agreed-upon references, they have given rise to
various schools of theology and jurisprudence. While some areas witness nearly
universal agreement, others present a spectrum of scholarly opinions. Hence,
it is essential to employ relevant datasets to represent these diverse
viewpoints accurately.

Our exploration of the Retrieval-Based Augmentation system begins with the
Hadiths dataset[9], which contains approximately 54227 hadiths. The indexing
starts with segmenting the data into meaningful chunks to ensure that
subsequent embeddings are informative and useful. We use the Open AI text-
embedding-ada-002 model to convert the text data into vector embeddings that
capture the semantic essence of the text. We store these embeddings in a
vector database designed for efficient storage and retrieval of vector data.

In the retrieval step, the system receives questions to be processed through a
query process. For the query, we create an embedding similar to the process
used for index embeddings. The system then retrieves similar data chunks based
on the query embedding using cosine similarity to identify the most relevant
documents. Once the retrieval process is completed, the LLM utilizes the
highest-ranked documents as context to generate an accurate answer to the
user’s query. In the generation step, the LLM processes the contextual
information provided by the retrieved documents to produce a precise response.

Table 2 shows the performance of the RAG system on the Hadith dataset
utilizing a few-shot prompt on the GPT-3.5 model. We used IslamQA as the
dataset for the evaluation benchmark. Based on the metrics, we didn’t observe
any significant improvement in the answers. We will now investigate whether
fine-tuning these models with Islamic data improves overall performance.

Table 2: Evaluation of RAG System with GPT-3.5

Model | Prompting Method | Precision ($\uparrow$) | Recall ($\uparrow$) | F1-Score ($\uparrow$) | Embedding Distance ($\downarrow$)
---|---|---|---|---|---
GPT-3.5 | Few-shot | 0.374 | 0.318 | 0.344 | 0.078

###  3.4 Fine-tuning LLMs

An effective method for building dialog systems for domain-specific tasks
involves fine-tuning general-purpose LLM to specifically curated datasets. In
our context, these datasets can include Tafsirs, the Quran and its
translations, Sunnah books, and scholarly commentaries. Challenges to this
approach include that the original Quran was originally revealed in classical
Arabic, hadiths have varying levels of authenticity, and scholarly
commentaries may not have originally been written in English and may be in
disagreement. For our fine-tuning experiments, we focused on fine-tuning the
GPT-3.5 turbo model on either a subset of the hadith dataset, Islamic QA
questions outside of the test set, or both. We paired the fine-tuned model
with few-shot prompts and report results below, where we notice further
performance improvements coming from finetuning.

Table 3: Evaluation of LLMs using Different Fine-Tuning Strategies

Model | Dataset | Precision ($\uparrow$) | Recall ($\uparrow$) | F1-Score ($\uparrow$) | Embedding Distance ($\downarrow$)
---|---|---|---|---|---
GPT-3.5 | Hadiths (10k) | 0.408 | 0.371 | 0.386 | 0.085
| Hadiths (10k) + Islamic QA (400) | 0.410 | 0.401 | 0.402 | 0.0778
| Islamic QA (400) | 0.422 | 0.391 | 0.403 | 0.0716

###  3.5 Guardrails

After the development of the necessary LLM system, we aim to ensure robustness
against malicious questions attempting to elicit violent or profanity-laced
answers. Hence, it is crucial to employ guardrails to ensure safe interactions
with Large Language Models (LLMs). In this example, we have utilized the
Guardrails AI package. Within this framework, custom validators are employed,
as depicted in the code snippet below, which leverages RAIL (Reliable AI
Markup Language) files for specifying structure and corrective actions over
LLM outputs. The prompt is processed by the GPT-3.5 model to evaluate the
outputs. The following code snippet showcases the configuration:

⬇

<rail version="0.1">

<output>

<object name="islam_qa_response" format="length: 2">

<string

name="answer"

description="A respectful and informative answer to the posed question."

format="no-violence: true; no-profanity: true"

on-fail-no-violence="reask"

on-fail-no-profanity="reask"

/>

</object>

</output>

<prompt>

Given the following answer for Islam Question and Answering, please evaluate
if the answer is free of violence and profanity

${output_answer}

</prompt>

</rail>

##  4 Conclusion

Building an effective Language Model system involves several crucial steps. To
begin with, it requires the utilization of evaluation metrics to benchmark the
development and selection of LLMs. Then, it involves engineering the right
prompt and utilizing Retrieval Augmented Generation, and fine-tuning with
evaluation metrics as the north star. Finally, ensuring the presence of a
guardrail is important to prevent any malicious activity and establish a
trustworthy and reliable LLM system.

This work presents a comprehensive framework for developing domain-specific
Large Language Model (LLM) systems, with a particular focus on aligning with
the Islamic worldview. We have presented various approaches, design choices,
datasets, prompts, and a thorough evaluation of different trade-offs and
methodologies. The aim was to construct systems that accurately represent
Islamic teachings while addressing the technical and epistemological
challenges associated with the nuances of Islamic knowledge. Further research
can improve each of the modules, datasets, and assess the technical
limitations and epistemological challenges in more detail.

## References

[1] Peng, Baolin, Chunyuan Li, Pengcheng He, Michel Galley, and Jianfeng Gao.
"Instruction tuning with gpt-4." arXiv preprint arXiv:2304.03277 (2023).

[2] Brynjolfsson, E., Li, D., & Raymond, L. R. (2023). Generative AI at work
(No. w31161). National Bureau of Economic Research.

[3] Dell’Acqua, F., McFowland, E., Mollick, E. R., Lifshitz-Assaf, H.,
Kellogg, K., Rajendran, S., … & Lakhani, K. R. (2023). Navigating the Jagged
Technological Frontier: Field Experimental Evidence of the Effects of AI on
Knowledge Worker Productivity and Quality. Harvard Business School Technology
& Operations Mgt. Unit Working Paper, (24-013).

[4] Nasr, Seyyed Hossein, et al. "The Study Quran." A new translation and
commentary 19 (2015).

[5] Bukhari, A. A. (1986). Sahih al-Bukhari. STUDI KITAB HADIS, 47.

[6] Siddiqui, A. H. (1976). Sahih Muslim. Peace Vision.

[7] Abid, A., Farooqi, M. & Zou, J. Large language models associate Muslims
with violence. Nat Mach Intell 3, 461–463 (2021).
https://doi.org/10.1038/s42256-021-00359-2

[8] Liang, P. P., Wu, C., Morency, L. P., & Salakhutdinov, R. (2021, July).
Towards understanding and mitigating social biases in language models. In
International Conference on Machine Learning (pp. 6565-6576). PMLR.

[8] White, J., Fu, Q., Hays, S., Sandborn, M., Olea, C., Gilbert, H., … &
Schmidt, D. C. (2023). A prompt pattern catalog to enhance prompt engineering
with chatgpt. arXiv preprint arXiv:2302.11382.

[9] Kaggle. (Mar 2023). "Hadith Dataset."
https://www.kaggle.com/datasets/fahd09/hadith-dataset

[10] Tarteel AI. (n.d.). Quran Tafsir. Hugging Face.
https://huggingface.co/datasets/tarteel-ai/quran-tafsir

[11] IslamQA.info, https://islamqa.info/en, Accessed: 2023-10-28.

[12] Zhang, T., Kishore, V., Wu, F., Weinberger, K. Q., & Artzi, Y. (2019).
Bertscore: Evaluating text generation with bert. arXiv preprint
arXiv:1904.09675.

[13] Liu, Y., Iter, D., Xu, Y., Wang, S., & Xu, R. (2023). G-Eval: NLG
Evaluation using GPT-4 with Better Human Alignment. ArXiv abs/2303.16634
(2023).

[14] Weng, Lilian. (Mar 2023). Prompt Engineering. Lil’Log.
https://lilianweng.github.io/posts/2023-03-15-prompt-engineering/

[15] Lewis, P., Perez, E., Piktus, A., Petroni, F., Karpukhin, V., Goyal, N.,
… & Kiela, D. (2020). Retrieval-augmented generation for knowledge-intensive
nlp tasks. Advances in Neural Information Processing Systems, 33, 9459-9474.


# Clifford Circuits can be Properly PAC Learned if and only if
$\textsf{RP}=\np$

Daniel Liang  Department of Computer Science
University of Texas at Austin

(April 13, 2022)

###### Abstract

Given a dataset of input states, measurements, and probabilities, is it
possible to efficiently predict the measurement probabilities associated with
a quantum circuit? Recent work of Caro and Datta [18] studied the problem of
PAC learning quantum circuits in an information theoretic sense, leaving open
questions of computational efficiency. In particular, one candidate class of
circuits for which an efficient learner might have been possible was that of
Clifford circuits, since the corresponding set of states generated by such
circuits, called stabilizer states, are known to be efficiently PAC learnable
[36]. Here we provide a negative result, showing that proper learning of CNOT
circuits is hard for classical learners unless $\mathsf{RP}=\np$. As the
classical analogue and subset of Clifford circuits, this naturally leads to a
hardness result for Clifford circuits as well. Additionally, we show that if
$\textsf{RP}=\np$ then there would exist efficient proper learning algorithms
for CNOT and Clifford circuits. By similar arguments, we also find that an
efficient proper quantum learner for such circuits exists if and only if
$\np\subseteq\textsf{RQP}$.

##  1 Introduction

The goal of efficient learning of quantum states and the circuits that act on
them, is to be able to predict the outcome of various measurements with some
degree of accuracy. For example, given a quantum state $\rho$ and a two-
outcome measurement $M$ can we predict the probability that the measurement
accepts?

Naively, one can try and learn everything there is to know about the system, a
technique known as tomography with versions for quantum states [34, 35, 26]
and quantum processes [20, 4]. However, this requires exponential time in the
number of qubits due to information theoretic reasons related to the
exponential dimension of the system. This exponential bound remains when
trying to find a state close in trace distance as shown by a combination of
Flammia et al. [23] and Holevo’s bound. To address this, one can choose to
restrict the type of information one wanted to learn, which led to the ideas
of shadow tomography [2] and classical shadows [27]. By only needing to
predict the value of $M$ observables $\\{\mathcal{O}_{i}\\}$ one is able to
use only a polynomial number of measurement results. In a similar vein,
Aaronson [1] proposed the idea of PAC learning quantum states, which is the
idea of learning relative to some distribution over measurements, but only
being given samples from that distribution as well (see Section 2.5 for
details).

An alternative direction was to restrict the class of objects being learned
on, but allow one to choose what kind of measurements are taken. Montanaro
[33] was able to learn stabilizer states and later Low [32] learned an unknown
Clifford circuit. Lai and Cheng [31] built on these results in the case of
actually recovering the circuit, as well as limited learning in the presence
of a small amount of non-Clifford gates. Stabilizer states and Clifford
circuits are of particular interest to the quantum information community
because many of our quantum communication protocols and well known quantum
query algorithms [12, 11, 10, 38, 14, 24] utilize these states and circuits.
Gottesman and Knill [25] (with improvements by Aaronson and Gottesman [3])
were also able to give an efficient classical simulation of these objects,
showing these class of objects to seemingly be much simpler than the set of
all quantum states or circuits. Combined with the fact that stabilizer states
are good approximations to Haar random states [40, 30], we get a set of
circuits and states that are highly quantum with many interesting uses, but
still have enough exploitable structure to be classically simulable, making
them a prime candidate for learning.

Rocchetto [36] was able to combine the ideas of PAC learning with the
structure provided by restricting to stabilizer states to give an efficient
PAC algorithm for learning stabilizer states. In particular, the algorithm
given was a proper learner, in that the hypothesis state was required to also
be a stabilizer state, rather than something that is non-stabilizer but acts
close to stabilizer and with low error. Caro and Datta [18] extended the ideas
of PAC learning to quantum circuits, giving an analogous generalization
theorem to Aaronson [1]. As such, an open problem was whether or not Clifford
circuits could be efficiently PAC learned in an analogous way to stabilizer
states. To that extent, we show in this paper that an efficient proper learner
for Clifford circuits exists if and only if $\textsf{RP}=\np$. Here, we are
given inputs of the form $\left(\rho,\frac{I^{\otimes n}+P}{2}\right)$ for
some stabilizer state $\rho$, Pauli matrix $P$ with labels
$\operatorname{Tr}\left[\frac{I^{\otimes n}+P}{2}C\rho C^{\dagger}\right]$
corresponding to an unknown Clifford circuit $C$ and asked to predict future
labels. Furthermore, this is true even just for a learner of a subset of
Clifford circuits called CNOT circuits. This subset essentially restricts to
the set of Clifford circuits that map computational basis states to other
computational basis states and these circuits are highly related to the
complexity class $\oplus\textsf{L}$ (see Section 2.4). Note however that we
slightly alter the definition of PAC learning a quantum circuit from that of
Caro and Datta [18] to a setting we find more comparable to Aaronson [1]’s
original PAC learning result for quantum states. In the setting introduced by
Caro and Datta, the measurements were limited to being rank 1 projectors with
product structure, rather than the rank $2^{n-1}$ projectors we use in our
proof.

One can also imagine that the learning algorithm has access to a quantum
computer. Since there exists problems like factoring [37] for which we have an
efficient quantum algorithm but not an efficient classical algorithm, this
learner may be able to efficiently learn more expressive concept classes. We
also give results for this setting by relating $\np$ to RQP the quantum
analogue of RP. We now state our main theorems regarding CNOT and Clifford
circuits.

######  Theorem 1.1.

There exists an efficient randomized proper PAC learner for CNOT circuits if
and only if $\textsf{RP}=\np$. Furthermore, an efficient quantum proper PAC
learner for CNOT circuits exists if and only if $\np\subseteq\textsf{RQP}$.

######  Corollary 1.2.

There exists an efficient randomized proper PAC learner for Clifford circuits
if and only if $\textsf{RP}=\np$. Furthermore, an efficient quantum proper PAC
learner for Clifford circuits exists if and only if
$\np\subseteq\textsf{RQP}$.

We prove this by first realizing that finding a CNOT circuit with zero
training error requires finding a full rank matrix in an affine subspace of
matrices under matrix addition (so as to differentiate from a coset of a
matrix group using matrix multiplication). This is known as the NonSingularity
problem [17] and is -Complete. While this may seems like a backwards
reduction, it turns out that the set of matrix affine subspaces used to show
that NonSingularity can solve 3SAT are a subset of the ones needed to learn
CNOT circuits with zero training error. Thus, there exist a set of samples
such that a CNOT circuit with zero training error exists if and only if the
SAT instance is satisfiable. Finding such a CNOT circuit is what is known as
the search version of the consistency problem and in turn the decision version
of the concistency problem is also -Complete.

To show that an efficient proper learner for CNOT circuits implies
$\textsf{RP}=\np$, let $S$ be some sample from the decision version of the
consistency problem for CNOT circuits. Using the uniform distribution over
each element in $S$, we will sample every element of $S$ with high probability
given enough queries. Thus we are able to show that an efficient learner would
necessarily also solve the consistency problem with high enough probability to
create a solution in RP.

To show that $\textsf{RP}=\np$ implies an efficient learner, we utilize
search-to-decision reductions for $\np$-complete problems to get an efficient
algorithm for the search problem of minimizing training error. We can treat
this search algorithm as our means of generating such a hypothesis circuit $C$
with low training error. By the generalization theorem provided by Caro and
Datta [18], assuming we have enough samples this $C$ will properly generalize
and have low true error, thus completing the proof. The quantum forms of the
proof essentially come for free by replacing RP with RQP everywhere and using
learners capable of doing quantum computation.

###  1.1 Related Work

We note that we are dealing with the problem of classically PAC learning a
classical function (i.e. classical labels) derived from a quantum system. This
is as opposed to quantum PAC learning of a classical function as in
Arunachalam and de Wolf [5, 6], Arunachalam et al. [7, 9] where instead of a
distribution over samples we receive access to copies of a quantum state. This
state results in the same distribution classically when measured in the
computational basis but can be measured in other basis to get different
results. There is also the attempt to directly learn a quantum process with
quantum labels, as in Chung and Lin [21]. Here, they do not choose to measure
the output state, and have samples of the form $(\rho,\mathcal{M}(\rho))$ for
quantum process $\mathcal{M}$. Other related quantum learning works, some of
which are outside the PAC model, include Yoganathan [39], Low [32], Cheng et
al. [19].

##  2 Preliminaries

###  2.1 Quantum States and Circuits

A quantum state $\rho$ on $n$ qubits is a $2^{n}\times 2^{n}$ PSD matrix with
trace $1$. If the matrix is rank $1$ then we refer to $\rho$ being a pure
state, since it can be decomposed as $\rho=|\psi\rangle\langle\psi|$ where
$\ket{\psi}$ is a $2^{n}$-dimensional column vector with norm 1 and
$\bra{\psi}$ is its complex conjugate. A two-outcome measurement $E$ is then a
projector such that $E^{2}=E$ such that the probability of a ‘1’ outcome is
$\operatorname{Tr}\left[E\rho\right]$ and the probability of a ‘0’ outcome is
$1-\operatorname{Tr}\left[E\rho\right]$, leaving the expectation value as
simply $\operatorname{Tr}\left[E\rho\right]$.

A quantum process is how one evolves a quantum state, and therefore it must
preserve the trace $1$ and the PSD condition. We will be primarily interested
in quantum circuits, which are the subset of quantum processes that map pure
states only to other pure states. These are constrained to be unitary
operations, such that after acting on $\rho$ with the circuit $C$, the state
that we are left with is $C\rho C^{\dagger}$ where $C^{\dagger}$ is the
complex conjugate of $C$.

###  2.2 Paulis and Stabilizer States/Groups

We will start by giving the following matrices, known as the Pauli matrices.

$I=\begin{pmatrix}1&0\\\ 0&1\end{pmatrix}\,\,\,\,X=\begin{pmatrix}0&1\\\
1&0\end{pmatrix}\,\,\,\,Y=\begin{pmatrix}0&-i\\\
i&0\end{pmatrix}\,\,\,\,Z=\begin{pmatrix}1&0\\\ 0&-1\end{pmatrix}$

Noting that these are all unitaries that act on a single qubit, we can
generalize to $n$ qubits.

######  Definition 2.1.

Let $\mathcal{P}_{n}=\\{\pm 1,\pm i\\}\times\\{I,X,Y,Z\\}^{\otimes n}$ be the
matrix group consisting all $n$-qubit Paulis with phase $\pm 1$ or $\pm i$.

We’ll also introduce some shorthand notation:

######  Definition 2.2.

Let $X_{i}$ and $Z_{i}$ be the Pauli acting only on the $i$-th qubit with $X$
or $Z$ respectively and the identity matrix on all other qubits.

######  Definition 2.3.

For $v\in\\{0,1\\}^{n}$, let $X^{v}=\prod_{i=1}^{n}X_{i}^{v_{i}}$ and
$Z^{v}=\prod_{i=1}^{n}Z_{i}^{v_{i}}$.

Note that $Z^{v}\cdot Z^{w}=Z^{v+w}$, assuming the dimensions of $v$ and $w$
match. It is easy to see that $v\neq w$ also implies that $Z^{v}\neq Z^{w}$.

A stabilizer state $\rho$ is any state that can be written as
$\frac{1}{2^{n}}\sum_{g\in G}g$, where $G$ is an abelian subgroup
$G\subset\mathcal{P}_{n}\setminus\\{-I^{\otimes n}\\}$ without the negative
identity. $G$ is known as the stabilizer group of $\rho$. As it turns out, if
$G$ is order $2^{n}$ then $\rho$ will be a pure state. This leads to the
alternative (and more popular definition) where
$\rho=|\psi\rangle\langle\psi|$, is the unique state that is stabilized by
$G$. That is, for all $g\in G$, $g\ket{\psi}=\ket{\psi}$. This definition
shows why $-I^{\otimes n}$ isn’t allowed to be in $G$, since $-I^{\otimes n}$
stabilizes nothing. It also shows why one must restrict the entries of $G$ to
only have real phase.

######  Proposition 2.4.

Any abelian subgroup of $G\subseteq\mathcal{P}_{n}\setminus\\{-I^{\otimes
n}\\}$ cannot contain any Paulis with an imaginary phase

###### Proof.

Given a Pauli with an imaginary phase, it’s square would be equal to
$-I^{\otimes n}$, making the group not closed. This is a contradiction. ∎

One of the reasons stabilizer states are so important is this bijection
between the stabilizer group of a stabilizer state and the state itself; by
simply knowing the generators of the state one can easily reconstruct the
state. And since there are at most $n$ generators, if one can efficiently
write down the generators themselves then there is a polynomial size
representation of a stabilizer state. We now show how one can write down any
member of a stabilizer group as follows. Given, $P\in\mathcal{P}_{n}$ with
real phase such that $P=\pm\bigotimes_{i}P_{i}$, define a function
$N:\mathcal{P}\rightarrow\\{0,1\\}^{2}$ for each qubit $N(I)=00$, $N(X)=10$,
$N(Z)=11$, and concatenate to make $N(P)=(N(P_{1}),N(P_{2}),\dots,N(P_{n}))$.
Additionally, have an extra bit for the sign for whether the sign is $-1$ or
$1$. This results in a $2n+1$ bit string for each generator, so writing down a
stabilizer state requires only $\mathcal{O}\left(n^{2}\right)$ bits to write
down classically.

###  2.3 Clifford Circuits

######  Definition 2.5.

A Clifford circuit is a unitary $U$ such that
$U\mathcal{P}_{n}U^{\dagger}=\mathcal{P}_{n}$, while ignoring global phase on
the unitary. More formally, consider the normalizer
$\mathcal{N}(\mathcal{P}_{n})=\\{U\in U(2^{n})\mid
U\mathcal{P}_{n}U^{\dagger}=\mathcal{P}_{n}\\}$, and let
$\mathcal{C}_{n}=\mathcal{N}(\mathcal{P}_{n})/U(1)$ be the Clifford group.

More informally, a Clifford circuit maps stabilizer states to other stabilizer
states.

######  Lemma 2.6.

Aaronson and Gottesman [3] Any Clifford circuit has an equivalent Clifford
circuit with $\mathcal{O}\left(n^{2}\right)$ gates and parallel depth
$\mathcal{O}(\log n)$.

Like stabilizer states, generators are an important part of how we deal with
Clifford circuits. If we consider how a Clifford circuit $U$ acts on the
canonical generators of $\mathcal{P}_{n}$, we find that

$\displaystyle
UX_{j}U^{\dagger}=(-1)^{p_{j}}\prod_{i=1}^{n}X_{i}^{\alpha_{ij}}Z_{i}^{\beta_{ij}}\hskip
20.00003ptUZ_{j}U^{\dagger}=(-1)^{q_{j}}\prod_{i=1}^{n}X_{i}^{\gamma_{ij}}Z_{i}^{\theta_{ij}}.$
(1)

A Clifford circuit can then be encoded as a $(2n+1)\times 2n$ boolean matrix
where column $2j-1$ is equal to
$(\alpha_{1j},\beta_{1j},\cdots,\alpha_{nj},\beta_{nj},p_{j})$ and column $2j$
is equal to $(\gamma_{1j},\theta_{1j},\cdots,\gamma_{nj},\theta_{nj},q_{j})$.
However, because commutation relations are preserved, not all possible values
of $\alpha,\beta,\gamma,\theta$ are allowed (the $p$ and $q$ values can be
arbitrary). This leads us to the idea of symplectic matrices.

######  Definition 2.7.

A symplectic matrix over $\mathbb{F}_{2}^{2n}$ is a $2n\times 2n$ matrix $S$
with entries in $\mathbb{F}_{2}$ such that

$\displaystyle
S^{T}\Lambda(n)S=\Lambda(n)\equiv\bigoplus_{i=1}^{n}\begin{pmatrix}0&1\\\
1&0\end{pmatrix}.$ (2)

These matrices form the symplectic group $\text{Sp}(2n,\mathbb{F}_{2})$.

The symplectic matrices preserve the symplectic inner product
$\omega(v,w)=v^{T}\Lambda(n)w$ on $\mathbb{F}_{2}^{2n}$. It turns out that if
we consider the submatrix defined by the first $2n$ rows of our potential
encoding of a clifford circuit, a necessary and sufficient condition to
preserving the commutation relations of the generators is for this submatrix
to be symplectic, as $\\{X_{i}\\}\cup\\{Z_{i}\\}$ form what is known a
symplectic basis. Formally,
$\mathcal{C}_{n}/\mathcal{P}_{n}\cong\text{Sp}(2n,\mathbb{F}_{2})$, where the
Pauli in the divisor determines the $p$ and $q$ values.

###  2.4 CNOT circuits and $\oplus\textsf{L}$

It is a well known fact that every Clifford circuit can be generated using
only $H$, $P$, and CNOT gates as defined below:

$\displaystyle H=\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\\
1&-1\end{pmatrix}\,\,\,\,\,\,P=\begin{pmatrix}1&0\\\
0&i\end{pmatrix}\,\,\,\,\,\,\text{CNOT}=\begin{pmatrix}1&0&0&0\\\ 0&1&0&0\\\
0&0&0&1\\\ 0&0&1&0\end{pmatrix}$ (3)

We note that $X=HP^{2}H$. If we restrict to the subset of circuits that are
generated by only $X$ and CNOT, we get what are known as CNOT circuits [3],
which are a clear subset of Clifford circuits.

######  Definition 2.8 (Aaronson and Gottesman [3]).

The complexity class $\oplus\textsf{L}$ is the class of problems that reduce
to simulating a polynomial-size CNOT circuit.

A perhaps more familiar definition for complexity theorists is the class of
problems that are solvable by a nondeterministic logarithmic-space Turing
machine that accepts if and only if the total number of accepting paths is
odd.

Let us now consider the set of all Clifford circuit that map computational
basis states to other computational basis states, thereby stabilizing the
subgroup $\\{\pm 1\\}\times\\{I,Z\\}^{\otimes n}$. Very briefly, we will call
these classical Clifford circuits as we will now prove that they are largely
equivalent to CNOT circuits.

######  Proposition 2.9.

Let $C$ be an arbitrary classical Clifford circuit. It can be efficiently
generated using solely $X$, $Z$, and CNOT gates. Moreover, it’s effect on the
computational basis states can be entirely simulated using only $X$ and CNOT.

###### Proof.

Let us first consider what happens to a computational basis state by acted
upon by $C$. Referencing Eq. 1, the $\gamma_{ij}$ must be $0$ for all $i$ and
$j$, and we will essentially ignore $\alpha_{ij}$, $\beta_{ij}$, and $p_{j}$
for now leaving us with $\theta_{ij}$ and $q_{j}$. Let us now view the
$\theta_{ij}$ as a $n\times n$ matrix $\Theta$ over $\mathbb{F}_{2}$. Since
every member of $\text{Sp}(2n,\mathbb{F}_{2})$ is full rank, $\Theta$ must
also be full rank. As an example, since the identity circuit is also a
classical Clifford circuit, the resulting $\Theta$ is the $n\times n$ identity
matrix. We note that a CNOT from qubit $i$ to qubit $j$ performs the rowsum
operation of adding row $i$ to row $j$. Thus it is possible to efficiently
construct a circuit with matching $\Theta$ using rowsum operations via CNOT
gates. To get a matching $q_{j}$, one can simply apply an X gate at the
beginning of each qubit that has $q_{j}=1$, since $XZX=-Z$, and the following
CNOT gates will not itself introduce any negative phases. From here, we have
already proved the moreover statement.

To prove the full result, we return to the $\alpha_{ij}$ and $\beta_{ij}$. We
will show that there exists a single unique solution. Similar to $\Theta$ we
will define the corresponding $n\times n$ matrices $A$ and $B$ for the
$\alpha_{ij}$ and $\beta_{ij}$ respectively. Based on Eq. 2, to form a
symplectic basis we find that $A^{T}\Theta=I$ and $A^{T}B=0$, since
$\gamma_{ij}=0$. Clearly $A^{T}=\Theta^{-1}$, which is guaranteed to exist,
and $B=0$ since $A$ will also be full rank. To match the $p_{j}$ values we
simply place $Z$ gates in front of the qubits where $p_{j}=1$, similar to the
$X$ gates for $q_{j}$. ∎

Another way of viewing this is that CNOT circuits are the set of all Clifford
circuits with $\gamma_{ij}=0$ and $p_{j}=0$ for all $i$ and $j$. Using the
moreover part, CNOT circuits can realize any valid full rank $\Theta$.

###  2.5 PAC Learning

The goal of PAC learning is to learn a function relative to a certain
distribution of inputs, rather than in an absolute sense. Let’s say we want to
learn an arbitrary $f$ from some concept class $\mathcal{C}$. If a hypothesis
function $h$ matches the true function $f$ on many of the high probability
inputs, then we can say that we have approximately learned $f$. If we can do
this with high probability for arbitrary $f$, then we probably approximately
(PAC) learned $\mathcal{C}$.

######  Definition 2.10.

Let $\mathcal{C}$ be a set of functions $f:\chi\rightarrow[0,1]$. We say that
$\mathcal{C}$ is $(\epsilon,\delta)$-PAC-learnable if there exists a learner
that, when given samples of the form $(x,f(x))$ for $x\sim\mathcal{D}$ for
arbitrary $f$ and unknown distribution $\mathcal{D}$, outputs with probability
at least $1-\delta$ a hypothesis $h$ with error satisfying

$\operatorname*{\mathbb{E}}_{x\sim
D}\left[\left(f(x)-h(x)\right)^{2}\right]\leq\epsilon.$

The number of samples used is referred to as the sample complexity, and we
refer to the learner being efficient if it can compute $h$ in polynomial time.

From here, one can define two types of learning, based on where $h$ comes
from. If $h$ is allowed to be any function that meets the PAC constraints, we
refer to this as improper learning. If instead $h\in\mathcal{C}$, we get what
is known as proper learning, which will be the focus of this paper. With
proper learning, we can then begin to talk about the consistency problem
formally.

######  Definition 2.11.

Let $S$ be a set of labeled samples such that $|S|<s$. Let
$\textsc{ConsistentSearch}(\mathcal{C},s)$ be the problem of finding a
function $h\in\mathcal{C}$ that is consistent with all of $S$ (i.e., for all
$(x,f(x))\in S$, $f(x)=h(x)$) if such an $h$ exists, otherwise reject.

Intuitively, given a set of samples the best one can really hope to do is find
such an $h$ that gets zero training error and hope that the true error for $h$
is also low. This leads to the idea of generalization, which aims to show that
if for all $(x,f(x))\in S$, $\left|h(x)-f(x)\right|\leq\alpha$ and $|S|>m$ for
suitable $m$ implies

$\operatorname*{\mathbb{E}}_{x\sim
D}\left[\left(f(x)-h(x)\right)^{2}\right]\leq\epsilon$

with high probability. In terms of computational efficiency, this effectively
reduces the problem of proper learning to the consistency problem, or an
approximation of the consistency problem depending on the value of $\eta$. It
also bounds the sample complexity to be at most $m$, since solving the
consistency problem without computational constraints is always doable in this
realizable setting. We will see a formal statements of a generalization
theorem in Section 3.

One can also define the decision version of the consistency problem, which is
deciding if there even exists an $h\in\mathcal{C}$ that is consistent with all
of $S$. We show that the existence of efficient learning algorithms can imply
efficient one-sided error algorithms for the decision version of the
consistency problem.

######  Definition 2.12.

Let $\textsc{ConsistentDecide}(\mathcal{C},s)$ be decision version of the
consistency problem for $\mathcal{C}$ using at most $s$ samples.

######  Proposition 2.13.

An efficient randomized
$\left(\epsilon<\frac{\alpha^{2}}{s^{2}},\delta<\frac{1}{2}+\frac{1}{2s}\right)$111We
abuse notation to signify that $\epsilon$ is a value less than
$\frac{\alpha^{2}}{s^{2}}$ and likewise for $\delta<\frac{1}{2s}$. proper
learning algorithm implies
$\textsc{ConsistentDecide}(\mathcal{C},s)\in\textsf{RP}$ where
$\alpha=\inf_{x\in\chi,f(x)\neq g(x)}\left|f(x)-g(x)\right|$ is the minimum
non-zero error any hypothesis function can make on a single input.

###### Proof.

For every set of samples $S$ such that $|S|\leq s$, we can define the
$\mathcal{D}_{S}$ to be the uniform distribution over all $x\in\chi$ such that
$(x,f(x))\in S$. By coupon collector, if we draw $\mathcal{O}(s\log s)$ many
samples then with probability at least $1-\frac{1}{s}$ we will have drawn
every item from $S$. Now imagine that there exists some hypothesis
$h\in\mathcal{C}$ that is not consistent with $S$. Then our error must be at
least $\frac{\alpha^{2}}{s^{2}}$ by the definition of $\alpha$.

Now assume we have some efficient randomized $(\epsilon,\delta)$ proper
learning algorithm for $\epsilon<\frac{\alpha^{2}}{s^{2}}$ and
$\delta<\frac{1}{2}+\frac{1}{2s}$. When running the learner on an arbitrary
$\mathcal{D}_{S}$, it will see samples $S$ with probability at least
$1-\frac{1}{s}$. To get error less than $\frac{\alpha^{2}}{s^{2}}$ the learner
must then be able to solve the search version consistency problem with
probability $p$ such that $\frac{1}{s}+(1-\frac{1}{s})p\geq 1-\delta$. Solving
for $p$ we find $p\geq\frac{1}{2}$ on accepting instances.

This gives rise to the following algorithm in RP for solving
$\textsc{ConsistentDecide}(\mathcal{C},s)$. Given samples $S$ with $|S|\leq
s$, we can run our learning algorithm and pretend that $S$ is what we sampled
from $\mathcal{D}_{S}$ to get hypothesis $h$. If $h$ is consistent with $S$
then accept, otherwise reject. On an accepting instance $h$ will be consistent
with probability at least $\frac{1}{2}$ while on rejecting instances it will
never be consistent so the algorithm will always reject. ∎

Informally, it can be possible to go the other way and show that an efficient
algorithm for $\textsc{ConsistentDecide}(\mathcal{C},s)$ implies an efficient
proper learner for $\mathcal{C}$. Namely, if a search-to-decision reduction
exists for the consistency problem on $\mathcal{C}$ and a generalization
theorem exists for the learning problem on $\mathcal{C}$ then we can also
expect to show that an efficient algorithm for the decision problem would
imply an efficient proper learner for $\mathcal{C}$. Of particular interest
will be -Complete problems, which always admit search-to-decision reductions
[28].

##  3 PAC Learning Quantum Circuits

Aaronson [1] was the first to try and apply the ideas of PAC learning to that
of learning quantum states by giving a generalization theorem for quantum
states. Here $\chi$ is the set of all two-outcome measurements and
$\mathcal{C}$ the set of quantum states with samples of the form
$\left(E,\operatorname{Tr}\left[E\rho\right]\right)$. We stress that with this
result and the proceeding result, the information is assumed to be classical
in nature222While the astute reader may note that representation of the
measurements and states may be impossible to efficiently classically encode
simply due to the dimension, for the case of Clifford/CNOT circuits later this
will not be an issue.. Caro and Datta [18] then gave a similar generalization
algorithm but for quantum circuits, where the goal is to learn

$\displaystyle\left\\{f(x,y)=\left|\braket{x}{U}{y}\right|^{2}\bigm{|}U\in\mathcal{U}_{\Delta,\Gamma}\left(d^{n}\right)\right\\}$
(4)

such that $\mathcal{U}_{\Delta,\Gamma}(d^{n})$ is the set of all unitaries on
$n$ qudits formed by two qudit gates of depth at most $\Delta$ and size at
most $\Gamma$. In their proof the measurements were rank 1 projections with
tensor product structure. We present a modified version of their result to
allow arbitrary rank measurements with an informal proof sketch explaining why
our modification works:

######  Theorem 3.1.

Caro and Datta [18] Let $X$ be the set of quantum states on $n$ qudits, and
let $Y$ be the set of all projectors on $n$ qudits. Let $U_{*}$ be a quantum
circuit of 2-qudit quantum unitaries with size $\Gamma$ and depth $\Delta$.
Let $\mathcal{D}$ be a probability distribution on $X\times Y$ unknown to the
learner. Let

$S=\left\\{\left(\left(x^{(i)},y^{(i)}\right),\operatorname{Tr}\left[y^{(i)}Ux^{(i)}U^{\dagger}\right]\right)\right\\}^{m}_{i=1}$

be a corresponding training data drawn i.i.d according to $\mathcal{D}$. Let
$\delta,\epsilon,\alpha,\beta\in(0,1)$. Then, training data of size

$m=\mathcal{O}\left(\frac{1}{\epsilon}\left(\Delta
d^{4}\Gamma^{2}\log\Delta\log^{2}\left(\frac{\Delta
d^{4}\Gamma^{2}\log(\Gamma)}{(\beta-\alpha)\epsilon}\right)+\log\frac{1}{\delta}\right)\right)$

suffice to guarantee that, with probability $\geq 1-\delta$ with regard to
choice of the training data, any quantum circuit $U$ of size $\Gamma$ and
depth $\Delta$ that satisfies

$\displaystyle\left|\operatorname{Tr}\left[y^{(i)}U_{*}x^{(i)}U_{*}^{\dagger}\right]-\operatorname{Tr}\left[y^{(i)}Ux^{(i)}U^{\dagger}\right]\right|\leq\alpha\,\,\,\,\,\forall
1\leq i\leq m$

also satisfies

$\displaystyle\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\left(\operatorname{Tr}\left[y^{(i)}U_{*}x^{(i)}U_{*}^{\dagger}\right]-\operatorname{Tr}\left[y^{(i)}Ux^{(i)}U^{\dagger}\right]\right)^{2}\right]\leq(1-\epsilon)\beta^{2}+4\epsilon$

###### Proof.

The Caro and Datta results shows that with regard to rank 1 projectors
$|y\rangle\langle y|$, the trace $\operatorname{Tr}\left[|y\rangle\langle
y|\cdot U|x\rangle\langle x|U^{\dagger}\right]$ can be described as a
polynomial over the entries of $U$ with bounded degree $d$. Because every rank
$r$ projector $E$ is simply the sum of $r$ rank 1 projectors, linearity of the
trace tells us that the resulting trace $\operatorname{Tr}\left[E\cdot
U|x\rangle\langle x|U^{\dagger}\right]$ is the linear combination of $r$
polynomials with bounded degree. Thus we are again left with a polynomial
bounded by the same degree $d$. ∎

Now that we have a formal statement of a generalization theorem, we can also
formalize the ideas at the end of Section 2.5 and expand on them.

######  Lemma 3.2.

Let $\mathcal{C}$ be a subset of $2$-qudit quantum unitaries with size
$\Gamma$ and depth $\Delta$ and let

$m=\mathcal{O}\left(\frac{1}{\epsilon}\left(\Delta
d^{4}\Gamma^{2}\log\Delta\log^{2}\left(\frac{\Delta
d^{4}\Gamma^{2}\log(\Gamma)}{\beta\epsilon}\right)+\log\frac{1}{\delta}\right)\right)$

be the parameter from Theorem 3.1. If
$\textsc{ConsistentDecide}(\mathcal{C},s)$ for $s>m$ is -Complete then an
-oracle can be used to efficiently
$\left((1-\epsilon)\beta^{2}+\epsilon,\delta\right)$ proper learn
$\mathcal{C}$.

###### Proof.

Because search-to-decision reductions exist for all -Complete problems [28],
an oracle for $\textsc{ConsistentDecide}(\mathcal{C},s)$ can be used to
efficiently solve $\textsc{ConsistentSearch}(\mathcal{C},s)$. Let us run our
algorithm for $\textsc{ConsistentSearch}(\mathcal{C},s)$ on a sample $S$ such
that $s\geq|S|\geq m$. We now have a $U_{*}$ such that

$\left|\operatorname{Tr}\left[y^{(i)}U_{*}x^{(i)}U_{*}^{\dagger}\right]-\operatorname{Tr}\left[y^{(i)}Ux^{(i)}U^{\dagger}\right]\right|=0\,\,\,\,\,\forall
1\leq i\leq m$

and so by Theorem 3.1

$\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left[\left(\operatorname{Tr}\left[y^{(i)}U_{*}x^{(i)}U_{*}^{\dagger}\right]-\operatorname{Tr}\left[y^{(i)}Ux^{(i)}U^{\dagger}\right]\right)^{2}\right]\leq(1-\epsilon)\beta^{2}+\epsilon.$

Naturally, any other oracle for an -Complete problem can also be used since
they all reduce to one another, thus completing the proof. ∎

######  Corollary 3.3.

Let $\mathcal{C}$ be a subset of $2$-qudit quantum unitaries with size
$\Gamma$ and depth $\Delta$ and let

$m=\mathcal{O}\left(\frac{1}{\epsilon}\left(\Delta
d^{4}\Gamma^{2}\log\Delta\log^{2}\left(\frac{\Delta
d^{4}\Gamma^{2}\log(\Gamma)}{\beta\epsilon}\right)+\log\frac{1}{\delta}\right)\right)$

be the parameter from Theorem 3.1. If
$\textsc{ConsistentDecide}(\mathcal{C},s)$ for $s>m$ is -Complete and
$\textsf{RP}=\np$ then an RP-oracle can be used to efficiently
$\left((1-\epsilon)\beta^{2}+\epsilon,\frac{\delta}{c}\right)$ proper learn
$\mathcal{C}$ for arbitrary $c=\mathcal{O}(1)$.

###### Proof.

If $\np\subseteq\textsf{RP}$ then there must exist an efficient one-sided
error randomized algorithm $\mathcal{A}$ for
$\textsc{ConsistentDecide}(\mathcal{C},s)$. With probability at least
$\frac{1}{2}$ if we query $A$ it will output the same thing -oracle on YES
instances. We can efficiently boost our success probability such that the
probability that the algorithm fails to perfectly match the -oracle on the at
most $\operatorname{poly}(n)$ queries to the oracle is less than $\frac{1}{c}$
for $c=\mathcal{O}(1)$, resulting in algorithm $\mathcal{A}^{\prime}$.

By Lemma 3.2 if we had an $\np$-oracle there would then exist an efficient
$(\epsilon,\delta)$ proper learner for $\mathcal{C}$ when given at least

$m=\mathcal{O}\left(\frac{1}{\epsilon}n^{4}\log n\log\\!\log
n\log^{2}\left(\frac{n\log^{2}n}{\epsilon}\right)+\frac{1}{\delta}\right)$

samples. Naturally, this reduction can only use $\operatorname{poly}(n)$ calls
to the -oracle, so with probability at least $1-\frac{1}{c}$ our queries from
$\mathcal{A}^{\prime}$ will be correct. The total probability that the learner
outputs a bad hypothesis is at most $\frac{\delta}{c}$. Thus we have an
efficient $\left((1-\epsilon)\beta^{2}+\epsilon,\frac{\delta}{c}\right)$
proper learner for $\mathcal{C}$. ∎

##  4 PAC Learning applied to Clifford Circuits

Because of the works of Rocchetto [36] and Lai and Cheng [31], Clifford
circuits are a prime candidate for an efficiently PAC-learnable class of
circuits. Additionally, due to Lemma 2.6 one could hope to use Lemma 3.2 with
$d=2$, $\Delta=\mathcal{O}(\log n)$, and $\Gamma=\mathcal{O}(n^{2})$ in the
same way the main theorem from Aaronson [1] was invoked for learning
stabilizer states.

Noting that each Pauli matrix is Hermitian, a very natural way to measure a
stabilizer state is in a product basis where we measure each qubit with
respect to a Pauli.

######  Definition 4.1.

If $P\in\mathcal{P}_{n}$ is a Pauli operator, then the two-outcome measurement
associated with $P$ is $\frac{I^{\otimes n}+P}{2}$, and is referred to as a
Pauli measurement.

######  Definition 4.2.

Let the problem of PAC learning Clifford circuits with respect to Pauli
measurements be defined as follows. Let $C$ be an unknown Clifford circuit and
let $\mathcal{D}$ be an unknown joint distribution over both stabilizer states
and Pauli measurements. Finally, let samples to $C$ be given as

$\left(\rho,E,\operatorname{Tr}\left[EC\rho C^{\dagger}\right]\right)$

where $\rho,E\sim\mathcal{D}$ are a stabilizer state and Pauli measurement
jointly drawn from $\mathcal{D}$ and represented as classical bit strings
using the stabilizer formalism. The goal is to then learn the measurements
$\operatorname{Tr}\left[EC\rho C^{\dagger}\right]$ up to error $\epsilon$
under the distribution $\mathcal{D}$.

A critical part of Rocchetto [36] was noting that the measurement results with
Pauli measurements could only have three distinct values:

######  Lemma 4.3.

Let $E^{P}=\frac{I^{\otimes n}+P}{2}$ be a Pauli measurement associated to a
Pauli operator $P\in\mathcal{P}_{n}$ and $\rho$ be an $n$-qubit stabiliser
state. Then $\operatorname{Tr}\left[E^{P}C\rho C^{\dagger}\right]$ can only
take on the values $\left\\{0,\frac{1}{2},1\right\\}$, and:

$\displaystyle\begin{cases}\operatorname{Tr}\left[E^{P}C\rho
C^{\dagger}\right]=1\text{ iff $P$ is a stabilizer of $C\rho C^{\dagger}$;}\\\
\operatorname{Tr}\left[E^{P}C\rho C^{\dagger}\right]=1/2\text{ iff neither $P$
nor $-P$ is a stabilizer of $C\rho C^{\dagger}$;}\\\
\operatorname{Tr}\left[E^{P}C\rho C^{\dagger}\right]=0\text{ iff $-P$ is a
stabilizer of $C\rho C^{\dagger}$.}\end{cases}$

Now let $S$ be the stabilizer group of $\rho$. From this, we can gather that
if $\operatorname{Tr}\left[E^{P}C\rho C^{\dagger}\right]=1$ then
$C^{\dagger}PC\in S$, and if $\operatorname{Tr}\left[E^{P}C\rho
C^{\dagger}\right]=0$ then $C^{\dagger}PC\in-S$ where $-S=\\{-G\mid G\in
S\\}$. Finally, if $\operatorname{Tr}\left[E^{P}C\rho
C^{\dagger}\right]=\frac{1}{2}$ then $C^{\dagger}PC$ is in the complement of
$S\cup-S$. If the measurement $E^{P}$ appears multiple times, we can gather
further information. For instance, have

$S=\left\\{\left(\rho_{i},E^{P},\operatorname{Tr}\left[E^{P}C\rho
C^{\dagger}\right]\right)\right\\}$

be the set of all samples such that $E^{P}$ is the measurement taken and let
$S_{i}$ be the stabilizer group of each $\rho_{i}$. Based on each
$\operatorname{Tr}\left[E^{P}C\rho_{i}C^{\dagger}\right]$ we know that
$C^{\dagger}PC$ must lie in some set $H_{i}$, and thus must lie in
$\bigcap_{i}H_{i}$. To actually be a Clifford circuit, we must also add the
constraint that $C^{\dagger}PC\neq I^{\otimes n}$, giving us

$C^{\dagger}PC\subset\left(\bigcap_{i}H_{i}\right)\setminus\left\\{I^{\otimes
n}\right\\}.$

The problem of finding a Clifford circuit with zero training error then
reduces to the search problem of finding a set of
$\alpha,\beta,\gamma,\theta,p,q$ from Eq. 1 that is consistent with all of
these constraints while remaining symplectic according to Eq. 2. Let
$\mathcal{C}$ be the set of Clifford circuits. We will call this problem
$\textsc{CliffordSearch}(s)=\textsc{ConsistentSearch}(\mathcal{C},s)$. Due to
Gottesman-Knill [25, 3] showing that Clifford circuits are classically
simulable, the act of verifying that we have a circuit that has zero training
error is efficient meaning that the decision version
$\textsc{CliffordDecide}(s)=\textsc{ConsistentDecide}(\mathcal{C},s)$ of the
problem is in :

######  Proposition 4.4.

The decision problem, $\textsc{CliffordDecide}(\text{poly}(n))$, of deciding
if there exists a Clifford circuit consistent with polynomially sized sample
$S$ is in .

###### Proof.

Given a set of $\alpha,\beta,\gamma,\theta,p,q$, it easy to check that the
$\gamma,\theta,p,q$ form a symplectic matrix by checking with respect to
$\Lambda(n)$. Checking that they are consistent with the samples in $S$ can be
done by iterating through $S$ since the trace can be computed efficiently
using Gottesman-Knill. ∎

Knowing this, we find that
$\textsc{CliffordSearch}(\text{poly}(n))\in\mathsf{FNP}$. This property
extends to analogous problems for CNOT circuits
$\textsc{CNOTSearch}(\text{poly}(n))$ and
$\textsc{CNOTDecide}(\text{poly}(n))$, since one can also efficiently verify
that $\gamma_{ij}=0$ and $p_{j}=0$ for all $i$ and $j$.

##  5 Generating Samples with Certain Constraints

We will now show how we can use samples from PAC learning to generate certain
kinds of constraints. It will suffice to only consider CNOT circuits with
computational basis state measurements and measurements of the form
$\left\\{I,Z\right\\}^{\otimes n}$. The net effect of this is that from a PAC
learning standpoint, for unknown CNOT circuit $C$ we only need to figure a set
of $C^{\dagger}Z_{i}C$ that is consistent with the samples as described in
Section 4. Since we will never be tested on a measurement with some component
of $X_{i}$ involved, this is equivalent to finding the $\theta_{ij}$ and
$q_{j}$ values from Eq. 1. We will again choose to view the $\theta_{ij}$ as
the matrix $\Theta$, such that $\Theta$ must be full rank.

######  Definition 5.1.

Given a set of abelian generators $\\{P_{i}\\}$, let

$\rho(P_{1},P_{2},\dots,P_{n})=\frac{1}{2^{n}}\sum_{P\in\textnormal{Span}(\\{P_{i}\\})}P$

be the stabilizer state that is formed from that stabilizer group.

######  Lemma 5.2.

Let $C$ be a CNOT circuit on $n$ qubits and have
$v+\textnormal{Span}(w)\subset\\{0,1\\}^{n}$ be a one-dimensional affine
subspace of column vectors such that $v\neq w$ and $w,v\neq 0$. Given an
arbitrary pauli $P$ there exists a set of $n$ samples that constrains
$C^{\dagger}PC$ to only have consistent solutions lying in
$Z^{v}\cdot\textnormal{Span}\left(Z^{w}\right)$. Furthermore these samples can
be efficiently generated.

###### Proof.

Let $(v,w,v_{3},\cdots,v_{n})$ be an arbitrary basis for $\\{0,1\\}^{n}$
containing $v$ and $w$. This can be done using $\mathcal{O}(n)$ samples in
expectation. Recalling Definition 2.3, let us start by creating the sample

$\displaystyle\bigg{(}\rho(Z^{v},Z^{w},Z^{v_{3}},Z^{v_{4}},\dots,Z^{v_{n}}),\frac{I+P}{2},1\bigg{)},$

which limits $C^{\dagger}PC$ to be in $\\{I,Z\\}^{\otimes n}$ with positive
phase.

We can create the set of samples:

$\displaystyle\bigg{(}\rho(Z^{v},Z^{w},-Z^{v_{3}},$ $\displaystyle
Z^{v_{4}},\dots,Z^{v_{n}}),\frac{I+P}{2},1\bigg{)},$
$\displaystyle\bigg{(}\rho(Z^{v},Z^{w},Z^{v_{3}},-$ $\displaystyle
Z^{v_{4}},\dots,Z^{v_{n}}),\frac{I+P}{2},1\bigg{)},$ $\displaystyle\vdots$
$\displaystyle\bigg{(}\rho(Z^{v},Z^{w},Z^{v_{3}},$ $\displaystyle
Z^{v_{4}},\dots,-Z^{v_{n}}),\frac{I+P}{2},1\bigg{)}.$

By construction $C^{\dagger}PC$ cannot have any component of $Z^{v_{3}}$
because of the first sample of this set, nor any $Z^{v_{i}}$ for $i>3$ due to
the remaining samples. This leaves $C^{\dagger}PC$ to be one of $Z^{v}$,
$Z^{w}$, or $Z^{v+w}$ (since it cannot be identity). To remedy this, we can
introduce the final sample:

$\displaystyle\bigg{(}\rho(-Z^{v},Z^{w},Z^{v_{3}},Z^{v_{4}},\dots
Z^{v_{n}},\frac{I+P}{2},0\bigg{)},$

which then eliminates $Z^{w}$ (and identity, due to the negative sign). The
total number of samples is $n$ and the whole process takes polynomial in $n$
time. ∎

We can easily extend this to the $0$-dimensional case by simply treating $w$
as $v_{2}$, using an extra sample to remove the last dimension. More
importantly, let’s say we’ve constrained $C^{\dagger}Z^{x}C$ to lie in
$Z^{v}\cdot\textnormal{Span}(Z^{w})$. The effect of this on $\Theta$ is that
if we sum the columns $i$ where $x_{i}=1$ then the sum must lie in
$v+\textnormal{Span}(w)$.

######  Corollary 5.3.

Let

$v+\textnormal{Span}(w)=\begin{bmatrix}|&|&|&|\\\ v_{1}&v_{2}&\dots&v_{k}\\\
|&|&|&|\\\ \end{bmatrix}+\textnormal{Span}\left(\begin{bmatrix}|&|&|&|\\\
w_{1}&w_{2}&\dots&v_{k}\\\ |&|&|&|\\\ \end{bmatrix}\right)$

be a one-dimensional affine subspace of $n\times k$ matrices over $\\{0,1\\}$
such that for all $i$, $v_{i}\neq w_{i}$ and $v_{i},w_{i}\neq 0$. Finally, let
$\Theta^{\prime}$ be an arbitrary $n\times k$ submatrix of $\Theta$. Then
there exists a set of $kn+k-1$ samples that constrain $\Theta^{\prime}$ to
only have consistent solutions lying in $v+\textnormal{Span}(w)$ for CNOT
circuit $C$. Furthermore these samples can be efficiently generated.

###### Proof.

WLOG, we will let the set of $k$ different columns we choose for
$\Theta^{\prime}$ to be columns $1$ through $k$. We will use induction on $k$
to prove this corollary, with the base case covered by Lemma 5.2. Now let us
assume that we have samples that constrain columns $2$ through $k$ to lie in

$\begin{bmatrix}|&|&|&|\\\ v_{2}&v_{3}&\dots&v_{k}\\\ |&|&|&|\\\
\end{bmatrix}+\textnormal{Span}\left(\begin{bmatrix}|&|&|&|\\\
w_{2}&w_{3}&\dots&w_{k}\\\ |&|&|&|\\\ \end{bmatrix}\right).$

The goal will be to generate constraints such that if column 2 is $v_{2}$ then
column 1 must be $v_{1}$. Otherwise, if column 2 is $v_{2}+w_{2}$ then column
1 is constrained to be $v_{1}+w_{1}$. To start us off, Lemma 5.2 lets us
constrain column $1$ to lie in $v_{1}+\textnormal{Span}(w_{1})$. We can then
use Lemma 5.2 again to constrain the sum of columns $1$ and $2$ to lie in
$v_{1}+v_{2}+\textnormal{Span}(w_{1}+w_{2})$. If we focus on columns $1$ and
$2$, the solutions to this specific constraint lie in an affine subspace that
starts with either

$\begin{bmatrix}|&|\\\ v_{1}+v_{2}&\vec{0}\\\
|&|\end{bmatrix}\text{or}\begin{bmatrix}|&|\\\
v_{1}+w_{1}+v_{2}+w_{2}&\vec{0}\\\ |&|\end{bmatrix}$

and then adds the same vector to both columns. To lie in the intersection of
the solutions we already have, we will need to set column $2$ to either be
$v_{2}$ or $v_{2}+w_{2}$ such that the the whole set of columns from $2$ to
$k$ lies in either

$\begin{bmatrix}|&|&|&|\\\ v_{2}&v_{3}&\dots&v_{k}\\\ |&|&|&|\\\
\end{bmatrix}\text{or}\begin{bmatrix}|&|&|&|\\\
v_{2}+w_{2}&v_{3}+w_{3}&\dots&v_{k}+w_{k}\\\ |&|&|&|\\\ \end{bmatrix}.$

as described before. The only way to get to the first value is to add

$\begin{bmatrix}|&|\\\ v_{2}&v_{2}\\\ |&|\end{bmatrix}$

to either starting point to get

$\begin{bmatrix}|&|\\\ v_{1}&v_{2}\\\
|&|\end{bmatrix}\text{and}\begin{bmatrix}|&|\\\ v_{1}+w_{1}+w_{2}&v_{2}\\\
|&|\end{bmatrix}$

respectively. Examining the constraints on the first column,
$v_{1}+w_{1}+w_{2}\neq v_{1}+w_{1}$ since $w_{2}\neq 0$ so if the second
column is $v_{2}$ then the first column must be $v_{1}$ as desired.

To get to $v_{2}+w_{2}$ as the value in the second column we instead need to
add

$\begin{bmatrix}|&|\\\ v_{2}+w_{2}&v_{2}+w_{2}\\\ |&|\end{bmatrix}$

to either starting points to get

$\begin{bmatrix}|&|\\\ v_{1}+w_{2}&v_{2}+w_{2}\\\
|&|\end{bmatrix}\text{and}\begin{bmatrix}|&|\\\ v_{1}+w_{1}&v_{2}+w_{2}\\\
|&|\end{bmatrix}$

respectively. Again, $v_{1}+w_{2}\neq v_{1}$ because $w_{2}\neq 0$. Thus if
the second column is $v_{2}+w_{2}$ then the first column must be
$v_{1}+w_{1}$.

Collectively, we achieve our goal of constraining the entire solution to lie
in $v+\textnormal{Span}(w)$. We used $n$ samples at the first step and $n+1$
for every inductive step after, giving us a total number of samples of
$(n+1)(k-1)+n=kn+k-1$. Since each step was efficient than the whole process
takes polynomial in $n$ time to generate all of the samples. ∎

##  6 On the -Completeness of NonSingularity

######  Definition 6.1.

Given matrices $M_{0},M_{1},\dots,M_{k}$ over some field $\mathbb{F}$,
NonSingularity is the problem of deciding if there exists
$\alpha_{1},\alpha_{2},\dots,\alpha_{k}$ such that
$M_{0}+\sum_{i}\alpha_{i}M_{i}$ results in a non-singular matrix.

######  Theorem 6.2 (Buss et al. [17]).

NonSingularity over $\mathbb{F}_{2}$ is -Complete.

The high level idea of the proof is to first reduce a 3SAT instance over
variables $\\{x_{i}\\}$ to solving an arithmetic formula $F$. The formula is
then turned into a weighted directed graph whose adjacency matrix $M(x)$ has a
determinant that is equal to the formula $F$, where $M(x)$ has entries from
$\\{0,1\\}\cup\\{x_{i}\\}$, and can thus be viewed as an affine subspace over
$\mathbb{F}_{2}^{(|F|+2)\times(|F|+2)}$.

While we will not prove the correctness of this statement, we will want to
ascertain exactly what kind of $M_{i}$ are formed through the reduction. We
now describe the construction of the graph (see Fig. 1 and Fig. 2 for relevant
illustrations):

Formula $F$ | The series-parallel $s$-$t$ graph $G_{F}$ with edge withs
---|---
Constant $c$ | $s$$t$$c$$1$
Variable $x$ | $s$$t$$x$$1$
$F=F_{1}\cdot F_{2}$ | $G_{F_{1}}$$G_{F_{2}}$$s=s_{1}$$t_{1}=s_{2}$$t=t_{2}$
$F=F_{1}+F_{2}$ | $G_{F_{1}}$$G_{F_{2}}$$s=s_{1}=s_{2}$$t=t_{1}=t_{2}$
Figure 1: Inductive Construction from Formula to Graph

$F:x_{1}(x_{2}+x_{3})+x_{3}\cdot x_{4}$

$s$$t$$x_{1}$$1$$x_{2}$$x_{3}$$1$$1$$x_{3}$$1$$x_{4}$$1$$1$$1$$1$$1$$1$$1$$1$$1$$1$

$\begin{pmatrix}0&x_{1}&0&0&0&x_{3}&0&0&0\\\ 0&1&1&0&0&0&0&0&0\\\
0&0&1&x_{2}&x_{3}&0&0&0&0\\\ 0&0&0&1&0&0&0&0&1\\\ 0&0&0&0&1&0&0&0&1\\\
0&0&0&0&0&1&1&0&0\\\ 0&0&0&0&0&0&1&x_{4}&0\\\ 0&0&0&0&0&0&0&1&1\\\
1&0&0&0&0&0&0&0&1\\\ \end{pmatrix}$

Figure 2: Example of constructing the adjacency matrix with a specific
determinant

  * •

For each atomic formula $F^{\prime}$, create vertices $s$ and $t$.

For each constant $c$ create a unique node $v_{c}$ with a path from $s$ to
$v_{c}$ with weight $c$ and a path from $v_{c}$ to $t$ with weight $1$.

For each variable $x_{i}$ create a unique node $v_{x_{i}}$ with a path from
$s$ to $v_{x_{i}}$ with weight $x_{i}$ and a path from $v_{x_{i}}$ to $t$ with
weight $1$.

  * •

For multiplication of $F_{i}$ and $F_{j}$, place the graphs of $F_{i}$ and
$F_{j}$ in series.

  * •

For addition of $F_{i}$ and $F_{j}$, place the graphs of $F_{i}$ and $F_{j}$
in parallel.

  * •

Create a path of weight $1$ from the global $t$ vertex to the global $s$
vertex.

  * •

Create self loops at every vertex besides the global $s$ vertex.

Let $M$ be the resulting adjacency matrix of this graph. For every entry that
is a constant, we can assign that to $M_{0}$. Then for each variable $x_{i}$,
we can set $M_{i}$ to be the matrix that is zero everywhere except where
$x_{i}$ appears in $M$. As an example, for a matrix

$\displaystyle M(x)=\begin{pmatrix}x_{1}&1\\\ x_{2}&x_{1}\end{pmatrix}$

we can describe it using $M(x)=M_{0}+x_{1}M_{1}+x_{2}M_{2}$ where

$\displaystyle M_{0}=\begin{pmatrix}0&1\\\ 0&0\end{pmatrix}$ $\displaystyle
M_{1}=\begin{pmatrix}1&0\\\ 0&1\end{pmatrix}$ $\displaystyle
M_{2}=\begin{pmatrix}0&0\\\ 1&0\end{pmatrix}$

######  Corollary 6.3.

NonSingularity over $\mathbb{F}_{2}$ is still -Complete if one only considers
$M_{1},M_{2},\dots,M_{n}$ that are non-zero on disjoint columns. That is, no
two $M_{i}$ $M_{j}$ exist such that column $k$ are both non-zero for arbitrary
$k$. In addition, if we restrict to the non-zero columns of a particular
$M_{i}$ for $i>0$ then

$M_{0}+\textnormal{Span}(M_{i})=\begin{bmatrix}|&|&|&|\\\
v_{1}&v_{2}&\dots&v_{k}\\\ |&|&|&|\\\
\end{bmatrix}+\textnormal{Span}\left(\begin{bmatrix}|&|&|&|\\\
w_{1}&w_{2}&\dots&v_{k}\\\ |&|&|&|\\\ \end{bmatrix}\right)$

such that for all $j$, $v_{j}\neq w_{j}$ and $v_{j},w_{j}\neq 0$. We will call
this the Simplified NonSingularity problem.

###### Proof.

Rather than reduce the general problem to this problem, we merely show that
the reduction from 3SAT naturally leads to instances of this specific problem.
Let $G$ be the graph produced by the reduction from 3SAT with adjacency matrix
$M(x)$. We first need to show that from the construction of $G$, the resulting
$M(x)$ has at most one variable appears in each column such that the $M_{i}$
act on disjoint columns for $i>0$. If $M(x)_{ij}=1$ if and only if there
exists an edge from vertex $i$ to vertex $j$, then we require that no more
than one variable-weighted edge can direct to any particular vertex in $G$.

By the construction given above, we see that every instance of a variable will
connect to it’s own unique vertex, with no other variable possibly connected
to it. This conversely means no more than one variable weighted edge can
connect to any particular vertex. For variable $x_{i}$ with $i>0$, the matrix
$M_{i}$ will then be nonzero for the columns of the adjacency matrix
associated with these vertices receiving the edges with weight $x_{i}$. Since
none of these vertices will receive both $x_{i}$ and some $x_{j}$, then the
$M_{i}$ will be nonzero for disjoint columns. Furthermore, since the weight of
an edge will never be $x_{i}+1$ then we ensure that if we restrict to the non-
zero columns of a particular $M_{i}$ for $i>0$ then

$M_{0}+\textnormal{Span}(M_{i})=\begin{bmatrix}|&|&|&|\\\
v_{1}&v_{2}&\dots&v_{k}\\\ |&|&|&|\\\
\end{bmatrix}+\textnormal{Span}\left(\begin{bmatrix}|&|&|&|\\\
w_{1}&w_{2}&\dots&v_{k}\\\ |&|&|&|\\\ \end{bmatrix}\right)$

such that for all $j$, $v_{j}\neq w_{j}$ and $w_{j}\neq 0$.

Finally, to ensure that $v_{j}\neq 0$, we note that each vertex besides $s$
receives a self loop with weight $1$. $s$ instead receives an edge from $t$
with weight $1$. These self loops and the edge from $t$ to $s$ ensures that
each column of $M_{0}$ has at least entry with $1$ in it such that the
$v_{j}\neq 0$. ∎

##  7 PAC Learning CNOT Circuits and

######  Lemma 7.1.

The decision problem, $\textsc{CNOTDecide}((n+1)n)$, of deciding whether or
not there exists a CNOT circuit consistent with at most $(n+1)n$ samples is
-Complete.

###### Proof.

By Corollary 6.3, if one can determine if an affine subspace of a certain
constrained set of matrices contains a full rank matrix then one can solve all
of . Looking at each individual $M_{i}$ for $i>0$, they are all non-zero on
disjoint columns. If we restrict to the non-zero columns of a particular
$M_{i}$ for $i>0$, we find that if we consider the space
$M_{0}+\textnormal{Span}(M_{i})$, that $M_{0}$ and $M_{i}$ meet the
requirements for Corollary 5.3. Since the $M_{i}$ act on disjoint columns, if
we apply Corollary 5.3 for each $M_{i}$ then we have efficiently created a set
of samples $S$ that restricts those columns of $\Theta$, the matrix form of
$\theta_{ij}$ values, to lie in $M_{0}+\textnormal{Span}(\\{M_{i}\\})$. To fix
the columns not touched by the $M_{i}$, it is not hard to show that the ideas
of Lemma 5.2 can also create a 0-dimensional affine space over these columns,
thereby setting the whole matrix to lie in
$M_{0}+\textnormal{Span}(\\{M_{i}\\})$. Altogether, we are able to use Lemma
5.2 and Corollary 5.3 to set $\Theta$ to lie in $M(x)$ from Simplified
NonSingularity. Since Proposition 2.9 ensures us that CNOT circuits can
instantiate any realizable $\Theta$, there will exist a CNOT circuit
consistent with $S$ if and only if $M(x)$ is an accepting instance. This shows
$\textsc{CNOTDecide}((n+1)n)$ is -Hard. Combined with Proposition 4.4 we find
that $\textsc{CNOTDecide}((n+1)n)$ to be -Complete. ∎

Since
$\textsc{CNOTDecide}((n+1)n)\subset\textsc{CNOTDecide}(\operatorname{poly}(n))$
then $\textsc{CNOTDecide}(\operatorname{poly}(n))$ is also -Hard.

######  Theorem 7.2 (Formal Statement of Theorem 1.1).

There exists an efficient randomized $(\epsilon,\delta)$ proper PAC learner
for CNOT circuits with arbitrary $\epsilon$ and $\delta$ as arbitrary
$\frac{1}{\operatorname{poly}(n)}$ values if and only if $\textsf{RP}=\np$.
Furthermore, an efficient quantum $(\epsilon,\delta)$ proper PAC learner for
CNOT circuits with arbitrary $\epsilon$ and $\delta$ as arbitrary
$\frac{1}{\operatorname{poly}(n)}$ values exists if and only if
$\np\subseteq\textsf{RQP}$.

###### Proof.

We will start by proving the $\np\subseteq\textsf{RP}$ version for classical
randomized learners. The quantum version will follow trivially by replacing
the learner with a quantum algorithm and therefore RP with RQP. The only
change then is that $\np\subseteq\textsf{RQP}$ does not necessary imply
$\np=\textsf{RQP}$ like it does with RP.

Because CNOT circuits with classical inputs and measurements only has labels
$0$ and $1$, the smallest non-zero error is $1$. By Proposition 2.13 with
$\alpha=1$, an efficient

$\left(\epsilon<\frac{1}{(n+1)^{2}n^{2}},\delta<\frac{1}{2}+\frac{1}{2(n+1)n}\right)$

randomized proper learner for CNOT circuits will imply
$\textsc{CNOTDecide}((n+1)n)\in\textsf{RP}$. Since
$\textsc{CNOTDecide}((n+1)n)$ is -Complete by Lemma 7.1, efficient randomized
learners for CNOT circuits with arbitrary
$\epsilon=\frac{1}{\operatorname{poly}(n)}$ and
$\delta=\frac{1}{\operatorname{poly}(n)}$ are only possible if
$\np\subseteq\textsf{RP}$.

Conversely, by Corollary 3.3 with $\beta=\frac{1}{2}$, $d=2$,
$\epsilon=\frac{4\epsilon^{\prime}-1}{3}$, $\delta=c\delta^{\prime}$,
$\Delta=\mathcal{O}(\log n)$ and $\Gamma=\mathcal{O}(n^{2})$ if
$\np\subseteq\textsf{RP}$ then there must exist an efficient
$(\epsilon^{\prime},\delta^{\prime})$ proper learner for CNOT circuits as long
as the number of samples $m$ is polynomial in $n$. For arbitrary
$\epsilon^{\prime}=\frac{1}{\operatorname{poly}(n)}$ and
$\delta^{\prime}=\frac{1}{\operatorname{poly}(n)}$ our required number of
samples becomes

$m=\mathcal{O}\left(\frac{1}{\epsilon}\left(\Delta
d^{4}\Gamma^{2}\log\Delta\log^{2}\left(\frac{\Delta
d^{4}\Gamma^{2}\log(\Gamma)}{\beta\epsilon}\right)+\log\frac{1}{c\delta}\right)\right)=\mathcal{O}(\operatorname{poly}(n))$

This is sufficiently small as desired, completing the proof. ∎

######  Corollary 7.3 (Formal Statement of Corollary 1.2).

There exists an efficient randomized $(\epsilon,\delta)$ proper PAC learner
for Clifford circuits with arbitrary $\epsilon$ and $\delta$ as arbitrary
$\frac{1}{\operatorname{poly}(n)}$ values if and only if $\textsf{RP}=\np$.
Furthermore, an efficient quantum $(\epsilon,\delta)$ proper PAC learner for
Clifford circuits with arbitrary $\epsilon$ and $\delta$ as arbitrary
$\frac{1}{\operatorname{poly}(n)}$ values exists if and only if
$\np\subseteq\textsf{RQP}$.

###### Proof.

Since CNOT circuits are also a form of Clifford circuits,
$\textsc{CNOTDecide}((n+1)n)\subset\textsc{CliffordDecide}((n+1)n)$, and so
$\textsc{CliffordDecide}((n+1)n)$ is also -Complete. The proof of Theorem 7.2
continues but with $\alpha=\frac{1}{2}$ instead due to Lemma 4.3. This leads
to slightly different constants, but the proof ideas all follow without major
change. ∎

##  8 Discussion and open problems

In this work, we prove a negative result in proper learning of one of the best
candidates for efficient PAC learning of quantum circuits. However, it should
be noted that in many cases there exist improper learners even in the case
where proper learning is -Hard, such as 2-clause CNF [15, 16]. This
immediately leaves the problem of whether or not an improper learner exists
for Clifford circuits. One way of showing hardness would be to leverage
cryptographic hardness such as in Kharitonov [29], Arunachalam et al. [8].
Another approach would be to assume the hardness of random k-DNF, such as the
work of Daniely and Shalev-Shwartz [22]. Unfortunately, the work of Caro and
Datta [18] is no longer useful in the improper learning case.

We also note that a single output bit of a CNOT circuit is simply an XOR,
which is easy to learn efficiently if there is no noise. However, because we
are dealing with reversible computation each output bit has to be a linearly
independent XOR such that each input bit is recoverable. Finding a CNOT
circuit that matches a single XOR function $f$ can be done by sampling
expected $\mathcal{O}(n)$ random XOR until we get $n$ linearly independent XOR
with one of them being $f$ (see Section A.1). Thus, the entire difficulty of
proper learning CNOT circuits is this linear independence of the output bits.
As such, even though
$\textsf{AC}^{0}\subseteq\textsf{TC}^{0}\subseteq\textsf{NC}^{1}\subseteq\textsf{L}\subseteq\oplus\textsf{L}$
with the lower classes having improper hardness results based on cryptographic
hardness [29], one cannot directly give an improper learning result for CNOT
circuits despite the fact that simulating CNOT circuits is complete for
$\oplus\textsf{L}$.

As noted previously, our PAC learning framework is slightly different from
that of Caro and Datta [18], in that we use Pauli matrices, rather than rank
$1$ projectors as measurements. To the author’s knowledge, there exists no
proof showing that one framework is necessarily harder than the other. The
author also do not see an obvious way of proving an analogous hardness theorem
in the specific framework of Caro and Datta [18] for Clifford or CNOT
circuits.

Finally, with everything from the input states to the circuits involved being
classical, it is entirely possible to prove the technical results about CNOT
circuits only talking about bit strings and parity functions. Namely, one can
replace the entire problem with samples of the form $(x,s,s^{T}Cx\mod 2)$
where $(x,s)\sim\mathcal{D}$ are $n$-bit strings and $C$ is a CNOT circuit.
Since the stabilizer group of a computational basis state always lies in
$\\{\pm 1\\}\times\\{I,Z\\}^{\otimes n}$, we can uniquely define it by the
subgroup that has positive phase. This is equivalent to the orthogonal
complement of $x$, which is the subspace
$W_{x}=\left\\{x\in\\{0,1\\}^{n}\bigm{|}w\cdot x=0\right\\}$. From there, a
sample of the form $(x,s,0)$ simply says that $Cx\in W_{s}$, and one can get
an analogous proof by copying the lemmas and theorems in Section 5 and Section
7. However, this proof isn’t anymore intuitive than the one given using
stabilizer groups, and in fact is probably less intuitive to the average
reader due to the lack of established formalism from stabilizers and paulis.
It would be interesting if a more intuitive purely classical proof could be
made to show hardness of learning CNOT circuits under this model.

## Acknowledgements

The author would like to thank Aravind Gollakota for being a wealth of
information with regard to statistical learning theory and William Kretschmer
for insightful commentary and feedback. The author would also like to thank
Patrick Rall, Justin Yirka, Sabee Grewal, and Scott Aaronson for useful
discussions.

## References

  * Aaronson [2007] Scott Aaronson.  The learnability of quantum states.  _Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences_ , 463(2088):3089–3114, 2007.  doi: 10.1098/rspa.2007.0113.
  * Aaronson [2018] Scott Aaronson.  Shadow tomography of quantum states.  In _Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing_ , STOC 2018, page 325–338, New York, NY, USA, 2018. Association for Computing Machinery.  ISBN 9781450355599.  doi: 10.1145/3188745.3188802.  URL https://doi.org/10.1145/3188745.3188802.
  * Aaronson and Gottesman [2004] Scott Aaronson and Daniel Gottesman.  Improved simulation of stabilizer circuits.  _Physical Review A_ , 70(5):052328, 2004.  doi: 10.1103/physreva.70.052328.
  * Altepeter et al. [2003] J. B. Altepeter, D. Branning, E. Jeffrey, T. C. Wei, P. G. Kwiat, R. T. Thew, J. L. O’Brien, M. A. Nielsen, and A. G. White.  Ancilla-assisted quantum process tomography.  _Phys. Rev. Lett._ , 90:193601, May 2003.  doi: 10.1103/PhysRevLett.90.193601.  URL https://link.aps.org/doi/10.1103/PhysRevLett.90.193601.
  * Arunachalam and de Wolf [2017] Srinivasan Arunachalam and Ronald de Wolf.  Guest column: A survey of quantum learning theory.  _ACM SIGACT News_ , 48(2):41–67, 2017.  doi: 10.1145/3106700.3106710.
  * Arunachalam and de Wolf [2018] Srinivasan Arunachalam and Ronald de Wolf.  Optimal quantum sample complexity of learning algorithms.  _The Journal of Machine Learning Research_ , 19(1):2879–2878, 2018.
  * Arunachalam et al. [2020] Srinivasan Arunachalam, Alex B Grilo, and Henry Yuen.  Quantum statistical query learning.  _arXiv preprint arXiv:2002.08240_ , 2020.
  * Arunachalam et al. [2021a] Srinivasan Arunachalam, Alex Bredariol Grilo, and Aarthi Sundaram.  Quantum hardness of learning shallow classical circuits.  _SIAM Journal on Computing_ , 50(3):972–1013, 2021a.  doi: 10.1137/20M1344202.  URL https://doi.org/10.1137/20M1344202.
  * Arunachalam et al. [2021b] Srinivasan Arunachalam, Yihui Quek, and John Smolin.  Private learning implies quantum stability, 2021b.
  * Bennett and Brassard [2014] Charles H. Bennett and Gilles Brassard.  Quantum cryptography: Public key distribution and coin tossing.  _Theoretical Computer Science_ , 560:7–11, Dec 2014.  ISSN 0304-3975.  doi: 10.1016/j.tcs.2014.05.025.  URL http://dx.doi.org/10.1016/j.tcs.2014.05.025.
  * Bennett and Wiesner [1992] Charles H. Bennett and Stephen J. Wiesner.  Communication via one- and two-particle operators on einstein-podolsky-rosen states.  _Phys. Rev. Lett._ , 69:2881–2884, Nov 1992.  doi: 10.1103/PhysRevLett.69.2881.  URL https://link.aps.org/doi/10.1103/PhysRevLett.69.2881.
  * Bennett et al. [1993] Charles H. Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, and William K. Wootters.  Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels.  _Phys. Rev. Lett._ , 70:1895–1899, Mar 1993.  doi: 10.1103/PhysRevLett.70.1895.  URL https://link.aps.org/doi/10.1103/PhysRevLett.70.1895.
  * Berg [2020] Ewout van den Berg.  A simple method for sampling random clifford operators, 2020.  URL https://arxiv.org/abs/2008.06011.
  * Bernstein and Vazirani [1997] Ethan Bernstein and Umesh Vazirani.  Quantum complexity theory.  _SIAM Journal on Computing_ , 26(5):1411–1473, 1997.  doi: 10.1137/S0097539796300921.  URL https://doi.org/10.1137/S0097539796300921.
  * Blum [2015] Avrim Blum.  Computational Hardness of Learning.  http://www.cs.cmu.edu/~avrim/ML07/lect1007.pdf, 2015.  URL http://www.cs.cmu.edu/~avrim/ML07/lect1007.pdf.  Lecture notes for CS 10-806 Foundations of Machine Learning and Data Science.
  * Blum and Rivest [1992] Avrim L. Blum and Ronald L. Rivest.  Training a 3-node neural network is np-complete.  _Neural Networks_ , 5(1):117–127, 1992.  ISSN 0893-6080.  doi: https://doi.org/10.1016/S0893-6080(05)80010-3.  URL https://www.sciencedirect.com/science/article/pii/S0893608005800103.
  * Buss et al. [1999] Jonathan F Buss, Gudmund S Frandsen, and Jeffrey O Shallit.  The computational complexity of some problems of linear algebra.  _Journal of Computer and System Sciences_ , 58(3):572–596, 1999.  ISSN 0022-0000.  doi: https://doi.org/10.1006/jcss.1998.1608.  URL https://www.sciencedirect.com/science/article/pii/S0022000098916087.
  * Caro and Datta [2020] Matthias C. Caro and Ishaun Datta.  Pseudo-dimension of quantum circuits.  _Quantum Machine Intelligence_ , 2(2), Nov 2020.  ISSN 2524-4914.  doi: 10.1007/s42484-020-00027-5.  URL http://dx.doi.org/10.1007/s42484-020-00027-5.
  * Cheng et al. [2015] Hao-Chung Cheng, Min-Hsiu Hsieh, and Ping-Cheng Yeh.  The learnability of unknown quantum measurements, 2015.
  * Chuang and Nielsen [1997] Isaac L. Chuang and M. A. Nielsen.  Prescription for experimental determination of the dynamics of a quantum black box.  _Journal of Modern Optics_ , 44(11-12):2455–2467, 1997.  doi: 10.1080/09500349708231894.  URL https://www.tandfonline.com/doi/abs/10.1080/09500349708231894.
  * Chung and Lin [2021] Kai-Min Chung and Han-Hsuan Lin.  Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem.  In Min-Hsiu Hsieh, editor, _16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)_ , volume 197 of _Leibniz International Proceedings in Informatics (LIPIcs)_ , pages 3:1–3:22, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  ISBN 978-3-95977-198-6.  doi: 10.4230/LIPIcs.TQC.2021.3.  URL https://drops.dagstuhl.de/opus/volltexte/2021/13998.
  * Daniely and Shalev-Shwartz [2016] Amit Daniely and Shai Shalev-Shwartz.  Complexity theoretic limitations on learning dnf’s.  In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, _29th Annual Conference on Learning Theory_ , volume 49 of _Proceedings of Machine Learning Research_ , pages 815–830, Columbia University, New York, New York, USA, 23–26 Jun 2016. PMLR.  URL https://proceedings.mlr.press/v49/daniely16.html.
  * Flammia et al. [2012] Steven T Flammia, David Gross, Yi-Kai Liu, and Jens Eisert.  Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators.  _New Journal of Physics_ , 14(9):095022, sep 2012\.  doi: 10.1088/1367-2630/14/9/095022.  URL https://doi.org/10.1088/1367-2630/14/9/095022.
  * Gottesman [1997] Daniel Gottesman.  Stabilizer codes and quantum error correction, 1997.
  * Gottesman [1998] Daniel Gottesman.  The heisenberg representation of quantum computers.  1998\.  doi: 10.48550/ARXIV.QUANT-PH/9807006.  URL https://arxiv.org/abs/quant-ph/9807006.
  * Haah et al. [2017] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu.  Sample-optimal tomography of quantum states.  _IEEE Transactions on Information Theory_ , pages 1–1, 2017.  ISSN 1557-9654.  doi: 10.1109/tit.2017.2719044.
  * Huang et al. [2020] Hsin-Yuan Huang, Richard Kueng, and John Preskill.  Predicting many properties of a quantum system from very few measurements.  _Nature Physics_ , oct 2020.  doi: 10.1038/s41567-020-0932-7.  URL https://doi.org/10.1038/s41567-020-0932-7.
  * Katz [2011] Jonathan Katz.  Notes on Complexity Theory Lecture 3.  https://www.cs.umd.edu/~jkatz/complexity/f11/lecture3.pdf, 2011\.  URL https://www.cs.umd.edu/~jkatz/complexity/f11/lecture3.pdf.  Lecture notes for CS 652 — Complexity Theory.
  * Kharitonov [1993] Michael Kharitonov.  Cryptographic hardness of distribution-specific learning.  In _Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing_ , STOC ’93, page 372–381, New York, NY, USA, 1993. Association for Computing Machinery.  ISBN 0897915917.  doi: 10.1145/167088.167197.  URL https://doi.org/10.1145/167088.167197.
  * Kueng and Gross [2015] Richard Kueng and David Gross.  Qubit stabilizer states are complex projective 3-designs, 2015.  URL https://arxiv.org/abs/1510.02767.
  * Lai and Cheng [2022] Ching-Yi Lai and Hao-Chung Cheng.  Learning quantum circuits of some t gates.  _IEEE Transactions on Information Theory_ , pages 1–1, 2022.  doi: 10.1109/TIT.2022.3151760.
  * Low [2009] Richard A. Low.  Learning and testing algorithms for the clifford group.  _Phys. Rev. A_ , 80:052314, Nov 2009.  doi: 10.1103/PhysRevA.80.052314.  URL https://link.aps.org/doi/10.1103/PhysRevA.80.052314.
  * Montanaro [2017] Ashley Montanaro.  Learning stabilizer states by Bell sampling, 2017.
  * O’Donnell and Wright [2016] Ryan O’Donnell and John Wright.  Efficient quantum tomography.  In _Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing_ , STOC ’16, page 899–912, New York, NY, USA, 2016. Association for Computing Machinery.  ISBN 9781450341325.  doi: 10.1145/2897518.2897544.  URL https://doi.org/10.1145/2897518.2897544.
  * O’Donnell and Wright [2017] Ryan O’Donnell and John Wright.  Efficient quantum tomography ii.  In _Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing_ , STOC 2017, page 962–974, New York, NY, USA, 2017. Association for Computing Machinery.  ISBN 9781450345286.  doi: 10.1145/3055399.3055454.  URL https://doi.org/10.1145/3055399.3055454.
  * Rocchetto [2018] Andrea Rocchetto.  Stabiliser states are efficiently PAC-learnable.  _Quantum Information & Computation_, 18(7-8):541–552, 2018.  doi: 10.26421/qic18.7-8-1.
  * Shor [1999] Peter W. Shor.  Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.  _SIAM Review_ , 41(2):303–332, 1999.  doi: 10.1137/S0036144598347011.  URL https://doi.org/10.1137/S0036144598347011.
  * Simon [1997] Daniel R. Simon.  On the power of quantum computation.  _SIAM Journal on Computing_ , 26(5):1474–1483, 1997.  doi: 10.1137/S0097539796298637.  URL https://doi.org/10.1137/S0097539796298637.
  * Yoganathan [2019] Mithuna Yoganathan.  A condition under which classical simulability implies efficient state learnability, 2019.
  * Zhu [2017] Huangjun Zhu.  Multiqubit clifford groups are unitary 3-designs.  _Phys. Rev. A_ , 96:062336, Dec 2017.  doi: 10.1103/PhysRevA.96.062336.  URL https://link.aps.org/doi/10.1103/PhysRevA.96.062336.

##  Appendix A Special Cases with Efficient Proper Learners

Despite the results given, there still exist situations where it is possible
to efficiently proper learn Clifford circuits and CNOT circuits. We give brief
proof sketches of some of them here.

###  A.1 CNOT Circuits for a distribution with support over a single
measurement

Let us try to learn CNOT circuits with regard to a distribution $\mathcal{D}$
such that there exists some pauli $P\in\\{I,Z\\}^{\otimes n}$ with
$\operatorname*{\mathbb{P}}_{(\rho,E)\sim\mathcal{D}}[E=\frac{I^{\otimes
n}+P}{2}]=1$. Because we are dealing with CNOT circuit the labels will always
be $0$ and $1$ so by Lemma 4.3 each label will tell us an affine subspace that
$C^{\dagger}PC$ lies in. We can efficiently compute the intersection of this
using Gaussian elimination with the generators to find a $P^{\prime}$ that is
consistent will all of the labels. From there, let $P,Q_{2},Q_{3},\dots,Q_{n}$
be a set of Paulis whose span is $\\{I,Z\\}^{\otimes n}$. Let
$P^{\prime},Q_{2}^{\prime},Q_{3}^{\prime},\dots,Q_{n}^{\prime}$ also be a set
of Paulis whose span is $\\{I,Z\\}^{\otimes n}$. It is clear that if we define
our CNOT circuit such that $C^{\dagger}PC=P^{\prime}$ and
$C^{\dagger}Q_{i}C=Q_{i}^{\prime}$ then we have a valid CNOT circuit.
Efficiently finding such $\\{Q_{i}\\}$ and $\\{Q_{i}^{\prime}\\}$ only takes
$\mathcal{O}(n)$ expected samples of random Paulis in $\\{I,Z\\}^{\otimes n}$
and so can be done efficiently. From there we appeal to Theorem 3.1 and we are
done.

###  A.2 Clifford circuits with the uniform distribution over Pauli
measurements

We note that if the distribution $\mathcal{D}$ entails the measurements being
uniform over the Paulis then the problem is trivially easy to properly learn
with $\epsilon<\frac{1}{\text{exp}(n)}$ and $\delta=0$ by just outputting a
random Clifford circuit. This is because the probability that a random Pauli
is in a given state’s stabilizer group is $\frac{2^{n}}{4^{n}}$ so we will
almost always see the label $\frac{1}{2}$ regardless of the hypothesis circuit
we choose. Thus, we will be specifically looking at the distribution-free
setting where an adversary can choose arbitrary hard distributions.

###  A.3 Clifford Circuits for a distribution with support over a single state

In the converse of an earlier situation, let us try to learn Clifford circuits
with regard to a distribution $\mathcal{D}$ such that there exists some
stabilizer state $\sigma$ with
$\operatorname*{\mathbb{P}}_{(\rho,E)\sim\mathcal{D}}[\rho=\sigma]=1$. This
situation effectively reduces to that of Rocchetto [2018]. If we run that
algorithm we will find a state $\sigma^{\prime}$ that is consistent with all
of the labels. Let $\\{g_{i}\\}$ be the generators of $\sigma$ and
$\\{g_{i}^{\prime}\\}$ the generators of $\sigma^{\prime}$. If we let
$Cg_{i}C^{\dagger}=g_{i}^{\prime}$ we define the first part of a Clifford
circuit that maps $\sigma$ to $\sigma^{\prime}$ as desired. We can then run
the algorithm from Berg [2020] to fill in the remainder of the Clifford
circuit. Appealing to Theorem 3.1 once again completes the proof.