Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: Traditional Quantum Neural Networks suffer from poor trainability and one biggest reason is that the gradient vanishes exponentially with the input qubit number. 

The paper proposes Tensor Tree(TT) Circuits based Quantum Neural Network to avoid such problems, a sufficient theoretical analysis was provided.

It proved a training guaranteed lower bound of $\mathcal{O}(1/n)$  on the expectation of the gradient norm on TT and further proved a lower bound for  the expectation of the gradient norm that is independent from the input state.

A binary MNIST experiment was also conducted.

Advantages:
A.	Clarity: The paper is well written and easy to be extended. 

B.	Originality: The theoretical analysis is sufficient. This paper proposed a framework which can be employed for analyzing QNNs with other different structures in the future.

Disadvantage: 

A. Experiment: Although theoretical analysis is sufficient and convincing, the experiment does not convince me very much: 
1. In figure 4d, the blue lines showed that the training error is 10% larger than testing error. This should be analyzed. Does it mean that the chosen test data is not very sufficient to represent the performance of the model?
2. The classification accuracy is not a very good criterion to evaluate the binary classification performance, F1 score would be much appropriate.
3. Only 0-1 classification experiment was conducted, the results of some other pairs should also be provided.
4. I suggest that other tensor network Quantum circuits could also be compared.

B. Limitation: I believe that TT-QNN has better trainability and can solve the gradient vanishing.  This paper only discussed an example structure and it is doubtable to generalize to other structures.

C. This paper (with 20 pages) exceeds the maximum size of ICLR which is 8 pages. 

review_title: This paper has sufficient theoretical analysis but is limited in experimental evaluation. 

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors propose a new analysis of a certain type of trainable quantum circuits, namely Tree Tensor Quantum Neural Networks (TT-QNNs), that gives new and positive guarantees of its learning abilities. Using their methods, that include a specific encoding circuit and a specific loss function, the gradient of each parameter vanishes less badly compared to the usual Random QNNs. The authors demonstrate a lower bound on the (expectation value of the) norm of the overall gradient, which is also observed numerically. This could ensure a better trainability of these quantum circuits, which is of great interest. Their methodology could be used in other circuit designs. The article is well written and quantum computing concepts are well introduced, at least for an accustomed audience.

However, some remarks could cloud the main results. 

Major Remarks [concerning the encoding circuit] : 
- The encoding circuit seems poorly efficient: it has to be trained for each sample of the dataset. For each sample, the circuit has to be changed n times to scan all measurement configurations. For each configuration, multiple measurements are needed to estimate the gradient of one parameter among the 3xLxn ones (?). And then this has to be repeated through many iterations to reach convergence. Is this procedure realistic? Maybe it is considering that the circuit itself is shallow but repeated many times. A comment from the authors would be useful. 
- Worsening the case of the previous question, it seems that each time the encoding circuit is run, it is needed to have the quantum state |x_in>, the amplitude encoding of the sample, as input. How is it done in practice during the training part of each encoding circuit, since the authors themselves say that it seems unplausible to obtain such  states with near term quantum computers? 
- p.5 it is said that the simulation has been done "classically" on this part, why? No numerical simulation is shown to see how well the training happened. Is it efficient? Is the input state created close to the amplitude encoding objective?
- Finally, if the encoding circuit proposed in this work was not to be used, and if one would use a random encoding instead, what could be said on the bounds of alpha(ro_in)? Could this kill the benefit claimed and lead to a similar vanishing gradient as Random QNNs? 

Other Remarks : 
- In the complexity analysis of Algorithm 2, it would have been more informative to provide the runtime O(n_gate n_para n_train T) in terms of n, m, L, s, and other circuit parameters. This makes more sense to grasp the difficulty of the proposed method. And maybe to compare it to the Random QNN Complexity Analysis? At least in the Appendix. 
- The choice of the form of the objective function f in (2), and the loss function in (7) should be better explained. Has it been chosen to suit the binary classification set up? and/or to ensure the bound necessary during the proof of Thm.3.1?
- Same question for the choice of Pauli-Z based measurements in both encoding and classifier circuits. 
- Similarly, the authors should explain in the main paper the choice of using only RY rotations in the main circuit. It seems from reading the Appendix that it is for avoiding to have a unitary 2-design, is it? Could this restrain the applications, compare to what we see in a lot a (random) QNNs with the mixture of the three types of Rotations?

Minor remarks : 
- extra parenthesis in the qubit at the top of p.3
- p.7, is n_test renamed n_teXt and then n_infer? It is hard to follow. 
review_title: Toward Trainability of Quantum Neural Networks 

final_score: rating: 6: Marginally above acceptance threshold
review_content: ##########################################################################

Summary:

 
The design of a useful generalization of neural networks on quantum computers has been challenging because the gradient signal will decay exponentially with respect to the depth of the quantum circuit (saturating to exponentially small in system size after the depth is linear in system size). This work provides a detailed analysis of quantum neural networks with a tree structure that uses only a depth logarithmic in the system size. The authors show that the gradient signal will only be polynomially small with respect to the system size. The authors also provide empirical verification of the theoretical analysis showing a much larger gradient norm. However, the improvement in prediction accuracy (under early stopping) when using tree-structure quantum neural networks is not very significant. This is likely because the considered system size (8 qubits) is too small to fully demonstrate the exponential decay and the inability to train random quantum neural networks.

##########################################################################

Reasons for score: 

I think the theoretical analysis of the tree-structure quantum neural networks is nice. It provides a rigorous result for training a promising class of quantum neural networks. The proven result can be derived in a straightforward manner if we know that the gradient signal decays exponentially in the depth (which is not what was originally stated in the barren plateau paper [1], the result in [1] only shows an exponential decay in the system size after a depth linear in the system size). This is because a quantum neural network with a tree structure only has a log(n) depth, so the gradient norm would be 2^{-log(n)} = 1/n. However, I don't think this intuition that gradient signal decays exponentially in circuit depth is widely known, so this work still provides a novel contribution from a theoretical aspect.
 
##########################################################################Pros: 

Pros:

1. The barren plateau problem has been a challenge that the quantum machine learning community has to overcome. This work provides a promising class of quantum neural networks that do not suffer from the barren plateau problem.
 
2. The authors provide rigorous support for the proposed class of quantum neural networks.
 
3. A good set of numerical experiments supplement their theoretical analysis.

 
##########################################################################

Cons: 

 
1. The proven result can be derived in a straightforward manner if we know that the gradient signal decays exponentially in the depth.

2.  We do not see a large improvement in prediction accuracy when the random quantum neural network employs early stopping. For example, in fig. 4(a), we can stop at iteration 50~60 and the prediction error of the random quantum neural network would be fairly small.
 

 
##########################################################################

Questions and comments during rebuttal period: 

1. Lower bound should be $\Omega(\cdots)$ rather than $\mathcal{O}(\cdots)$.


2. The proposed TT-QNN will have a limited expressibility due to the logarithmic depth. Do you know any application where the target function can be represented using a TT-QNN?


3. I would strongly encourage the authors to run experiments with a larger system size (e.g., 12 to 15 qubits). Experiments with 8 qubits are too small and a gradient norm of 0.2 (for random QNN) is quite large. This is likely the cause of the lack of a large prediction advantage when using TT-QNN. Random QNN is just completely untrainable in large system sizes. Numerical experiments with a large system size will likely make the paper much stronger from an empirical perspective (if we can see a larger improvement in prediction error).


[1] McClean, Jarrod R., et al. "Barren plateaus in quantum neural network training landscapes." Nature communications 9.1 (2018): 1-6.
review_title: Review of "Toward Trainability of Quantum Neural Networks"

Meta-review: This paper introduces two new quantum neural networks with specific structures: TT-QNNs and SC-QNNs. The main contribution of this work is to show a theoretical lower bound that the gradient of the two neural networks (at random initialization) with respect to certain training objectives is well lower bounded by 2^{-2 L}, where L is the number of layers in the network. Previously, the known work only manage to prove this lower bound with less-realistic QNNs with 2-design, or prove an 2^{-poly(n)} lower bounds for random QNNs, where the input of the neural network is an n-qubit. This paper makes a first step towards solving the vanishing gradient problem of QNNs at random initialization. 



The major concern of the paper is the usefulness of these QNNs with proposed architectures: The proposed QNNs might be theoretically easier to train, but what if they can only learn a significantly smaller class of functions? In classical world, such phenomenons are very common: Linear classifiers (or even linear functions over prescribed feature mappings) are much easier to train and have much better theoretical properties, but they fail short in terms of representation power comparing to real neural networks.



In this paper, on the theory side, there is no argument about the representation power of these QNNs: It is unclear which set of functions they can represent efficiently, which limits their theoretical interests to machine learning committee. On the empirical side, the reviewers all agree that the empirical results are weak at this point: The proposed new QNNs did not show significant advantages over random QNNs (especially with early stopping), and other types of QNNs were not compared. Moreover, there seems to be some efficiency issue regarding implementing these QNNs -- More convincing empirical evidence or theoretical evidence about the power of these QNNs need to be addressed.  
Decision: Reject