Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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.
strength_and_weaknesses: + new framework for quantum neural networks that avoids barren plateau
- using amplitude estimation within a quantum neural network makes it not really near-term
- there are many different ways of avoiding barren plateau that also keep the possibility of implementing the neural networks
clarity,_quality,_novelty_and_reproducibility: The paper is clear, the techniques are quite straightforward.
summary_of_the_review: Interesting idea but with many drawbacks and not enough novelty in the techniques
review_title: null

final_score: rating: 1: strong reject
review_content: 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. 
strength_and_weaknesses: Strengths:
- having empirical evaluation of the quantum approach is a plus

Weaknesses:
- 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. 
- 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.
- the datasets used in the empirical evaluation are extremely small (9 features). Is this related to basis encoding being used?
clarity,_quality,_novelty_and_reproducibility: The novelty of the approach is very limited - it relies on well-known ability to speed up search for good solutions (as provided by an arbitrary labeling function) by a polynomial factor using Grover's search / amplitude amplification. Due to the space and time complexity inherent to the method (see below), its significance for quantum machine learning in the near/medium term is also very limited. 

It is well-known that if input is encoded as a sufficiently-long binary string (e.g. one qubit per classical bit), then unitary computation is capable of performing arbitrary logical functions, same as classical computer, and can thus compute convolutions, pooling, activation functions, etc. The problem is that this requires impractically large number of qubits - e.g., the authors' mention using $d_w$ qubits to encode the model, where $d_w$ is the total number of bits in all the trainable weights of the model. 

The computational complexity analysis section mentions that the complexity does not depend on the training set size. Yet, consider number of samples that is below $N$, the VC-dimension of the model (for large networks, that could be a very large number of samples, larger than any practical dataset). Then, the model is capable of arbitrary labeling any training set of size $n \leq N$, indicating that the optimal (correct) labeling is one among $2^n$ possible labelings. In absence of any contrary analysis by the authors, one can assume that the volume of weights that lead to the optimal solution is exponentially (in $n$) small in the space of all possible weights - and the method has complexity growing with the inverse (in Thm 1, or the power of the inverse, in Thm 2) of that relative volume, i.e., complexity grows quite fast with $n$.
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.

As 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. 

clarity,_quality,_novelty_and_reproducibility: The paper is clearly written and it is of high quality. I believe the paper is novel but coming from a different domain I am not fully aware of related works.
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.

While 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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
strength_and_weaknesses: Strength:
1. The paper is well organized with the whole approach demonstrated in a logical way. It is pleasant to read the paper.
2. Figures are properly used to illustrate points.
3. Classical simulation and Qiskit are used in the experiment to show the efficiency of the model.

Weakness:
1. 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). 

2. 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?

3. 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”.

4. 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.
5. 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?

6. 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.

[a] Iris Cong, Soonwon Choi, and Mikhail D Lukin. 2019. Quantum convolutional neural networks. Nature Physics 15, 12 (2019), 1273–1278.
[b] Johannes Bausch. 2020. Recurrent quantum neural networks. Advances in neural information processing systems 33 (2020), 1368–1379.
[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).
[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.
[e] https://qiskit.org/documentation/finance/tutorials/01_portfolio_optimization.html
clarity,_quality,_novelty_and_reproducibility: See the weakness part and summary part, in general the novelty is moderate.
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.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper presents a gradient-free framework for quantum deep learning based on Grover's algorithm. The reviewers agree that the approach taken in the paper is not particularly new. There is also a lack of discussion of prior work. This is more minor in my view but some reviewers also pointed out the experimental evaluation could be more exhaustive (using larger datasets).

I note that there was very little to no discussion between the reviewers due to a large agreement the paper is not ready for publication. I myself largely agree with the reviewers. I'm therefore not able to recommend this paper for acceptance. I encourage the authors to address the complaints of the reviewers, and perhaps resubmit to a more specialized conference or journal in quantum computing.
justification_for_why_not_higher_score: Clear from metareview and scores from reviewers.
Decision: Reject