Date of publication ?? ??, ????, date of current version ?? ??, ????.
??.????/???.????.???

This work is supported by JST COI-NEXT (JPMJPF2221) and JST SPRING
(JPMJSP2123).

Corresponding author: Yikai Mao (email<EMAIL_ADDRESS>
# Q-gen: A Parameterized Quantum Circuit Generator

YIKAI MAO1  SHASWOT SHRESTHAMALI2, AND MASAAKI KONDO3  Graduate School of
Science and Technology, Keio University, Yokohama, Kanagawa 223-8522, Japan.
Graduate School of Information Science and Electrical Engineering, Kyushu
University, Nishi-ku, Fukuoka 819-0395, Japan.  RIKEN Center for Computational
Science, Kobe, Hyogo 650-0047, Japan.

###### Abstract

Unlike most classical algorithms that take an input and give the solution
directly as an output, quantum algorithms produce a quantum circuit that works
as an indirect solution to computationally hard problems. In the full quantum
computing workflow, most data processing remains in the classical domain
except for running the quantum circuit in the quantum processor. This leaves
massive opportunities for classical automation and optimization toward future
utilization of quantum computing. We kickstart the first step in this
direction by introducing Q-gen, a high-level, parameterized quantum circuit
generator incorporating 15 realistic quantum algorithms. Each customized
generation function comes with algorithm-specific parameters beyond the number
of qubits, providing a large generation volume with high circuit variability.
To demonstrate the functionality of Q-gen, we organize the algorithms into 5
hierarchical systems and generate a quantum circuit dataset accompanied by
their measurement histograms and state vectors. This dataset enables
researchers to statistically analyze the structure, complexity, and
performance of large-scale quantum circuits, or quickly train novel machine
learning models without worrying about the exponentially growing simulation
time. Q-gen is an open-source and multipurpose project that serves as the
entrance for users with a classical computer science background to dive into
the world of quantum computing.

###### Index Terms:

Quantum algorithm, Quantum circuit, Quantum simulation

=-15pt

##  I Introduction

The development of quantum mechanics has promoted the birth of quantum
computing. To simulate large quantum systems, a new type of computer that
operates based on the rules of quantum mechanics will inherently perform
better than any classical computer [1]. In the past few decades, the potential
of quantum computing has been demonstrated in many areas including condensed-
matter physics, high-energy physics, and chemistry [2]. Recently, the rapid
progress in quantum information theory has revealed that quantum computing can
be applied to a much broader field other than just performing simulations. One
of the most promising directions is using quantum computing to efficiently
solve classically intractable problems [3]. This is an exciting new area for
many computer science researchers. However, they still face a steep learning
curve, mostly because the principles used for quantum computation are
fundamentally different compared to classical computing.

The introduction of quantum computing to the classical computing community has
been disruptive. The vast majority of literature on quantum computing comes
from either mathematics or physics background, and practical applications from
quantum computers are still not feasible due to heavy noise and limited qubit
count. Although quantum computing research is still mostly theoretical, the
recent development of NISQ computing has proved that classical computing has
great potential to help utilize quantum computers in their current state. Even
in the post-NISQ era when large-scale fault-tolerant quantum processors are
realized, the probabilistic nature of quantum measurements and the pre/post-
processing involved in most quantum algorithms will still require support from
classical computers [4].

[t](topskip=0pt, botskip=0pt, midskip=0pt)[width=0.99]images/workflow.png A
typical workflow of circuit model quantum computing. The classical system
takes the computing problem and data from the user to construct a quantum
circuit. The circuit is then transpiled into low-level representation to be
executed on the quantum hardware. This work is aimed at automating the quantum
circuit generation step.

Figure I illustrates a typical circuit model quantum computing workflow, which
shows that the majority of computing tasks are performed in the classical
domain. We envision that a complete quantum computing process will always
involve some classical components, so classical design methods and computing
tools are indispensable in accelerating the development of quantum computing.
For example, While the current quantum hardware is still catching up on
reducing noise, we can improve the high-level circuit to use fewer gates or
find better transpilation logic to minimize the qubit count. We can also
investigate different routing/placement policies to more efficiently utilize
the existing qubit connections, and deploy error-mitigation algorithms to
further reduce error rate. All these research topics call for a large supply
of practical quantum circuits to help with testing and evaluation. However,
quickly obtaining various quantum circuits is still not a straightforward
task.

This work introduces Q-gen, a quick and efficient tool to create high-level,
realistic quantum circuits. For computer science researchers with a limited
background in quantum physics, Q-gen removes the knowledge barrier and enables
a rapid workflow from problem description to the resultant quantum circuit.
Q-gen includes 15 well-known quantum algorithms targeted for different
computing problems and offers a modular, parameterized generation process. In
addition to specifying the number of qubits of the circuit, Q-gen also
provides algorithm-specific generation parameters for more variability, making
it possible to produce many circuits with different structures that belong to
the same algorithm. The circuits are generated as Qiskit [5] circuit objects,
which can be modified and investigated using the native tools from the Qiskit
library. This high-level representation offers great portability as it can be
either saved directly as a .qpy file or easily translated into other lower-
level descriptions like openQASM [6].

To demonstrate the generation capability of Q-gen, We present the Q-gen
quantum circuit dataset consisting of 454 circuits. These circuits are
produced with various generation parameters from all 15 available algorithms,
ranging from shallow circuits with no CNOT gates to deep circuits with more
than 50,000 CNOT gates. Many research projects involve analyzing the output of
a quantum circuit, but simulating large circuits can easily cost hours to
days. To remove this time overhead for researchers, we also provide ready-to-
use simulation results in our dataset as measurement counts and state vectors.
Based on the statistics of the Q-gen circuit dataset and the analysis of the
simulation result, we organized the quantum algorithms into 5 hierarchical
systems with intuitive algorithm complexity ratings, offering a systematic way
to quickly understand the origin and application of quantum algorithms.

The contributions of this work include:

  * •

A quantum circuit generator based on Qiskit that supports 15 practical quantum
algorithms, offering high variability with algorithm-specific generation
parameters.

  * •

A high-level quantum circuit dataset containing large-scale quantum circuits
and their simulation result, either as measurement counts or state vectors.

  * •

A organized quantum algorithm system explaining their origin and connections,
offering a systematic understanding for new quantum computing researchers.

  * •

A heuristic analysis of the Q-gen quantum circuit dataset, presents the idea
of algorithm complexity categorized by their applications.

  * •

Open-sourced publication for better community collaboration and future
upgrades.

The remainder of the paper is structured as follows: Section II gives the
background and prior research related to quantum circuit generation and
optimization. Section III introduces all the available algorithms in Q-gen and
explains the generation parameters. Section IV explains the design philosophy
of the Q-gen algorithm system and presents the analysis of the Q-gen circuit
dataset. We summarize this work in section V.

##  II Background & related works

###  II-A Circuit Model Quantum Computing

The quantum circuit computing model is analogous to classical digital
computing, where computations are performed using a sequence of logic gates.
In the quantum circuit model, quantum computations are carried out using
quantum gates, which are a series of unitary matrix operators that introduce a
state or phase transition on the qubit(s) it acts on. Qubits are the
fundamental units of quantum information, capable of existing in a
superposition of states and entangling with others. These properties enable
quantum computers to solve certain problems exponentially faster than
classical computers.

In a typical circuit model quantum computing workflow, the quantum algorithm
is described using a high-level quantum circuit, and then circuit
transpilation compiles the circuit into low-level hardware-specific
instructions [7] for execution. In this process, the circuits are optimized to
reduce extra SWAP gates [8, 9], and various policies [10, 11, 12] are applied
to search for the best placement of the qubits on the quantum processor.
Additionally, software error mitigation [13, 14] and hardware error correction
[15, 16] techniques are developed to reduce the negative effect of decoherence
and communication noise.

###  II-B Quantum Circuit Generation and Dataset

Several open-source frameworks exist to help automate or assist in creating
quantum circuits. Qiskit [5], Cirq [17], and Braket [18] are three major
quantum computing frameworks that provide pre-built components and templates
for generating higher-level quantum algorithms. All the frameworks also
support the OpenQASM [6] representation for lower-level representation of
quantum circuits.

Currently, we believe that no projects are specifically targeted for high-
level quantum circuit generation, but many works focused on quantum
benchmarking usually include some low-level circuit dataset or a lightweight
circuit generator with limited functionality. The SupermarQ [19] benchmark
suite includes 8 application circuits and a circuit generator parameterized by
the number of qubits. The QASMBench [20] benchmark suite provides more than 50
openQASM implementations of various scales of quantum circuits in different
qubit settings. The Application-Oriented Benchmarks [21] offer 11 algorithms
categorized into 3 groups with a specialized generator for creating random
benchmark circuits.

###  II-C AI for Quantum Computing

Artificial Intelligence (AI) has experienced explosive development since the
mid-2010s. In addition to the classical optimization methods mentioned in
section II-A, there is a growing interest in using AI to help accelerate the
development of quantum computing. This also gives a strong motivation for our
work because machine learning models require a large number of quantum
circuits with high variability for efficient training.

For circuit optimization, there are works on using Large Language Models (LLM)
to design better quantum circuits [22] and using Transformers to simplify CNOT
circuits [23]. Deep reinforcement learning techniques are also explored to
minimize the number of T gates [24]. Many works proposed different machine
learning models for predicting the output fidelity of quantum circuits [25,
26, 27, 28, 29], which can be used for finding better layout and improve CNOT
routing. Works that have the potential for AI integration can also benefit
from a large supply of quantum circuits. One example is circuit knitting, a
technique of cutting the full circuits into smaller pieces for more efficient
execution [30, 31, 32].

[t](topskip=0pt, botskip=0pt, midskip=0pt)[width=0.95]images/alg_group_0.png
Q-gen quantum circuit dataset statistics and example circuit of the Deutsch-
Jozsa algorithm, the Bernstein-Vazirani algorithm, and Simon’s algorithm.

##  III Q-gen: Algorithm Design & Analysis

In this section, we introduce the quantum algorithms included in Q-gen. We
explain the significance of the algorithms, the Q-gen implementation with the
available generation parameters, and the potential applications. Each
algorithm is accompanied by a circuit complexity visualization consisting of
gate statistics and circuit size data, controlled by the algorithm-specific
problem size parameter. The pictured example circuit is generated by Q-gen
using the simplest available generation parameters.

###  III-A Deutsch-Jozsa Algorithm

The Deutsch-Jozsa algorithm [33] determines whether a special boolean function
$f$ is constant or balanced: a constant $f$ will always output all 0 or 1
regardless of the input, and a balanced $f$ will always output 0 for half of
the input and 1 for the other half. Classically, at least two queries to $f$
are required to find the answer, but the quantum version of this algorithm
only requires one query.

Q-gen can generate the oracle with both types of boolean functions, and the
oracle width is decided by the problem size parameter. The constant oracle is
a very simple oracle that only applies X gate to the output qubit, the
balanced oracle adds more circuit complexity by creating entanglement with
CNOT gates. Intuitively, as the problem size grows, the depth of the generated
circuit remains constant for the constant oracle, and the number of single-
qubit gates grows linearly, shown in figure II-C. If the oracle is balanced,
the depth and number of CNOT gates both grow linearly.

This algorithm is useful for generating simple circuits (no CNOT gates) with
constant depth but growing width. The only other algorithm in Q-gen that has a
similar circuit complexity pattern is the quantum key distribution algorithm,
but its number of single-qubit gates and measurements is doubled.

###  III-B Bernstein-Vazirani Algorithm

The Bernstein-Vazirani algorithm [34] solves problems similar to but harder
than the Deutsch-Jozsa problem. The hidden function in this algorithm returns
0 or 1 based on the bitwise product of the input string with a hidden “secret”
string $s$, the goal is to find $s$ with as few queries to the oracle as
possible. The best classical solution must query every input bit of $f$. In
contrast, the quantum version of this algorithm only requires one query.

Q-gen can generate the Bernstein-Vazirani oracle randomly or based on a binary
string, with its width controlled by problem size. The oracle places the
control of the CNOT gate on the input qubit if $s=1$ and leaves the qubit
untouched if $s=0$, the target of all CNOT gates are placed on the additional
phase-kickback qubit. The growth pattern of the Bernstein-Vazirani algorithm
is similar to the Deutsch-Jozsa algorithm, but as problem size increases, the
depth and number of CNOT gates all grow linearly at a higher rate.

This algorithm is good for generating elementary quantum circuits with some
entanglement. Also, the output of the Bernstein-Vazirani circuit is easily
verifiable without any post-processing, which makes it a good candidate for
quantum benchmarking.

###  III-C Simon’s Algorithm

Simon’s algorithm [35] has proved that quantum computers can offer exponential
speed-up over their classical counterparts. The oracle function $f$ in Simon’s
problem can be one-to-one or two-to-one according to a secret string $s$.
Similar to the Deutsch-Jozsa algorithm and the Bernstein-Vazirani algorithm,
we want to determine the type of $f$ as fast as possible. While the best
classical solution requires $O(\sqrt{2^{n}})$ queries, the quantum algorithm
only requires $O(n)$ queries [36], achieving exponential speed-up.

The circuit structure of Simon’s algorithm is special in terms of circuit
width. Although problem size is still defined as the oracle width, the
generated circuit will have a qubit count that doubles the number of problem
size. Upon measurements, the result will be multiple guesses related to the
secret string $s$, and $s$ can be revealed with some moderate post-processing.
Simon’s algorithm requires more CNOT gates than the other two query algorithms
in Q-gen, and the growth rate for the number of CNOT gates is approximately
2$\times$ of circuit depth, as shown in figure II-C.

Simon’s algorithm has the highest circuit complexity compared with the
Deutsch-Jozsa algorithm and the Bernstrin-Vazirani algorithm, considering
their simulation time and the number of CNOT gates at the same problem size.
Since it requires multiple shots and post-processing to find the correct
answer, Simon’s algorithm is good for testing the full quantum$+$classical
hybrid computing workflow.

###  III-D Quantum Fourier Transform

Quantum Fourier transform (QFT) [37] is the quantum implementation of the
classical Discrete Fourier Transform (DFT). To perform DFT on $2^{n}$
elements, classical algorithms like the Fast Fourier Transform (FFT) require
$O(n2^{n})$ operations. QFT only needs $O(n^{2})$ operations, which is
exponentially fewer than the classical algorithms [3]. Note that QFT does not
directly solve any specific problems, if the qubits are measured in the
computational basis, the result will appear random as they have been
transferred to the Fourier basis.

Q-gen takes problem size as the circuit width and generates the barebone QFT
subroutine. Although this circuit can be directly integrated into other
higher-level algorithms, it is not directly verifiable. Q-gen provides three
generation parameters that make verification possible: the qubits can be
initialized in the Fourier basis using an integer input, and the QFT
subroutine can be inverted to transform the qubits into the computational
basis. By measuring the qubits, the result will be the integer number used for
initialization. While QFT’s circuit complexity growth pattern is exponential,
as shown in figure III-D, it is still a very efficient implementation since
the depth only reaches around 4,000 when problem size is 47 qubits.

QFT is the building block for many practical quantum algorithms, so reducing
its circuit complexity and at the same time increasing its accuracy is an
important research topic. For instance, the approximate QFT algorithm can
ignore phase rotations below a certain threshold and still yield the correct
result with acceptable error. Q-gen’s parameterized generation offers a
quantitative approach to quickly analyze the behavior of various QFT circuits.

[t](topskip=0pt, botskip=0pt, midskip=0pt)[width=0.95]images/alg_group_1.png
Q-gen quantum circuit dataset statistics and example circuit of quantum
Fourier transform (QFT), quantum phase estimation (QPE), and Shor’s algorithm.

###  III-E Quantum Phase Estimation

Quantum phase estimation (QPE) [38] is one of the key applications of QFT.
This algorithm uses phase-kickback and inverse-QFT to estimate the
phase/eigenvalue of any unitary operator $U=e^{2\pi i\theta}$. The phase angle
$\theta$ is recorded in the counting qubits by the iterative controlled-U
gates applied on the eigenstate qubit. With $n$ counting qubits and the
measurement result equal to $x$, $\theta$ can be estimated as $\theta\approx
x/2^{n}$.

The QPE circuits from Q-gen have one eigenstate qubit for $U$ to act on, and
$n$ counting qubits, controlled by problem size. The number of counting qubits
directly affects the estimation accuracy of the circuit, when $\theta$ has a
denominator equal to $2^{n}$, it is possible to retrieve the exact angle of
$\theta$. Due to the high implementation cost of the iterative controlled-U
gates, the complexity of QPE circuits grows exponentially, reaching a depth
more than $5.0\times 10^{5}$ at problem size = 17. This causes other QPE-based
algorithms to have an even higher gate count, like the quantum walk search
algorithm.

QPE has many practical applications because some classically hard problems can
be condensed to phase estimation, the most famous examples include period-
finding and prime factorization. However, it is still hard to implement QPE on
current NISQ hardware due to its high circuit complexity. Although we can
reduce the number of counting qubits, it also causes the estimation accuracy
to drop. Q-gen can generate a large sample of QFT circuits to form a baseline
of estimation accuracy, which can then be used to study the trade-off between
reduced gate count and loss of accuracy.

###  III-F Shor’s Algorithm

Shor’s algorithm [39] can factor any large number $N$ in polynomial time,
better than every known classical algorithm. Under the hood, the core problem
that contributes to this quantum speedup is the period-finding problem. If the
period $r$ of the modular exponential function $f(x)=a^{x}modN$ can be found
in polynomial time, the factor(s) of $N$ can also be found in polynomial time.
Shor’s algorithm uses QPE to accelerate the period-finding process, the
subsequent search for factor(s) can be done efficiently using classical
algorithms.

Shor’s algorithm is a quantum-classical hybrid algorithm that utilizes
classical pre-processing to return a result before the QPE subroutine if $N$
is simple. To ensure the algorithm reaches the quantum part, $N$ has to be
reasonably hard to factor. Specifically for Shor’s algorithm, $N$ has to be
odd and not formed by $m^{n}$ for $m\geq 1$ and $n\geq 2$. Additionally, a
random guess of $a$ is required to kick-start the modular exponential
function, and $a$ must be a coprime of $N$ [3]. Q-gen automatically generates
the suitable $a$ and provides a list of $N$ (as problem size, up to 123) ready
to use for the quantum circuit. The main difficulty in Shor’s algorithm is the
quantum implementation of the modular exponential function, many customized
implementations exist focusing on minimizing the gate count or using a
specialized basis gate set [40, 41]. Q-gen implements a relatively efficient
modular exponential circuit using $2n+3$ qubits with $n$ equal to the bit-
length of $N$ [42, 43]. Most importantly, this implementation is general
regardless of $N$, ideal for Q-gen’s parameterized generation process.

Like most quantum algorithms, Shor’s algorithm only displays quantum advantage
over classical algorithms when the problem size is sufficiently large [44].
Although the ability to factor large prime numbers in polynomial time
potentially breaks the RSA cryptosystem, it is still unclear whether this can
be realized on a practical quantum computer in the foreseeable future. As of
2023, the largest factored RSA number has 829 bits (RSA-250) [45]. A quick
analysis using Q-gen shows that factoring the same number using a quantum
computer requires at least 1,661 qubits, excluding the auxiliary qubits.

[t](topskip=0pt, botskip=0pt, midskip=0pt)[width=0.95]images/alg_group_2.png
Q-gen quantum circuit dataset statistics and example circuit of Grover’s
algorithm, quantum counting, and quantum walk algorithm.

###  III-G Grover’s Algorithm

Grover’s algorithm [46] uses the Grover oracle $G$ and Diffusion operator $D$
to accelerate search problems. $G$ contains logical computations that mark the
target states with a negative phase, and $D$ then amplifies the measurement
probability of the marked states while simultaneously reducing the probability
of other states. For an unstructured database with $N$ items, Grover’s
algorithm can find all $M$ targets after approximately $\sqrt{N/M}$ Grover
iterations ($G+D$), providing a quadratic speedup over the classical
algorithms.

Q-gen can automatically generate $G$ based on problem size with the optimal
$M$ that only requires 1 Grover iteration. The target state in $G$ can also be
specified as an input string. Q-gen will append the appropriate number of
Grover iterations to the circuit, or take this number as another input. The
width of Grover’s circuit always equals the number of measurement gates and
they both grow linearly, but its circuit complexity grows exponentially as the
search space increases. Noticeably, compared with the quantum counting
algorithm, the number of CNOT gates grows faster than the number of single-
qubit gates, as shown in figure III-F.

Q-gen offers a quick way to statistically and empirically analyze the
performance of Grover’s algorithm, especially when the search space is large.
The parameterized circuit generation also enables an in-depth investigation of
the algorithm. For example, testing how different numbers of Grover iterations
affect result accuracy.

###  III-H Quantum Counting

The quantum counting algorithm [47] can estimate the number of solutions $M$
inside $N$ items, it is a combination of Grover’s algorithm and quantum
Fourier transformation (QFT). This algorithm can be seen as a prerequisite for
Grover’s algorithm since Grover’s algorithm requires $M$ to calculate the
correct number of iterations. It can also determine whether a solution even
exists inside $N$ items, which can accelerate certain NP-complete problems
like the Hamiltonian Cycle problem [3].

There are two groups of qubits inside the quantum counting algorithm: the
searching qubits iterate over the search space $N$, and they use controlled
Grover’s operator to mark $M$ on the counting qubits. The default setting of
Q-gen takes problem size as the number of counting qubits and assigns an equal
number of searching qubits to ensure optimal search results. The number of
solutions $M$ can be randomly generated or specified. Under the default
setting, as problem size increases, the width of the generated circuits grows
faster than the number of measurement gates. Compared with Grover’s algorithm,
The number of single-qubit gates grows faster than the number of CNOT gates.

Q-gen’s generation settings can be easily changed to investigate the
efficiency and accuracy of quantum counting under different problem spaces.
More importantly, this algorithm is another great candidate for benchmarking
the quantum$+$classical hybrid computing workflow, since it contains two
famous quantum subroutines: Grover’s operator and inverse-QFT, plus moderate
classical post-processing.

###  III-I Quantum Walk Algorithm

Quantum walk [48] is the quantum version of the random walk search algorithm.
On each walking step, the “walker” enters superposition to search all the
nodes on a graph simultaneously. For a graph with $N$ nodes and has $M$
targets, approximately $1/\sqrt{|M|/N}$ iterations are required to find all
targets [49]. This is another quantum search algorithm that provides a
quadratic speedup.

Q-gen implements the coined quantum walk, which uses a coin to direct how the
“walker” moves. Specifically, Q-gen uses the Grover coin, equivalent to the
Diffusion operator $D$ from Grover’s algorithm. Each iteration contains a
phase oracle that marks the target states, followed by quantum phase
estimation using the coined walk steps. Q-gen takes problem size as the width
of the coin, then automatically determines the width of the node qubits, and
the number of counting qubits for phase estimation. Due to the extremely high
gate cost of the coined walk steps, under the default setting, a 3-qubit coin
will generate a circuit with more than $1.0\times 10^{6}$ CNOT gates and more
than $1.5\times 10^{6}$ single-qubit gates.

Although this is a resource-intensive algorithm, many parameters are still
available in Q-gen to simplify its circuit structure. The number of counting
qubits for phase estimation can be reduced, or the width of the node qubits
can be set smaller. The number of iterations can also be specified,
potentially lowering the search accuracy.

[t](topskip=0pt, botskip=0pt, midskip=0pt)[width=0.95]images/alg_group_3.png
Q-gen quantum circuit dataset statistics and example circuit of quantum key
distribution, superdense coding, and quantum teleportation.

###  III-J Quantum Key Distribution

Quantum key distribution [50] is a secure quantum communication protocol based
on one primary quantum principle: measurement collapses superposition. Suppose
a sender prepares a qubit in a specific basis and sends it through a quantum
communication channel. In that case, the receiver can retrieve the same
information by measuring the qubit in the same basis. However, if the qubit is
measured in a different basis before reaching the receiver, the qubit
collapses prematurely and the receiver will get a random result.

Q-gen generates the full quantum circuit simulating the key distribution
process. The problem size controls the qubit width of the circuit, equivalent
to the bit width of the key. The interception parameter controls whether an
“attacker” will be inserted before the final measurement. This parameter
causes the circuit to have mid-circuit measurements, which is the only
occurrence among Q-gen’s algorithms. Q-gen can also simulate the circuit and
output the information measured at each stage, including if the “attacker” has
been detected. The generated circuits only contain single-qubit gates with a
linear growth pattern. The depth has two fixed variations depending on whether
interception is true.

This key distribution protocol is not designed to be risk-free. For example,
if the “attacker” inadvertently picked the same measurement basis as the
sender, the interception will go undetected. However, adding more qubits to
the key can significantly lower this risk. Q-gen’s generation parameters
provide a quick method to analyze the quantum circuit’s complexity under
different security conditions.

###  III-K Superdense Coding

Superdense coding [51] is a quantum communication protocol that encodes 2 bits
of classical information using 1 qubit. This protocol requires the sender and
receiver to share a pair of entangled qubits before the transmission starts,
usually prepared by a third party. The sender can pick from 4 quantum gates to
apply on the qubit, corresponding to 4 possible binary numbers using 2
classical bits. After the sender receives this qubit, the message can be
decoded by disentangling the qubit pair. Superdense coding is also secure, as
the entanglement will be destroyed if any qubit is prematurely measured before
reaching the receiver.

Q-gen generates the three steps of superdense coding: entangling, encoding,
and disentangling. The problem size controls the width of the circuit, equal
to the number of qubits used for transmission. The number of CNOT gates grows
linearly alongside the depth of the circuit. The number of qubits to encode,
and the single-qubit gates used for each encoding, can all be specified or
randomly generated.

The superdense coding circuits are highly structured and easy to scale up.
This makes it a great candidate for benchmarking the entanglement ability, and
the measurement fidelity of the quantum hardware.

[t](topskip=0pt, botskip=0pt, midskip=0pt)[width=0.95]images/alg_group_4.png
Q-gen quantum circuit dataset statistics and example circuit of the quantum
approximate optimization algorithm (QAOA), the variational quantum eigensolver
(VQE), and the variational quantum classifier (VQC).

###  III-L Quantum Teleportation

Quantum teleportation [52] recreates the sender’s qubit on the receiver’s side
using a pair of entangled qubits and classical bits. The sender’s qubit is
processed with one of the qubits from the entangled pair, and then measured to
obtain a 2-bit classical data. This data is transferred to the receiver
through a classical channel so the receiver can reconstruct the sender’s qubit
on top of the other qubit from the entangled pair. This protocol can be seen
as the opposite of superdense coding.

The minimal teleportation circuit in Q-gen involves 3 qubits. The state to be
teleported is initialized on $q_{0}$, the entangled pair is created on $q_{1}$
and $q_{2}$. After the deferred measurement on $q_{0}$ and $q_{1}$, the
original state is recreated on $q_{2}$. An inverse-initializer is then placed
on $q_{2}$, if the state is successfully teleported, it should inverse the
qubit back to $\ket{0}$. The problem size defines how many sets of
teleportation circuits to create, thus the generated circuit is analogous to a
classical parallel communication bus. The number of CNOT and single-qubit
gates follow a linear growth pattern, and the circuit’s depth is always fixed,
as shown in figure III-I

The quantum teleportation algorithm in Q-gen is easily verifiable because the
ideal measurement should always be all $\ket{0}$. Additionally, because every
set of teleportation circuits is physically isolated, this algorithm can
potentially detect crosstalk errors between different regions on a quantum
processor.

###  III-M Quantum Approximate Optimization Algorithm

The quantum approximate optimization algorithm (QAOA) [53] can approximate the
solution of the combinatorial optimization problem. For complex optimization
problems like MaxCut and Max-kXOR, QAOA gives higher quality solutions and
takes less time compared to the classical algorithms [54]. The cost function
from the combinatorial optimization problem is encoded into a quantum circuit
called variational form, then the expectation value can be measured repeatedly
to optimize the parameters of the cost function, ultimately converging to the
solution.

The QAOA circuit in Q-gen is based on the popular MaxCut problem, which tries
to partition a graph so that the number of edges between the two sets of nodes
is maximum. Q-gen generates the variational form based on the input graph and
randomly initializes all the parameters. The number of nodes in the graph is
defined by problem size, and each edge in the graph is translated to an Rzz
gate which decomposes into two CNOT gates and one Rz Gate. The depth and gate
counts of the QAOA circuit grow linearly with problem size. Even if the input
graph is fixed and the repetitions of the variational form increase, the
circuit’s depth still grows linearly, making QAOA a very efficient quantum
algorithm [53].

QAOA is a heuristic algorithm that gives better approximations after every
measurement and optimization cycle. Although it has the potential to
outperform certain classical algorithms, the implementation of QAOA still
heavily depends on the topology of the input graph. Q-gen can help researchers
quickly explore the circuit structure of QAOA under different input graphs.

[t](topskip=0pt, botskip=0pt, midskip=0pt)[width=0.9]images/alg_system.png The
complete Q-gen algorithm system illustration. The algorithm’s complexity
rating is designed to be compared vertically within its category instead of
horizontally across different algorithm categories. To help form the
connection between different algorithms, we include some generalized quantum
computing problems, indicated by the dashed circles. The connections are
gathered from various textbooks, lecture notes, and scientific papers. [3]
[55] [56] [57] [58]

###  III-N Variational Quantum Eigensolver

The variational quantum eigensolver (VQE) [59] can estimate the minimum
eigenvalue of a physical system represented by a matrix. Since the current
quantum hardware is not capable of running deep QPE algorithms, VQE is
designed as an alternative to efficiently approximate the solution with the
help of a classical optimizer [59]. VQE has many practical applications in the
chemistry and physics fields. For example, finding the ground state energy of
molecules [60].

The implementation of the variational forms for VQE depends on the specific
system being simulated. Q-gen fully utilizes Qiskit’s circuit library to give
a wide variety of generation parameters. The choices of the single-qubits
gates for the initial mixing unitary are generated according to the gates
parameter, the entanglement pattern (full, linear, etc.) is generated based on
the entanglement parameter, and the repeat parameter controls the number of
repetitions of the full variational form. Like the other variational
algorithms in Q-gen, the rotation angle of the gates can all be specified or
randomly generated.

Because the VQE algorithm in Q-gen is highly customizable, it enables explicit
control of the percentage of single-qubit and two-qubit gates, which produces
circuits with vastly different structures.

###  III-O Variational Quantum Classifier

The variational quantum classifier (VQC) is the quantum version of the
traditional neural network classifier [61]. By embedding classical data into a
quantum feature map circuit, a variational form can be trained on this feature
map just like training the classical neural networks. Machine learning is
another promising application of variational quantum algorithms. As the
datasets and models get larger, quantum computing can potentially make
training more efficient by utilizing the exponentially growing parameter space
represented by more entangled qubits.

Q-gen implements a common VQC circuit using the ZZFeatureMap and the
RealAmplitudes variational form [62]. The repetition number of the feature map
and the variational form can be separately controlled, depending on the
dataset embedding design and the number of trainable parameters. Additionally,
different feature maps provided by the Qiskit library can be easily swapped
in, like the PauliFeatureMap and ZFeatureMap [63]. Compared with QAOA and VQE
circuits in Q-gen, VQC circuits contain significantly more CNOT gates due to
the entanglement introduced by the feature map circuit, as shown in figure
III-K.

By taking advantage of the striking similarities between the connected neurons
and the entangled qubits, VQC demonstrates how quantum computing can augment
classical computing tasks. The circuit generation parameters in Q-gen can be
tuned similarly to the traditional configuration variables like learning rate
and batch size.

TABLE I: Q-gen Dataset Generation Summary

Q-gen Category | Algorithm |  | Available
---
Parameters
(* = problem size)
| Dataset
---
Parameters
| Mean
---
Generation
Time (ms)
| #Circuits
---
in Dataset
| Circuit
---
Width
Range
| Circuit Depth
---
Range
| #Single-Qubit
---
Gates
#CNOTs | #Measure
Quantum | Deutsch- | oracle width* | [2, $\infty$] | 1.72 | 44 | [3, 46] | [5, 5] | [7, 93] | N/A | [2, 45]
Query | Jozsa [33] | oracle type | constant oracle |  |  |  |  |  |  |
Algorithms |  | oracle content | random |  |  |  |  |  |  |
| Bernstein- | oracle width* | [2, $\infty$] | 2.17 | 44 | [3, 46] | [5, 22] | [6, 92] | [1, 18] | [2, 45]
| Vazirani [34] | oracle content | random |  |  |  |  |  |  |
| Simon’s [35] | oracle width* | [2, $\infty$] | 1.46 | 22 | [4, 46] | [5, 19] | [4, 46] | [3, 38] | [2, 23]
|  | oracle content | random |  |  |  |  |  |  |
Quantum | QFT [37] | input number bitwidth* | [2, $\infty$] | 555 | 45 | [2, 46] | [13, 4237] | [9, 3243] | [5, 2139] | [2, 46]
Fourier |  | input number initialization | random |  |  |  |  |  |  |
Transform |  | inverse? | True |  |  |  |  |  |  |
Algorithms |  | measurement? | True |  |  |  |  |  |  |
| QPE [38] | #counting qubits* | [2, $\infty$] | 6660 | 19 | [3, 21] | [24, 4195104] | [17, 3146336] | [11, 2097560] | [2, 20]
|  | input phase initialization | 1/8 |  |  |  |  |  |  |
| Shor’s [39] | N* | (Section IV-B) | 17350 | 20 | [18, 30] | [22194, 122970] | [32677, 205864] | [14532, 89187] | [8, 14]
|  | a | random |  |  |  |  |  |  |
Quantum | Grover’s [46] | oracle width* | [2, $\infty$] | 11.3 | 13 | [2, 14] | [14, 73455] | [12, 24647] | [3, 40954] | [2, 14]
Search |  | oracle content | random |  |  |  |  |  |  |
Algorithms |  | #solution | $2^{(\text{problem size}-2)}$ |  |  |  |  |  |  |
|  | #iteration | optimal |  |  |  |  |  |  |
| Quantum | #counting qubits* | [2, $\infty$] | 4680 | 6 | [4, 14] | [251, 569271] | [200, 450687] | [125, 325933] | [2, 7]
| Counting [47] | #searching qubits | = problem size |  |  |  |  |  |  |
|  | #solution | random |  |  |  |  |  |  |
| Quantum | #theta qubits | $2^{(\text{problem size})}$ | 4040 | 2 | [11, 20] | [26919, 2018376] | [21874, 1583025] | [15124, 1045248] | [4, 8]
| Walk [48] | #node qubits | $2^{(\text{problem size})}$ |  |  |  |  |  |  |
|  | #coin qubits* | [2, $\infty$] |  |  |  |  |  |  |
|  | #iterations | optimal |  |  |  |  |  |  |
|  | #solutions | $2^{(\text{problem size}-2)}$ |  |  |  |  |  |  |
Quantum | Quantum Key | circuit width* | [2, $\infty$] | 2.66 | 45 | [2, 46] | [5, 6] | [3, 87] | N/A | [4, 92]
Communication | Distribution [50] | interception? | True |  |  |  |  |  |  |
Algorithms | Superdence | circuit width* | [2, $\infty$] | 2.57 | 45 | [2, 46] | [6, 95] | [3, 30] | [2, 90] | [2, 46]
| Coding [51] | encoding size | half of the qubits |  |  |  |  |  |  |
| Quantum | #qubit to teleport* | [2, $\infty$] | 11.9 | 14 | [6, 45] | [14, 14] | [16, 120] | [8, 60] | [2, 15]
| Teleportation [52] | state to teleport | random |  |  |  |  |  |  |
Variational | QAOA [53] | #graph nodes* | [2, $\infty$] | 2.47 | 45 | [2, 46] | [6, 141] | [5, 138] | [2, 92] | [2, 46]
Quantum |  | type of graph | cyclic |  |  |  |  |  |  |
Algorithms |  | gate parameters | random |  |  |  |  |  |  |
| VQE [59] | circuit width* | [2, $\infty$] | 50.5 | 45 | [2, 46] | [6, 94] | [8, 184] | [1, 1035] | [2, 46]
|  | variational form repetition | 1 |  |  |  |  |  |  |
|  | variational form gate type | RY, RZ |  |  |  |  |  |  |
|  | type of entanglement | full entanglement |  |  |  |  |  |  |
|  | gate parameters | random |  |  |  |  |  |  |
| VQC [61] | circuit width* | [2, $\infty$] | 190 | 45 | [2, 46] | [9, 317] | [9, 1219] | [3, 2115] | [2, 46]
|  | feature map repetition | 1 |  |  |  |  |  |  |
|  | variational form repetition | 1 |  |  |  |  |  |  |
|  | gate parameters | random |  |  |  |  |  |  |

##  IV Q-Gen: Evaluation & The Circuit Dataset

In this section, we evaluate the characteristics and functionality of Q-gen by
putting it to work. We explain the architecture and design philosophy of our
quantum circuit dataset, which is generated by utilizing the plentiful
generation parameters provided by Q-gen.

###  IV-A Hierarchical Algorithm System

The most intuitive way to demonstrate Q-gen’s capability as a circuit
generator is to show that it can easily generate a large variety of quantum
circuits. We realized that organizing the generated circuits into a well-
structured dataset and providing open-source access can greatly assist studies
that require large-scale quantum circuit testing and benchmarking, or even
push new research directions on AI$+$Quantum.

However, the quantum algorithms provided by Q-gen have different structures
and targeted applications. A good implementation of Grover’s algorithm should
find the marked state in fewer iterations. In contrast, a good quantum key
distribution protocol should protect the message from the attacker with
minimum encryption overhead. The complex relationships between different
quantum algorithms affect how researchers evaluate and optimize the
performance of their novel projects. For example, a circuit optimization tool
aimed at reducing the number of CNOT gates should not pick the Deutsch-Jozsa
algorithm or the quantum key distribution algorithm for testing, due to their
low utilization rate of CNOT gates. For studies aimed at improving the QFT
algorithm, it is also valuable to test its performance on the QPE algorithm,
because it is a direct extension of the QFT algorithm.

Therefore, to facilitate understanding and effective use of all the available
algorithms in Q-gen, we summarize them into an organized system with 5
algorithm categories based on their theoretical origin, circuit structure, and
targeted application. The complete Q-gen algorithm system is visualized in
figure III-M, we also hope this figure can offer a clear and direct
introduction for new researchers to dive into quantum computing.

####  IV-A1 Quantum Query Algorithms

The quantum query algorithms include the Deutsch-Jozsa algorithm, the
Bernstein-Vazirani algorithm, and Simon’s algorithm. They try to query a
“black-box” function (oracle) to find its hidden information. The hidden
information of the oracle can be randomly generated based on problem size or
specified as a bitstring. Since most of the quantum computation happens inside
the oracle, the oracle’s complexity directly affects the generated circuit’s
complexity.

####  IV-A2 Quantum Fourier Transform Algorithms

The quantum Fourier transform algorithms include quantum Fourier transform
(QFT), quantum phase estimation (QPE), and Shor’s algorithm. Similar to the
classical Fourier transform where functions are transferred from the time
domain to the frequency domain, quantum Fourier transform (QFT) converts the
quantum states from the computational basis to the Fourier basis. They are
some of the most important algorithms in quantum computing, providing
fundamental building blocks for many other quantum applications.

####  IV-A3 Quantum Search Algorithms

The quantum search algorithms include Grover’s algorithm, quantum counting,
and quantum walk algorithm. The quantum search algorithms can accelerate
search problems on datasets with no predefined classical data structures. The
quantum search circuits still involve an oracle like the quantum query
algorithms, but this oracle represents the search space, followed by
additional operations according to specific algorithms. In general, as the
search space grows, the circuit complexity of the generated circuits grows
exponentially in terms of gate number/circuit depth.

####  IV-A4 Quantum Communication Algorithms

The quantum communication algorithms include quantum key distribution,
superdense coding, and quantum teleportation. The quantum communication
algorithms utilize different merits of quantum channels to securely and
rapidly transfer information. Q-gen generates the full quantum communication
process from sender to receiver. Because the message should remain protected
during the process, besides demonstrating the functionality of quantum
communication, the generated circuits can also be used to benchmark the
fidelity of the quantum hardware.

####  IV-A5 Variational Quantum Algorithms

The variational quantum algorithms include the quantum approximate
optimization algorithm (QAOA), the variational quantum eigensolver (VQE), and
the variational quantum classifier (VQC). Variational quantum algorithms
combine quantum computing with classical optimization. The quantum circuit is
constructed to solve for a specific ground state of a given system, and a
classical optimizer iteratively optimizes the angles of the rotation gates
involved in the circuit. Note that a variational quantum circuit is often
called a parametrized quantum circuit, which refers to the parameterized
quantum gates involved in the circuit. Q-gen’s parameterization refers to the
high-level generation parameters of a quantum algorithm.

[t](topskip=0pt, botskip=0pt,
midskip=0pt)[width=0.9]images/simulation_full.png Simulation times for the
Q-gen database circuits using either two Xeon Gold 6354 CPUs or the Nvidia
A100 GPU.

###  IV-B Quantum Circuit Dataset Design

The algorithms under one Q-gen category share similar characteristics, like
circuit structure and measurement output pattern. Given the high variability
of the available generation parameters, it is possible to generate some
outlier circuits that have unrealistic gate arrangements. Still, when creating
the Q-gen dataset, we try to keep the parameters reasonable so the generated
circuits are close to practical application circuits. The generation details
for each algorithm category are explained below:

  1. 1.

The quantum query circuits are relatively easy to generate in terms of average
generation time and circuit size. All the oracles in the three algorithms are
set to contain random output states, and the oracle of the Deutsch-Jozsa
algorithm is always set to be a constant oracle.

  2. 2.

The quantum Fourier transform circuits are significantly harder to generate.
The QFT circuits are generated as inverse-QFT and measurement gates to produce
verifiable histograms. The QPE circuits have fixed input initialization of
$\theta=\frac{1}{8}$, the same phase angle as the T gate. The input number of
QFT circuits and the initial guess ($a$) of Shor’s circuits are both randomly
generated.

  3. 3.

The quantum search circuits take the longest average time to generate in Q-gen
if normalized to the same circuit width. Due to the exponentially growing gate
count, it also produces the deepest circuits compared to other algorithm
categories. For Grover’s algorithm and the quantum walk algorithm, we specify
the number of solutions as $2^{(\text{{problem size}}-2)}$ so that the number
of iterations will always be 1. Although the number of solutions is fixed, the
individual solution state inside the oracle is still randomly picked. The
quantum counting circuits always generate the same number of counting qubits
and searching qubits according to problem size.

  4. 4.

The quantum communication circuits have the simplest generation parameters in
Q-gen. The quantum key distribution circuits contain interceptions from the
attacker, the superdense coding circuits encode half of the qubits, and the
quantum teleportation circuits randomly initialize the states to teleport.

  5. 5.

The variational quantum algorithms can produce circuits with vastly different
structures depending on the generation parameters. The QAOA circuits are
generated with cyclic input graph, and the variational form of the VQE
circuits is generated with RY/RZ gates and full entanglement. The repetition
number of the variational form for the VQE and VQC circuits is fixed to 1. For
all the circuits in this category, the rotation angles of the single-qubit
gates are randomly generated.

The minimum problem size is set to 2 for every algorithm (except Shor’s
algorithm) because most of them require at least 2 qubits, it is then
incremented by 1 for each generation step until the circuit gets too large for
generation or simulation. For Shor’s algorithm, its circuit structure is
decided by the input number to be factored. We generated Shor’s circuit with a
list of problem size from a subset of odd composite numbers, up to 123. Table
I summarizes the full generation details and the statistics of the Q-gen
quantum circuit dataset.

###  IV-C Algorithm Complexity Rating

We want to provide each circuit in the Q-gen dataset with its corresponding
noise-free output to form a straightforward input-output pair, either in
measurement count or state vector format. This enables researchers to utilize
the Q-gen dataset like any machine learning dataset without worrying about the
simulation overhead of large circuits, which can easily take hours to days.

For circuit simulation, we obtain the measurement count using the Qiskit Aer
simulator running on a rack server with two Xeon Gold 6354 processors and the
Nvidia A100 GPU. The simulation times for all the Q-gen dataset circuits are
plotted in figure IV-A5. For most algorithms, the simulation time difference
between GPU and CPU is negligible. However, the simulation of Shor’s algorithm
and quantum teleportation quickly ran out of memory on the CPU. The GPU can
significantly outperform the CPU on these two algorithms thanks to its 80GB
graphics memory. The state vector simulations are performed on the Qulacs
simulator due to its efficiency when running large quantum circuits. The
circuits are converted from Qiskit to Qulacs format with the Naniwa converter,
and the simulation results can be cross-verified with the state vector output
from the Aer simulator.

Another addition to complement the usability of the Q-gen quantum circuit
dataset is the algorithm complexity rating, denoted by the star
($\medwhitestar$) symbols in figure III-M. We define an algorithm’s complexity
based on its simulation time, generation time, and gate statistics. Note that
this rating should not be confused with the circuit complexity mentioned in
section III. A quantum circuit’s complexity can be quantified regardless of
its application, most commonly using the circuit depth. However, it is hard to
come up with a comprehensive and uniform metric to define the complexity of a
quantum algorithm across all the fields of quantum computing. Under the Q-gen
algorithm category system, the individual algorithms within the same category
have the same application and similar circuit structure, so we assign the
ratings independently for each algorithm category. This gives researchers a
clear hierarchical view of the complexity of the quantum algorithms, and helps
software developers quickly grasp the coding difficulty if they want to commit
new algorithms to the Q-gen algorithm system.

##  V Conclusion

In this work, We present the Q-gen quantum circuit generator to intuitively
and efficiently generate practical quantum circuits. We motivate this work by
showing that a comprehensive quantum circuit generator can accelerate the
advancement of current NISQ applications, and may become an integral part of
the future quantum computing workflow. Q-gen provides 15 practical quantum
algorithms with tailored generation parameters, offering a convenient tool for
researchers and developers with any background level to quickly start
interacting with quantum circuits. We demonstrate the functionality of Q-gen
by generating a large quantum circuit dataset utilizing all the available
generation parameters, and we evaluate the structure of the generated
circuits, showing a wide coverage of different circuit properties including
circuit size and gate counts. Based on the circuit dataset and its simulation
results, we further improve the usability of Q-gen by defining a hierarchical
quantum algorithm system, presenting a streamlined starting point for quantum
computing research.

##  VI Data & Code Availability

The Q-gen quantum circuit generator and the Q-gen quantum circuit dataset can
be accessed at github.com/yikaimao/Q_gen,
www.kaggle.com/datasets/ykmaoykmao/q-gen-quantum-circuit-dataset. We thank the
Qiskit community for sharing the algorithm implementations on the now
deprecated Qiskit Textbook[64]. Q-gen is an open-source project, the generated
circuits are experimental and should be used for research purposes only.

## References

  * [1] R. P. Feynman, “Simulating physics with computers,” _International Journal of Theoretical Physics_ , vol. 21, pp. 467–488, 1982. [Online]. Available: https://doi.org/10.1007/BF02650179
  * [2] I. M. Georgescu, S. Ashhab, and F. Nori, “Quantum simulation,” _Reviews of Modern Physics_ , vol. 86, no. 1, p. 153–185, Mar. 2014. [Online]. Available: http://dx.doi.org/10.1103/RevModPhys.86.153
  * [3] M. A. Nielsen and I. L. Chuang, _Quantum Computation and Quantum Information: 10th Anniversary Edition_. Cambridge University Press, 2010.
  * [4] J. Preskill, “Quantum computing in the nisq era and beyond,” _Quantum_ , vol. 2, p. 79, Aug. 2018. [Online]. Available: http://dx.doi.org/10.22331/q-2018-08-06-79
  * [5] A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross, B. R. Johnson, and J. M. Gambetta, “Quantum computing with qiskit,” 2024. [Online]. Available: https://arxiv.org/abs/2405.08810
  * [6] A. Cross, A. Javadi-Abhari, T. Alexander, N. De Beaudrap, L. S. Bishop, S. Heidel, C. A. Ryan, P. Sivarajah, J. Smolin, J. M. Gambetta, and B. R. Johnson, “Openqasm 3: A broader and deeper quantum assembly language,” _ACM Transactions on Quantum Computing_ , vol. 3, no. 3, p. 1–50, Sep. 2022. [Online]. Available: http://dx.doi.org/10.1145/3505636
  * [7] T. Häner, D. S. Steiger, K. Svore, and M. Troyer, “A software methodology for compiling quantum programs,” _Quantum Science and Technology_ , vol. 3, no. 2, p. 020501, Feb. 2018. [Online]. Available: http://dx.doi.org/10.1088/2058-9565/aaa5cc
  * [8] A. Hashim, R. Rines, V. Omole, R. K. Naik, J. M. Kreikebaum, D. I. Santiago, F. T. Chong, I. Siddiqi, and P. Gokhale, “Optimized fermionic swap networks with equivalent circuit averaging for qaoa,” 2021. [Online]. Available: https://arxiv.org/abs/2111.04572
  * [9] A. MATSUO, S. YAMASHITA, and D. J. EGGER, “A sat approach to the initial mapping problem in swap gate insertion for commuting gates,” _IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences_ , vol. E106.A, no. 11, p. 1424–1431, Nov. 2023. [Online]. Available: http://dx.doi.org/10.1587/transfun.2022EAP1159
  * [10] P. D. Nation and M. Treinish, “Suppressing quantum circuit errors due to system variability,” _PRX Quantum_ , vol. 4, no. 1, Mar. 2023. [Online]. Available: http://dx.doi.org/10.1103/PRXQuantum.4.010327
  * [11] S. S. Tannu and M. K. Qureshi, “A case for variability-aware policies for nisq-era quantum computers,” 2018. [Online]. Available: https://arxiv.org/abs/1805.10224
  * [12] G. Li, Y. Ding, and Y. Xie, “Tackling the qubit mapping problem for nisq-era quantum devices,” 2019. [Online]. Available: https://arxiv.org/abs/1809.02573
  * [13] Z. Cai, R. Babbush, S. C. Benjamin, S. Endo, W. J. Huggins, Y. Li, J. R. McClean, and T. E. O’Brien, “Quantum error mitigation,” _Reviews of Modern Physics_ , vol. 95, no. 4, Dec. 2023. [Online]. Available: http://dx.doi.org/10.1103/RevModPhys.95.045005
  * [14] P. S. Mundada, A. Barbosa, S. Maity, Y. Wang, T. Merkh, T. Stace, F. Nielson, A. R. Carvalho, M. Hush, M. J. Biercuk, and Y. Baum, “Experimental benchmarking of an automated deterministic error-suppression workflow for quantum algorithms,” _Physical Review Applied_ , vol. 20, no. 2, Aug. 2023. [Online]. Available: http://dx.doi.org/10.1103/PhysRevApplied.20.024034
  * [15] Y. Ueno, M. Kondo, M. Tanaka, Y. Suzuki, and Y. Tabuchi, “Qecool: On-line quantum error correction with a superconducting decoder for surface code,” in _2021 58th ACM/IEEE Design Automation Conference (DAC)_. IEEE, Dec. 2021. [Online]. Available: http://dx.doi.org/10.1109/DAC18074.2021.9586326
  * [16] ——, “Qulatis: A quantum error correction methodology toward lattice surgery,” in _2022 IEEE International Symposium on High-Performance Computer Architecture (HPCA)_ , 2022, pp. 274–287.
  * [17] various authors, “Cirq,” May 2024. [Online]. Available: https://doi.org/10.5281/zenodo.11398048
  * [18] Amazon Web Services, “Amazon Braket,” 2020. [Online]. Available: https://aws.amazon.com/braket/
  * [19] T. Tomesh, P. Gokhale, V. Omole, G. S. Ravi, K. N. Smith, J. Viszlai, X.-C. Wu, N. Hardavellas, M. R. Martonosi, and F. T. Chong, “Supermarq: A scalable quantum benchmark suite,” 2022. [Online]. Available: https://arxiv.org/abs/2202.11045
  * [20] A. Li, S. Stein, S. Krishnamoorthy, and J. Ang, “Qasmbench: A low-level qasm benchmark suite for nisq evaluation and simulation,” 2022. [Online]. Available: https://arxiv.org/abs/2005.13018
  * [21] T. Lubinski, S. Johri, P. Varosy, J. Coleman, L. Zhao, J. Necaise, C. H. Baldwin, K. Mayer, and T. Proctor, “Application-oriented performance benchmarks for quantum computing,” 2023. [Online]. Available: https://arxiv.org/abs/2110.03137
  * [22] Z. Liang, J. Cheng, R. Yang, H. Ren, Z. Song, D. Wu, X. Qian, T. Li, and Y. Shi, “Unleashing the potential of llms for quantum computing: A study in quantum architecture design,” 2023. [Online]. Available: https://arxiv.org/abs/2307.08191
  * [23] F. Charton, A. Krajenbrink, K. Meichanetzidis, and R. Yeung, “Teaching small transformers to rewrite ZX diagrams,” in _The 3rd Workshop on Mathematical Reasoning and AI at NeurIPS’23_ , 2023. [Online]. Available: https://openreview.net/forum?id=btQ7Bt1NLF
  * [24] F. J. R. Ruiz, T. Laakkonen, J. Bausch, M. Balog, M. Barekatain, F. J. H. Heras, A. Novikov, N. Fitzpatrick, B. Romera-Paredes, J. van de Wetering, A. Fawzi, K. Meichanetzidis, and P. Kohli, “Quantum circuit optimization with alphatensor,” 2024. [Online]. Available: https://arxiv.org/abs/2402.14396
  * [25] X. Zhang, M. Luo, Z. Wen, Q. Feng, S. Pang, W. Luo, and X. Zhou, “Direct fidelity estimation of quantum states using machine learning,” _Physical Review Letters_ , vol. 127, no. 13, Sep. 2021. [Online]. Available: http://dx.doi.org/10.1103/PhysRevLett.127.130503
  * [26] A. Vadali, R. Kshirsagar, P. Shyamsundar, and G. N. Perdue, “Quantum circuit fidelity estimation using machine learning,” _Quantum Machine Intelligence_ , vol. 6, no. 1, Dec. 2023. [Online]. Available: http://dx.doi.org/10.1007/s42484-023-00121-4
  * [27] Y. Mao, S. Shresthamali, and M. Kondo, “Quantum circuit fidelity improvement with long short-term memory networks,” 2023. [Online]. Available: https://arxiv.org/abs/2303.17523
  * [28] H. Wang, Z. Liang, J. Gu, Z. Li, Y. Ding, W. Jiang, Y. Shi, D. Z. Pan, F. T. Chong, and S. Han, “Torchquantum case study for robust quantum circuits,” in _Proceedings of the 41st IEEE/ACM International Conference on Computer-Aided Design_ , ser. ICCAD ’22. ACM, Oct. 2022. [Online]. Available: http://dx.doi.org/10.1145/3508352.3561118
  * [29] G. S. Hartnett, A. Barbosa, P. S. Mundada, M. Hush, M. J. Biercuk, and Y. Baum, “Learning to rank quantum circuits for hardware-optimized performance enhancement,” 2024. [Online]. Available: https://arxiv.org/abs/2404.06535
  * [30] G. Gentinetta, F. Metz, and G. Carleo, “Overhead-constrained circuit knitting for variational quantum dynamics,” _Quantum_ , vol. 8, p. 1296, Mar. 2024. [Online]. Available: http://dx.doi.org/10.22331/q-2024-03-21-1296
  * [31] C. Piveteau and D. Sutter, “Circuit knitting with classical communication,” _IEEE Transactions on Information Theory_ , vol. 70, no. 4, p. 2734–2745, Apr. 2024. [Online]. Available: http://dx.doi.org/10.1109/TIT.2023.3310797
  * [32] K. N. Smith, M. A. Perlin, P. Gokhale, P. Frederick, D. Owusu-Antwi, R. Rines, V. Omole, and F. T. Chong, “Clifford-based circuit cutting for quantum simulation,” 2023. [Online]. Available: https://arxiv.org/abs/2303.10788
  * [33] D. Deutsch and R. Jozsa, “Rapid solution of problems by quantum computation,” _Proc., Math. Phys. Sci._ , vol. 439, no. 1907, pp. 553–558, Dec. 1992.
  * [34] E. Bernstein and U. Vazirani, “Quantum complexity theory,” _SIAM J. Comput._ , vol. 26, no. 5, pp. 1411–1473, Oct. 1997.
  * [35] D. Simon, “On the power of quantum computation,” in _Proceedings 35th Annual Symposium on Foundations of Computer Science_ , 1994, pp. 116–123.
  * [36] G. Cai and D. Qiu, “Optimal separation in exact query complexities for simon’s problem,” 2017. [Online]. Available: https://arxiv.org/abs/1610.01920
  * [37] D. Coppersmith, “An approximate fourier transform useful in quantum factoring,” 2002. [Online]. Available: https://arxiv.org/abs/quant-ph/0201067
  * [38] A. Y. Kitaev, “Quantum measurements and the abelian stabilizer problem,” 1995. [Online]. Available: https://arxiv.org/abs/quant-ph/9511026
  * [39] P. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in _Proceedings 35th Annual Symposium on Foundations of Computer Science_ , 1994, pp. 124–134.
  * [40] M. Amico, Z. H. Saleem, and M. Kumph, “Experimental study of shor’s factoring algorithm using the ibm q experience,” _Physical Review A_ , vol. 100, no. 1, Jul. 2019. [Online]. Available: http://dx.doi.org/10.1103/PhysRevA.100.012305
  * [41] C. Zalka, “Fast versions of shor’s quantum factoring algorithm,” 1998. [Online]. Available: https://arxiv.org/abs/quant-ph/9806084
  * [42] S. Beauregard, “Circuit for shor’s algorithm using 2n+3 qubits,” 2003. [Online]. Available: https://arxiv.org/abs/quant-ph/0205095
  * [43] R. Maia and T. Leao, https://github.com/ttlion/ShorAlgQiskit, 2019.
  * [44] T. Hoefler, T. Haener, and M. Troyer, “Disentangling hype from practicality: On realistically achieving quantum advantage,” 2023. [Online]. Available: https://arxiv.org/abs/2307.00523
  * [45] “Factorization of rsa-250,” https://web.archive.org/web/20200228234716/https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2020-February/001166.html.
  * [46] L. K. Grover, “A fast quantum mechanical algorithm for database search,” 1996. [Online]. Available: https://arxiv.org/abs/quant-ph/9605043
  * [47] G. Brassard, P. HØyer, and A. Tapp, _Quantum counting_. Springer Berlin Heidelberg, 1998, p. 820–831. [Online]. Available: http://dx.doi.org/10.1007/BFb0055105
  * [48] R. Portugal, _Quantum walks and search algorithms_ , 2013th ed., ser. Quantum Science and Technology. New York, NY: Springer, Feb. 2013.
  * [49] R. de Wolf, “Quantum computing: Lecture notes (ch. 8.2),” 2023. [Online]. Available: https://arxiv.org/pdf/1907.09415
  * [50] C. H. Bennett and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing,” _Theoretical Computer Science_ , vol. 560, p. 7–11, Dec. 2014. [Online]. Available: http://dx.doi.org/10.1016/j.tcs.2014.05.025
  * [51] C. H. Bennett and S. J. Wiesner, “Communication via one- and two-particle operators on einstein-podolsky-rosen states,” _Phys. Rev. Lett._ , vol. 69, pp. 2881–2884, Nov 1992. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.69.2881
  * [52] C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters, “Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels,” _Phys. Rev. Lett._ , vol. 70, pp. 1895–1899, Mar 1993. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.70.1895
  * [53] E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,” 2014. [Online]. Available: https://arxiv.org/abs/1411.4028
  * [54] K. Blekos, D. Brand, A. Ceschini, C.-H. Chou, R.-H. Li, K. Pandya, and A. Summer, “A review on quantum approximate optimization algorithm and its variants,” _Physics Reports_ , vol. 1068, p. 1–66, Jun. 2024. [Online]. Available: http://dx.doi.org/10.1016/j.physrep.2024.03.002
  * [55] S. Aaronson, “Introduction to quantum information science lecture notes.” [Online]. Available: https://www.scottaaronson.com/qclec.pdf
  * [56] W. van Dam, S. Hallgren, and L. Ip, “Quantum algorithms for some hidden shift problems,” 2002. [Online]. Available: https://arxiv.org/abs/quant-ph/0211140
  * [57] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, “A variational eigenvalue solver on a photonic quantum processor,” _Nature Communications_ , vol. 5, no. 1, Jul. 2014. [Online]. Available: http://dx.doi.org/10.1038/ncomms5213
  * [58] O. Sattath, “Stephen wiesner, my quantum thoughts.” [Online]. Available: https://orsattath.wordpress.com/2021/08/14/stephen-wiesner/
  * [59] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, “A variational eigenvalue solver on a photonic quantum processor,” _Nature Communications_ , vol. 5, no. 1, Jul. 2014. [Online]. Available: http://dx.doi.org/10.1038/ncomms5213
  * [60] D. A. Fedorov, B. Peng, N. Govind, and Y. Alexeev, “Vqe method: A short survey and recent developments,” 2021. [Online]. Available: https://arxiv.org/abs/2103.08505
  * [61] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, “Quantum machine learning,” _Nature_ , vol. 549, no. 7671, p. 195–202, Sep. 2017. [Online]. Available: http://dx.doi.org/10.1038/nature23474
  * [62] “Qiskit machine learning.” [Online]. Available: https://github.com/qiskit-community/qiskit-machine-learning
  * [63] “Qiskit circuit library.” [Online]. Available: https://docs.quantum.ibm.com/api/qiskit/circuit_library
  * [64] various authors, “Qiskit textbook,” 2023. [Online]. Available: https://github.com/Qiskit/textbook

|  Yikai Mao is a Ph.D. student at Kondo Lab, from the Graduate School of
Science and Technology, Keio University. He received his bachelor’s degree in
computer engineering from the University of Florida in 2018, and his master’s
degree in electrical and computer engineering from the University of
California, Davis in 2021. His current research interests include quantum
computing, quantum-classical hybrid computing, and computer architecture.
---|---
|  Shaswot Shresthamali is a Research Associate Professor in the Department of
Advanced Information Technology at Kyushu University. He earned his doctorate
from The University of Tokyo in 2021 where his research focused on resource
management and scheduling in IoT nodes with Reinforcement Learning. He is
currently affiliated with the Cyber-Physical Computing laboratory at Kyushu
University. His research interests span the intersections of Machine Learning,
Novel Computing Architectures, and Quantum Computing. He is also a Visiting
Researcher at Keio University.
---|---
|  Masaaki Kondo received Ph.D in Engineering from the University of Tokyo in
2003. He is currently a professor of Faculty of Science and Technology, Keio
University, and also the team leader of next generation high performance
architecture research team in the RIKEN Center for Computational Science. His
research interests include computer architecture, high-performance computing,
quantum computer, and low-power LSI design.
---|---