A High Performance Compiler for Very Large Scale Surface Code Computations

George Watkins
Aalto University, Espoo, Finland
Simon Fraser University, Vancouver, Canada

Hoang Minh Nguyen
Simon Fraser University, Vancouver, Canada

Varun Seshadri
Technische Universität München, Munich, Germany

Keelan Watkins
Simon Fraser University, Vancouver, Canada

Steven Pearce
Simon Fraser University, Vancouver, Canada

Hoi-Kwan Lau
Simon Fraser University, Vancouver, Canada

Alexandru Paler
Aalto University, Espoo, Finland

We present the first high performance compiler for very large scale quantum error correction: it translates an arbitrary quantum circuit to surface code operations based on lattice surgery. Our compiler offers an end to end error correction workflow implemented by a pluggable architecture centered around an intermediate representation of lattice surgery instructions. Moreover, the compiler supports customizable circuit layouts, can be used for quantum benchmarking and includes a quantum resource estimator. The compiler can process millions of gates using a streaming pipeline at a speed geared towards real-time operation of a physical device. We compiled within seconds 80 million logical surface code instructions, corresponding to a high precision Clifford+T implementation of the 128-qubit Quantum Fourier Transform (QFT). Our code is open-sourced at <https://github.com/latticesurgery-com>.

§ INTRODUCTION

Applying surface quantum error correcting codes (QECCs) efficiently to large computations is challenging in terms of classical computing resources necessary for the compilation process. Compilers tailored for QECC are only starting to appear, often with significant limitations with respect to the scale of the circuits that can be handled or the compilation time.

Large scale QECC compilation is a necessity, because practical algorithms, like Shor's and Grover's assume high-quality qubits with a very low error rate [50], but we are unlikely to obtain hardware (physical) qubits with such fidelity in the near future [44]. QECCs solve this issue by using a large number of error prone physical qubits to encode higher fidelity logical qubits. For example, a will quantum factoring algorithm needs roughly $1000$ qubits to factor a $1000$-bit number and millions of gates [42, 15]. Consequently, practical algorithm require very large scale quantum computers, while only some carefully crafted examples of problems where quantum hardware has an advantage with small devices exist [4].

Surface codes are a family of QECCs that require low qubit connectivity and a reasonably high hardware error rate (such as between $0.1\%$ and $1\%$) to create good logical (computational) qubits [14, 55, 52] and only require degree four nearest neighbour connectivity. These properties make them a promising option for error correcting devices with a couple hundred logical qubits. Physical devices with compatible layouts have already been made or proposed, albeit on a small scale [4, 30, 3, 2, 6]. Examples of larger scale quantum circuits protected by surface QECCs were compiled manually in [17, 16]. The complexity of optimising surface code circuits has been shown to be related to NP-hardness [19, 56].

Example output of our compiler: discrete time steps of a surface code computation. Time axis runs towards the back of the image. The discrete time steps are depicted as a sequence of slices, evolving over time. Each patch (colored square) holds an error-corrected logical qubit. Quantum operations are implemented by merging and splitting patches.

We present and demonstrate the extremely high scalability of our efficient QECC compiler. This is a step forward for quantum software: we create a streaming pipeline and a compilation environment for the compilation and optimisation of very large scale QECCs. Our high performance pipeline makes it possible to process extremely large circuits (would not fit in memory). We can compile directly, in a streaming process, by reading and writing to mass storage. Streaming enables the real-time operation of our compiler, meaning that this tool may be integrated in the classical control software necessary to operate quantum computers [38].

This paper is organised as follows: In Sec. <ref> we introduce the concepts necessary for presenting the compilation methods and workflow. Sec. <ref> describes the two-stage compilation pipeline that consists of gate level processing (Sec. <ref>) and logical operation routing (Sec. <ref>). The latter includes also a fast method to perform state vector simulation that takes into account the entangling and disentangling action of the lattice surgery operations. Finally, Sec. <ref> illustrates the performance of our compiler. We compile within seconds a high-precision 128-qubit Quantum Fourier Transform (QFT) [36]. To the best of our knowledge, this is the largest-scale compilation of this kind.

§ BACKGROUND

This section introduces the necessary background details for describing the compilation process.
The application of error correction to quantum circuits resembles the process well known to classical computer scientists of program compilation: the compiler reads code in a programming language (higher level quantum gates) and outputs machine instructions (lattice surgery quantum gates).

We opted for flexibility and developed a compiler with a well-defined intermediate representation to separate circuit pre-processing from surface code instruction layout. Surface code instructions for large scale computations at present is interesting for at least two purposes, one is being able to produce reliable resource estimates, and the other is to start preparing for when we will have such devices, so that hardware engineers can start designing devices with instruction sets for error correction in mind.

We assume the reader is familiar with the basic concepts of quantum computing and quantum information [36, 35]. We assume the conventional meaning for common quantum gates (Phase gates S and T, Hadamard gate H, CNOT, Toffoli – to a large extent, the standard gates as listed in Table <ref> in Appendix) and the Pauli matrices (I, X, Y, Z). By the phase rotation gate $R_Z(\theta)$ we mean:

\begin{equation*}
R_Z(\theta) =
\begin{bmatrix}
1 & 0 \\
0 & e^{i\frac{\theta}{2}}
\end{bmatrix}
\end{equation*}

We will frequently use Pauli product rotations, for which we assume the following: given an axis P (which may be a Pauli matrix or a tensor product of Pauli matrices) we denote by $P(\theta) = \text{exp}( - i\theta P) = \cos(\theta)I - i \sin(\theta)P$. Note that under this convention, $R_P(\theta) = P(\frac{\theta}{2})$ for $P=X,Z$. Also, when the Pauli matrices appear with sub-indices, e.g. $Z_1Z_2Z_3Z_4$ in Fig. <ref>, we mean the tensor product $X \otimes Z$ of the Pauli matrices applied to qubits indexed $1$ and $2$. Similarly, we use gate $R_X(\theta)=HR_Z(\theta)H$.

§.§ Surface Codes

A graphical depiction of surface code layout. The white circles are data qubits protected from errors by measuring stabilizers around them. The squares in the lighter and darker shades of yellow represent stabilizer measurements. For example, the squares marked with $Z$ and $X$ represent the $Z_1 Z_2 Z_3 Z_4$ and $X_5 X_6 X_7 X_8$ stabilizer measurements respectively. If an error occurs in a data qubit, such as a phase flip occurring on 9, the $X$ stabilizers around it will pick it up by changing outcome (syndromes, highlighted in purple). There are advanced methods to decode sets of errors (e.g [14, 53, 22]). Errors can either be corrected on the spot or tracked classically by inverting later readouts. This cycle of detecting, decoding and correcting is referred to as the surface code cycle.

A major challenge with the current generation of quantum computers is the occurrence of errors while performing computations. Errors may occur because of control system faults or stray interaction with the environment. A proposed solution for avoiding errors are Quantum Error Correcting Codes (QECC). These codes add some degree of fault tolerance to computations by using many physical qubits to form fewer but more reliable abstract logical qubits[51]. Surface codes are a family of QECCs that aim at improving computational fidelity by entangling physical qubits in a physical lattice [47, 36]. This kind of codes, with topological properties, was first theorized with exotic particles known as “anyons” [29]. Surface codes are appealing because they are well understood, and feature a high error threshold. In near future, quantum computing hardware with thousands of qubits might be realized [45, 46, 6] which would be able to
operate a surface code cycle on a lattice of qubits.

The key step of surface code error detection is stabilizer measurement, as shown by the shaded squares in Fig. <ref>. These measurements act as parity checks on bit flips or phase flips of a square lattice of data qubits. The surface code and its cycle (the sequence of quantum gates applied for enforcing the code constraints) only tell us how to protect a lattice from error. The surface code distance indicates how much error is tolerated [9].

Abstracting physical qubits to patches. We omit the details of stabilizers and data qubits that make up patches, and instead represent distance-independent features. It is always possible to compute back these details about stabilizers from the output format and code distance. The picture to the left shows how this abstract representation relates to the physical implementation, and to the right there is a fully abstract patch, which has its own logical state. The different stabilizers on the boundaries yield two different kinds of boundaries, which are often referred to as rough and smooth.

§.§ Logical Qubits and Logical Operations

Logical (computational) qubits are encoded by “cutting out” portions of a device's physical lattice into patches, which are cluster states error corrected by the surface code cycle. This encoding of logical qubits is known as the planar code [9, 11]. Patches have boundaries outside of which they don't interact, except when performing certain logical operations (Sec. <ref>). Fig. <ref> outlines how patches relate to the surface code. The patch-based approach has been shown to be a resource-efficient choice for quantum error correction [21, 43, 32].

Lattice surgery of patches. Patches are merged by activating the stabilizer measurements with the data qubits between them (blue regions). This operation causes the two patches to become one, hence losing a degree of freedom and projecting the logical state into a subspace. After stopping the stabilizer measurements and measuring the mediating data qubits, the patches are split. Overall, this operation is equivalent to a logical multi body measurement [21]. The observable depends on the boundaries: rough for $X$ and smooth for $Z$. This figure shows measurements of the observables $Z\otimes Z$ (top) and $Z\otimes X$  (bottom)

We will be looking at square patches with two kinds of boundaries that encode a single qubit. Patch size is proportional to code distance and the performance of the decoding algorithm (e.g. [14, 22]). For our intents, it suffices to know that the size of the patches will depend on the physical error rate of the device, length of the computation and desired success rate of the logical computation. In Sec. <ref> we estimate the resources [20] necessary to execute the compiled output.

Having obtained logical qubits, we require a method to perform operations between them. Table <ref> offers an overview of all the surface code operations supported by our compiler at the logical level. Some logical operations are performed directly on patches: Pauli X and Z [8], and Hadamard gates [21], can be implemented in this way and are called transversal operations. It is also possible to directly initialize a patch in the $\ket{0}$ or $\ket{+}$ states and to measure in the X or Z basis [32]. For the remaining operations needed to complete a universal gate set we use lattice surgery [21]. This protocol achieves entangling multibody measurements by merging and splitting patches.

We use these measurements along with prepared ancilla states to implement CNOT as shown in [21], and the S and the T gates (Fig. <ref> in Appendix). T gates utilize a magic state, $\ket{m} = \frac{1}{\sqrt{2}}(\ket{0}+e^{\frac{i \pi}{4}}\ket{1})$, which in the surface code cannot be initialized directly with a high fidelity. These states have to be prepared by distillation. There are several protocols for magic state distillation [7, 33], but for our compilation purposes it suffices to acknowledge the fact that these distillations occupy some amount of space on the device's lattice and that they have a certain duration in time: distillation regions are described by their bounding box which includes a time axis for how long it will take to produce the next magic state.

Operation     Method

Patch initialization in the $\ket{0}$ and $\ket{+}$ states     Direct Initialization of data qubits [21]

Single patch measurements
Direct measurement of data qubits [21]

Pauli X and Z     Transversal in surface codes [14]

Hadamard gates
Transversal in planar code patches [21]

Entangling multi body measurements
Lattice surgery merges and splits, mediated by ancilla for routing[32]

Boundary Rotation
Patch deformation[32]

S gates
Lattice surgery with twist defects [34]

Preparation of Magic states $\ket{m} = \ket{0}+e^{\frac{i \pi}{4}}\ket{1}$
Distillation in dedicated regions [33]

The list of logical surface code operations supported by the compiler. The operations are formalized into logical lattice instructions (LLI), which serve as a central intermediate representation to our compiler. LLI decouples the pre-processing to surface code instructions from laying them out on an abstract lattice.

§ METHODS

We address the problem of taking a circuit specified in a machine readable format, and converting the circuit to the surface code operations outlined in Table <ref>. For small circuits it is easy enough to perform such conversion by hand, but automation is necessary for large scale circuits.

Our compiler is a computer program that reads text in a source formal language and outputs machine code in another language, called the target. In our case the source is a quantum circuit in a subset of OpenQASM 2.0 [10], while the target is a JSON logical operation instructions (Sec. <ref> and Fig. <ref>).

There have been other compilers that take circuits and compile them to instruction sets for error corrections. For example, OpenSurgery [40] leverages lattice surgery as well. Our compiler's source and target are similar to OpenSurgery, but improves on the compiler time performance, offers new optimizations, adds the ability to customize layout, and handles parallel magic state distillation. The error correcting compiler Surfbraid [37] achieves a similar goal for braided surface codes. There also are compilers that focus specifically on routing long range surface code interactions [23, 5]. While we do tackle such problem, as it is necessary for our overall compilation goal, the focus of this project is broader in  scope and we may integrate existing tools at a later stage.

Our compiler offers the flexibility to design custom very large scale layouts with a layout specification and automatically map large-scale circuits to them. A small scale procedure for mapping algorithms onto surface code architectures, exploring the trade offs of different layouts has been presented in [31]. Manually obtained surface code layouts with techniques such as the AutoCCZ for optimizing ripple carry adders where presented for example by [16]. Finally, one last approach to quantum compilers worth mentioning are variational compilers [57], which share with our project the challenges of circuit pre-processing.

§.§ The Compilation Pipeline

The compiler operates a two-stage pipeline (Fig. <ref>): 1) a pre-processing stage, and 2) a layout and routing stage. The two stages communicate through an intermediate representation we refer to as logical lattice instructions (LLI from Table <ref>). The LLI contains all the information about the logical operations happening on the lattice, but none about the physical locations of the patches, or about routing and distillation regions. The physical qubit lattice will be operated according to LLI instructions (Table <ref>).

The pipeline as implemented in the compiler.

The first stage, the gate level processing stage, operates mostly at the logical circuit level. We resort to a universal gate set based on surface code operations. We gradually process the input circuit's gates to align with our surface code instructions. Once the circuit is in a suitable format (only Clifford+T gates or certain Pauli rotations), the circuit maps 1-to-1 with surface code operations and is written down as LLI.

The second stage is the slicer. Herein, the LLI are combined with a layout specification in space and time (Fig. <ref>). The LLI language is circuit layout agnostic, meaning that the mapping of the logical qubits to the physical lattice may have a great impact on the efficiency of the compiled circuit. The result of these steps is a “sequence" of slices of the physical lattice. The slices depict the state of the computation at each point in time, as shown in (Fig. <ref>). We offer two such slicers: one written in Python, geared towards the verification of small scale circuits (Sec. <ref>) and a high performance one written in C++ for large scale circuits (Sec. <ref>).

§.§ Gate Level Processing

The first stage takes a logical circuit specified as a subset of OpenQASM 2.0 [10]. We offer two ways to pre-process the circuit: 1) with Pauli rotations and Pauli product measurements, and 2) directly with higher level quantum gates such as Toffoli gates. In both cases, we first parse the circuit into a list of gates, using either Qiskit [13], PyZX [28], a custom parser or a combination of the three depending on the circuit.

The gate list expression of the input circuit might use gates which are not supported by the error-correction procedure. In this step we reduce the gate set so that it easily translates to LLI. Our custom parser is able to break down very small angle rotations, such as $Z(\frac{\pi}{2^{128}})$ by symbolic processing of the argument. These rotations are needed to compile, for example, a 128-qubit quantum Fourier transformation (QFT) circuit. After parsing, the list of gates is passed through the pipeline to the next stage.

First, controlled gates are broken down to CNOTs and single qubit rotations using the identity in Fig. <ref>. The circuit now only has single qubit Clifford gates, CNOTs and single qubit rotations. At the last stage of pre-processing in the gate model single qubit rotations smaller than $\frac{\pi}{4}$ are approximated to single qubit Clifford+T gates.

It is possible to convert controlled-rotation gates to Clifford operations plus some small angle $Z(\theta)$ rotations (Figure <ref> in Appendix). The latter are not Clifford+T and are difficult to perform in a fault-tolerant way [25]. We achieve arbitrary $Z(\theta)$ rotations by approximating them with Clifford+T gates, for which we leverage the Gridsynth package [48] which outputs approximations constituted of sequences of H, X, Z, S and T gates. The T gates are performed by consuming magic states, which are prepared in dedicated distillation regions[8, 33].

We utilize two methods to convert the Gridsynth appproximation to LLI. The first is to directly apply the gates with the methods of Table <ref>: H, X and Z transversally, S with a twist and T as $Z(\frac{\pi}{8})$ rotation as shown in Fig. <ref>. The second approach, we refer to as Pauli rotation compression, is shown in Fig. <ref>, and consists of interpreting the gate sequences returned by the Gridsynth approximations as a sequence of Pauli rotations of varying angles.

The direct application of gates is simpler and results in the same Clifford corrective terms for every rotation. With Pauli rotation compression the Clifford corrective terms change for every angle, thus more complex classical control would be required by a downstream stage. In the Appendix we present an algorithm for Clifford gate optimization.

Pauli rotation compression of Cliffod+T approximations of small angle rotations E.g. $R_Z(\frac{\pi}{2^{128}})$: gate sequences obtained from Gridsynth are interpreted in the Pauli Frame by breaking it into subsequences. For instance, the sequence $HSHTSHX$ would be split as $HSH$, $TS$, $H$, $X$ and would become the sequence $X_{\frac{\pi}{4}} Z_{\frac{3\pi}{8}} HX$

§.§ Slices and Routing

To overcome the logistical challenges of structuring a computation on surface code device, we arrange the computation in space and time. Space structure is given by partitioning the physical lattice into square cells. A cell may hold or may not hold a patch, be part of a distillation region, or may be used for routing, but patches, distillation regions and routing areas are always placed in accordance to cell boundaries ( Figs. <ref>, <ref> and <ref>).

Time structure is given by thinking of the computation in terms of slices. Surface code computations can be viewed as 3D structures in space-time [39, 40, 16], and a slice is a plane through the structure at a fixed time value (Fig. <ref>). In a nutshell, a slice is a temporally discretized partition of the computation (clock timesteps in Litinski [32] or moments in Google Cirq [12] terminology, for example). Each slice represents a snapshot of the the LLIs that are happening simultaneously on the lattice – slice duration is given by the duration of the slowest LLI.

Routing is the problem of deciding how the cells of a slice are allocated to patches or reserved for other purposes. Finding optimal layouts has a great impact on the depth of the computation. Different layouts can for example be used to trade off space for time [31]. Layouts may need to change depending on the task during an algorithm. For example, the oracle in Grover's search algorithm  may be very different from the implementation of the diffusion operator [24]. We defined our own configurable layout specification (Fig. <ref>). The compiler reads a text file containing the layout specification and produces slices with patches arranged accordingly.

ASCII specification for patch layouts. Q indicates a patch holding a logical qubit, r marks cells that are reserved for routing (the cyan “snakes" of Fig. <ref>). Numbers 0 to 9 are used to identify distillation regions. The boundaries of the distillation regions are computed by connected components search for same numbers, so it is possible to have more than 10 distillation regions. Magic states produced by these regions are queued in the r cells neighbouring a distillation block. Finally, A marks cells reserved to allocate new ancilla patches in the states, such as the $\ket{+}$ states that mediate CNOTs or the places for the $Y$ eigenstates used by $\frac{n}{4}$ Pauli rotations.

§.§.§ On-the-fly, Functionally Verified Slicer

Our first slicer supports the real-time, on-the-fly functional verification for correctness. This slicer can be used as a preliminary verification of smaller scale lattice surgery circuits. The slicer and the simulation operate on an array of patches of variable length and assumes that all magic states have been prepared ahead of time. The verified slicer is very powerful when it comes to understanding the details of small computation and we used it in the development of the compiler.

The simulator, called the Lazily Tensored State-vector Simulation (LTSvS), has the major feature of being able to simulate patch states at the LLI instruction level, such as simulating multi body measurements and Pauli operator gates. LTSvS tensors at the matrix level only when strictly required, otherwise just tracks the fact that the global state is given by a tensor product of sub vectors. LTSvS offers a great performance advantage over näive state vector simulation: our simulator doesn't expand the full state vector of all logical qubits on the lattice. In particular, qubits that are known to not be entangled, because they were just initialized or measured, are automatically tracked in separate sub-state vectors. Qubits may be entangled within a sub-state vector. An example of unentangled qubits is the array of magic states waiting to be used or ancilla patches.

Methodologically, the LTSvS simulator is very similar to the matrix-product-states (MPS) simulation techniques [54], which are efficient on circuits with low counts of entangling gates. Compared to the MPS simulators, e.g. from Qiskit [13], ours is fine tuned for computations with many ancillae and measurements, can handle classical control and can be executed in parallel with the compilation process.

§.§.§ High Performance Slicer

The main goal of our compiler is to handle very large scale circuits with thousands of logical qubits and millions of LLIs. At this scale every CPU clock cycle and every byte are precious. Our high performance compiler is written in C++ because it comes with zero cost abstraction [49].

The first step of the slicer is to read a layout file (Fig. <ref>) in order to create an abstract layout representation that describes the device layout. The layout is used to initialize a slice template which will be reused for the routing. The template will be recomputed once the layout dictates this. Our implementation of slice processing keeps memory usage to a minimum because $O(1)$ slices are ever kept in memory by the slicer itself. Moreover, this representation is stored in a high performance data structure based on bitstreams and hash-maps. The representation will be used for computing routes using a variant of Dijkstra's algorithm.

The slicer streams LLI from text or standard input, updating the slice with each instruction, evolving the slices over time. Since the slicer can also stream read from standard input and write to standard output, its possible to implement external programs (e.g. Python scripts or other command line tools) that visit slices by reading from standard input. Given the capability of evolving the lattice state, the slice processing functionality is implemented by defining a C++ functor to visit all slices.

The streamed evolution of slices includes managing distillation, queuing magic states [39, 41], initializing ancillas and LLI operations. A user may collect statistics on slices, such as magic state queue and routing space usage in seconds, without having to store in terabytes of memory that slow down the processing. At the same time this functor approach has the advantage of hiding the implementation details from the client so that they can focus on the processing functionality.

To place routing regions, we used our own implementation of Dijkstra's algorithm, which is implemented in place, such that our tool can search the lattice without constructing a graph of it. Our implementation has close to zero cost overheads with respect to memory and CPU instructions needed to translate back and forth between the lattice layout and the graph needed for performing Dijkstra's algorithm. To further speed up routing, we employ a cached routing technique where previously computed routes are saved and reused later.

§ RESULTS

We implemented our compiler and the source code is open sourced at <https://github.com/latticesurgery-com>. The compiler is continuously tested and verified for functional correctness with modern continuous integration, while practical performance plays a significant role. Our compiler offers a wide range of configuration options, ranging from optimization heuristics, intermediate representations of the computations, as well as flexible layouts. We present results for compiling very large quantum circuits, and focus on scalability and resource estimation.

Time taken to compile a QFT with the C++ slicer on a laptop (Intel i5350U, 8GB RAM) and number of LLI instructions for different QFT sizes. The Clifford+T implementation of the QFT requires thousands of gates for each controlled rotation, to retain the rotation accuracy we set ($10^{-41}$).

§.§ 128-Qubit QFT

To validate the performance of our compiler and high performance slicer we took a circuit that has wide spread use and presents technical fault-tolerant execution challenges. The Quantum Fourier Transform (QFT) is a crucial component providing quantum speedup to algorithms such as Shor's algorithm and quantum phase estimation [36]. The fault-tolerant implementation of the QFT is challenging because of the presence of small angle controlled rotations. For the QFT to retain the desired level of precision, these have to be approximated by a long sequence of Clifford+T, which results in a very long computation. We set Gridsynth's precision to $10^{-41}$ for the Clifford+T approximations for small angle rotations, which results in thousands of gates. Such number was chosen as it is 3 orders of magnitude less than the smallest angle rotation in our circuit $\frac{\pi}{2^{128}} \approx 10^{-38}$, after expanding out the controlled rotations (Sec. <ref>).

The number of controlled rotations increases quadratically with the number of qubits the QFT is applied to. Thus, at 128 qubits and after small angle rotation approximation, the QFT circuit has more than 80 Million LLI without gate to Pauli compression. The number of LLI includes Clifford corrective terms that are meant to be applied depending on measurement outcomes. Thanks to concurrent magic state distillation, there are no idle slices waiting for magic states to be produced. We used the high performance slicer to compile the 128-qubit QFT: for example, laying out the slices for the roughly 80 million LLI of the 128-qubit QFT takes less than 15 minutes on an ordinary laptop. The generation of LLI of a QFT on 128 qubits takes negligible time (under 10s on a laptop). Fig. <ref> illustrates the performance of the C++ slicer for the QFT128 circuit.

A snapshot of the resource requirement landscape for random H, T and CNOT circuits. The horizontal axes show circuit width (number of qubits) and depth (number of gates). The vertical axis shows the code distance required to execute the desired circuit with a success rate of 99%. The colour scale represents the space-time volume of the computation, which relates closely with code distance.

§.§ Resource Estimation

A challenging problem in the community of fault-tolerant QC is determining the amount of physical resource that is necessary to carry out a logical computation with a certain degree of precision. Such resource is often quantified by  physical qubits over time – often called a space time volume. The depth of the circuit and the required magic state fidelity affect the code distance, which in turn affect the number of physical qubits required. Moreover, the degree of parallelization achieved at the routing stage will affect computation depth.

Our compiler includes a prototypical resource estimator for surface code computations. We use the Qentiana [18] software to estimate such values, and computed some code distances for randomized circuits of H, T and CNOT gates (Fig. <ref>).

§ CONCLUSION

We introduced and described a compiler for lattice surgery quantum circuits and showcased some of the results achieved with it. We motivated the design choices behind our two stage pipeline. The first stage included how input circuits are parsed, pre-processed, reduced to Clifford+T and viewed as Pauli rotations. The second stage focuses on laying out circuits on physical devices, which presents substantial performance challenges.

We demonstrated the compiler's performance by compiling a 128-qubit QFT. We believe this is a notable achievement: despite its widespread appearance in algorithms, to the best of our knowledge, no surface code compiler is able to handle such large scale circuits. We also showcased the compiler's ability to estimate resource requirements, in particular patch code distance, which is promising in the perspective of quantum benchmarking.

Our project is laying the foundation for a full-stack quantum circuit compilation framework. Future work will leverage hybrid classical and quantum instruction sets such as LLVM/QIR to program high performance classical control while integrating the Quantum Processing Unit (QPU) instructions.

§ ACKNOWLEDGEMENTS

George Watkins and Alexandru Paler were with funding from the Defense Advanced Research Projects Agency [under the Quantum Benchmarking (QB) program under award no. HR00112230007 and HR001121S0026 contracts]. The views, opinions and/or findings expressed are those of the authors and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government. Varun Seshadri, Hoang Minh Nguyen, Keelan Watkins and George Watkins have been supported by the Unitary.fund. Hoi-Kwan Lau acknowledges support from the Canada Research Chair.

[1]
S. Aaronson and D. Gottesman, “Improved simulation of stabilizer circuits,”
Physical Review A, vol. 70, no. 5, p. 052328, 2004.

[2]
R. Acharya, I. Aleiner, R. Allen, T. I. Andersen, M. Ansmann, F. Arute,
K. Arya, A. Asfaw, J. Atalaya, R. Babbush et al., “Suppressing
quantum errors by scaling a surface code logical qubit,” arXiv
preprint arXiv:2207.06431, 2022.

[3]
C. K. Andersen, A. Remm, S. Lazar, S. Krinner, N. Lacroix, G. J. Norris,
M. Gabureac, C. Eichler, and A. Wallraff, “Repeated quantum error detection
in a surface code,” Nature Physics, vol. 16, no. 8, pp. 875–880,
Jun. 2020. [Online]. Available:

[4]
F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas,
S. Boixo, F. G. Brandao, D. A. Buell et al., “Quantum supremacy using
a programmable superconducting processor,” Nature, vol. 574, no.
7779, pp. 505–510, 2019.

[5]
M. Beverland, V. Kliuchnikov, and E. Schoute, “Surface code compilation via
edge-disjoint paths,” arXiv preprint arXiv:2110.11493, 2021.

[6]
J. E. Bourassa, R. N. Alexander, M. Vasmer, A. Patil, I. Tzitrin, T. Matsuura,
D. Su, B. Q. Baragiola, S. Guha, G. Dauphinais et al., “Blueprint for
a scalable photonic fault-tolerant quantum computer,” Quantum,
vol. 5, p. 392, 2021.

[7]
S. Bravyi and J. Haah, “Magic-state distillation with low overhead,”
Physical Review A, vol. 86, no. 5, p. 052329, 2012.

[8]
S. Bravyi and A. Kitaev, “Universal quantum computation with ideal clifford
gates and noisy ancillas,” Physical Review A, vol. 71, no. 2, p.
022316, 2005.

[9]
S. B. Bravyi and A. Y. Kitaev, “Quantum codes on a lattice with boundary,”
arXiv preprint quant-ph/9811052, 1998.

[10]
A. W. Cross, L. S. Bishop, J. A. Smolin, and J. M. Gambetta, “Open quantum
assembly language,” arXiv preprint arXiv:1707.03429, 2017.

[11]
E. Dennis, A. Kitaev, A. Landahl et al., “Topological quantum memory
[ol],” arXiv preprint quant-ph/0110143, vol. 24, 2001.

[12]
C. Developers, “Cirq,” Aug. 2021, See full list of authors on Github:
https://github .com/quantumlib/Cirq/graphs/contributors. [Online].
Available: <https://doi.org/10.5281/zenodo.5182845>

[13]
H. A. et al., “Qiskit: An open-source framework for quantum computing,” 2021.

[14]
A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, “Surface
codes: Towards practical large-scale quantum computation,” Physical
Review A, vol. 86, no. 3, p. 032324, 2012.

[15]
C. Gidney and M. Ekerå, “How to factor 2048 bit rsa integers in 8 hours
using 20 million noisy qubits,” Quantum, vol. 5, p. 433, 2021.

[16]
C. Gidney and A. G. Fowler, “Flexible layout of surface code computations
using autoccz states,” arXiv preprint arXiv:1905.08916, 2019.

[17]
M. Hanks, M. P. Estarellas, W. J. Munro, and K. Nemoto, “Effective compression
of quantum braided circuits aided by zx-calculus,” Physical Review X,
vol. 10, no. 4, p. 041030, 2020.

[18]
D. Herr, F. Nori, and S. J. Devitt, “Lattice surgery translation for quantum
computation,” New Journal of Physics, vol. 19, no. 1, p. 013034,

[19]
——, “Optimization of lattice surgery is np-hard,” npj Quantum
Information, vol. 3, no. 1, p. 35, 2017.

[20]
D. Herr, A. Paler, S. J. Devitt, and F. Nori, “Time versus hardware: Reducing
qubit counts with a (surface code) data bus,” arXiv preprint
arXiv:1902.08117, 2019.

[21]
C. Horsman, A. G. Fowler, S. Devitt, and R. Van Meter, “Surface code quantum
computing by lattice surgery,” New Journal of Physics, vol. 14,
no. 12, p. 123011, 2012.

[22]
M. S. Hu and D. Elkouss, “Quasilinear time decoding algorithm for topological
codes with high error threshold,” 2020.

[23]
F. Hua, Y. Chen, Y. Jin, C. Zhang, A. Hayes, Y. Zhang, and E. Z. Zhang,
“Autobraid: A framework for enabling efficient surface code communication in
quantum computing,” in MICRO-54: 54th Annual IEEE/ACM International
Symposium on Microarchitecture, 2021, pp. 925–936.

[24]
S. Jaques, M. Naehrig, M. Roetteler, and F. Virdia, “Implementing grover
oracles for quantum key search on aes and lowmc,” in Annual
International Conference on the Theory and Applications of Cryptographic
Techniques.1em plus 0.5em minus 0.4emSpringer, 2020, pp.

[25]
T. Jochym-O’Connor, A. Kubica, and T. J. Yoder, “Disjointness of stabilizer
codes and limitations on fault-tolerant logical gates,” Physical
Review X, vol. 8, no. 2, p. 021047, 2018.

[26]
JQ-Authors, “Command-line json processor,” 2022. [Online]. Available:

[27]
T. Kim and B.-S. Choi, “Efficient decomposition methods for controlled-r n
using a single ancillary qubit,” Scientific Reports, vol. 8, no. 1,
Apr. 2018. [Online]. Available:

[28]
A. Kissinger and J. van de Wetering, “PyZX: Large Scale Automated
Diagrammatic Reasoning,” in Proceedings 16th International
Conference on Quantum Physics and Logic, Chapman University, Orange,
CA, USA., 10-14 June 2019, ser. Electronic Proceedings in Theoretical
Computer Science, B. Coecke and M. Leifer, Eds., vol. 318.1em plus
0.5em minus 0.4emOpen Publishing Association, 2020, pp. 229–241.

[29]
A. Y. Kitaev, “Fault-tolerant quantum computation by anyons,” Annals of
Physics, vol. 303, no. 1, pp. 2–30, 2003.

[30]
S. Krinner, N. Lacroix, A. Remm, A. Di Paolo, E. Genois, C. Leroux,
C. Hellings, S. Lazar, F. Swiadek, J. Herrmann, G. J. Norris, C. K. Andersen,
M. Müller, A. Blais, C. Eichler, and A. Wallraff, “Realizing repeated
quantum error correction in a distance-three surface code,” 2021. [Online].
Available: <https://arxiv.org/abs/2112.03708>

[31]
L. Lao, B. van Wee, I. Ashraf, J. van Someren, N. Khammassi, K. Bertels, and
C. G. Almudever, “Mapping of lattice surgery-based quantum circuits on
surface code architectures,” Quantum Science and Technology, vol. 4,
no. 1, p. 015005, 2018.

[32]
D. Litinski, “A game of surface codes: Large-scale quantum computing with
lattice surgery,” Quantum, vol. 3, p. 128, 2019.

[33]
——, “Magic state distillation: Not as costly as you think,”
Quantum, vol. 3, p. 205, 2019.

[34]
D. Litinski and F. von Oppen, “Lattice surgery with a twist: Simplifying
clifford gates of surface codes,” Quantum, vol. 2, p. 62, 2018.

[35]
N. D. Mermin, Quantum computer science: an introduction.1em plus
0.5em minus 0.4emCambridge University Press, 2007.

[36]
M. A. Nielsen and I. L. Chuang, “Quantum computation and quantum
information,” Phys. Today, vol. 54, no. 2, p. 60, 2001.

[37]
A. Paler, “Surfbraid: A concept tool for preparing and resource estimating
quantum circuits protected by the surface code,” arXiv preprint
arXiv:1902.02417, 2019.

[38]
——, “Aggregated control of quantum computations: When stacked
architectures are too good to be practical soon,” Computer, vol. 53,
no. 8, pp. 74–78, 2020.

[39]
A. Paler, S. J. Devitt, and A. G. Fowler, “Synthesis of arbitrary quantum
circuits to topological assembly,” Scientific reports, vol. 6, no. 1,
pp. 1–16, 2016.

[40]
A. Paler and A. G. Fowler, “Opensurgery for topological assemblies,”
arXiv preprint arXiv:1906.07994, 2019.

[41]
A. Paler, A. G. Fowler, and R. Wille, “Synthesis of arbitrary quantum circuits
to topological assembly: Systematic, online and compact,” Scientific
reports, vol. 7, no. 1, pp. 1–16, 2017.

[42]
S. Parker and M. B. Plenio, “Efficient factorization with a single pure qubit
and log n mixed qubits,” Physical Review Letters, vol. 85, no. 14, p.
3049, 2000.

[43]
H. Poulsen Nautrup, N. Friis, and H. J. Briegel, “Fault-tolerant interface
between quantum memories and quantum processors,” Nature
communications, vol. 8, no. 1, pp. 1–8, 2017.

[44]
J. Preskill, “Quantum Computing in the NISQ era and beyond,”
Quantum, vol. 2, p. 79, Aug. 2018. [Online]. Available:

[45]
G. Research, “Google quantum ai journey,” 2022. [Online]. Available:

[46]
I. Research, “Ibm quantum roadmap,” 2022. [Online]. Available:

[47]
J. Roffe, “Quantum error correction: an introductory guide,”
Contemporary Physics, vol. 60, no. 3, pp. 226–245, 2019.

[48]
N. J. Ross and P. Selinger, “Optimal ancilla-free clifford+ t approximation of
z-rotations,” arXiv preprint arXiv:1403.2975, 2014.

[49]
B. Stroustrup, “Abstraction and the c++ machine model,” in
International Conference on Embedded Software and Systems.1em
plus 0.5em minus 0.4emSpringer, 2004, pp. 1–13.

[50]
M. Suchara, A. Faruque, C.-Y. Lai, G. Paz, F. T. Chong, and J. Kubiatowicz,
“Comparing the overhead of topological and concatenated quantum error
correction,” arXiv preprint arXiv:1312.2316, 2013.

[51]
B. M. Terhal, “Quantum error correction for quantum memories,” Reviews
of Modern Physics, vol. 87, no. 2, p. 307, 2015.

[52]
Y. Tomita and K. M. Svore, “Low-distance surface codes under realistic quantum
noise,” Physical Review A, vol. 90, no. 6, p. 062320, 2014.

[53]
S. Varsamopoulos, K. Bertels, and C. G. Almudever, “Decoding surface code with
a distributed neural network–based decoder,” Quantum
Machine Intelligence, vol. 2, no. 1, pp. 1–12, Jun. 2020.

[54]
G. Vidal, “Efficient classical simulation of slightly entangled quantum
computations,” Physical review letters, vol. 91, no. 14, p. 147902,

[55]
D. S. Wang, A. G. Fowler, and L. C. Hollenberg, “Surface code quantum
computing with error rates over 1%,” Physical Review A, vol. 83,
no. 2, p. 020302, 2011.

[56]
K. Wasa, S. Nishio, K. Suetsugu, M. Hanks, A. Stephens, Y. Yokoi, and
K. Nemoto, “Hardness of braided quantum circuit optimization in the surface
code,” arXiv preprint arXiv:2302.00273, 2023.

[57]
X. Xu, S. C. Benjamin, and X. Yuan, “Variational circuit compiler for quantum
error correction,” arXiv preprint arXiv:1911.05759, 2019.

§ APPENDIX

§.§ Compiler Pipeline and Operating Systems

The natively supported subset of OpenQASM 2.0 instructions is presented in Table <ref>. It is possible to accept a wider range of circuits with additional processing by using Qiskit and PyZX. For example, we have successfully processed Grover circuits with multi qubit gates and Toffoli based adders by decomposing additional gates such as mcx, ccx and rccx which are not in the natively supported set. This kind of gate decomposition is done on a case by case basis.

h, x, z, s, sdg, t, tdg     Single qubit gates with the usual meaning. The -dg suffix stands for dagger.

cnot or cx, cz     Controlled X and Z gates.

rx(theta), rz(theta)     $R_Z$ and $R_X$ gates. Argument theta has to have form [N*pi/D for integers N and D, with the D being a non negative power of two. Both N and D can be of arbitrary size.

crx(theta), crz(theta)     Controlled $R_Z$ and $R_X$ gates. The argument has the same form as for the $R_Z$ and $R_X$ gates.

measure     Single qubit measurement in the Z basis.

qreg     Only one quantum register is supported.

2|p.9|Classical registers, barriers and include directives are ignored. Unsupported instructions and gates raise an exception.

Natively supported subset of OpenQASM 2.0 instructions supported by our compiler.

Figure <ref> is a diagram of how the C++ slicer can take advantage of the operating systems ability to broker messages by using POSIX pipes and an example shell command to run such a pipeline.

E.g.: $./qft_to_stdout.py 128 | lsqecc_slicer -l 12by12.txt | jq .[][][] | grep null | wc -l

qft_to_stdout.py is our tool to stream LLI for a high precision QFT, the 128 argument indicates the number of qubits. lsqecc_slicer -f json is our C++ slicer, which lays out the LLI instructions and outputs a stream of JSON slices to stout, the -l 12by12.txt flag tells it which layout to use. Finally jq [26] is a streaming JSON processor that can extract information from the sequence of slices, here combined with some POSIX utilities to count the total number of routing cells.

§.§ Circuit Simulation and Gate Decomposition

For verification purposes, we require a state-vector snapshot of the logical state of the lattice computation at every time-step. To meet both goals, we use a form of state-vector tracking that stores patch states without tensoring non-entangled states states together. This approach greatly extends what is possible to verify and debug compared to a naive state-vector simulator. Since this simulation is for debugging and verification purposes it is also able to detect when simulated states are numerically close enough to some common state such as $\ket{0}, \ket{+}, \ket{m}$ and display them as such. Figure <ref> is a graphical depiction of a circuit with intermediate states in a Lazily Tensored State-vector Simulation (LTSvS).

Simulating a deep lattice surgery computation is challenging, because there are constantly patches being entangled and measured out, but at a given time few are actually entangled. Each state is represented by certain number of complex variables (c.v.).

Conversion of gates and Pauli rotations to multi-body measurements and other LLI are presented in Fig. <ref>.

This figure only shows rotations by $\frac{\pi}{8}$ and $\frac{\pi}{4}$, but other angles with the same denominator are also possible by adjusting the classical logic controlling the corrective terms that follow. The $\frac{\pi}{8}$ Pauli rotations consume a distilled magic state, while the $\frac{\pi}{4}$ rotations consume a positive $Y$ eigenstate which is prepared by applying a twist based measurement[34].

In Figure <ref>, controlled rotations are common in circuit such as the QFT. The first step towards converting them to fault-tolerant instructions is breaking them down into single qubit rotations and CNOTs [27]. Single qubit rotations of angles greater than $\frac{\pi}{8}$ have to be approximated, while CNOTs we implement with lattice surgery [21].

[wires=1]Z(π/2n)     1         1

[wires=1]Z(π/2n)          [wires=1]Z(-π/2n)
Decomposing controlled rotations into CNOTs and single qubit rotations.

Fig. <ref> illustrates the efficiency of the rotation compression technique we described in Fig. <ref> from Sec. <ref>. How much compression we get exactly depends on the types of gate sequences appearing in the approximations (e.g. both HSSSTH and a lone T compress to a single Pauli rotation). Testing on rotations from $R_Z(\frac{\pi}{2^{8}})$ to $R_Z(\frac{\pi}{2^{128}})$ we observed a factor of $\approx 2.5$ fewer LLI per small angle rotation – this is an an illustration of our optimisation heuristics.

Benchmarking the decomposition techniques for arbitrary rotations to surface code instructions with and without Pauli rotation compression. The benchmark circuit is a single $R_Z(\frac{\pi}{2^n})$ rotation. It is possible to see how grouping gates that rotate in the same basis (as shown in Fig. <ref>) drastically reduces the number of required surface code instructions.

§.§ Clifford Elimination

According to the Gottesman-Knill theorem, it is possible to efficiently simulate circuits which only contain a particular set of gates, known as Clifford gates [36, 1]. It is natural to ask whether it is possible to leverage classical computing to reduce the load on the QPU when processing such circuits. Litinski [32] outlined an algorithm to remove the Clifford part of the circuit at compile time, when all we care about are measurement outcomes (i.e. we are not compiling the circuit to be a state preparation routine). We call this algorithm the Litinski Transform (LT) and provide an implementation in the following manner.

The first step of LT is to convert each gate of the input circuit into a sequence of  rotations about $\frac{\pi}{2}$, $\frac{\pi}{4}$ or $\frac{\pi}{8}$, or multibody measurements with Pauli product observables. Of these blocks, only the $\frac{\pi}{8}$ rotations are not Clifford, so we apply Litinski's commutation rules to bring them all to the front of the circuit. Next the $\frac{\pi}{2}$ and $\frac{\pi}{4}$ rotations are commuted past the previously end-of-circuit measurements. Since this case we only care about measurement outcomes, the Clifford rotations that are now after measurement can be discarded.

This transformation is meant to reduce depth when dealing with circuits that are primarily composed of stabilizer gates [34].
[inline]Numbers. The LT has the drawback that it makes parallelizing surface code operations harder, because the operations end up spanning more logical qubits due to the effect of the commutation identities.


11institutetext: Northern Arizona University
11email: {jacob˙penney, igor.steinmacher<EMAIL_ADDRESS>
Universidade Federal Fluminense
11email<EMAIL_ADDRESS>
# Anticipating User Needs: Insights from Design Fiction on Conversational
Agents for Computational Thinking

Jacob Penney 11 0009-0004-1629-5883
João Felipe Pimentel 22 0000-0001-6680-7470
Igor Steinmacher 11 0000-0002-0612-5790
Marco A. Gerosa 11 0000-0003-1399-7535

###### Abstract

Computational thinking, and by extension, computer programming, is notoriously
challenging to learn. Conversational agents and generative artificial
intelligence (genAI) have the potential to facilitate this learning process by
offering personalized guidance, interactive learning experiences, and code
generation. However, current genAI-based chatbots focus on professional
developers and may not adequately consider educational needs. Involving
educators in conceiving educational tools is critical for ensuring usefulness
and usability. We enlisted nine instructors to engage in design fiction
sessions in which we elicited abilities such a conversational agent supported
by genAI should display. Participants envisioned a conversational agent that
guides students stepwise through exercises, tuning its method of guidance with
an awareness of the educational background, skills and deficits, and learning
preferences. The insights obtained in this paper can guide future
implementations of tutoring conversational agents oriented toward teaching
computational thinking and computer programming.

###### Keywords:

Conversational Agents Scaffolding Computational Thinking Natural Language
Programming Introductory Programming Courses Design Fiction

##  1 Introduction

Knowledge of computer programming is key for modern society and for students
[52]. Professionals from a diverse variety of industries need to write
programs for tasks such as making financial predictions, office work,
scientific research, creating entertainment, etc. [44, 34, 27, 6, 22]. End-
user programmers—those who program but are not professional developers—have
grown enough as a population to compel large tech firms to make major
investments into technologies intended to ease development for them [28]. This
increasing need among future workforce professionals to learn how to program
is reflected in their educational needs today. It is not surprising that a
large number of undergraduate programs include introductory programming in
their curriculum. In fact, the literature shows plenty of evidence that STEM
students perceive programming as a key skill in their careers [12, 13, 56, 7].

However, computer programming is difficult to learn [26, 27, 32, 47, 59]. Both
undergraduate Computer Science majors and the growing population of non-majors
who program struggle and show clear signs of poor performance, frustration,
and lack of engagement [16, 4, 18]. Some institutions have reported dropout
rates up to 50% [25], and the estimated mean global pass rate for introductory
Computer Science courses is around 68% [62]. Substantial effort has been made
to discover why learning how to program is chronically problematic. While
there is no definitive consensus in the literature on what factors determine
performance in introductory CS courses [62], many findings highlight student
frustrations with programming language syntax, which is rigid and allows only
a very restricted set of operations, as a reason for why learning is difficult
[20, 18, 29, 37, 60]. In interviews with students, Petersen et al. [49]
discovered a variety of contributing factors that prompt class withdrawal,
such as the usage of ineffective study strategies; falling behind in the class
and consequently receiving less support from in-class exercises and labs; and
difficulty handling the relatively high level of detail in the material, which
required developing problem-solving skills and was eased when they had access
to step-by-step instructions. Student participants in other works also report
difficulty adapting to the demands of CS1 courses, citing difficulty with new
teaching methods emphasizing independent thinking, critical thinking, and
innovative learning, as well as less interaction with teachers and classmates,
disconnection between the knowledge and real-life cases, and not receiving
enough academic support with timely help and real-time feedback [8].

New study strategies built on novel technologies, such as large language
model-based (LLM-based) conversational agents – that allow exercising
computational thinking in a conversational way – have the potential to
overcome traditional strategies, allowing more students to succeed and grow in
introductory programming courses. Such tools have achieved incredible
performance even on complex assignments [45, 33, 51, 57, 17]. GPT-3 has been
used to create explanations of code snippets that are significantly easier to
understand and more accurate summaries of code than what can be produced by
first-year CS students [31], providing students on-demand access to
explanations that explain code, freeing up instructor time. GPT-4 has even
displayed rivaling human tutor performance in various programming education
scenarios [50]. Not only are these tools capable, but findings show that users
feel that they improve their outcomes. For example, programmers of various
skill levels who used or were exposed to the features of a custom LLM-based
conversational agent perceived that it could improve their productivity [55],
and students feel more motivated to learn, more engaged in the course, and
more connected to their classmates [8].

While evidence displays that LLM-based conversational agents can improve
various outcomes for developers and students of different skill levels, little
research exists on how to design such technology to improve the learning of
computational thinking. Most existing solutions that allow for using a
conversational way to program expose the artificial intelligence of the tool
in a way not tailored to facilitate learning to program. This is because they
typically focus on professional productivity, giving the user the desired
solution instead of using coaching and scaffolding, in the Cognitive
Apprenticeship Model usage [14], to teach the user. Such tools could be used
to refocus students’ initial efforts on learning computational thinking [39,
1] instead of focusing on implementation. The literature shows that
implementation details can frustrate students because of the rigid set of
operations allowed by programming language syntax [20, 18, 29, 37, 60].

With this in mind, this work seeks to understand instructors’ expectations of
a conversational agent’s capabilities in effectively facilitating the
acquisition of computational thinking skills. The research question we answer
here is:

Research Question What are instructors’ expectations of a programming
conversational agent intended to scaffold computational thinking?

To answer this question, we used the Design Fiction method. We analyzed the
data collected from sessions with instructors by means of open and axial
coding procedures. From this analysis, we learned that instructors expect a
conversational agent intended to scaffold computational thinking to approach
students with an awareness of their educational history and context and tailor
its response to their questions accordingly. These responses should guide the
student, maximizing skill set development. We hope these findings will inspire
future research, design, and evaluation of conversational agents as well as
serve as criteria for evaluating AI-based generative agents.

##  2 Related Work

After the recent proliferation of genAI tools, there have been escalating
salvos of works exploring their use cases, quantifying and qualifying their
abilities, and speculating about futures in which they have become fixtures.
This work is situated among others which explore the perspectives of
instructors about the experiences of students using conversational agents
empowered by genAI to aid the learning process, the imagined and real
benefits, and the potential pitfalls. Phung et al. [50] quantify the skills of
existing LLM’s, displaying not only where the state-of-the-art is at but also
discussing where it is headed. Becker et al. [1] motivate educators in the
booming genAI discussion, conveying an urgency to concertedly influence coming
opportunities. Maher et al. [40] propose and acknowledge many of the same
benefits and concerns, respectively, that our participants imagined and
introduce a methodology for analyzing AI tool impact via examining impact on
student experience and abilities. Guo [23] discusses ways that genAI can
already be used for programming autodidacticism and considers ways that
scientists and engineers can ply them for the educational needs of their
specific fields.

The closest work to ours was performed by Lau et al. [30]. They ran interviews
with instructors to understand how they plan to handle the use of genAI tools
in their introductory programming classes. They found that the most common
reason that instructors do not want to use AI-based tools in their classes is
because they felt it is still important to learn the fundamentals of
programming, even if AI tools will be doing a lot of the coding in the future.
This opposition depends completely on the diegesis used, which asks the
participant to imagine a tool that handles programming for the student with
consistent perfect output, not paradigms that run counter to this solution-
oriented functionality. Our work expands upon Lau et al. by taking some first
steps towards answering open research questions they have posed, specifically
Scaffolding novice understanding and Tailoring AI coding tools for pedagogy.
We did this by approaching a population of instructors, as they did, with a
diegesis oriented towards future conversational agents that do not have the
limitations of current LLM-based ones.

##  3 Research Design

###  3.1 Research Approach

To explore the design space of the conversational agent, we employed Design
Fiction [61]. This method features the deliberate use of diegetic prototypes
to suspend disbelief about change [61] and envision and explain plausible
futures [2, 38, 24, 21, 35, 42, 36]. Human-Computer Interaction studies often
use this method to probe, explore, and critique future technologies [30, 54,
63, 42, 3]. Some researchers use design fiction to anticipate issues [3] while
others emphasize values related to new technologies [43, 11] and anticipate
users’ needs [10, 21, 46], which is the focus of this paper.

###  3.2 Method

The Fictional Narrative. We started the design fiction session by presenting a
fictional narrative to the participants through a video [48]. The video was
intended to prompt participants to think about how a conversational agent
could effectively scaffold computational thinking for students in introductory
computer programming courses. In this scenario, a fictional student named Luna
is learning Computer Science and, while she has access to an instructor during
her class periods, she is left to find her own answers after class. The
context of the video is a future in which present technological limitations
have been overcome, and she has access to ecumenical AI tools that can help
her with her studies. One such tool, Atlas, is a conversational agent that may
interact conversationally and have access to and awareness of the student’s
context through integrations, such as coding environments, execution
artifacts, exercises, and the progression of the course. The tool is presented
as intended to help the student express her thoughts computationally. Having
placed themselves in this narrative, we asked the participant to help us
define how the conversational agent should behave so that it can help the
student learn.

Participant Recruitment. To participate in the design fiction sessions, we
recruited instructors who have at least one year of professional experience
teaching Computer Science or computational thinking. To access this
population, we started by recruiting from the pool of instructors from our
personal network and we used snowball sampling to help find new participants.

We screened potential participants by looking at their personal or university
websites and invited those who had experience teaching introductory
programming classes. During the invitation, we also sent our consent form that
discussed relevant information about the study, including stipulations that
our interviews would be recorded but that the recording and any resulting
transcripts would be deleted after our work concluded.

In total, nine instructors agreed to participate in the study, as presented in
Table 1.

Table 1: Demographics of participants. _Exp._ indicates the experience in years of the participant. _Uni. Type_ indicates the type of the university and the highest education level that it grants. ID |  | Exp.
---
Gender | Country |  | Uni. Type
---
| Introductory Classes
---
P1 | 14 | F | USA | Public-PhD | Algorithms, Data Structures, Programming
P2 | 20 | M | Brazil | Public-MSc | Algorithms, App Programming
P3 | 3 | M | USA | Public-PhD | Web Programming, Programming
P4 | 2 | M | Brazil | Public-MSc | Algorithms, Programming
P5 | 15 | M | Brazil | Public-PhD | Programming
P6 | 1.5 | M | Brazil | Public-BSc | Data Structures, Programming, Object Orientation
P7 | 10 | F | Brazil | Public-PhD | Programming
P8 | 15 | M | Brazil | Private-BSc | Algorithms, Data Structures, Web Programming
P9 | 3.5 | M | USA | Public-PhD | Algorithms, Data Structures, Programming

Design Fiction Sessions. Qualified participants were invited to a meeting
wherein one researcher introduced the goals of the work, displayed the two-
minute prompt diegesis video, and interviewed the participants about how the
conversational agent could help scaffold computational thinking and how they
feel about such a tool. These interviews lasted for 30-60 minutes and were
guided by these questions:  1. How can Atlas help Luna with computational
thinking?  2. How should Luna interact with Atlas?  3. Where should Atlas be
integrated to offer the best teaching experience?  4. Are there any statistics
that Atlas should collect from students and give to instructors?  5. What
benefits do you foresee with the use of Atlas?  6. What drawbacks do you
foresee with the use of Atlas?  7. If you had two competing personal
assistants, which criteria would you use to choose which one to use with your
students?  8. Do you have other suggestions about how Atlas should work?

Figure 1: Our research method consists of five main steps, with the outcome of
one step being the input to the next.

Basic flowchart of the paper’s procedure. The first step of our research
method was conducting design fiction interviews. Second, we used a speech
recognition model to transcribe the interview text, after which a researcher
listened to the interview and corrected errors in the transcription. Third, a
researcher coded the corrected transcription. Fourth, a second researcher
coded the same content. Fifth, one researcher cyclically refined the code
categories. This process yielded our final output.

Analysis Method To analyze the narratives, as in similar studies [63, 30], we
applied open and axial coding procedures [15] through multiple rounds of
analysis (see figure 1). This analysis aimed to collect design insights and
expectations that serve as guidelines for implementing such a conversational
agent. After concluding an interview, the resulting recording was transcribed
using a speech recognition tool [53], and a researcher reviewed the
transcription with the recording to correct errors. Then, a researcher
analyzed the text and coded participant quotes, after which a second
researcher reviewed the first coding and applied coding a second time. After
these two rounds of coding, we iteratively and cyclically reviewed and refined
our categories, initially as a team and then conducted by the lead researcher.
High-level categories of participant expectations began to emerge from our
interview data and began to stabilize as our number of participants grew,
indicating advancement towards data saturation, where these high-level
categories nearly stopped evolving. We stopped interviewing participants since
the final interviews did not bring significant insights to our results.

##  4 Results

In this section, we present our participants’ expectations for an educational
conversational agent and their sentiments about those expectations.

###  4.1 Expectations

Participants described five categories of expectations that they felt would
make the tool optimal for the end goal of scaffolding computational thinking
for novice Computer Science students, displayed in Figure 2: programming
guidance, code elucidation, student telemetry, course administration, and
UI/UX.

Figure 2: Categorization of expectations narrative data

Graph displaying hierarchical codes used to organize and understand the data.

Programming Guidance. Instructors expect conversational agents to be able to
scaffold computational thinking for students by guiding them stepwise through
the development of algorithms in natural language instead of giving students
solutions. The general idea was elaborated most lucidly by participant P1: So,
there are some standard questions that the teacher sometimes asks to say,
‘Look at what you want to do. What is the next step you would need to take in
order to express yourself in the language you’re using, in natural language,
so to speak?’. While doing this, the agent should approach the student with an
awareness of their educational background and knowledge and tailor their
responses accordingly, such as explaining a concept differently to address the
student’s misunderstanding (P3). Support for giving the student solutions was
overwhelmingly negative, and support for giving code was mixed and
conditional, with four viewing it unfavorably (P3, P5, P6, P8) and three in
support of translating pseudocode into code (P2, P4, P7). P4 felt that it was
permissible because the intention is that students should focus on algorithmic
thinking, not implementation. P3 felt it was permissible that the
conversational agent give an algorithm in code that models the current
problem, but which is not the solution and must be synthesized with their own
ideas to successfully complete.

Code Elucidation. The conversational agent should be able to explain things in
the environment that the student might be confused about, such as problem
statements, code snippets, diagnostics, compilation and runtime errors, and
underlying algorithms and concepts, such as memory. It should also be able to
use diverse means to do so. For example, the most popular elucidation
expectation that participants had was visualization, such as for algorithms
(P1, P2, P9), memory (P8), debugging (P1), and code flow (P2). P2 emphasized I
understand that, from my experience, one of the best ways to make the student
understand computational thinking and how it works is by drawing diagrams.
Other examples of envisioned elucidation behaviors include retrieving
documentation, highlighting passages relevant to the problem being addressed,
and even explaining them if the student does not understand it (P3) and
proactive and reactive debugging (P1, P2, P3, P8, P9) and refactoring (P5,
P6), wherein the agent explains what can or should be done and why.

Student Telemetry. Participants acknowledged that many of the behaviors they
expect from a conversational agent may require it to collect and use
information about the student, and some desired for the agent to return
statistics about the class for their consideration. Our participants thought
of various pieces of information that would be useful to the agent and them.
The most discussed was information about the student’s formal and informal
educational history (P2, P3), field of study or career (P4), doubts or
struggles with course topics (P4, P5, P6), past usage of the tool (P2), and
ability and disability (P3, P8). As discussed before, having information about
the student could allow the agent to tailor responses, ideally to a high
level. P3 explained that there are many different ways to get to a solution,
and if a student had that particular background, for instance, and Atlas was
aware of that background, that might really help Atlas to maybe redirect the
student to a different angle or a different approach to maybe better explore
their lack of understanding on a topic.

As per our participants, Atlas should display to the professor which topics
students are struggling with, not only to help the current course but to
create an awareness of specific struggles for the next iteration of the
course. P6 thinks that [the agent should collect statistics and create a]
categorization of the main difficulties, so that… in a new class, the
instructor can already have an idea of what they should address…. Participants
also imagined that the conversational agent could observe the problem-solving
behaviors of the student, such as detecting when they were stuck, how many and
what kind of mistakes they made, the amount of effort and time the student put
into work on the platform, the performance of their code solutions (maybe
similar to how tools like Leetcode evaluate the speed of a solution), and
whether or not the student cheated.

To the contrary and looking towards the future of pedagogy, P3 felt that
collecting statistics on student performance facilitates usage of outmoded
methods of assessment: the idea that students can navigate their own learning
process at their own speed is entirely novel to… modern education. And I think
that especially with tools like Atlas, we should really be stepping back from
the concept of performance and especially like temporal performance
achievements.

Course Administration. Concerning course administration, participants were
interested in the creation of study materials and exercises that were
predicated on their students’ past education, work they have done with the
conversational agent, and deficiencies with the current topic. Some
participants (P6, P8, P9) envisioned students being given remedial exercises
based on scores on assessments taken in the agent. P4 envisioned assessments
advancing incrementally, as they would in curriculum, and felt this pattern of
escalation lends itself well to gamification, which would act as a means to
maintain engagement. P3 opposed the conversational agent giving preprepared
exercises because they cannot address the individual’s particular
misunderstandings or tailor their help to fit them. They also opposed the
agent creating final grades for a class… or even final grades for a set of
concepts because it may lack the flexibility and nuance that humans display
when assessing how well a student has learned.

UI/UX. Expectations for how the user interface should behave, how the student
should interact with the agent, or what the user experience should be like
were varied and inconsistent. Participants imagine interacting with
conversational agents via voice (P2, P6, P9), traditional input methods,
virtual/augmented reality (P7, P8), and mobile (P6), with some detractors. P8
felt that popular utilities, like search engines, already respond via text, so
the method of IO was not interesting. P2 felt that virtual reality doesn’t
offer much at the moment, but may in the future. The ability to customize the
agent was interesting to a few participants (P1, P2, P9), specifically the
ability to toggle functionality through atomic settings. Another suggestion
was the use of modes dedicated to common usages, such as taking exams (P9).
One participant, P4, mentioned accessibility a couple of times, referencing
students with physical disabilities, such as deafness, and neuroatypicality,
such as ADHD, and discussed that it would be meaningful for the system to have
flexibility with IO methods to include such students.

###  4.2 Sentiments

In addition to expectations, the participants discussed three categories of
sentiments they had about such a tool in response to questions 5-7.

Benefits. All-in-all, participants saw benefits of using a conversational
agent oriented towards education for both students and instructors, but
particularly for engaging, emotionally buttressing, and increasing
understanding for students. Participants felt the tool could continuously
assist students as they worked, potentially even in an omnipresent way (P8).
Through this, they could experience decreases in feelings of isolation or
fending for oneself (P7) and anxiety from not being able to finish their work
right away and while a teacher is not around (P9). P3 explained that by
providing a guide that will be present to help decompose and guide them
through problems you’re giving students an opportunity to explore the problem
without freaking out and… giving up, which they feel is one of the biggest
barriers to success for computer science students. The benefits to instructors
that we found discussed most were that the agent could provide them with
metrics about the class and help to free up their time by assisting with
responding to students (P1), allowing them to focus on other areas of the
class (P9), or even allowing them to teach more students (P9).

Drawbacks. Reliance on the agent, teaching students incorrectly, and
deteriorating relationships in the classroom are among the worries that
participants had about the agent. If the tool engages in proactive
intervention while the student is incorrectly implementing something, as an
instructor might, it may condition students to wait for help (P2, P4). If the
design is poor and students are capable of getting to solutions without
receiving scaffolding, the student may not learn or may not be able to perform
without the tool (P1, P4, P5). Of course, the instructor may have to watch for
signs of misuse or cheating (P1, P2, P3). Then again, if the design works,
participants worried that students may lose connection to their instructor or
feel that they no longer need class time (P1, P6, P9). P3 noted that the tool
may be difficult to administer, and it may make finding instructors more
difficult because the institution will need those who can operate the tool.

Priorities. In the scenario where participants were deliberating over which
conversational agent to use, proven effectiveness with teaching students,
credibility, and customization would sway their decision the most.
Participants sometimes remarked on specific qualities that would promote
learning the most, such as knowing when it is appropriate to intervene to
offer assistance (P5, P7), teaching as opposed to simply giving answers and
offering a comfortable interaction to the student (P6) and choosing the most
effective means of teaching a concept, such as using visuals (P8). Emphasis on
the tool’s credibility betrayed that the participants who mentioned it did not
fully immerse in the diegesis when it proposed that present technical
limitations were not a concern, but that concern is significant and present.
Instructors felt that customization would offer the ability for the tool to
cater to needs more finely, such as by adjusting language (P4); the instructor
having the ability to toggle functionality when needed, such as for specific
assignments or tasks (P1, P9); and the student being able to toggle
functionality as well, so they can get the experience they want (P9).

Answer to the Research Question What are instructors’ expectations of a
programming conversational agent intended to scaffold computational thinking?
The conversational agent is expected to act as a competent guide which would
allow the student to move at their own pace through guided algorithm
implementations and have access to thorough explanations in a variety of
media, adapted to the individual student’s background. Instructors would like
the agent to collect statistics about student performance, usage, and
background to make other abilities possible. Correct scaffolding behavior and
credible guidance stemming from good data are preeminent and will sway
educators to use a given conversational agent.

##  5 Discussion

Some of the behaviors that the instructors expect can already be meaningfully
realized by existing LLMs and conversational agents built on top of them, such
as ChatGPT. As introduced in Section 1, LLMs have displayed that they can
outperform first-year Computer Science students in creating explanations of
basic function definitions [31]. More advanced models have displayed
approaching the efficacy of human tutors in tasks such as providing hints to a
student to help resolve current issues and generating new tasks that exercise
specific types of concepts/bugs [50], abilities that our participants also
expected. However, these recent findings do not address the more abstract
ability to scaffold problem-solving skills or algorithm implementation via
piecewise, tailored guidance without giving code or pseudocode, for one major
example. Taming the output of LLMs for educational purposes is still an open
problem, and developers implementing conversational agents for this purpose
must consider how this can be accomplished.

Instead of allowing the student unrestricted access to the LLM’s bank of
information, developers should consider ways to regulate the LLM so that the
response models actual problem-solving processes or provokes the student into
critical thinking. Developers should also recognize that it is important to
instructors that this response be tailored to the students’ background and
learning style. One popular method of tailoring LLMs is by prompt engineering,
or prompt crafting [5], on the natural language input. LLM outputs are known
to be sensitive to inputs, producing different results for the same questions
posed with different phrasing, and this quality can be exploited to strongly
improve output appropriateness for a conversational agent focused on a
specific domain [17].

In the current landscape, recent scholarship notes that novel conversational
agent implementations using GPT-4, such as Khanmigo, are advancing the state-
of-the-art [41] of teaching using LLMs. Khanmigo poses questions to the
student to prompt problem-solving behavior and can use redirection to refocus
the student on the current question if they try to circumvent it.
Functionalities such as this are possible through prompt engineering; indeed,
LLM pipelines that rely on prompt engineering under the hood appear to be the
current standard response to the question of taming LLM output, as we see with
established conversational agent implementations such as Github
Copilot111https://github.blog/2023-07-17-prompt-engineering-guide-generative-
ai-llms/ and cutting-edge LLM-based tools from industry research, such as
Microsoft Lida222https://microsoft.github.io/lida/ [19]. Nevertheless, some
expectations that our participants had cannot yet be realized. Dynamically
creating visualizations tailored to address students’ specific
misunderstandings or situations is still hard with current LLMs; regardless,
it is one of the most anticipated abilities among our participants.

Finally, researchers interested in expanding upon our work can also
investigate how certain effects can be accomplished. For example, participants
were interested in the idea that assisting students may make them feel
emotionally supported. While some felt that this was a natural consequence of
having access to a powerful resource such as Atlas, it is not clear whether
this hypothesis holds or what the role of other aspects would be, such as non-
traditional interaction (e.g., voice and visual representations) and social
characteristics (e.g., race, gender, culture) in the emotional support of
students. For instance, researchers at the intersection of education and
gender have established that gender plays a significant role in student
engagement and that women STEM students are more inclined to seek help from
women STEM instructors [58]. Researchers looking to increase the comfort and
effectiveness of LLM-based conversational agents should acknowledge and
integrate work that examines the intersection of student and instructor
identity with course engagement. A variety of other social characteristics of
chatbots [9] can be investigated in this context. Future studies building upon
this work can also incorporate the students’ perspectives. Such research could
present the same scenarios and pose the same questions to discern potential
discrepancies in expectations and sentiments.

##  6 Limitations

In this work, we focused on the perspectives of instructors who teach or have
recently taught introductory computer science. This method follows in the
footsteps of other recent works [30], but is a limitation because our results
are skewed toward the experiences and interests of one population, only half
of the classroom dynamic. Having no student voices leaves this work lacking
insight on how students expect conversational agents to behave to help them
develop computational thinking skills more effectively. New research focused
on the student perspective may reveal entirely different sets of expectations
and sentiments than those discussed by our current participants.

Even with focusing exclusively on instructors, our sample population is not
diverse. We recruited instructors who work at five universities in Brazil and
one in the United States. Most (7) were Brazilian cisgender men. we had only
two instructors who were cisgender women, both Brazilian and one who taught in
the United States. Consequently, our outcomes are biased along gender,
culture, and region, for example because we have no trans or non-binary
participants, and none from or teaching in Asia, Africa, or Europe. None
explicitly expressed that they lived with disabilities which influenced their
perspective, nor did they explicitly express that their racialization was a
factor in their responses. The gender distribution of our participant cohort,
in particular, arguably reflects the homogeneous gender distribution of the
field it drew from, which has and still underrepresents cisgender women.
Additional research which intentionally explores the experiences of more
diverse populations may yield concerns not touched upon here. Of particular
interest are the experiences of marginalized populations and discovering ways
such tools can serve those who are least served by current pedagogy and
educational institutions. Besides the identity of the instructors, other
meaningful limitations may include that all but one instructor taught at
public universities.

Much like related studies that use design fiction or similar methods [30], our
participants often discussed the future and hypothetical LLM-based
conversational agents of the future in terms of existing conditions and
similar extant technologies. While our interview questions and initial video
prompt encouraged participants to envision a tool without the limitations
faced by those that exist now, the sentiments they expressed may reflect the
reality that they know. This includes how they conceived of UI/UX, such as
imagining the tool using input methods that are currently common, such as
voice; struggles LLMs face, such as the relevancy of data that the model was
trained upon; and even common fears about LLM-based tools negatively impacting
economic conditions for instructors.

##  7 Conclusion

In this paper, we presented the expectations and sentiments of instructors
involved with teaching Computer Science on the various functionalities that a
LLM-based conversational agent could offer to best serve them in their work.
Instructors imagined a tool that can scaffold computational using insights
into the individual they are instructing, providing accessible tailored
education outside of the classroom. This paper’s findings lay the foundation
for the implementation of novel solutions or the improvement of existing ones
that can cater to the academic community, as well as introduce lines of
further investigation. Future work on this topic include a design fiction
study with student populations, Wizard of Oz experiments intended to classify
student intentions and how they are expressed in dialogue, and design and
prototype implementation of the conversational agent.

##  8 Acknowledgments

This work was supported by the National Science Foundation grants 2236198,
2247929, and 2303042. We thank Alexander Gustav Siegel for assistance with our
coding process and the instructors who shared their valuable experience
participating in our research.

## References

  * [1] Becker, B.A., Denny, P., Finnie-Ansley, J., Luxton-Reilly, A., Prather, J., Santos, E.A.: Programming Is Hard – Or at Least It Used to Be: Educational Opportunities and Challenges of AI Code Generation. In: SIGCSE TS. pp. 500–506 (2023)
  * [2] Blythe, M.: Research through design fiction: narrative in real and imaginary abstracts. In: CHI. pp. 703–712. ACM (2014)
  * [3] Blythe, M., Encinas, E.: The Co-ordinates of Design Fiction: Extrapolation, Irony, Ambiguity and Magic. In: GROUP. pp. 345–354. ACM (2016)
  * [4] Bosse, Y., Gerosa, M.A.: Why is programming so difficult to learn?: Patterns of Difficulties Related to Programming Learning Mid-Stage. ACM SIGSOFT Software Engineering Notes 41(6), 1–6 (2017)
  * [5] Bull, C., Kharrufa, A.: Generative AI Assistants in Software Development Education: A vision for integrating Generative AI into educational practice, not instinctively defending against it. IEEE Software pp. 1–9 (2023)
  * [6] Burnett, M.: What Is End-User Software Engineering and Why Does It Matter? In: IS-EUD. pp. 15–28. Springer (2009)
  * [7] Camp, T., Zweben, S., Walker, E., Barker, L.: Booming Enrollments: Good Times? In: SIGCSE TS. pp. 80–81 (2015)
  * [8] Cao, C.: Scaffolding CS1 Courses with a Large Language Model-Powered Intelligent Tutoring System. In: Companion Proceedings of the 28th International Conference on Intelligent User Interfaces. p. 229–232. IUI ’23 Companion, Association for Computing Machinery, New York, NY, USA (2023). https://doi.org/10.1145/3581754.3584111, https://doi.org/10.1145/3581754.3584111
  * [9] Chaves, A.P., Gerosa, M.A.: How Should My Chatbot Interact? A Survey on Social Characteristics in Human–Chatbot Interaction Design. International Journal of Human–Computer Interaction 37(8), 729–758 (2021)
  * [10] Cheon, E., Su, N.M.: Configuring the User: “Robots Have Needs Too”. In: CSCW. pp. 191–206. CSCW ’17, ACM, New York, NY, USA (2017). https://doi.org/10.1145/2998181.2998329, http://doi.acm.org/10.1145/2998181.2998329
  * [11] Cheon, E., Su, N.M.: Futuristic Autobiographies: Weaving Participant Narratives to Elicit Values around Robots. In: HRI. pp. 388–397. HRI ’18, ACM, New York, NY, USA (2018). https://doi.org/10.1145/3171221.3171244, http://doi.acm.org/10.1145/3171221.3171244
  * [12] Chilana, P.K., Alcock, C., Dembla, S., Ho, A., Hurst, A., Armstrong, B., Guo, P.J.: Perceptions of non-CS majors in intro programming: The rise of the conversational programmer. In: VL/HCC. pp. 251–259. IEEE (2015)
  * [13] Chilana, P.K., Singh, R., Guo, P.J.: Understanding Conversational Programmers: A Perspective from the Software Industry. In: CHI. pp. 1462–1472 (2016)
  * [14] Collins, A., et al.: Cognitive Apprenticeship: Teaching the Craft of Reading, Writing, and Mathematics. Technical Report No. 403. Tech. rep., BBN and UIUC (1987)
  * [15] Corbin, J., Strauss, A.: Basics of Qualitative Research: Techniques and Procedures for Developing Grounded Theory. Thousand Oaks, CA: Sage, 3rd edn. (2008)
  * [16] Dawson, J.Q., Allen, M., Campbell, A., Valair, A.: Designing an Introductory Programming Course to Improve Non-Majors’ Experiences. In: SIGCSE TS. pp. 26–31 (2018)
  * [17] Denny, P., Kumar, V., Giacaman, N.: Conversing with Copilot: Exploring Prompt Engineering for Solving CS1 Problems Using Natural Language. In: SIGCSE TS. pp. 1136–1142 (2023)
  * [18] Denny, P., Luxton-Reilly, A., Tempero, E., Hendrickx, J.: Understanding the syntax barrier for novices. In: ITiCSE. pp. 208–212 (2011)
  * [19] Dibia, V.: LIDA: A Tool for Automatic Generation of Grammar-Agnostic Visualizations and Infographics using Large Language Models. In: ACL. Association for Computational Linguistics (March 2023)
  * [20] Edwards, J., Ditton, J., Trninic, D., Swanson, H., Sullivan, S., Mano, C.: Syntax Exercises in CS1. In: ICER. pp. 216–226 (2020)
  * [21] Encinas, E., Blythe, M.: The Solution Printer: Magic Realist Design Fiction. In: CHI. pp. 387–396. ACM (2016)
  * [22] Ghaoui, C.: Encyclopedia of Human Computer Interaction. IGI Global (2005)
  * [23] Guo, P.J.: Six Opportunities for Scientists and Engineers to Learn Programming Using AI Tools such as ChatGPT. Computing in Science & Engineering (2023)
  * [24] Harmon, E., Bopp, C., Voida, A.: The Design Fictions of Philanthropic IT: Stuck Between an Imperfect Present and an Impossible Future. In: CHI. pp. 7015–7028 (05 2017). https://doi.org/10.1145/3025453.3025650
  * [25] Kinnunen, P., Malmi, L.: Why students drop out CS1 course? In: ICER. pp. 97–108 (2006)
  * [26] Ko, A.J., Myers, B.A.: Development and evaluation of a model of programming errors. In: HCC. pp. 7–14. IEEE (2003)
  * [27] Ko, A.J., Myers, B.A., Aung, H.H.: Six Learning Barriers in End-User Programming Systems. In: VL/HCC. pp. 199–206. IEEE (2004). https://doi.org/10.1109/VLHCC.2004.47
  * [28] Kuhail, M.A., Farooq, S., Hammad, R., Bahja, M.: Characterizing Visual Programming Approaches for End-User Developers: A Systematic Review. IEEE Access 9, 14181–14202 (2021)
  * [29] Kummerfeld, S.K., Kay, J.: The neglected battle fields of syntax errors. In: ACE. pp. 105–111. Citeseer (2003)
  * [30] Lau, S., Guo, P.J.: From “Ban It Till We Understand It” to “Resistance is Futile”: How University Programming Instructors Plan to Adapt as More Students Use AI Code Generation and Explanation Tools such as ChatGPT and GitHub Copilot. In: ICER (2023)
  * [31] Leinonen, J., Denny, P., MacNeil, S., Sarsa, S., Bernstein, S., Kim, J., Tran, A., Hellas, A.: Comparing Code Explanations Created by Students and Large Language Models. In: Proceedings of the 2023 Conference on Innovation and Technology in Computer Science Education V. 1. p. 124–130. ITiCSE 2023, Association for Computing Machinery, New York, NY, USA (2023). https://doi.org/10.1145/3587102.3588785, https://doi.org/10.1145/3587102.3588785
  * [32] Lewis, C., Olson, G.: Can principles of cognition lower the barriers to programming? In: Empirical studies of programmers: second workshop. pp. 248–263 (1987)
  * [33] Li, Y., Choi, D., Chung, J., Kushman, N., Schrittwieser, J., Leblond, R., Eccles, T., Keeling, J., Gimeno, F., Dal Lago, A., et al.: Competition-level code generation with AlphaCode. Science 378(6624), 1092–1097 (2022)
  * [34] Lieberman, H., Paternò, F., Klann, M., Wulf, V.: End-User Development: An Emerging Paradigm. In: End User Development, pp. 1–8. Springer (2006)
  * [35] Lindley, J., Coulton, P., Brown, E.L.: Peer Review and Design Fiction: “Honestly, they’re not just made up.”. CHI Extended Abstracts (Alt. CHI). ACM (2016)
  * [36] Linehan, C., Kirman, B.J., Reeves, S., Blythe, M.A., Tanenbaum, J.G., Desjardins, A., Wakkary, R.: Alternate endings: using fiction to explore design futures. In: CHI. pp. 45–48. ACM (2014)
  * [37] Lister, R.: Computing education research programming, syntax and cognitive load. ACM Inroads 2(2), 21–22 (2011)
  * [38] Lupton, E.: Design is storytelling. Cooper-Hewitt Museum, Chicago, IL (November 2017)
  * [39] Luxton-Reilly, A.: Learning to Program is Easy. In: ITiCSE. pp. 284–289 (2016)
  * [40] Maher, M., Tadimalla, Y., Dhamani, D.: IS CHATGPT GOOD FOR YOUR STUDENTS? A STUDY DESIGN OF THE IMPACT OF AI TOOLS ON THE STUDENT EXPERIENCE IN LEARNING JAVA. In: EDULEARN23 Proceedings. pp. 5702–5709. 15th International Conference on Education and New Learning Technologies, IATED (3-5 July, 2023 2023). https://doi.org/10.21125/edulearn.2023.1493, https://doi.org/10.21125/edulearn.2023.1493
  * [41] Markel, J.M., Opferman, S.G., Landay, J.A., Piech, C.: GPTeach: Interactive TA Training with GPT Based Students. In: L@S. p. 226–236 (2023)
  * [42] Muller, M., Erickson, T.: In the Data Kitchen: A Review (a Design Fiction on Data Science). In: CHI. pp. alt14:1–alt14:10. CHI EA ’18, ACM, New York, NY, USA (2018), http://doi.acm.org/10.1145/3170427.3188407
  * [43] Muller, M., Liao, Q.V.: Exploring AI Ethics and Values through Participatory Design Fictions. Human Computer Interaction Consortium (2017), https://www.slideshare.net/traincroft/hcic-muller-and-liao-participatory-design-fictions-77345391
  * [44] Myers, B.A., Ko, A.J., Burnett, M.M.: Invited research overview: end-user programming. In: CHI. pp. 75–80 (2006)
  * [45] Nguyen, N., Nadi, S.: An empirical evaluation of GitHub copilot’s code suggestions. In: MSR. pp. 1–5. IEEE (2022)
  * [46] Noortman, R., Schulte, B.F., Marshall, P., Bakker, S., Cox, A.L.: HawkEye - Deploying a Design Fiction Probe. In: CHI. pp. 422:1–422:14. CHI ’19, ACM, New York, NY, USA (2019). https://doi.org/10.1145/3290605.3300652, http://doi.acm.org/10.1145/3290605.3300652
  * [47] Pea, R.D., Kurland, D.M.: On the cognitive effects of learning computer programming. New Ideas in Psychology 2(2), 137–168 (1984)
  * [48] Penney, J.M., Pimentel, J.F., Steinmacher, I., Gerosa, M.A.: Anticipating User Needs: Insights from Design Fiction on Conversational Agents for Computational Thinking (2023), https://youtu.be/SleAo-IM7kU
  * [49] Petersen, A., Craig, M., Campbell, J., Tafliovich, A.: Revisiting why students drop CS1. In: KOLI-CALLING. p. 71–80. Koli Calling ’16, Association for Computing Machinery, New York, NY, USA (2016). https://doi.org/10.1145/2999541.2999552, https://doi.org/10.1145/2999541.2999552
  * [50] Phung, T., Pădurean, V.A., Cambronero, J., Gulwani, S., Kohn, T., Majumdar, R., Singla, A., Soares, G.: Generative AI for Programming Education: Benchmarking ChatGPT, GPT-4, and Human Tutors. International Journal of Management 21(2), 100790 (2023)
  * [51] Prenner, J.A., Babii, H., Robbes, R.: Can OpenAI’s Codex Fix Bugs? An Evaluation on QuixBugs. In: Proceedings of the Third International Workshop on Automated Program Repair. p. 69–75. APR ’22, Association for Computing Machinery, New York, NY, USA (2022)
  * [52] Prensky, M.: Programming: The New Literacy. Edutopia magazine (2008)
  * [53] Radford, A., Kim, J.W., Xu, T., Brockman, G., McLeavey, C., Sutskever, I.: Robust Speech Recognition via Large-Scale Weak Supervision. In: ICML. pp. 28492–28518. PMLR (2023)
  * [54] Ringfort-Felner, R., Laschke, M., Sadeghian, S., Hassenzahl, M.: Kiro: A Design Fiction to Explore Social Conversation with Voice Assistants. Proceedings of the ACM on Human-Computer Interaction 6(GROUP), 1–21 (2022)
  * [55] Ross, S.I., Martinez, F., Houde, S., Muller, M., Weisz, J.D.: The Programmer’s Assistant: Conversational Interaction with a Large Language Model for Software Development. In: IUI. pp. 491–514 (2023)
  * [56] Sax, L.J., Lehman, K.J., Zavala, C.: Examining the Enrollment Growth: Non-CS Majors in CS1 Courses. In: SIGCSE TS. pp. 513–518 (2017)
  * [57] Sobania, D., Briesch, M., Rothlauf, F.: Choose Your Programming Copilot: A Comparison of the Program Synthesis Performance of GitHub Copilot and Genetic Programming. In: Proceedings of the genetic and evolutionary computation conference. pp. 1019–1027 (2022)
  * [58] Solanki, S.M., Xu, D.: Looking Beyond Academic Performance: The Influence of Instructor Gender on Student Motivation in STEM Fields. American Educational Research Journal 55(4), 801–835 (2018)
  * [59] Soloway, E., Spohrer, J.C.: Studying the Novice Programmer. Psychology Press (2013)
  * [60] Stefik, A., Siebert, S.: An Empirical Investigation into Programming Language Syntax. ACM Transactions on Computing Education (TOCE) 13(4), 1–40 (2013)
  * [61] Sterling, B.: Cover Story Design fiction. interactions 16(3), 20–24 (2009)
  * [62] Virkki, O.T.: Performance and Attrition in Information Technology Studies; A Survey of Students’ Viewpoints. In: EDUCON. pp. 1–9 (2023). https://doi.org/10.1109/EDUCON54358.2023.10125231
  * [63] Wessel, M., Abdellatif, A., Wiese, I., Conte, T., Shihab, E., Gerosa, M.A., Steinmacher, I.: Bots for Pull Requests: The Good, the Bad, and the Promising. In: ICSE. vol. 26, p. 16. ACM/IEEE (2022)