Quark: A Gradient-Free Quantum Learning Framework for Classification Tasks
Authors: Zhihao Zhang
Zhuoming Chen
Heyang Huang
Zhihao Jia
Venue: Submitted to ICLR 2023 (2023)
Keywords: Quantum Computing
Deep Learning
Quantum Machine Learning

Abstract: As more practical and scalable quantum computers emerge, much attention has been focused on realizing quantum supremacy in machine learning. Existing quantum ML methods either (1) embed a classical model into a target Hamiltonian to enable quantum optimization or (2) represent a quantum model using variational quantum circuits and apply classical gradient-based optimization. The former method leverages the power of quantum optimization but only supports simple ML models, while the latter provides flexibility in model design but relies on gradient calculation, resulting in barren plateau (i.e., gradient vanishing) and frequent classical-quantum interactions. To address the limitations of existing quantum ML methods, we introduce Quark, a gradient-free quantum learning framework that optimizes quantum ML models using quantum optimization. Quark does not rely on gradient computation and therefore avoids barren plateau and frequent classical-quantum interactions. In addition, Quark can support more general ML models than prior quantum ML methods and achieves a dataset-size-independent optimization complexity. Theoretically, we prove that Quark can outperform classical gradient-based methods by reducing model query complexity for highly non-convex problems; empirically, evaluations on the Edge Detection and Tiny-MNIST tasks show that Quark can support complex ML models and significantly reduce the number of measurements needed for discovering near-optimal weights for these tasks.

Under review as a conference paper at ICLR 2023
QUARK: A GRADIENT-FREE QUANTUM LEARNING FRAMEWORK FOR CLASSIFICATION TASKS
Anonymous authors Paper under double-blind review
ABSTRACT
As more practical and scalable quantum computers emerge, much attention has been focused on realizing quantum supremacy in machine learning. Existing quantum ML methods either (1) embed classical model into target Hamil- tonian to enable quantum optimization or (2) represent a quantum model using variational quantum circuits and apply classical gradient-based optimization. The former method leverages the power of quantum optimization but only supports simple ML models, while the latter provides flexibility in model design but re- lies on gradient calculation, resulting in barren plateau (i.e., gradient vanishing) and frequent classical-quantumg interactions. To address the limitations of exist- ing quantum ML methods, we introduce Quark, a gradient-fiee quantum learn- ing framework that optimizes quantum ML models using quantum optimization. Quark does not rely on gradient computation and therefore avoids barren plateau and frequent classical-quantum interactions. In addition, Quark can support more general MI. models than prior quantum ML methods and achieves a dataset-size- independent optimization complexity. Theoretically, we prove that Quark can out- perform classical gradient-based methods by reducing model query complexity for highly non-convex problems; empirically, evaluations on the Edge Detection and Tiny-MNi -NIST tasks show that Quark support complex ML models and signif- icantly reduce the number of measurements needed for discovering near-optimal weights for these tasks.
INTRODUCTION
Quantum computing provides new computational paradigm to achieve exponential speedups over classical counterparts for various tasks, such as cryptography (Shor) 1994). scientific simu- lation (Tazhigulov et al. 2022). and data analytics (Arute et al. 2019). A key advantage of quantum computing is its ability to entangle multiple quantum bits, called qubits, allowing r qubits to encode -i-deennsio vector, while encoding this vector in classical computing requires 2n bits.
Inspired by this potential, recent work (Jaderberg et al.) 2022 Macaluso et al., 2020b; Torta et al, 2021 Kapoor et al. 2016 Bauer et al.) 2020 Farhi & Neven 201 8a Schuld et al. 2014 Cong al.
2019b) has focused on realizing quantum speedups over classical algorithms in the field of super- vised I learning. Existing quantum ML work can be divided into two categories: classical model with quantum optimization (CMQO) and quantum model with classical optimization (QMCO). First, CMQO methods embed a classical ML model jointly with the optimization problem into a tar- get Hamiltonian and optimize the model using quantum adiabatic evolution (QAE) (Finnila et al.
1994 or quantum approximate optimization algorithm (QAOA) (Farhi et al., 2014; Torta et al. 2021. As the transition between a classical model and the target Hamiltonian only applies to low- order polynomial activations (see Figure 2). CMQO methods do not support MI. models with non- linear activations that cannot be represented in low-order polynomial (e.g., ReLU). Second, QMCO methods optimize variational quantum models ! by iteratively performing gradient descent using classical optimizers. QMCO methods are fundamentally limited by barren plateau (i.e., gradient vanishing (MeClean et al., 2018) and the high cost of frequent quantum- classsccl interactions.
To address the limitations of existing quantum ML methods, introduce Quark, a gradient-fiee free quantum learning framework for classification tasks that optimizes quantum models with quantum
TThey are also known variational quantum circuits (VQC)-based models in the quantum literature.

---

Under review as a conference paper at ICLR 2023
preparation
Amplitude amplitiatioo?
Amplttude amplifiation
Measure
10)
10)
Rg
10)
Vinger
10)
10)
UM
UgT
U
U
10]
10)
10)
(0)
(0)
Ccomb
Combb
Figure I: An overview of the Quark optimization framework. Each horizontal line indicates a qubit, and each box these lines represents one or multiple quantum gates applied on these qubits. Quark's optimization pipeline includes three stages: (1) Vo preparation, which initializes Ro and performs model's forward processing UM- (2) amplitude amplification using a Grover-basee based algorithm, and (3) weights measurement. Quark uses K --parallel datasets (KPD) to maximize the probability of observing highly accurate weights in each measurement. Darker bars in the probability plots denote weights with higher accuracies.
an overview of Quark. A key idea behind Quark is entangling the weight E of an ML model (i.e., the Rw register in Figure I} and the encoded dataset (i.e., the Rn register in Figure D in a quantum state, where model weights that achieve optimal classification accuracy the training dataset can be observed with the highest probabilities in measurement. Therefore, users can obtain highly accurate model weights by directly measuring the updated Rw weight register. To maximize the probability of observing optimal weights, we introduce two key techniques.
optimization (QMQO). Figuee.
Amplitude amplification. Quark uses Grover-based mechanism iteratively update the prob- ability distribution of weights based on their training accuracies. As a result, the probability of observing weights with higher accuracy increases after each Grover iteration, as shown in Figure
K K-parallel datasets (KPD). Applying amplitude amplification on one dataset results in a linear amplification scenario where the measuring probability of each weight is proportional its training accuracy (w:). We further introduce K -parallel datasets, technique to enable exponential am- plification. Specifically, by entangling identical training datasets with model weights parallel (using k x RD. as shown in Figure 1}. the probability of observing weight w; in measurement is proportional J (x,,)* Therefore, le increases, the optimized probability distribution of weights gradually converges to the optimal weights.
Compared with CMQO methods, Quark provides more flexibility in model design by composing models directly on quantum circuits and therefore supports broader range of MI. models. Com- pared with QMCO methods, Quark does not require gradient calculation and therefore does not suffer from barren plateau. Quark avoids frequent classical-quantum interactions by realizing both model design and optimization fully on quantum. Besides, by using basis encoding for the train- ing dataset, Quark supports non-linear operations (e.g.. ReLU) in its model architecture, and the optimization complexity is independent of the training dataset size.
Theoretically, compare model query complexity between Quark and gradient- grasient-based methods on a balanced C-way classification task, and prove that Quark can outperform gradient-based methods by reducing model query complexity for highly non-convex problems. In addition, prove that using K -paarllll datasets can further reduce model query complexity under certain circumstances.
Simulations on two tasks (i.e., Edge Detection and Tiny-MNIST) show that Quark supports complex ML models, which can include quantum convolution, pooling, fully connected, and ReLU layers.
Throughout the paper, we use the term weight to refer to the set of all trainable parameters of a model. Number of model forward being called
2

---

Under review as a conference paper at ICLR 2023
Classical Computing
Quantum Computing
Support
Barren- Barren-Plateau
Limited to law- order palynomial activations
Optimaer
Hanilttonaan
Data
Quarium Arneaing based aptimow
Grod based
Eagio
Optimioe
Quantum Model Ciassical Optiminar
operations
Ampiluude Erooding
Data
VGc Modwl
Quark IQuantum Model
Optimber
Duta
Drover-raeee Optirize
Figure Comparison between CMQO, QMCO, and Quark (QMQO).
In addition, Quark can significantly reduce the number of measurements needed for discovering near-optimal weight by applying amplitude amplification and KPD.
Contributions. This paper makes the following contributions:
We propose Quark, a gradient-free quantum learning framework for classification tasks that optimizes quantum ML models with quantum optimization. Quark avoids barren plateau and frequent classical-quantum interactions, supports more general models than prior quan- tum ML frameworks, and achieves
sizeneeeiize optimization complexity.
Theoretically, we prove that Quark can outperform gradient-based methods by reducing model query complexity for highly non-convex problems and that using KPD can further reduce model query complexity.
Empirically, we show that Quark can support complex ML models and significantly reduce the number of measurements needed for discovering near-optimal weight for the Edge Detection and Tiny-MNIST tasks.
RELATED WORK
Figure compares Quark with existing quantum ML approaches.
2.1 CLASSICAL MODEL WITH QUANTUM OPTIMIZATION
Existing CMQO methods aim at solving classical ML problems with quantum optimization tech-
niques by leveraging the advantage of quantum parallelism (Nielsen & Chuang 2(02)). Based
the well-established algorithmic foundation in quantum annealing (Finnila et al. 1994 Kadowaki
& Nishimori] 1998 Brooke al. 1999 Santoro al. 20022 Santoro & Tosatti (006) and adiabatic
quantum computing (Farhi et al. 2001 Albash & Lidar 2018), prior work (Denil & De Freitas
2011 Dumoulin
2014] & Henderson 2015) attempts for the quantum restricted Boltz-
mann machine (RBM) by formulating RBM as an Ising model (Cipral 1987). Inspired by the quan- tum approximate optimization algorithm (QAOA) (Farhi et 2014), Torta al.) (202T) embeds single binary perceptron layer into target Hamiltonian to search for optimal weights. However, CMQO methods are limited by the locality restriction of the target Hamiltonian and can only embed models with low-order polynomial activations (e.g., square). This limitation prevents CMQO meth- ods from supporting practical deep learning architectures, which generally contain non-polynomial activations such as ReLU and sigmoid.
Similar to Quark, Kapoor et al. (2016) also uses Grover's algorithm to find a hyperplane that can perfectly separate the training dataset. However, this method only applies to an idcalistic setup where a hyperplane with perfect classification exists in its search space. Besides, the method cannot adapt generic model architectures other than single-layer perceptrons.
3

---

Under review as a conference paper at ICLR 2023
2.2 QUANTUM MODEL WITH CLASSICAL OPTIMIZATION
Motivated by the recent advances in variational quantum algorithms (VQAs) (Cerezo et al. 202 QMCO methods use variational quantum circuits (VQC) (Benedetti et al. 2019) to represent the trainable parameters of an ML model. [aaviiekk et al. (2019); Schuld & Killoran (019)) use VQC as a variational feature map to reproduce linear support vector machines (M) and kernel methods on quantum circuits, which can outperform classical counterparts under certain circumstances (Liu
et al. 2021
Besides conventional MI. methods, recent work has also explored the feasibility of classical neu- ral networks on quantum circuits (Massoli et al., 2022). Farhi & Neven (2018b); Macaluso et al.) (020aa: Killoran al. (2019) use VQC as building blocks for their quantum perceptron models with a classical gradient-based optimizer. Quantum dissipative neural network (Beer et al., 2020) (QDNN) and quantum convolutional neural network (Cong et al., 2019a) (QCNN), on the other hand, move a step forward towards more complicated neural architectures. QDNN enlarges its model space by applying unitary operators on both the input and output qubits, while QCNN uses a measurement-control/
operation to enable non-linear operations. However, |MCClean et al. (2018) shows that the barren plateau phenomenon commonly exists in VQC-based methods, where gradi- ents vanish exponentially with the model size. Though Beer ct al. (2020) claims to design a VQC model immune to barren plateau, Sharma et al. (2022) contradicts such claim with analytical proof. Though Du et al. (2021) uses a Grover algorithm as part of their method, they still require VQC as their model building blocks that require gradients update.
Besides, due to amplitude- based data encoding, VQC-based methods in general suffer from linear dependency with respect to dataset size in terms of model query complexity during training. Another drawback for amplitude encoding is that due to the unitary constraint of quantum transformations, non-linear operations are hard to implement for VQC-based methods. In contrast, our method uses basis encoding that concerns only qubits state transformation rather than amplitude transformation, which enables more efficient model query complexity and more general non-linear transformations.
3 PRELIMINARIES
3.1 NOTATIONS
Let D = {(x, (i), denote training dataset, where 2; {0, 1] is the binarized fea- ture vector associated with the i-th sample, and y/s E {0, 13 is its label. Let 9 = f(w, {0, 1],, denote our model parameterized by objective 1(j, y). our goal is to find near-optimal w' that mininizes/maximizes the overall objec- tive J(w)
(0, 1)dd x (0,1)d
{0,1]
Given an
N E(...))D (( 2z), y.). We focus on classification tasks and use the objective set and absolute value
(0..)) w) = 10 = y). We use |- to denote the cardinality and use || ll2 and ||- to denote the Ly-norm and infinity norm of a vector. Finally, we & to denote tensor product, and use -, @ A, and V to denote NEGATE, XOR, AND, and OR in logical expressions, respectively.
scalar,
3.2 QUANTUM BASICS
A bit in the quantum regime, called a qubit, represented by a super-position of (0) and [1), which is formally defined as 12) a0) + c*1B)1), where and / are the amplitudes, and ee is the relative phase. Furthermore, the rule also enforces (2|=) of |z). In an n-qubit system, quantum state is represented
where (2) is the conjugate transpose
superposition of 2 basis states. For computational simplicity, we will be using the basis states that are spanned by {10), [1) and
denote the superposition of a n-qubits state as [T) Σ²- -
(i) where (i)) is the corresponding
computational basis. We thus use (ws)) E {10). [1)]dw to denote weight basis state, |x,, y3) for the entangled data basis state where (x,)) E {10),, [1)]d= is the feature and (,,) E {10),, {1)}d the label.
As comparison, in the classical computing regime, each operation can only be applied one state.
4 METHODOLOGY
To realize quantum supremacy, we circumvent the overhead induced by frequent classical quaasicalqquantm interactions and the gradient calculation step in the VQC-based methods, which may result in barren
4

---

Under review as a conference paper at ICLR 2023
.49
.49
Amplituda Ampiification
Proo
0
200
[x] (n)
2000
1100
0
[3] 0
(N]
(N) (1)
[4) = 10)
( 11)
Figure 3: Toy illustration of Quark's insight, where the dataset {(x0 30 0), (2) 1, 91 1)} is constructed by oracle function g(x) = 0 @ æ. We define our learner model as 0 fxx w) @ x. The colored qubit strings stands for the states activated by model forward (eyan for (w) and yellow for ww = 1). violet bars stand for solution states measuring probability, gray stands for non-solution states measuring probability.
plateau as the circuit depth increases. In addition, as VQC-based methods use the amplitude encod- ing scheme for data encoding, non-linear operations hard to implement, while their training time can linearly depend on the training dataset size.
To this end, we designed Quark in QMQO fashion, which (1) achieves gradients-free optimization over the entire weight distribution, (2) uses basis encoding to achieve potential speedup as sample size scales up, and (3) enables flexible quantum model design that easily incorporate non- lincarities. Figure shows an overview of the quantum circuit design in Quark.
As we are using basis encoding over the entire data distribution, we initialize the data register Rp [ii y:)- To initialize a model's weights register Rw, we construct
as D) ((E..))
V
uniform state by applying the Hadamard gate on each weight qubit: (W) = Ei= 2n
v2 w.)
In addition, Quark includes an auxiliary register Ro for storing intermediate results and model's output, which is initialized as IO) jo) Therefore, the initial state is represented (W) @ D) Ø 1O). By encoding the quantum model architecture as a unitary matrix UM, the model's forward processing is defined as:
UM (WW)
D) O))
Σ 2
Σ V
IJ (,
where (W) is the model's output for weight w; and sample x3 Given the above expression for the model forward processing, key insight for Quark update the probability of observing weight in measurement based its training objective J (w). This is achieved through Grover's algorithm by defining the solution state space S = [w,) |z fw,, xz)) y) = f(w;, x;, Appendix A. innluude introduction to the original Grover's algorithm. After amplitude amplifi- cation, we observe a model weight by measuring the weight register Rw.
To further illustrate insight, Figure 3 shows toy example, where the underline oracle function that generates the training data is g(x) = + x. Using one qubit for æ, the training dataset is constructed
[(x 0, yo 0), (x: y1 1)}. By defining the learner model f(x, w. = w ( x. where w is the trainable parameter, Quark includes four qubits (i.e., |wo). [x). ly)) and lo)). . For initial state preparation, we simply go through the model forward circuit with uniform weight initialization that result in an uniform amplitude state, as shown on the left of Figure 3 As
no optimization happens at this stage, the probabilities for observing (w) J0) and |w) 11) in measurement are equivalent. After amplitude amplification, Quark reaches an optimized amplitude
state (shown on the right of Figure 3) where the probability of observing the optimal weight (w) [0) in a measurement is much higher.
For the rest of this section, Section D.ettion[.T]ittroooon introduces Quark's on-circuit model design philosophy, Sec- tion describes the Grover-based method for amplitude amplification, and Section 4.3 introduce
"We omit the model's intermediate results (O) for simplicity.

---

Under review as a conference paper at ICLR 2023
W;
W,
W3
X
max(
X
x2
% Ng
X;
Am
92
0
0g
(a) Convolution
(b) MaxPool
Figure 4: Logical gates illustration of quantum module design. (a) Convolution: for 1 x 3 Conv
kernel with weights W [W1, Wz. Wa] and input X; [111 X the output is given by
O (-W + Xa)) A (- @ x))) A (-(Wa @ X13)). ). (b) MaxPooling: for input X;
(Xa, X2, X13 the max pooling output is given by O = Xa V X,2 X13-
K-Parallel Dataset (KPD), technique that enables exponential amplification to further improve the optimization algorithm.
4.1 MODEL DESIGN
The model circuit UM can be designed through arbitrary combinations of base gates (CNOT, Rota- tional gates, Hadamard gate, etc.), which can then entangle [W), D) to get a trainable model.
Leveraging the flexibility of basis encoding, Quark is capable of realizing modules used in classical deep models. Figure 4 illustrates two Quark modules (Conv, MaxPool) used in our experiments. Besides Convolution and MaxPooling, Quark can support more diverse operations given enough qubits. We include the demonstration of the Fully Connective and ReLU modules in Appendix A.4
During training, we encode the entire data distribution through basis encoding so can apply model forward simultaneously for all data samples. During inference, we encode each sample as single state | Prediction can be obtained by measurements over the output register after the model forward step UM 0) ww" fa, 0) [ww",, (w=,,t)) it)), where w" is the measured optimal weight.
4.2 AMPLITUDE AMPLIFICATION
To increase the probability of measuring the weights with the highest classification accuracy, we use Grover's algorithm to amplify the amplitude for any state [w,)) (,,,,, xr)) E S, thus the measuring probability of optimal weights would be amplified the most. In this section, we will formally define the unitary operators need for Grover's 's update, followed by the complexity analysis of the optimization algorithm.
For conventional Grover's algorithm, need two reflection unitaries, namely U.T, Uw. where UgT is the reflection against the non-solution sub-space and Uv, is the reflection against the initial state. In our case, by defining solution state
(s)
Σ
v Vis
(w,) 11 Bes
and initial state
Vo
Σ
wi)
(f
2dh D
8.j
the Grover operator can be easily built from Usemb UNO where U,T -I I Uwo
2 Mo) (Yol I..
Now that we have the Grover operator well-defined, we can formally do analysis on the algorithm in terms of model query complexity.
Theorem By defining a = Suyew, (ww)dd Tw.ew J(w as the probability to measure an c-optimal solution
after the Grover's 's update, the model query complexity for getting an e-optimal solution wa E We on balanced C-way classification task is O I

---

Under review as a conference paper at ICLR 2023
(w;) is the objective value (accuracy) for weights w,, W is the complete weight space, and W. is the c-optimal weight subspace. The proof Theorem 1
is included in Appendix A.3.1 it follows
from the analysis that we need O(VC) Grover iterations per measurement and Of JuEEw J[w;)ab )al T w.ww, Hws
measurements in expectation for sampling an e-optimal weight.
Notice that the complexity of our method does not depend on sample size N. As we are sampling solutions from an optimized distribution for general non-convex problem, our method does depend
an O( Jerew J(1;)dd
Se,ew, J(w.)d8 term. However, to achieve an c-optimal solution general non-convex problem, the worst scenario for VQC-based methods with gradient- optimizers needs O Su,ew d6
Swrew, d5) iterations to sample initial points lie within convex regions that contain c-optimal so-
lutions. With per iteration gradient evaluation cost that is in the order of O(N), this gives an overall N) for VQC-based methods. Since O frrjew (we])dd Tw,ew, J(wv)d8 < O Sun Suiew dó
complexity of O Suyew d8
Ja. Ja
Ju,ew, d6
and VC < N in practice. Our method provides speed-up for finding an c-optimal solution in the general non-convex setup.
In addition, as Quark does not require gradients calculation, it will not suffer from the notorious problem of barren plateau. For more idealistic case of convex problems, [arg et al. (2020) has given proof of no quantum speed-ups can be obtained in this case with no exception of our method.
4.3 K-PARALLEL DATASETS (KPD)
A naive implementation can only achieve p(w,) [w;), which requires more measurements for sampling e-optimal solution. To this end, we further extend our method to achieve p(to)) o J (w:))* through K-Parallel Dataset (KPD), shown in Figure [ simulated annealing, by updating weights distribution proportional to J(w;). the probability mass would gradually converge to the global optimal solutions.
when & >> 1. The intuition is similar to
We do so by concatenating the same dataset K times for increasing solution states in the order of K as:
K-1
UM
(W)
(1Dx) 2 10n))
=E
wc
II k=0
Σ
Iay vyMlf
2
Dr
k=
j
the solution set is now defined as:
K
K-1
Sk: : (wwa)
ja Mo Mf 25,))
A
(y)z = f(w,, 211))
We then update |s), Po), Ucamb accordingly as Appendix A.2 Now the ratio of solution states between different weights can grow exponentially in terms of K.
Juyew, ds Theorem By defining Ju.ew/w. do as the volume ratio between e-optimal weight subspace
[Wel and non-c-optimal weight subspace IW- Wel. the model query complexity for getting an c-optimal solution wi We balanced C-way classification task with k-parallel dataset is O(11 1 1))))(()).
The proof of Theorem is included in Appendix A.3.2 Here, the trade-off is that the number of Grover iterations needed per measurement grows to O (c# As we also need to apply the model forward for each dataset, the KPD Grover complexity in terms of model query complexity now OKC²). On the other hand, as we are converging to the global solution, the number of measurements needed can be reduced from ((L) to O(1 1 1)*) as 3 < a. Thus the optimal value for depends on the specification a, 3, C.
Theorem 3 Given at, B, C, the optimal value of l is k* = [log 1 + +1 if 2 m - VC where
[log L. + else At* = 1.

---

Under review as a conference paper at ICLR 2023
Mavuring Probabilit
0.015
normalized accuracy
Moauring Prebabillty
0.015
normalized accuracy
Maxuring Probabillty
0 0.100
normalized securacy
0.075
0.010
0,010
2,050
0.005
0,005
0.025
0.000
125
192
256
0.000
54
128 Weight
192
256
0.000
54
192
256
Weight
Weight
(a) Initial distribution
(b) Amplitude ampl. 1-PD
(c) Amplitude ampl. w/ 4-PD
Figure 5: Amplitude ampl. + KPD on Edge Detection. normalized accuracy: J(w,) = Σ, [ww]]
J(me))
Thus for cases where m m- VC 3 < we have optimal k > 1 which proves the effective- ness of KPD under certain circumstances. We include the proof of Theorem 3 in Appendix A.3.3
5 EXPERIMENTS
In this section, we empirically verify the effectiveness of Quark on two tasks, namely Edge Detec- tion and Tiny-MNIST. Algorithm 1 formally states the pipeline of Quark Instead of leveraging the approximated iteration number from theoretical derivations for Grover's s update, we use more precise but efficient estimation practice to achieve a more accurate amplitude amplification effect. We include the detail of Grover iteration number estimation in Appendix A.5. Notice that most of the simulation results are obtained numerically since we have no access to large scale quantum devices that fit our setup. However, we do Qiskit Aer (Anis & al. 2021) to verify the producibility of our numerical simulation results on models that are applicable, results are included in Appendix A.6
Algorithm 1: Quark's optimization pipeline.
Input: Data Oracle: UD: Model Oracle: Um: Objective Oracle: U1; Number parallel dataset: k; Measurement budget: m;; Weights buffer: B
Output: Optimized Model Weight: w"
U Ucomb: (o)) = Preprocessing(U/ (U (,,UU, // get Grover iteration 9r Grover operator Uconb and initial state (V)
for == 0; i < m; ++i do
for = 0: < g: ++jdo do
1 j+1) = Commb W
// Grover update
w; = Measure ()))) B.add
// Weights measurement on Rw
return arg wa Evaluate(w))
5.1 EDGE DETECTION
For Edge Detection, our goal is identify if a 3 binary matrix has 1) both vertical and horizontal lines 2) vertical lines only 3) horizontal lines only 4) no lines, where line is defined by three consecutive 'I's in a row or column. Thus the task is a 4-way classification task with 512 instances. We split the 512 samples into a training set with 400 randomly selected instances and test set with the rest. We use Quantum Convolutional Model that consists of several kernels with Maxpooling modules described in Figure 4 for this task. Results are demonstrated J(wx) in Figure (normalized accuracy: J(w,) E. J(w:) ), from which we can clearly see a linear relationship between model accuracy and optimized weights distribution using 1-PD. For 4-PD, we can observe that weights distribution further concentrates on the global optimal solutions.
convolution
Indeed, as we concatenate more training datasets, the probability mass will gradually converge to the optimal solutions, thus reducing the number of measurements we need significantly. We include the results for 2-PD and 3-PD in Appendix A.5.3
Preprocessing( and Evaluate() included in Appendix A.5.1
8

---

Under review as a conference paper at ICLR 2023
Measuring Trebubillity
1,00
normalized accurncy
Measuring Probabillty
1.00
normalized accuracy
Measuring Frohabilltty
normalized aecuracy
0.75
8.75
0.50
0,500
0.25
6.25
0.00
8152
16:34 Weight
24566
32768
8192
16384 Weight
24576
32768
8192
16384 Weight
24576 32768
(a) Initial Distribution
(b) Amplitude ampl. 1-PD
(c) Amplitude ampl. w/ 4-PD
Figure 6: Amplitude ampl. + KPD on Tiny-MNIST. normalized accuracy: J(w,) = Σ, (wn)
J(wa)
5.2 TINY-MNIST
For Tiny-MNIST, we down-sample original 28 x 28 images from MNIST to 3 x 3 and remove duplicated samples. Due to device limitation, we only consider classes 1, 2, which makes this task a 3-way classification task. We use Weighted Mask modules (details are included in Appendix (A.4) with MaxPooling modules to compose 82.61% % testing accuracy by the best model in the search space. Whereas a well-optimized classical single layer perceptron model can achieve 85% in training accuracy and 80% test accuracy.
model, which achieve 86.08% training accuracy and
J(w.) Similarly, shown in Figure (normalized accuracy: J(w:) Σ. J(my) a linear relationship between model accuracy and optimized weights distribution can be observed using I-PD, while 4- PD can further increase the probability for sampling optimal solutions. We also include the results of 2-PD and 3-PD on Tiny-MNIST in Appendix A.5.4.
Besides distribution evolution, also statistically demonstrate the relationship between measured top-1 model's test accuracy and measurements budget using uniform random sampling, I-PD, and 4-PD respectively in Figure In order to achieve equally well-performed model, 4-PD only requires ~ 30 shots on Edge Detection task for mean test accuracy > 98% while uniform random sampling needs ~ 900 (~ 30x more) shots with much higher variance. Similar trend can be observed on Tiny-MNIST where 4-PD only requires 1000 shots for mean test accuracy >> 76.5% while uniform random sampling needs ~ 20000 (~ 20x more) shots with higher variance. We include the training ones in Appendix A.5.5
0.9
1.00
test accuracy
test accuracy
0.8
0.75
0.7
0.50
URS
URS
1-PD
0.6
1-PD
0.25
4-PD
4-PD
500
1000
0.5
0
10000
20000
30000
measurement budget(shots)
measurement budget(shots)
(a) Edge Detection
(b) Tiny -NISTT
Figure 7: The mean + std of the test accuracy of the best discovered model with different measure- ment budget (in shots), URS shows the result where the weights are uniformly random sampled.
CONCLUSION
In this paper, we propose new quantum learning framework Quark that does not involve gradients calculation and operates in fully-quantum fashion. Acknowledging the notorious problem of bar- ren plateaus from VQC based methods, Quark shed some lights on circumventing this phenomenon through a gradient-free optimization pipeline. Quark also enables more general set of module de- sign due to basis encoding, so that non-linear operations can be easily implemented. Theoretically, present some evidences in terms of model query complexity for Quark to demonstrate trade-offs between VQC based methods and Quark. Empirically, we have verified the effectiveness of Quark through numerical simulations Edge Detection and Tiny-MNIST.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Steven H Adachi and Maxwell P Henderson. Application of quantum annealing to training of deep neural networks. arXiv preprint arXiv:1510.063356 2015.
Tameem Albash and Daniel A Lidar. Adiabatic quantum computation. Reviews of Modern Physics, 90(1):015002, 2018.
Md Sajid Anis and al. Qiskit: An open-source framework for quantum computing, 2021.
Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, al. Quantum supremacy using programmable superconducting processor. Nature, 574(7779):505-510 2019.
Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin-Lic Chan. Quantum algorithms for quan- tum chemistry and quantum materials science. Chemical Reviews, 120(22): 12685- 2020.
Kerstin Beer, Dmytro Bondarenko, Terry Farrelly, Tobias Osborne, Robert Salzmann, Daniel Scheiermann, and Ramona Wolf. Training deep quantum neural networks, Nature Communica- tions, 11, 2020.
Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini. Parameterized quantum cir- cuits as machine learning models. Quantum Science and Technology. 4(4):04301, 2019.
J Brooke, David Bitko, Rosenbaum, and Gabriel Aeppli. Quantum annealing of disordered magnet. Science, 284(5415);779-78. 1999.
Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon Benjamin, Suguro Endo, Keisuke Fujii, Jarrod Ryan McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick Coles. Variational quantum algorithms. Nature Reviews Physics, 2021. URL pettps://wwee nature. com/
articles/s42225
00348-2
Barry A Cipra. introduction to the ising model. The American Mathematical Monthly, 94(10); 937-959, 1987.
Iris Cong, Soonwon Choi, and Mikhail D. Lukin. Quantum convolutional neural networks. Nature
Physics. 15(12):1233-1278 aug 2019a. doi: 10.1038/441567-119666888. URL https://
doi org. 10 1ttpg//00..0000221113111 019 0648-8
Iris Cong, Soonwon Choi, and Mikhail D Lukin. Quantum convolutional neural networks. Nature Physics. 15(12):1273-1277 2019b.
Misha Denil and Nando De Freitas. Toward the implementation of quantum rbm. 2011.
Yuxuan Du, Min-Hsiu Hsich, Tongliang Liu, and Dacheng Tao. A grover-search based quantum learning scheme for classification. New Journal of Physics, 23(2):023020, feb 2021. doi: 10. 0188/1367-263//abdee URL https: wrg.eii..rrrglo http://1..08/1133510
Vincent Dumoulin, Ian Goodfellow, Aaron Courville, and Yoshua Bengio. On the challenges of physical implementations of rbms. In Proceedings of the AAAI Conference Artificial Intelli- gence, volume 28, 2014.
Edward Farhi and Hartmut Neven. Classification with quantum neural networks on near term pro- cessors. arXiv preprint 1002.0000000000 2018a.
Edward Farhi and Hartmut Neven. Classification with quantum neural networks on near term pro- 802. 0000 06002
cessors, 2018b. URL
Edward Farhi, Jeffrey Goldstone. Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda. A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem. Science, 292(5516):472 2001.
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algo- rithm. arXiv preprint arXiv: /4/ 4,2028, 2014.
10

---

Under review as a conference paper at ICLR 2023
Aleta Berk Finnila, MA Gomez, C Sebenik, Catherine Stenson, and Jimmie D Doll. Quantum annealing: A new method for minimizing multidimensional functions. Chemical physics letters, 21965-6):443-355 1994.
Ankit Garg. Robin Kothari, Praneeth Netrapalli, and Suhail Sherif. No quantum speedup over gradient descent for non-smooth convex optimization. arXiv preprint arXiv:2010.0180/ 2020.
Vojtëch Havlfčck, Antonio D. Córcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow, and Jay M. Gambetta. Supervised learning with quantum-enhane fea- ture spaces. Nature, 567(7747):209 212, Mar 2019. ISSN 1476-4687. doi: 10. 10.1038/ s4 s41586-019-0980-2 URL httpth::pppt.oppppppppppp
Ben Jaderberg. Lewis W Anderson, Weidi Xie, Samuel Albanie, Martin Kiffner, and Dieter Jaksch. Quantum self-supervised learning. Quantum Science and Technology, 7(3):035005, 2022.
Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing in the transverse ising model. Physical Review E, 58(5)5535, 1998.
Ashish Kapoor, Nathan Wiebe, and Krysta Svore. Quantum perceptron models. Advances in neural information processing systems, 29, 2016.
Nathan Killoran, Thomas R Bromley, Juan Miguel Arrazola, Maria Schuld, Nicolás Quesada, and Seth Lloyd. Continuous-variable quantum neural networks. Physical Review Research, 1(3): 033063, 2019.
Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme. A rigorous and robust quantum speed-up supervised machine learning. Nature Physics, 17(9):01131017, Sep 2021. ISSN 1745-2481. doi: 10.
URL https: wrg.//orr///.. 10000....... 1038/
B-1567-021-01287-2
Antonio Macaluso, Luca Clissa, Stefano Lodi, and Claudio Sartori. A variational algorithm for quantum neural networks. Computational Science - ICCS 2020, 12142:591 604, 2020a.
Antonio
Macaluso, Luca Clissa, Stefano Lodi, and Claudio Sartori. A variational algorithm for quantum neural networks. In International Conference on Computational Science, pp. 591-604. Springer, 2020b.
Fabio Valerio Massoli, Lucia Vadicamo, Giuseppe Amato, and Fabrizio Falchi. A leap among quantum computing and quantum neural networks: survey. ACM Comput. Surv., mar 2022. ISSN 0360-03000. doi: 10.1145/3529756. URL htt.::ttts///cm //dot wtt.:oo..rr111..1...//.. Just Accepted.
Jarrod McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven. Bar- ren plateaus in quantum neural network training landscapes. Nature communications, 9(1):166, 2018.
Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.
Giuseppe E Santoro and Erio Tosatti. Optimization using quantum mechanics: quantum annealing through adiabatic evolution. Journal of Physics Mathematical and General, 39(3))R333, 2006.
Giuseppe E Santoro, Roman Martonák, Erio Tosatti, and Roberto Car. Theory of quantum annealing of an ising spin glass. Science, 295(5564):2427-4430 2002.
Maria Schuld and Nathan Killoran. Quantum machine learning in feature hilbert spaces. Phys. Rev. Lett. 122:040504, Feb 2019, doi: 10. N0..i03.pyssRee..e.. 12..122222222222 22.0040544. URL htttps://iikkkk. aps. wew./org//eo do/ 11t3:/11/eeeee..eeeeeme
122. 040504
Maria Schuld, Ilya Sinayskiy, and Francesco Petruccione. The quest for quantum neural network. Quantum Information Processing, (3(11):257722586 2014.

---

Under review as a conference paper at ICLR 2023
Kunal Sharma, M. Cerezo, Lukasz Cincio, and Patrick J. Coles. Trainability of dissipative perceptron- based quantum neural networks. Physical Review Letters, 128(18), may 2022. doi: 128.18000..... 1. URL Stttaa///bb..orgg....13322pppppp 128. 180505
Peter W Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceed- ings 35th annual symposium on foundations of computer science, pp. 124 134. Icee, 1994.
Ruslan Tazhigulov, Shi-Ning Sun, Reza Haghshenas, Huanchen Zhai, Adrian Tan, Nicholas Rubin, Ryan Babbush, Austin Minnich, and Garnet Kin-Lic Chan. Simulating challenging correlated molecules and materials the sycamore quantum processor. 2xxv:2203.11291, 2022. URL
https:// //re:///rxvvv wwwprii..rrgeeee
abg/abs////aeooooooaogggaa///aa/ abs /22../522211111
Pietro Torta, Glen B Mheng, Carlo Baldassi, Riccardo Zecchina, and Giuseppe E. Santoro. Quan- tum approximate optimization algorithm applied the binary perceptron. arXiv preprint arXiv:2112.10219, 2021.
A APPENDIX
A.1 GROVER'S ALGORITHM
A well-known algorithm for amplitude amplification is Grover's algorithm. The original Grover's algorithm is trying to search specific states that satisfy some properties which are called solution states. Instead of enumerating over all possible states to find the solution states that lic in the solu- tion set S, Grover's algorithm tries to amplify the solution states' amplitudes using two reflection unitary matrices U,T, Uvo- Let (u) denote the initial state of all qubits and |s) = =.,es vis (s:)
represent the basis state spanned by all solution states. UST and Uw, are constructed as follows:
U,r = I 2/5) (sl
Uv. 2| v)) (Vol
(3)
Geometrically, U is the reflection operator over |s E..gs (1(0)11))*)) (8s), which is an
state orthogonal to the solution space. Similarly, Uw. is the reflection operator over Vo). Given 0 = aresin ( (VVa) ss T)), (oo) be expressed
(oo cos 0|s sin 018)
The combination of the two reflection unitary matrices Usomb Uv, U,T t is equivalent to a rotation of 20 on the plane spanned by is and ())). Therefore, applying the combination of the two reflection matrices & times gives:
[I Ucomb
|oo
cos ((2k 1)0)[=T) + sin ((2k + 1)0){s)
(5)
As for most practical setups the solutions are always sparse and existed, we have 0 < 0 maximize the amplitude for [s), & should be in the order of (
<
3. To
A.2 DEFINITION
The [s), vo in KPD are updated as:
K
1s)
Σ
(wn)
Ji Vj. (11,
VIS
K Ezo
My,
and
K
Vo
Σ i.jo JK
w.)
Tiee If xz21)
2d... D
.again the Grover operator can be easily built from Usumb = U, where U,r I 2 2/s) (s), Uw. (o) T.
12

---

Under review as a conference paper at ICLR 2023
A.3 PROOF
A.3.1 THEEREM
Given the probability for sampling a solution state p, then the Grover iterations achieve the maximum amplitude amplification effect is V= As in case, the probability for sampling
Sx, Jw,ew J(m4)dd Jw db then suppose we are doing balanced C-way classification
solution state is given by
task the Grover iterations we need is:
Sw, ew dō Ju,ew Jw;)dd
(6)
V Eura (ww)
1
c
Vc
(8)
(9) (10) is due to for balanced C-way classification, should expect the accuracy for random model to be the same as random guess č
Jw,ew, J(w;)d8
As we have defined
Juyew ds) as the probability to measure c-optimal solution, thus
in order to sample a e-optimal solution by measurements, it takes ( trials. Which gives us an overall complexity of 0( /C
A.3.2 THEOREM 2
Given we are doing a balanced C-way classification task for & parallel dataset, the probability for sampling a solution state is now Surew J(we)*
Ju,ew d5d6 [w.-w[[(u:)]]] Since the objective function we defined is non-negative (ww;) 2 0, thus we have J(w,) ) to be convex function in Jww). As expectation operator preserve convexity we have [[[((;;)*] 2 B[J(w;;]* we have:
Swsew 14d8
(9)
S Jn dw
[J [
< Bwnnw([[w:)]
(10)
V
(11)
Thus the Grover iteration needed is upper bounded by t
13

---

Under review as a conference paper at ICLR 2023
For measurement, the expected iterations we need is Juyew J(w))+ which can be approximated
Jucew J(we]+
as:
Jw,W dd
Sueww J(w)) * d8 + ww.ww/w d8
(12)
Suvew. d6
SweEW. J(w;)=
1 + S JwnEw/w. dw
(13)
SwLEw. d
= 1 1+ Smew/ww (w:)
Smew. 1o Swewwww 18
(14)
Sw,Ew, db
Swiew/w. 1k
Swsew, 18
Se,ew/w, "
1 Jwjew/W. 1=
(15)
Jw,ew. [(o,)* B
Jujew. 1=d6
1+ B www.ww www.w//wwww/..... (w)))* 1
(16)
Bw,ew, [ww,)) B
1+ BarEw/W w. W. [Jx,))]
(17)
Ew,,w, [ [[m)
13
E EW/ (w;)]
1+
(18)
Ew. [J(w))
B
J.rEw/w. ((v))d
Ju,ew/w.
1+
Jue ((w.)d6 )kb
(19)
B
Jwsew. 1dd
1 Sw,ew, 1d8
Swrew/W. Iw:) )d5
Sweww/w. 1d8 Swyew. [w; )kv
(20)
B
= 1 1+ (3 SWEW J (w:)dō - Swyew. [ws]ed
(21)
J.,ew. (w:)dō
B
= 1 1 (3( 1))* 3
(22)
1+ gh1 1 1)a
(23)
a
(18) > (19) is assuming ww/e [[[:]]] > Var,,ewww, [w;)) which is usually the case in practice since J(w;) itself is upper bounded by [0, 1 O()) within the non-c optimal region and
J (w;) can be assumed to be near-uniformly distributed within W/W, across range [0, 1-1-- (e))],
which is general assumption. Thus Bu,ew/w,[[Wwg [J(w])*
can be dominated by Bweew (J(w)))* (w.ew,,[(w.)))
[(w.)))
Bw,ww/w. [J(e))]
Ex,ew, [[(22)]]
A.3.3 THEOREM 3
As the trade-off is between measurements needed versus Grover iterations per measurement, we can list their rate of change make the comparison. For k-parallel dataset, Grover iterations increased
by = Ac &
For measurements needed, the exact ratio should be 1+ - 1jt however we can further approximate this ratio as F (9)^ given 8 1 1)* which is equivalent
to A < |log: 1 +11 Thus the optimal & should satisfy 2 k - C well as k < [log 1 +1 1. +1.
As k 1 C k > is monotonically decreasing with respect k thus as long 9 2 m mm--13 Ch for = log q
! + 1 we could have our optimal k = [log L + 1, otherwise A: = 1.
14

---

Under review as a conference paper at ICLR 2023
A.4
MODULE DESIGN DETAILS
X X
XG
Wia
R2
X2
Mixs
0
X]
X2 0
X
=,=1
(a) Fully connected layer
(b) ReLU
Figure 8: Representing fully connected layer and ReLU activation as quantum circuits in the Quark optimization framework. (a) Fully connective layer: for 2 FC layer with weights Wiy and input X [X,, X2, X3). the output is given by O = (Wa A X1) + (W2 A X2) (Was a A Xa). (b) ReLU: for an input X; = [S, X1, X2] where S is the sign qubit, the ReLU output is given by X (X @ (-SAX)
In addition the convolution and maxpooling layers shown in Figure 4a and Figure 4b Quark can also incorporate other commonly used tensor algebra operators. Figure demonstrates how to represent fully connected and ReLU layer as quantum circuits in Quark.
Due to the limitation of the number of qubits, our parameterization can be viewed as a binary model over a bounded weight space W. In our experiments, we make little modification to Quantum Learning modules introduced before. For Edge Detection task,
2 Oo (A Wo, @ X.,)) @ W0.3 1=0 ==0
(24)
2
0, = (A W @ Xj,)) @ W1,3
(25)
i= j=0
We use (n0O) = 100), (01), [10), (11) to express the different predictions respectively.
For Tiny MNIST task,
O₂ = CVCV Wt (i.))) + WEDD k = 0, 1= 1=0
(26)
We use 10,0i) = [10), 11) to express the prediction of Number and use 10,O,) |01),, 100) to express the prediction of Number 2 and Number respectively.
A.5
EXPERIMENTS
A.5.1
QUARK PROCESS
10c
10c
(a) QC'A
(b) QCB
Figure 9: QCAAi is the quantum circuit for calculating the average accuracy for different parameters, which is used in computing the number Grover iterations as shown in Algorithm 2 QCB shows the quantum circuit for computing the accuracy of specific weight, which is used in Algorithm
15

---

return J: Under review as a conference paper at ICLR 2023
Algorithm 2: Get Grover Iterations Number
Input: Data Encoder Oracle: Up: Model Forward Oracle: UMi: Objective Function Oracle:
UL; number of parallel dataset: k; Shots to estimate accuracy: $
Output: Grover Iterations Number:
Initialize Obj = 0:
QC = QCA UM, UL.k); // Construct the quantum circuit shown in
Figure (a)
for i 0: < 8; ++i do
| Obj = Obj + C...mesuureRol--11
Obj- Obj/S: SS:
arcsin (bb)):
g return g:
E.;
Algorithm 3: Evaluate
Input:
Data Encoder Oracle: UD: Model Forward Oracle: UMi: ; Loss Function Oracle: UL;
number of parallel dataset: k; Shots to estimate accuracy: s; Weight: w
Output: J(w)
Initialize J -=0 0:
QC = QCB D. UM UL, ki : Construct the quantum circuit shown in
Figure (b)
for = 0; s: ++i do
L J= QC.measure (oo
J= J/s:
We use Preprocessing() to:
Calculate number of Grover iterations we need (The procedure illustrated in Figure ((a) and Algorithm
Construct Grover Operator Ucomb-
Uniformly initialize Rw with Hadamard gates.
Initialize k RD with UpS to encode identical training dataset in parallel.
In Algorithm 2 we may find that is close to 4, making G extremely large or non-existent. How- ever, we can introduce extra samples to dataset to resolve the issue. These auxiliary samples are identified by an additional qubit, that automatically being classified into non-solution space.
In function Evaluate(), we evaluate the objective value of a specific weight w. The procedure is illustrated Figure 9)) and Algorithm
A.5.2 TINY-MNIST EXPERIMENTAL SETUP
To construct MiNS-MNIST dataset, we select images with label 1, 2, 7 form the original MNIST training set and downsample them to 3x3 images with binarization applied to form D,. As samples with same representations in D, cannot share different labels, we majority voting decide labels for duplicate samples within D2 to form our final dataset. We apply same procedure for both training and testing datasets. This gives 46 instances for testing. We use Tiny- Miy-MNIST for evaluating both classical methods and Quark. The settings of classical methods are shown in Table
Tiny-MNISS dataset with 79 instances for training and
16

---

Under review as a conference paper at ICLR 2023
Architecture
9 FC Softmax CrossEntropy
Loss Function
Optimizer
Adadelta
learning rate batch size
1.0
8
epochs
100
seed
0.1.2.3.4.566.7.889
Table 1: Basic Settings of Classical Method
A.5.3 EDGE DETECTION RESULTS
0.04
Measuring Probability
normalized accuracy
Measuring Probabiiity
normalized accuracy
0.06
0.03
8.002 0.02
0.04
0.01
0.00
64
28 Weight
192
256
0.00
64
128 Weight
192
256
(a) 2-PD
(b) 3-PD
Figure 10: The effect of amplitude amplification for Edge Detection.
A.5.4 TINY-MNIST RESULTS
1c4
1c-4
Mcasuring Probability
normalized accuracy
Measuring Probability 5
normalized accuracy
1.5
1.0
0.5
0.0
8192
16384 Weight
24576
32768
8192
16384
24576 32768
Weight
(a) 2-PD
(b) 3-PD
Figure 11: The effect of amplitude amplification for Tiny-MNIST.
17

---

Under review as a conference paper at ICLR 2023
A.5.5
SHOTS & TRAINING ACCURACY
0.9
1.00
training accuracy
training accuracy
0.8
0.75
0.7
0.50
URS
URS
1-PD
0.6
I-PD
0.25
4-PD
4-PD
500
1000
0.5
10000
20000
measurement budget(shots)
measurement budget(shots)
(a) Edge Detection
(b) Tiny-MNIST
Figure 12: mean + std of the best model's training accuracy measured within given measurement budget.
A.6 QUANTUM SIMULATION
To further verify our framework, we use Qiskit Aer (Anis & et al. 2021) to simulate the process of solving simplified Edge Detection task with Quark. The goal is to identify whether a 3x3 binary matrix has horizontal lines. The task is binary classification task with 512 instances. We randomly select 400 of them as the training and the as the test set. The result simulation is shown in Table Each data point is acquired with 20 runs. The corresponding result of numerical simulation shown in Table
shots 59.14%
4
8
16
32
64
128
train
67.9%
68.36%
75.33%
85.04 35.04%
85.79%
91.93%
94.14%
std 12.21%
10.34%
9.05%
11.26%
9.27%
9.01%
6.18%
4.30%
test 58.17%
65.04%
65.54%
75.63%
84.69%
84.55%
90.18%
92.41%
std
13.54%
10.35%
9.60%
11.32%
10.09%
10.59%
7.33%
5.77%
Table
2: Relationships between training & test accuracy and shots.
(Qiskit Simulation)
shots 60.74%
8
16
64
128
train
66.20%
71.52%
77.49%
83.82%
89.59%
93.93%
96.88%
std 10.72%
10.26%
10.96%
11.12%
10.09%
7.87%
5.53%
3.86%
test 60.03%
64.99%
70.11%
76.18%
82.83%
88.90%
93.22%
95.96%
std 11.17%
11.07%
11.97%
12.28%
11.23%
8.72%
6.11%
4.95%
Table
3: Relationships between training & test accuracy and shots. (Numerical Simulation)
18

---

Under review as a conference paper at ICLR 2023
Figure 13: The quantum circuit for simplified edge detection.
19


Reviews:
[{"review_id": "eQYMjQ5ytz8", "reviewer": "Reviewer_YQCZ", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents an approach to training machine learning models using quantum computing. It is based on the well-known Grover's search / amplitude amplification approach. ", "summary_of_the_review": "The approach uses a well-known approach to speed-up any search problem via Grover's approach. The practicality of the approach for near/medium term quantum devices is very low. The computational complexity of the approach is not thoroughly assessed.", "strength_and_weaknesses": "Strengths:\n- having empirical evaluation of the quantum approach is a plus\n\nWeaknesses:\n- the basis encoding used in the method requires O(#features) qubits just to store the dataset, and additional O(#trainable parameters) qubits to store the model during computation. This severely limits the usefulness of the approach in a near and medium term. \n- complexity analysis is expressed not in terms of input characteristics such as #samples, #features but instead (Thm 1) is is said to be (roughly) inversely proportional to the ratio of expected value of the objective function for optimal solutions to the expected value of the objective function for all possible solutions (all possible weights). This is smaller than the volume of optimal solutions among all possible solutions (authors' also mention that in pg.7). The problem is that for most reasonable models and classification problems, this volume is very small (otherwise, we would use random sampling to find a good model), yet authors do not attempt to offer any quantification of how small it is.\n- the datasets used in the empirical evaluation are extremely small (9 features). Is this related to basis encoding being used?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "XB9CkxmjS2g", "reviewer": "Reviewer_Wci6", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors present a gradient-free framework for quantum deep learning using known techniques for the optimization, in particular Grover's algorithm. The techniques are not really new and the scheme is not at all near-term as is shown from the lack of experiments.", "summary_of_the_review": "Interesting idea but with many drawbacks and not enough novelty in the techniques ", "strength_and_weaknesses": "+ new framework for quantum neural networks that avoids barren plateau\n- using amplitude estimation within a quantum neural network makes it not really near-term\n- there are many different ways of avoiding barren plateau that also keep the possibility of implementing the neural networks", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "2QqZiNvdmor", "reviewer": "Reviewer_5Kqc", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed a novel gradient free quantum learning framework called QUARK, which is designed for classification tasks. Different numbers of qubits are assigned to Data, Weight and Output session, and the data are encoded with basis encoding method. Weights are applied to data through controlled CNOT gates and the weights are updated by Grover algorithm to amplify the amplitudes of weights. A few experiments are conducted on toy datasets and the results are reported.", "summary_of_the_review": "This paper is well organized but the authors may not be enough familiar with quantum computing. Quantum machine learning does face the problems of barren plateau and nonlinearity, but the proposed model does not fulfill the contributions listed by the authors. The qubit requirement is huge with only classification tasks can be done, and the only advantage in time complexity is brought by the Grover search they employed in the model. The training and testing procedures are not clearly explained and several circuits in the paper are not correct. We seek for a more quantum-oriented solution to QML instead of using quantum as a shell.", "strength_and_weaknesses": "Strength:\n1. The paper is well organized with the whole approach demonstrated in a logical way. It is pleasant to read the paper.\n2. Figures are properly used to illustrate points.\n3. Classical simulation and Qiskit are used in the experiment to show the efficiency of the model.\n\nWeakness:\n1. My foremost concern is why quantum. The whole proposed method from my observation is using NEGATE, XOR, AND, OR on the qubits and all of them are classical operators. As in Figure 13, apart from the low resolution, I can barely see any other gates that are complex. It seems to me that all the framework, except for Grover, is in the field of Real numbers. Each qubit is used as a 0-1 indicator and the word “superposition” only occurred in Section 3.2 (Quantum basics). I just wonder why all the effort to design such a quantum paradigm with all the components classical (and the Grover is used to push the qubit to either 0 or 1 which is exactly the same as nonlinear unit in classical ml). \n\n2. As for the first point in the contribution listed in section 1, the author said Quark is a gradient-free quantum learning framework. However, the Quantum model with classical optimization (QMCO) does not always use the classic gradient-based optimizers. For example, Qiskit uses a gradient-free method COBYLA to optimize VQE in the portfolio optimization tutorial [e]. There are many gradient-free optimizers that can be used in quantum models, so why not compare these methods?\n\n3. In the second point in the contribution, the authors used the phrase “outperform gradient-based methods”. However, there is no evidence to show that the results of Quark are better than gradient based QML. I think the proper words can be “faster than gradient-based methods”.\n\n4. In the third point in the contribution, the authors said “Quark can support complex ML models”. I think the authors ignored the qubit requirement of the proposed model, which is fatal to “complex ML models”. Using basis encoding itself requires lots of qubits as well as the qubits we need for all the parameters in the Weight and the Output and even repeat the data for k times. There are plenty of other QML approaches (e.g. QCNN [a], QRNN [b], QGAN [c], QLSTM [d]) and it is questionable for defining classification task as “complex” model.\n5. How the model is trained is not clarified in the paper. How to tune the weights using the labels y_i is not shown in the algorithms. Besides, when it comes to the test stage, what should we do about the y_i in D is not clear. If the dimension is changed, then the training and testing circuits should be two different circuits?\n\n6. In figure 8, the author proposed a FC layer and a ReLU circuits. The circuit for FC layer is wrong. W_1 and W_2 should act on X independently. However, according to the circuit, W_2 is applied to a state after W_1, which is different before W_1. As for 8(b), I don’t see the nonlinearity in the circuit since all the gates can be written in the unitary form and the number of qubits is not changed, maybe the author could further explain why this is nonlinear.\n\n[a] Iris Cong, Soonwon Choi, and Mikhail D Lukin. 2019. Quantum convolutional neural networks. Nature Physics 15, 12 (2019), 1273–1278.\n[b] Johannes Bausch. 2020. Recurrent quantum neural networks. Advances in neural information processing systems 33 (2020), 1368–1379.\n[c] He-Liang Huang, Yuxuan Du, Ming Gong, Youwei Zhao, Yulin Wu, Chaoyue Wang, Shaowei Li, Futian Liang, Jin Lin, Yu Xu, Rui Yang, Tongliang Liu, Min- Hsiu Hsieh, Hui Deng, Hao Rong, Cheng-Zhi Peng, Chao-Yang Lu, Yu-Ao Chen, Dacheng Tao, Xiaobo Zhu, and Jian-Wei Pan. 2021. Experimental Quantum Generative Adversarial Networks for Image Generation. Physical Review Applied 16, 2 (2021).\n[d] Samuel Yen-Chi Chen, Shinjae Yoo, and Yao-Lung L Fang. 2022. Quantum long short-term memory. In IEEE International Conference on Acoustics, Speech and Signal Processing. 8622–8626.\n[e] https://qiskit.org/documentation/finance/tutorials/01_portfolio_optimization.html", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "0x1eOTENbb", "reviewer": "Reviewer_o76V", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a quantum machine learning algorithm that can be trained without gradient descend, by applying the observation properties of quantum operators in a setting of superposition. The main idea is that a superposition is defined for the possible qubits describing the weights, datasets and outputs, with a function that produces the outputs according to the inputs and weights. Using Grover’s algorithm, the amplitudes for the probability of observing certain weights are amplified to maximize the training accuracy. Using many datasets in parallel and by simulating quantum operators, the method can learn different distributions of weights according to observations, setting a new direction towards a full end-to-end ``training” of quantum machine learning networks with new building blocks.", "summary_of_the_review": "The paper sets a step towards full quantum machine learning systems, by a carefully designed machinery to allow defining a superposition of quantum weights, observables and outputs, and with an amplifier module to drive the probabilities of the weights to move towards maximizing the task-specific accuracy.\n\nWhile the paper is technically novel, I miss some complexity analysis as well as a brief analysis of where do the authors think the main computational burden for the simulation comes from. ", "strength_and_weaknesses": "The paper is well written and presented, and all derivations are technically sound. The paper sets a new direction towards unifying previous methods on quantum machine learning. The method is solid and worth a read, with a devoted supplementary material to get the good amount of content that cannot be fit onto the main document.\n\nAs a reader with interest in the topic but with no downstream-specific experience with hands-on on tools like Qiskit, I feel almost obliged to ask what is the main reason for the computational demand and why the experimental setting has to be reduced to very simple tasks such as edge detection in 3x3 matrices and a 3-class sub MNIST problem. The paper does not include any computational analysis neither by means of the used tool nor by the capacities of having real instrumentation. Why are the experiments limited to such a simple setting and what are the computational resources required for a simulation based on Qiskit? Knowing such information would allow potential researchers to find out which are the practical limitations in a real scenario where one can resort to simulations only. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject