Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper provides new approximation theorems for a family of functions representable by hybrid quantum-classical circuits. 


Specifically, the paper looks at neural nets that can be evaluated quickly by a three-stage circuit, where the second stage is quantum and the first and third phases are classical. The paper shows that neural networks in such a class allow for more efficient approximation of certain functions than (a) was previously known and (b) is possible using a related class of networks that can be implemented using an entirely classical circuit. 



Overall, I found the paper’s significance hard to evaluate. Here are a few questions I had a hard Time finding answers to in the text of the paper: 

- Why is this problem important to begin with? Is the bottleneck with neural nets their evaluation, or their training? Is the hope that by using quantum computers to evaluate complex NN’s we can allow for learning more complex functions? How would one train such networks?  I felt like the big picture was missing. I know my way around quantum computing and algorithms but still found the paper hard to read and understand. I think a typical ICLR audience-member would be entirely lost.

- The comparison with known bounds for classical circuits in Section 5 was quite hard to understand. Taking it at face value, the gains in complexity from moving to the quantum model seem limited: gains of $poly\log(1/\epsilon)$ in depth and circuit size? Is it clear that no better classical circuits are known for approximating the functions of interest? 

Some specific comments and suggestions: 

- Equation 1: What does it mean that y is bounded when sigma is a polynomial? Does sigma have to be such that it’s value is bounded on the range of possible inputs (something like $-(d+1)$ to $(d_1)$)?
- Expand the notation in the definition of equation (2). I interpreted it to mean that derivatives of up to order n are defined almost everywhere, and bounded. But the comment after that (when n=1 and f is not differentiable) confused me. 
- Lemma 3.3: how complex is the network as a function of delta? I had trouble mapping the form of $f_2$ into the form of the network. I guess it has something like depth 3 and a number of neurons equal to the number of possible $\mathbf{ k, v}$ pairs?
- I felt like what was missing at the end of Section 3.2 was a self-contained recap statement. 
- Moving the main Theorem statements (4.5 and 4.6) earlier to the introduction (along with the comparison to bounds for classical circuits) would help. (That is, explaining the result top-down, rather than bottom-up.) The effort to keep everything in mind until I got to final statements exceeded my stack depth. I like to think that I would have had no trouble understanding a more self-contained exposition of the main results.


review_title: hard to understand context and significance

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper considers the expressivity and approximation properties of machine learning models where a parameterized quantum circuit is used to 'accelerate' a classical neural network. The results consider a model with a date encoder, a quantum circuit, and then a classical feedforward neural net for post-processing. To make the results non-trivial only models with asymptotically similar classical and quantum complexity are considered.

Using a technique best on Taylor polynomial approximations, the paper finds that a large class of smooth functions can be approximated using O(log(1/\epsilon)^(n/d)) quantum gates, qubits,  and classical width. This is slightly (logarithmic factors of  1/\epsilon) smaller than the best known upper bounds with ReLU or unconstrained quadratic networks.

Pros:

The paper shows how some techniques used to obtain classical approximation theorems can be extended to quantum gates. The slight improvement from the addition of a quantum element raises the possibility of showing a stronger separation in the future.

Cons:
The results in their current form do not really show any benefit (from the point of view of approximation) for quantum neural networks, since the bounds are only logarithmicallly better than classical bounds. 

The technique used seems to be to use quantum units to mimic subfunctions in a manner quite similar to classical units, and does not provide much insight into why we should expect a 'quantum improvement' here.
review_title: Universal approximation theorem for parameterized quantum circuits

final_score: rating: 4: Ok but not good enough - rejection
review_content: The problem studied in this work is of interest in the quantum machine learning community, as the power of small and noisy quantum computers for machine learning problems is far from being understood. Therefore, it is important to study the expressivity of quantum neural networks as function approximators. This work uses the model introduced by Tensorflow Quantum, where different neurons can be implemented on either quantum or classical computers.

However, it is unclear how this result applies to current topologies of QNN/variational circuits used in current literature. From my knowledge of quantum variational circuits, the architecture proposed is different. To my understanding, this work addresses specifically the model proposed for TensorFlow quantum, and this should probably be made more explicit, as it's somehow different from current literature, where quantum neural network architectures are the sole computational node, and no classical computation is performed classically (besides the optimization of the parameters of the variational circuit). The model described in this work is called the "prologue, acceleration, epilogue".

If I understood the work properly, the role of quantum computers is to evaluate on a quantum computer the "binary" part of a Binary Polynomial Neural Network (this is what the authors call the acceleration phase), after in a prologue part the data is loaded as initial quantum state with a log-depth circuit.Then, in the epilogue phase, a nonlinearity, like a a ReLU function is applied classically,
 
It is really interesting the comparison with the approximation function of neural networks in classical computers. Perhaps more (recent) literature review on quantum expressiveness of other variational circuits can be added.
 
I checked some of the proofs in the manuscript, and they are correct. The paper is nicely written, but perhaps might benefit some more clarity, especially in the proofs in the appendix.

Overall, the submission would have benefited from experiments, showing that a QNN built with the architecture proposed in this work can achieve high accuracy in classification/regression tasks. This can be either done on small quantum computers, or even simulated in GPUs or large classical computers. Also, it would have been beneficial to write more clearly section 3.3, perhaps with an example, on how the classical optimizer is meant to choose the parameters of this circuit in a machine learning problem, i.e. how this architecture is meant to be used in practice.

Other remarks are the following:
- Please use a consistent notation for multiplication. If my understanding is correct, In proposition 3.2 and the subsequent lines, you use the notation $x \times y$, $xy$, and $x \dot y$ to denote the same operation.

-  In section 4.1 it's not clear to me what this sentence means:
 At the end of these operations, both zero states $\ket{0}$ in $Q_1$ and $Q_2$ are y, and the $\ket{0..}$ state in the combination of these two systems, $Q_{1,2}$ will be $y^2$. How can the zero register be $y^2$?
 
-  What is the $p$ in the Discussion section, when discussing the result of Yarotsky?

- I think in some parts of the paper the authors use $n$ for the number of qubits, and then $\log n$.

- Figure 1 could be split into two figures (left and right), and the notation in the figure could be better explained as the figure is referenced many times in the paper.

- Is written in the section where the  prologue phase is described "As pointed by Bravo-Prietoet al. (2020), unitary matrix A can be decomposed to the quantum circuit with gate complexity ofO(logn), where logn is the number of qbits." This is only true if the matrix $A$ is of the kind specified before, i.e. it's just one single column.

- The fact that the depth of BPNN in hybrid quantum-classical computing can be of $O(1)$ is a strong result that perhaps should be compared more with the literature on the power of quantum shallow circuits or constant depth circuits.  

Also, I think the work should conform to the widespread and standard notation of using qubits and not qbits.

 Some typos:
 - Proof Proposition 4.2. "the Of" should be "the of".
 - After lemma 3.3 "which is introduced in the following texts" -> which is introduced next (or in the following section).
 - "To take the advantages of high-parallel in quantum computing, we made an observation on the network structure of BPNN as described in the following Property." Might be improved. It might be changed into "high-parallelism" and rephrased the whole sentence.
 -Section 4.2
 "d input variables and f has weak derivative" should be derivativeS.
 - . This brings flexibility in implementing functions (e.g., ReLU), while at the same calls for interface for massive data transfer between quantum and classical computers. Perhaps you wanted to say "at the same time calls for fast interfaces"
review_title: On the Universal Approximability and Complexity Bounds of Deep Learning in Hybrid Quantum-Classical Computing

Meta-review: This paper provides approximation results for functions that can be represented by hybrid quantum-classical circuits. It is felt that venues such as QIP would be a more suitable venue, and perhaps some experiments/simulations could be added.
Decision: Reject