Accelerating Inference for Multilayer Neural Networks with Quantum Computers
Authors: Arthur G. Rattew
Po-Wei Huang
Naixu Guo
Lirandë Pira
Patrick Rebentrost
Venue: ICLR 2026 Poster (2026)
Keywords: quantum machine learning
QML
quantum algorithms
quantum deep learning
quantum computing
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: We introduce quantum algorithmic primitives enabling the first coherent quantum speedup of inference in multilayer neural networks.

Abstract: Fault-tolerant Quantum Processing Units (QPUs) promise to deliver exponential speed-ups in select computational tasks, yet their integration into modern deep learning pipelines remains unclear. In this work, we take a step towards bridging this gap by presenting the first fully-coherent quantum implementation of a multilayer neural network with non-linear activation functions. Our constructions mirror widely used deep learning architectures based on ResNet, and consist of residual blocks with multi-filter 2D convolutions, sigmoid activations, skip-connections, and layer normalizations. We analyse the complexity of inference for networks under three quantum data access regimes. Without any assumptions, we establish a quadratic speedup over classical methods for shallow bilinear-style networks. With efficient quantum access to the weights, we obtain a quartic speedup over classical methods. With efficient quantum access to both the inputs and the network weights, we prove that a network with an $N$-dimensional vectorized input, $k$ residual block layers, and a final residual-linear-pooling layer can be implemented with an error of $\epsilon$ with $O(\text{polylog}(N/\epsilon)^k)$ inference cost.

Published as a conference paper at ICLR 2026
ACCELERATING INFERENCE FOR MULTILAYER NEURAL NETWORKS WITH QUANTUM COMPUTERS
Arthur G. Rattew Po- Wei Huang*., Naixu Guot, Lirandē Pira', Patrick Rebentrost
Department of Materials, University of Oxford, Oxford OX1 3PH, United Kingdom
2 Mathematical Institute. University of Oxford, Oxford OX2 6GG. United Kingdom
3 Quantum Motion, 9 Sterling Way, London N7 9HJ, United Kingdom
4 Centre for Quantum Technologies, National University of Singapore, Singapore 117543
5 Department of Computer Science, National University of Singapore, Singapore 117417
ABSTRACT
Fault-tolerant Quantum Processing Units (QPUs) promise to deliver exponential speed-ups in select computational tasks, yet their integration into modern deep learning pipelines remains unclear. In this work, we take a step towards bridging this gap by presenting the first fully-coherent quantum implementation of a multi- layer neural network with non- non-linear activation functions. Our constructions mirror widely used deep learning architectures based on ResNet, and consist of residual blocks with multi-filter 2D convolutions, sigmoid activations, skip-connections, and layer normalizations. We analyse the complexity of inference for networks under three quantum data access regimes. Without any assumptions, we establish a quadratic speedup over classical methods for shallow bilinear-style networks. With efficient quantum access to the weights, we obtain quartic speedup over classical methods. With efficient quantum access to both the inputs and the network weights, we prove that network with N-dimensional vectorized input, & residual block layers, and a final "siidaallinear-pooling layer can be implemented with an error of e with (ooolylogNN/e))) inference cost.
INTRODUCTION
Within the past decade, deep learning methods (LeCun et al. become the mainstream methodology for tackling problems machine learning and generative artificial intelligence, including tasks in computer vision (He et al. 2016 Ho et al. 2020 Dosovitskiy
2015 Goodfellow et al.) 2016) have
2020) and various al. 202T). natural language processing (Vaswani al. 2017 Brown al.
other tasks with increasing applicability (Silver et al. 2016 Jumper et al. 2021
Fawzi et al. 2022).
This progress is partly facilitated by advances GPUs, which offer speed-ups for parallelizble operations such matrix-vector arithmetic. However, we approach the physical limits of Moore's law (Moore 1965), the continuous upscaling of CPUs and GPUs may begin to plateau. Consequently, natural question is whether quantum computing (Feynman 1982 1986 Nielsen & Chuang 2010) and potential quantum processing units (QPUs) can offer further acceleration for deep learning.
The field of quantum machine learning (QML) (Biamonte et al. 2016 Schuld & Petruccione 202 Du et al., 2025), investigates this possibility. QML can broadly be separated into two main paradigms: (1) quantum algorithms tailored to the structure of near-term quantum hardware (Preskill (018)) under assumptions of limited quantum resources, and (2) using quantum subroutines to obtain provable speed-ups for existing machine learning models, typically requiring large amounts of quantum resources necessitating error-corrected fault-tolerant quantum computers.
In the first paradigm, proposals of quantum neural networks (QNN) based variational quantum algorithms (VQA) (Peruzzo et al., 2014: Cerezo et al. (021]) train parametrized quantum circuits (PQC) (Benedetti al. 201 (019b) analogously multi-layer neural networks. However, these algo-
rithms face trainability issues in the form of poor local minima (Bittel & Kliesch 2021: Anschuetz &
Kiani 2022) and vanishing gradients, or barren plateaus (McClean al. 2018
Larocca et al. 2025).
aarrhur.attew.sccnnee@@@eee @mailll.mmmmmmmmmmmmmmmmm

---

Published as a conference paper at ICLR 2026
(a)
Conv
Fllatte
Squaree
Normalize
Pool
Square
"Cat"
Concatenatic
(b)
x
2D
Neural
Conv
Normaliz
Flatzen
Square
Normalize
1.2 Pool
Square
xd
"Cat"
Neunal Net
(c)
xx
2D Cony
Nomullze
Square
Xd
"Cat"
Neural Net
Figure 1: Architecture for Convolutional Neural Networks. This figure shows the architectures we consider with provable quantum complexity guarantees for inference under three regimes of quantum data access assumptions. (a) Depicts the architecture where both the inputs and network weights are provided in an efficient quantum data structure. (b) Only the network weights are provided in an efficient quantum data structure. (c) No input assumptions are made. In all architectures, the input is assumed be rank-3 tensor (e.g., images with 4 channels).
Moreover, techniques mitigating these issues often result in the algorithms being classically simula- ble (Cerezo al. 2025 Bermejo al.) (024).. While alternate approaches such as quantum kernel
methods (Havliček et al. 2019; Schuld & Killoran (019)) and others have been proposed (Benedetti
al. 2019a] Huang Rebentrost 2024), they often face similar trainability issues (Thanasilp et al.
2024
Rudolph et al. 2024).
The second paradigm focuses on the use quantum subroutines (Harrow al. 2009: Montanaro 2016; Gilyén et al. 2019 Dalzell al. (2255) to provide asymptotic speed-ups the underly- ing linear algebra of classical machine learning models, e.g., matrix inversion, matrix vector arithmetic, and sampling. Applications include support vector machines (Rebentrost al. 2014).
regression (Wiebe et al. 2012). feedforward neural networks (Allcock et al.] al.aall222222 2020), convolutional neural networks (Kerenidis al.) 2020), transformers
(Guo et al.] 2024b). ) and other models (Lloyd
et al., 2014 Wiebe et al. 2016 Rebentrost et al.
2018
Kapoor et al. 2016 Cherrat et al. 2024
al.
202Tb: Yang al. 2023 Ivashkov et al. 2024 Wang et al.] 2025). Other works have also
explored speeding up classical neural network training and inference (Kerenidis & Prakash, 2020
Abbas al.
2023
Liu et al. 2024).
Main Contributions. In this paper, propose method that can be used accelerate inference for multilayer residual networks (ResNets) (He et al.) 2016) on quantum computers, given their significance enabling deep networks (Xie al.) 2017: Dong et al., 202T). We provide quantum subroutines and techniques for regularized multi-flee filter 2D convolutions, sigmoid activations, exip-connections, and layer normalizations all of which we show can be coherently implemented on quantum computers. We list the main contributions as follows.
In Section 2]
we further develop modular vector-encoding framework for quantum matrix-vector arithmetic. This is special case of quantum block-encodings, with many useful properties.
we derive a novel quantum algorithm for the multiplication arbitrary full-rank and dense matrices with the element-wise square of given vector, without incurring rank-dependence. To the best of our knowledge, this is the first result which allows a quantum algorithm to utilize an arbitrary full-rank and dense matrix without Frobenius norm complexity dependence.
In Section 2.3
In Section 2.4 provide novel QRAM-free block-encoding for 2D multi-fitte convolutions.
2

---

Published as a conference paper at ICLR 2026
In Section 4, to the best of our knowledge, we derive the first coherent quantum implementations of multi-layer neural networks with non-linear activations. We provide rigorous end-to-end complexity proofs for inference under three QRAM regimes:
Regime 1 (inputs and weights provided via QRAM): Assuming QRAM access to both inputs and weights, for network with non-linear activations acting on N-dimensional inputs we prove O (ppolylog(NV) (/op))oggN//))) inference cost. Moreover, we argue that existing techniques are insufficient to dequantize this result.
Regime2 2 (weights provided via QRAM): When cost linear in the dimension of the input must be paid (i.e., no QRAM for the input). but the network weights are stored in QRAM, we prove quartic speedup over exact classical implementations for shallow architectures.
Regime 3 (no QRAM): In the absence of any QRAM, we prove quadratic speedup over an exact classical implementation.
The relevant architectures in each regime can be seen in Figure We derive number of techniques and algorithms which have broad utility in implementing machine learning architectures on quantum computers. However, our main focus is on accelerating inference for classification, with our formal problem statement given in Definition T] At a high-level, we assume that we are given trained neural network which, given an input, outputs a probability distribution over possible outputs (c.g.. over image classes). The goal is to draw sample from this output distribution (thereby assigning class to the input). We introduce an error parameter c, which allows the algorithm to sample from a distribution whose & norm distance from the true distribution is bounded by at most c.
Definition 1 (The Approximate Sampling- -Based Classification Problem). Let 0 S 1. Given a neural network represented by function h : RD + CC (i.e. with D-dimensional imputs and C' C-dimensional outputs) which returns probability distribution as its output (i.e., for any x E R,,, y := h(x) is all non-nege negative, and |ly|] = 1). then the sampling -based classification problem is to return a sample from some probability vector such that yyy ~ll S
For example, in the case of CIFAR-10, D 3 x 32 x 32 3072, and C = 10. Then, given some input x E R3372 y R 10 the entries of y correspond to the probability of assigning given class (e.g., class i is assigned with probability yi. etc). This problem statement also naturally captures other applications, such as autoregressive next-token prediction, where the output distribution would instead be over the set of possible tokens rather than classes.
Comparison to Prior Work. In prior work, to achieve multi-layer architectures in feedforward and convolutional neural networks as well as transformers, intermediate measurements for inner products (Allcock al. (2020) or quantum state tomography that read out the entire state (Kerenidis) et al. 2020 Guo et al.] 2024b) are required to extract information out to classical computers where data is required to be re-encoded into the quantum circuit for computation the next layer, breaking the coherence of the quantum architecture and limiting potential speed-ups. We compare against the prior work in Table To the best of our knowledge, our work provides the first fully coherent quantum implementation of classical multi-layer neural networks Further, our work is also the first in works that accelerate classical deep learning algorithms to present an architecture which does not use QRAM. Moreover, we demonstrate that careful tracking on bounds of the vector norm (as it propagates through the forward-pass of a given network) is required to prevent arbitrary decay of the norm in multilayer structures, and subsequent unbounded runtimes. We provide rigorous proofs and develop tools to prove this norm preservation in our architectural blocks. Further, we make the observation that residual skip connections that enable deep networks classically are fundamental to the norm stability and preservation, enabling us to provide an efficient and coherent multilayer architecture not present in prior work.
Notation. We use standard big and small O notations for asymptotics, using Ô to hide polylogarith- mic factors. The notation [N] represents the set of integers O,..., N - 1. We use kets to represent arbitrary (not necessarily normalized vectors). Logarithms are assumed to be base-2 unless otherwise stated. The subscript on the ket denotes the number of qubits it acts on (i.e., the log of the dimension), thus | E C²". When we assume a ket is normalized, we will explicitly state that it is. The one exception is with the definition of vector-encoding (as defined subsequently in DDefimition 3). For example, an (1, a, e)-VE for (e),, implicitly implies that [|] mll = 1, and so we will not explicitly state the normalization of the encoded vector every time introduce VE. A bra is defined as
3

---

Published as a conference paper at ICLR 2026
Architecture Coherent Coherent QRAM-
Norm Preser- vation
Polylog 1/e
Polylog N
Multi-
Non-
Free
Layer
Linearity
CNN Inspired
Cong et al. (2019)"
x
x
N/A
N/A
PQC
Allcock al. 2020)
Feed-forward
x
X
X
X
X
X
Kerenidis et al. (2020)
CNN
x
x
X
X
Guo et al. (2024b)
Transformer
X
-
X
X
Our work Regime 1
Residual CNN
Biliear
Our work
Regime 2
Residual CNN
Biliner
Our work Regime 3
X
Residual CNN
Table 1: Comparison with prior work. We briefly explain the meaning of each column. Coherent multi-layer refers to the construction of multi-layer architectures separated by non-linear activation functions without tomography. Coherent non-linearity refers the implementation of non-linear transformations on the quantum computer without readout. Norm preservation refers to the preser- vation of vector norms throughout the network forward pass. Next, each quantum implementation of a classical architecture incurs some еπто over the exact classical implementation, and as such an entry / in the polylog 1/e column indicates (pollylogl////)) (1/e) error-dependence, whilst X entry indicates (ppoly /c) error- prror-dependence Finally, polylog N refers to polylogarithmic complexity in the input dimension N. "Note: the architecture presented in Cong et al.) (2019), is inspired by CNNs but is based parameterized quantum circuits (PQC). As they do not aim to accelerate an existing classical architecture, it not possible to provide an entry the polylog column. Moreover, they do not provide complexities when considering classical input data, and we do not give an entry in the column corresponding to polylog N.
the conjugate transpose of ket, (1/n (v) f. We use the notation In to refer to n-qubit (i.e., 2" ""ddimensional) identity matrix. We define the Kronecker product with the symbol 8, and will sometimes refer this tensor product. We define basis functions both in vector notation and in ket notation, i.e., (j) = cj. E.g.. (0) Cy
0
0)² When we define a function f on scalars,
i..., f C + C, given vector æ E CN we sometimes use the notation f(x) := Σj= f(zz)ej. iee. f(x denotes element-wise application of to æ.
QUANTUM MATRIX- VECTOR ARITHMETIC
In this section, we define and motivate the tools necessary to perform quantum matrix-vector arithmetic, These subroutines are essential for our subsequent results implementing classical neural networks quantum computers. In[Section 2.1 we provide summary of quantum block-encodings and quantum vector encodings. Novel contributions this section: In /Section 2.2, we further develop the framework of vector-encodings, introducing trraihhtffrwart new quantum algorithms for vectors encoded as VEs, enabling vector sums, matrix-vector products, tensor products, and vector concatenations. In /Section 2.3] present novel algorithm which applies arbitrary full-rank and dense matrix to the alement-wise square a vector, without incurring a Frobenius norm dependence. Finally, in /Section 2.4 we give novel QRAM-free block-encoding for 2D multi-filter convolutions.
2.1 QUANTUM
AND VECTOR-ENCODINN
widely used tool in quantum algorithm design is the block-encoding Gilyen et al. 2019), which can be viewed way to encode and manipulate matrices in quantum algorithms. A block-encoding is a unitary matrix U, specified by quantum circuit, whose top left block contains matrix A (such that || < 1) which is scaled approximation to some matrix A. We give the formal definition in the following.
4

---

Published as a conference paper at ICLR 2026
Definition 2 (Block encoding (Gilyén et al. and a E N, then we say that the F x 2
2019)). Suppose that A 2 x 2" matrix, a, R. unitary matrix U is an (ar, a, enbooock-nncodiin of A, if
A a (0) @a do ()U 80 s T)ll 6.
(1)
Essentially, noting that (0) 8 & (1 0
0), see that (0) 0 / selects the first 2 rows of
U. and then (0)$0 8/ selects the first 2 columns of ((0) Sa IJU, meaning that (10) Sa ( (10) oa
I) is simply the top-left 2 x 2 block of U. Indeed, ife O. then A/a - ((0) oo ())
@ I).
Additionally, a can be viewed as an upper-bound on the normalization factor of A, e.g., if = 0, then
||A/a||/ S 1. Any matrix encoded in a sub-block of a unitary matrix cannot have norm exceeding 1.
Analogously to how a quantum block-encoding encodes general matrix in the top left block of a unitary, we can embed arbitrary -uub-normalized) N-diimeniional vectors in the first N rows of larger vector corresponding to a normalized quantum state.
This naturally leads to the following definition of quantum rector-encodings (VEs), the definition of which we take nearly verbatim from Rattew & Rebentrost (2023), where they were called SPBEs.
Definition 3 (Vector-Encoding (VE) (Rattew & Rebentrost 2023 Let a 2 I, a E N. and 2 We call the 20+m x 2n unitary matrix Up (a, a, c) VE for the 2n dd-menssiionl quantum state (n) if
l1 a (10)a @ In) (0)a))aall2 S.
Note that ((0), @ T,) (0)10) a+n corresponds to the exact vector encoded by Ug. specifically encoded in the first 2n rows of the first column of Uz.. The parameter a is measure of the norm of the encoded vector, e.g., if = 0 then (1(O), & I.)) Up 10)++1l12 = 1/a. One of the most essential components of working with matrix-vector arithmetic in quantum algorithms is tracking the norm of the encoded vectors throughout the algorithm, as the quantum complexity is usually inversely proportional the norm of the encoded vector. Vector encodings give methodical way to track encoded vector norms when implementing various matrix-arithmetic operations on the encoded vectors.
In summary, block-encodings provide a formal framework for working with matrices in quantum algorithms, and vector-encodings provide a formal way for working with vectors.
2.2 NEW OPERATIONS ON VECTOR ENCODINGS
To enable our results architectural blocks, we had to develop primitive operations on vector- encodings. These results are straight-forward modifications of existing techniques into the VE framework, but are necessary to allow easy tracking of the norm of encoded vectors, which is crucial parameter dictating the complexity of quantum neural network accelerations.
Lemma (Vector Sum, Proof in Appenddix Bj. Let 0 S T < L. We are given unitary circuits Up and Us which are (or, a, co) and (3, b,(1) VEs for (1)), and (0) respectively. Define e : max b), [T), = _lW),, + 1= == (l|T),,ll 122 and [T), == IT/n/N. Then, using one controlled U circuit, one controlled Us circuit, and two additional single-qubit gates, we can construct a unitary matrix V such that V is a (N-1.ct (2 + V)EN)-VE IT).
Lemma 2 Matrix-Vector Product, Proof in Appendix B). We are given an (or, a, (,,,a,,))-bi U for the n-qubit operator A, and UW a (3,b, for the Eg-normalized n-qubit quantum state W.). Let N ;= (,) 112. Us has Tr circuit complexity, and U has TA circuit complexity. Then, we can obtain an a + b - n qubit unitary U with (T + TA) circuit complexity such that U is an (a./N + b, (Co + /c1)/N) for the quantum state state A Alp))./N.
Lemma 3 (Tensor Product of Vector Encodings, Proof in Appendix B). Given Uv an (a, a, e)-VE for 11)) with (TT) circuit complexity, and Us an (8, b, 8)-VE (0)m with (TT₂) circuit complexity, then we can obtain the circuit V which is an (a.3 a + b, + 5 + co)-VE for (1)a @ (0)m with (m To) + max(n, b)) circuit depth.
Lemma 4 (Concatenation of Vector Encodings, Proof in Appendix B). Let D 24, N 2n, and 0 S < 1. Assume that d < n. Suppose are given set of D unitary circuits, (Ui)eeja such that each U, is an (ai, a, v)-VE for the quantum state (t)) with (TT) circuit complexity. Let
'If D not power of 2, padding can be added.
5

---

Published as a conference paper at ICLR 2026
Wiatn Ej=o 1all))) and let N == -IIl)a++al V
aj Then, we can obtain
(D/N, d a, for N= with (dDDT) circuit complexity.
2.3 MATRIX VECTOR SQUARED PRODUCT
We are now ready present the first key result of this section, showing how given matrix W (with [W]|2 I 1) and a vector encoding of æ, we can obtain a vector encoding of (xx)² The key idea to avoid obtaining a quantum block-encoding of the operator W (which in general requires W to be either low-rank, or sparse (Gilyén et al., 2019)). We then implement the product by using to coherently combine the columns of W weighted by the corresponding elements of the input vector, and then apply the result to modified version of the input vector.
Theorem 1 (Product of Arbitrary Matrix with a Vector Element-wise Squared, Informal). Let N =2. We are given matrix W E CNxN, provided via a pre-processed efficient quanium accessible data-structure Additionally, we are given the unitary Us with circuit complexity ((Ts), a (a, a, c)-VE for the quantum state (w) Define the function : C + R as g(x) = |x: and
N = (lg((())))) Then we can construct the unitary Uy which is N 2a 2n + 3, 20s
N --VE
for W Wo(lv).))N) and has ( + n2) circuit depth
This result is stated formally and proven as Theorem B. in the Appendix, and we formally define one possible implementation of the quantum accessible data-structure assumption in Definition B.3 To use
this to prepare the quantum state Wg W9((e),, //V,, N, the vector normalization result (Lemma B.8 can be directly applied to the output VE yielded by Theorem preparing the state with ( (T n 2) /NV
circuit complexity. This is the first such result without a Frobenius norm dependence on A.
We will now informally sketch the proof of this procedure. First, define the columns of W as wN-1). Define the normalized version as |w,) w// ||wz]l2- and define aj == |,,ll|2- We assume access three objects.
W = (wy
(1) A block-encoding of A := diag (an,-.. aN.)
(2) An oracle implementing Uw (0))) (wn)) (3) A vector-encoding for (1) = Σ Vy15)) Then, by using our vector-encoding circuit, we can get an encoding of (o) = E, { = (No(wol
"N-1(W1))" Then, using our block-encoding of A, we can efficiently get a block-
encoding of (aowoln ... aN. u (where In is 2n dimensional identity matrix, and only the first rows are non-zero). We can then use the product of matrix-encoding with vector encoding result take the product of aartonn vector-encoding.
0
aN, 2 with (o) yielding the desired
2.4 TRAM-FREE QUANTUM ENCODING OF 2D MULTI-FILTED CONVOLUTIONS
While the matrix- form of a 2D convolution has been given many times before in the literature, to the best of our knowledge the following is the first result giving block-encoding of QRAM-free 2D multi-filter convolution. We also stress that the following result can be highly optimized, especially QRAM is used. We leave such optimizations to future work. The full proof is provided in /Section B.2
Lemma 5 (QRAM-Free Block-Encoding of 2D Convolution With Filters). Let M =2", let n = 2m, let N = 2", and let D = 2d. Define the matrix form of the 2D multi-filter convolution operation, C E CCCM2xCMM as per Lemma B.17 Here, C represents the number of input and output channels, and D represents the dimension of the kernel over rows and columns (i.e., the kernel is a rank-4 4 tensor containing C. C x D x D filters). Then, after performing some one-time classical preccomputation, we can obtain a (1, 3 + 8D + 2 log(CD)) 0)- ennodinnn of 2(0 with O(m 3 D* log(C") log(D)) circuit depth.
C
While the degrees on the number of channels and the filter size D seem large, the filter size is usually quite small in practice (e.g., often 3). Moreover, there are straight-forwant optimizations of this result which can substantially reduce the degrees on both C and D. Convolutional layers are
For simplicity, here we are assuming that the parameter (as defined in Theorem B.
is to 77.

---

Published as a conference paper at ICLR 2026
Figure 2: Generic Residual Architectural Block. This diagram illustrates the structure of a typical residual block used in deep neural networks. The input vector is transformed through a sequence of operations: a learnable linear transformation W, a non-linear activation function f, and a residual (skip) connection that adds the original input the transformed signal. The output is then passed through a normalization layer (norm).
excellent candidates for QRAM-free implementation, since the number of parameters they contain are usually much smaller than the dimension of the vectorized tensors which they act upon. Indeed, of the matrix-form of
essentially obtain Lemma by efficiently constructing the highly-structun object corresponding to each parameter in the convolutional kernel, and then taking linear combination of the result. This explains why the complexity of our procedure is polylogarithmic in the dimension, whilst being polynomial in the number of parameters. This is in contrast exact classical algorithms which have polynomial dimension-dependenne. Moreover, our result can be substantially optimized further, potentially by exploiting the fact that circulant convolutions are diagonalized by the Fourier transform.
ARCHITECTURAL BLOCKS
In this section we will derive two key architectural blocks, residual block, and multi-layer residual block, which allow our subsequent complexity claims. We present an additional architectural block building on these in Appendix C but do not include in the main text as it is not essential for understanding the key complexity details of such quantum implementations.
Lemma 6 (General Skip Norm Block). Let 61 E (0, 1]. Let K E [1.2]. Consider the architecture shown in Figure 2) Let N = 2". We are given the unitary Up (1,a, 6n) for (&), with circuit
complexity 1) and are given the unitary Uw a (1, b. blobbecc-ennodingg for the n-qubit operator
W/R with circuit complexity OTT2) such that ||W]12 I 1. Define f(x) = erf(4x/50 /5). (1)))
I ((W))))) and := [Ilws)n l1z Then, we can obtain a ()) 702(0 - -1))-VE for n//N with circuit complexity Ologg(
log( + (a + 6 b n + Ti + T2))
The rigorous proof of this result is provided in Appendix C. but it essentially follows from using preceding results matrix-vent vector multiplication, vector sums, and the extant results layer normalization and applications of the error-function. The key insight enabling this proof is that in residual block such as the one we have described, the forward norm of the vector is efficiently lower- boundee prior to every normalization layer. Without such skip connection, and the techniques we developed for working with vector-encodinge (which enable effective tracking of the norm of vector propagating through network), the norm at the end of such block could be arbitrarily small, leading to complexities which could be on the order of N (or even unbounded) for k-layer architectures completely intractable even for constant depth networks. As a consequence, we are able to prove the following result for multi-layer residual blocks.
Lemma (Sequence of k Residual Blocks). Let N 2 Suppose we are given a unitary Up with circuit complexity O(Ti) such that it is a (1, a, -)-VE for (+).. Let k be an asymptotic constant. Suppose we have a sequence of k residual blocks (as per Lemma 6). with weights implemented by unitaries {Uw.1r Y such that Uw, (with circuit complexity O(T2)) is a (1, b, 0) -llo-blok--eee -llock-encodinggg. for the n n-qubit operator W2/ and Vi, [W, I 1. Then, we can prepare a (1, 2 (a + 2b + -). c)-VE for the output of the ls residual blocks with O(og(VN/cc(*
2h + n T₃ + T2)) circuit depth.
This result is proven Appendix C and follows by repeatedly invoking Lemma 6 with its output as the next input. It appears that the complexity of this result as a function of the number of layers k is
We implicitly assume that || W wn > 0, which is reasonable assumption for any input which comes from the same distribution as the training data.
7

---

Published as a conference paper at ICLR 2026
fundamental limitation of any quantum algorithm. As described in greater detail in Appendix C for a unitary matrix (a linear operator) to enact a non-linear transformation on a vector, its definition must in general be imput-dependent. Consequently, unless Lemma 6 be implemented with only a single copy of its input, it seems unlikely that this complexity can be avoided. This suggests that quantum computers are best suited for accelerating the wide and shallow regime, which is a popular regime for classical inference accelerators (since wide networks can be parallelized on classical hardware, but depth cannot be parallelized). Classically, with the aim of accelerating both inference and training, there are a range of techniques for compressing neural networks (Cheng al.) 2018). Moreover, classically, deep neural networks are much harder to accelerate than their shallow and wide counterparts (you can parallelize matrix-multiplin layers). Consequently, there are a number of classical architectures striving for shallow networks (e.g. Zagoruyko & Komodakis (2016)) which can serve as sources of inspiration for designing architectures best suited for quantum accelcration. We discuss this in greater detail in Appendix C
but not consecutive
4 ARCHITECTURES
We will now use the architectural blocks derived above to prove the quantum complexity in inference for the architectures shown in Figure I (a), which is then used to prove the complexity of the architecture in panel (b). A corollary is used to prove the complexity of the architecture in panel (c).
In all 3 regimes, the key architectural block shared in common is the sequence of k residual convolu- tional blocks, which is enacted by combining Lemma 5 aand 5|and Lemma 7] The architectures then only differ in how the input tensor is transformed, and in how the output of the & residual convolutional blocks is processed. Consequently, we will now provide high-level intuition for the important se- quence of & residual convolution blocks. First, Lemma 7 is simply obtained by chaining the result for a single residual block (given by [emma 6) k times, using the output of each invocation as the input for the next. Lemma 6 iftsll is implemented by enacting each of the vector-encoding operations corresponding to the operations shown in Figuure 2 matrix- vector multiplication via Lemma 2] non- linear activation via viamLemma 1 vector sum via Lemma I] and vector normalization via Lemma B.8] Noting that [Lemma B.19 and Lemma B.8 are forward improvements over the results from prior work, we delegate them to the appendix. It is also worth noting that our selection of the erf activation function is not restrictive, and was selected for analytical convenience. This could easily be swapped with other activation functions compatible with Lemma B.18 e.g., GELU or tanh. Finally, the last key piece of intuition regards the dimension of the specific vectorized tensor which is input to the sequence of i residual blocks. In Regime 1, this tensor is simply fixed concatenation of the input tensor, and consequently for an input with vectorized dimension ( has dimension O(N). In Regimes and the input tensor is mapped through a tensor product d times, resulting in an input to the residual block sequence of dimension O(N2) (when d = 2).
Thus, our results in all 3 data-access regimes all follow from the general result, formally stated below:
Theorem 2 (General Multilayer Convolutional Network with Skip Connections). Let M = 2n N 2nh M2.. Consider the neural network architecture shown in Figure i (a). Let the input X be rank- Lank-3 3 tensor of dimension 4 x M x M (with an R, G. B and null channel, where the null channel has all Os). Assume that [\vec(X)]l = 1, and that we have access to a unitary Ux that is a (1, 0)-E for the input in column-major layout | = -i= E5=0 Ed' Xx,k,31/2255) (k) Assume that Ux has O(Tx) circuit complexity. As shown in the figure, we have a sequence of k residual convolutional layers, where each convolutional layer has 16 input channels, 16 output channels (i.e., 16 filters) with filter width and height 3. L.e., each convolutional layer has 16 16 x 3 x 3 = 2304 parameters. Assume that there is 0 padding so the inpul and oulputs always have the same dimension, and that there is stride of 1. Suppose each convolutional layer has been regularized, so that its spectral norm is at most 1. Let W represent the N x N full-rank linear layer applied in the final output block of the network, and assume that ||W]] < L. Let C represent the number of output classes, and assume that C = 2 (padding can be added otherwise), Let the overall network be represented by the function h T 4 + RCC Let y = h((X) (and note that || = 1, and y E RCC. Then, with 2 + n²)) total circuit depth, and with ( n) ancillary qubits, we can draw a sample from an e e1normalizedd C-dimensional vector y such that 1yy U11ق <.
O Olog(
N (
8

---

Published as a conference paper at ICLR 2026
Proof. We have a 4 channel input and we want to map this to 16 channel in- put (by concatenating | vector with itself 4 times). Let [x) :=
Vi ((X 2+2mm (X (-m (X (X12+2m)*. ) We can invoke Lemma 4 with Ux four times, obtaining a (1,0.0) for 4 with ((xx) circuit complexity. Using Lemma 5 for each of the 0, .... k- convolutions, we can obtain a (1, 27, 0)-blloc--nncoding for C//2T|Call, (the matrix form of the corresponding convolution) with O(m²) circuit depth. Consequently, we can invokeLLemnn 7 to obtain Usonv a (1, 2 (63 + n)),)) <)-VE for the fz-normalized output of the sequence of l residual blocks. Moreover, Usomy has O(log( (ooo(v// (/N/////////// 2 + Tx + m²)) circuit depth. Then, we can invoke Lemma C.2 with Useny to draw a sample from some probability vector ÿ RCC such that ll y S c with O(log( v /c)))22 2k++ (Tx + +2)) circuit depth and with O(2" n) ancilla qubits. O
An important point to consider is that in order for a unitary matrix (or more generally, any linear operator) to enact non-linear transformation, its definition must depend on the vector it is being applied to. For instance, consider the simple example where we are given a vector æ, and we define A = dz). Then, Ax (x)² (with the square applied clement-wise which is clearly a non-linear transformation. Consequently, our algorithm for Theorem 2) adaptively (and efficiently) constructs a new circuit on the fly for each new input this is accounted for in the result statement.
4.1 KEY RESULTS UNDER DIFFERING QUANTUM DATA ACCESS ASSUMPTIONS
The feasibility of quantum random access memory, the primary method assumed in the literature for accessing classical data in quantum algorithms, is widely debated in the literature (Jaques & Rattew 2025). However, recent work (Dalzlll et al. (025a) provides a promising path forward, addressing many of the limitations raised in Jaques & Rattew (025).. Regardless, algorithms papers often fail to meaningfully address the memory assumptions they make, and so we include a comprehensive discussion of in AAppnndxx D highlighting the feasibility of the technology, and that importantly our QRAM assumptions are no stronger than the usual made in such algorithms papers. The key concept discussed in Appendix Djis that any algorithm utilizing a QRAM device must consider the classical opportunity cost of using that device, which dictates the constraints placed on realizing useful QRAM (e.g., for such purposes the physical QRAM device cannot simply be implemented in the circuit model).
Regime 1: Input and Network Use QRAM. The primary purpose of the architecture we presented in Regime 1 is to show that quantum computers can implement multi-layer neural networks based on real architectures coherently, with reasonable input assumptions, and with cost polylogarithmic in the dimension of the network. As per the main-text in this regime we assume that the matrix weights (in particular for the final full-rank linear layer) and vectorized input are provided via QRAM. The architecture for this regime is shown in Figure (a). Let the dimension of the vectorized input be O(N). Since the input is provided via QRAM, Tx as defined in Theorem 2 is Tx E (polyyogg( N)) (see, Section D.2). Thus, for constant number of layers k, the cost to perform inference (in accordance with Definition 1 becomes (polylog( /N /c)²). Please see Section 1 for a detailed discussion outlining important application areas where such input assumptions are practical (namely, where the input can be constructed in an amortized fashion online). Moreover, in [Section E. we also discuss considerations relating the receptive field of such architectures, and argue that existing techniques are insufficient to dequantize this result.
Regime 2: Network Stored in QRAM, Input Loaded Without QRAM. The architecture in this regime is shown in Figure I (b). The architecture contains d paths of purely classical neural networks. which each operate on (N) dimensional (vectorized) inputs. These classical architectures are assumed to have Ö(N) time complexity in terms of the input. These separate paths are then normalized, converted to quantum states, and then the Kronecker product of the result is taken. The result is fed into exactly the same architecture as in Regime 1. This architecture is inspired by bilinear determine the cost of this architecture, we can
neural networks (Lin et al. 2015). Consequently, again invoke Theorem Here, we need to pay Ô(N) ) cost to load each of the input paths in as a quantum state (via brute-force (Plesch & Brukner 2011).Txx E O(N). Consequently, we obtain
an overall algorithmic complexity of O(N log( 2
2k). which for constant k and d, simplifies to

---

Published as a conference paper at ICLR 2026
((N)og(1/))))) When d = 2, the dimension after the tensor product is N2. Consequently, the final linear layer contains a matrix multiplication of an N2² x N2 matrix with an N dimensional vector, which takes (2(N+) time. Consequently, for constant K, this architecture produces quartic speedup for the inference problem defined in Definition 1 over exact classical computation. When d 1, the speedup due to the final layer is instead quadratic. This speedup can be increased by setting d to larger values.
Regime 3: No QRAM. This architecture is identical to the one presented in Regime 2, only dropping the final full-rank linear block. In Section E.3 we show that the architecture in Figure (c) can perform inference with a total O(N log (1)))==))))) circuit complexity. Since the dimension of the vector acted on by the 2D convolution is O(N") (when d=2), the classical cost to compute this is (((N)); showing a quadratic speedup over an exact classical implementation. The speedup can be made asymptotically larger by increasing d. We have more detailed discussion of this regime
in Section
CONCLUSION
This work proposes a modular framework for accelerating classical deep learning inference using fault-tolerant quantum subroutines. Our approach offers direct quantum implementations of important neural network architectural blocks (such as convolutions, activation functions, normalization layers, and residual connections), and uses structured primitives such as quantum block-encodings.
In summary, we provide a number of novel theoretical contributions. We further develop the VE framework for quantum vector encodings. We derive a novel quantum algorithm for the multiplication of an arbitrary dense and full-rank matrix with the element- -wise square of a given vector, which to the best of our knowledge, is the first such result which does not incur a Frobenius norm (and thus rank) complexity dependence. We provide a novel QRAM-free block-encoding of multi-filter 2D convolutions. We then prove the first end-to-end complexity guarantees for the coherent quantum acceleration of multi-layer neural network inference, under three QRAM regimes. In the first regime, we give complexity which is polylogarithmic in both the dimension of the input, and the number of parameters in the network. In the second, we show quartic speedup over exact classical computation. In the third, we show a quadratic speedup.
FUTURE WORK
To the best of our knowledge, this is the first paper to implement multi-layer neural networks coherently on quantum computer, and as such, many important open directions of research remain. Moreover, progress towards achieving practically passive QRAM is important for realizing the speedups in the first two regimes. Moreover, exploring the connection between this work and the techniques utilized in scientific computing (e.g., quantum differential equation solvers, finite
difference methods, etc (Cao et al., 22013] Montanaro, 2016 Childs et al., 2021 Berry & Costa
2024 Jennings et al.] 2024] An et al. 22266; [Shang al. 2025 Liu et al. 202 laj 2023] Krovi
2023
Costa et al. 2025 Wu et al. 2025)) would be interesting. Most importantly, we wonder if
is possible to coherently enact sequences of non-linear transformations without exponentially increasing circuit depth (and with polylogarithmic crror-dependence) thereby allowing very deep multi-layer architectures to be quantized, but we suspect that this may be provably impossible (at least in general). Furthermore, it is conceivable that an approach enacting the non-linear transformations coherently with techniques based on QPE (Mitarai et al., 2019) might be able enact a sequence of non non-linearities without exponentially increasing circuit depth (albeit at the cost of an exponentially worse and exponentially decaying error-depende derrnddeenddncc). Combining such approaches may let quantum computers coherently accelerate architectures with depths of e.g., up to 25. Alternatively, one could combine sequences of coherent multi-layer architectural blocks with intermittent tomography to reset the depth cost, in essence fusing the techniques presented in our paper with those used in the prior work. would also be worthwhile to explore accelerating UNet based architectures, as many of techniques directly apply, and distilled UNet-based diffusion model could potentially be quite shallow. Finally, while this work assumes our networks are trained classically, it would be interesting to explore how the techniques develop could also be used to help accelerate training.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
AGR would like to thank Simon Benjamin and Sam Jaques for helpful discussions about QRAM. AGR acknowledges support from the Engineering and Physical Sciences Research Council (EPSRC) project Software Enabling Early Quantum Advantage (SEEQA) under grant EIP/000455//, and additionally acknowledges support from Quantum Motion. PWH acknowledges support from the EPSRC Doctoral Training Partnership (DTP) under grant EP/W52431 1/1, with CASE Conversion Studentship in collaboration with Quantum Motion. PWH further acknowledges support from the Ministry of Education, Taiwan, for Government Scholarship Study Abroad (GSSA) and St. Catherine's College. University of Oxford, for an Alan Tayler Scholarship. NG. LP, and PR supported by the National Research Foundation, Singapore, and STSTAR under its CQT Bridging Grant and its Quantum Engineering Programme under grant NRF2021 1-2201-QEE2-02-PPP- NG also acknowledges support through the Research Excellence Scholarship from Sandbox LP additionally acknowledges support from the Alice Postdoctoral Fellowship, awarded by the Centre for Quantum Technologies, National University of Singapore.
AUTHOR CONTRIBUTIONS
AGR conceived of the project, led it, and developed the theory. PWH contributed to the design of the architectures considered, and produced the key figures. AGR and PWH drafted the original manuscript. PR supervised the project, and provided input on the theory. NG verified the proofs. LP helped position the paper over prior work. All authors contributed the final manuscript.
REFERENCES
Amira Abbas, Robbie King, Hsin- Yuan Huang, William J. Huggins, Ramis Movassagh, Dar Gilboa, and Jarrod McClean. On quantum backpropagation, information reuse, and cheating measurement collapse. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 44792-44819, Curran Asso- ciates, Inc., 2023. URL
les/ es/paper/
Kazi Main Uddin Ahmed, Math HJ Bollen, and Manuel Alvarez. A review of data centers energy consumption and reliability modeling. IEEE access, 9:152536-152563 2021. URL https
//doi. 1109/ACCESS.
2021 .11.50922
Jonathan Allcock, Chang- Yu Hsich, Iordanis Kerenidis, and Shengyu Zhang. Quantum algorithms for feedforward neural networks. ACM Trans. Quantum Comput., 1(1), October 2020. URL
https://dos worg/.r....... 1145/3411466
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bue, E. Fox, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems. volume 32. Curran Associates, Inc., 2019. URR htttps::/ppocceeeaaetpe newriss..eeuuruuecmeeeeee wwt.cpepppppeeeeeeee wwwes//appr//////// hash/ /etp///aaae22277255522222.
(eweeaa11111888888888 Abstract. httttttttttmmll
Dong An, Akwum Onwunta, and Gengzhi Yang. Fast-forwarding quantum algorithms for linear dissipative differential equations. Quantum, 10:1986, January 2026. ISSN 2521-327X. URL
https://don wttpa//.2///..1111111.
22331/ 100a-2266-000 -1-8-996
Eric R. Anschuetz and Bobak Kiani. Quantum variational algorithms are swamped with traps. Nature Communications, 13(1), December 2022.
s 44167 022 35364-3
Ryan Babbush, Jarrod R. McClean, Michael Newman, Craig Gidney, Sergio Boixo, and Hartmut Neven. Focus beyond quadratic speedups for coror-correcte quantum advantage. PRX Quantum, 2:010103, Mar 2021. URL https: //tink///nk.... aps. org/doi/10. 1103/PRXQuant um. 010103

---

Published as a conference paper at ICLR 2026
Marcello Benedetti, Delfina Garcia-Pintos, Oscar Perdomo, Vicente Leyton-Ortega Yunseong Nam, and Alejandro Perdomo-Orth A generative modeling approach for benchmarking and training shallow quantum circuits. npj Quantum Information, 5(1), May 2019a. URL https://dol
org/ 100..1038/00000 000034881141 534 031-011-555---
Marcello Benedetti, Erika Lloyd, Stefan Sack, and Mattia Fiorentini. Parameterized quantum circuits as machine learning models. Quantum Sei. Technol. 4(4):043001, November 2019b. URL
http://doi.org
Pablo Bermejo, Paolo Braccia, Manuel S. Rudolph, Zoë Holmes, Lukasz Cincio, and M. Cerezo. Quantum convolutional neural networks (effectively) classically simulable, 2024. URL https
//arxiv. www./a////a/a.ao.oo.a/....a....t 2408 12739
Dominic W. Berry and Pedro C. S. Costa. Quantum algorithm for time-dependent differential equations using Dyson series. Quantum, 8:1369, June 2024. URL /nttss://aoioor//11
22331/q 2024- 06 13 1369
Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549(7671):195-202 2016. URL /RRLattss///o0.0rg//11
1038/nature2:0
Lennart Bittel and Martin Kliesch. Training variational quantum algorithms is NP-Hard. Phys. Rev. Lett., 127:120502, Sep 2021. URL hetps://link aps wtgp/oo/lo.ooaae
PhysRevIett
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agar- wal, Ariel Perbert-Vosss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Ma- teusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCan- dlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Curran Asso- ciates, Inc., 2020. URLLtttpp::/pproeeeddnsss 11l///1577c0 0000///88715570000tto0o/11111122 abstaaaatttttttaaaattaatttaaat.e httm
Daan Camps and Roel Van Beeumen. Approximate quantum circuit synthesis using block encodings. Phys. Rev. A, 102:052411, Nov 2020. URL htttps://inkk.e http://iin...p.....ooo/oo....... http////////..11//.
PhysRevA. 102. 052411
Daan Camps. Lin Lin, Roel Van Beeumen, and Chao Yang. Explicit quantum circuits for block encodings of certain sparse matrices. SIAM J. Matrix Anal. Appl., 45(1):801-827, 2024. URL
Yudong Cao, Anargyros Papageorgiou, Iasonas Petras, Joseph Traub, and Sabre Kais. Quantum algorithm and circuit design solving the poisson equation. New Journal of Physics. 15(1::11302. January 2013. URL https: //t.////.///// ttt.:/oo..oooooo.ooooooooooooo.. 10. 088 / 11777-36--777 2630 /1/0///5/11/ 10100/1551111000000 00110
Aaron Carroll and Gernot Heiser. An analysis of power consumption in smartphone. In Proceedings of the 2010 USENIX Conference on USENIX Anmual Technical Conference, USENIXATC 10. pp. 21, USA, 2010. USENIX Association. URL httpht/:::/ 1855840. 18558611
.ac. wttp./////oo/1..55.....
M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles. Variational quantum algorithms. Nut. Rev. Phys, 3(9):625-64) 644, August 2021. URL
1038/s4222 021-00348-1
M. Cerezo, Martin Larocca, Diego Carcía-Martín, N. L. Diaz, Paolo Braccia, Enrico Fontana, Manuel S. Rudolph, Pablo Bermejo, Aroosa Ijaz, Supanut Thanasilp, Eric R. Anschuetz, and Zoë Holmes. Does provable absence of barren plateaus imply classical simulabil- ity? Nature Communications, 16(1), August 2025. URL https:/ h/op:://do.. /oo. 1ool.org/1o.10300
941467-025 63075-63339-66
12

---

Published as a conference paper at ICLR 2026
Shantanav Chakraborty, Aditya Morolia, and Anurudh Peduri. Quantum reg.uurreeegguurieeeee least squares. Quantum, 7:988, April
URL htt.:ttto./..olooooo...222333/22
Yu Cheng, Duo Wang, Pan Zhou, and Tao Zhang. Model compression and acceleration for deep neural networks: The principles, progress, and challenges. IEEE Signal Processing Magazine, 35
(1):126-136, 2018. URL Utthttps:: /tttps::/doi.... http//di..ooo.gg/// 1009900..1..PP 2017 7 2765695
El Amine Cherrat, Iordanis Kerenidis, Natansh Mathur, Jonas Landman, Martin Strahm, and Yun Yvonna Li. Quantum vision transformers. Quantum, 8:1265, February 2024. URL
https: wttp//oorgg///. 20w.1..222202222 2024 02-222-2222212222 1265
Nai-Hui Chia, András Pal Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang. Sampling- sublinear low-rank matrix arithmetic framework for dequantizing quantum ma- chine learning. Journal of the ACM, 69(5):1-72, October 2022. URL
1145/3549524
Andrew M. Childs and Nathan Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Information and Computation, 12(11 & 12):901-924, November 2012. URL
https: :/do::///i .org/I0 6. 264216177 1/T11////1122222 11-12-111211
Andrew M Childs, Jin Peng Liu, and Aaron Ostrander. High quantum algorithms for partial differential equations. Quantum, 5:574, 2021. URL
9- 2--2011-11100 1121-111-0-574
Iris Cong, Soonwon Choi, and Mikhail D. Lukin.
Quantum convolutional neural networks.
Nature Physics, 15(12):1273-227 August 2019.
URL http:///ol.orx/100.00
641567-019-0648
D. Coppersmith. An approximate Fourier transform useful in quantum factoring, 2002. URL https://arra wwtpoo/gg//b/aaooooo
0ahh0220066 -02
Pedro C. S. Costa, Philipp Schleich, Mauro E. S. Morales, and Dominic W. Berry. Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescal- ing. upj Quantum Information, 11(1), August 2025. URL 84 641534-000 0204-022-0108--
Marcus Cramer, Martin B. Plenio, Steven T. Flammia, Rolando Somma, David Gross, Stephen D. Bartlett, Olivier Mandon-Cardinal, David Poulin, and Yi-Kai Liu. Efficient quantum state tomog- raphy. Nature Communications, 1(1), December 2010. URL https: //tp/////ii////o/ wttp:/o..../....00.00..00......0
ncomms 1147
Alexander M. Dalzell, András Gilyén, Connor T. Hann, Sam McArdle, Grant Salton, Quynh T. Nguyen, Aleksander Kubica, and Fernando G. S. L. Brandão. A distillatiionneeeepotttiion protocol for fault-tolerant QRAM, 2025a. URL http::::::/....... htt.:/ttpp.//aa.....rooo///o/// www.ii.rrgabbb//5000000 20265
Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão. Quantum algorithms: A survey of applications and end-to-end complexities, April 2025b. httlhttts///do..rrrt
9781009639651
Yihe Dong, Jean-Baptiste Cordonnier, and Andreas Loukas. Attention is not all you need: pure attention loses rank doubly exponentially with depth. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning. volume 139 of Proceedings of Machine Learning Research, pp. 2793 2803. PMLR, 18-24 Jul 2021. URL wtt.mm/pppesss.eeeeeeeeeee http:///w11///g/2ll.... html
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2021. URL /Rtpatpss:///eeeeeeeeeeeee //operrevee// net/ c
13

---

Published as a conference paper at ICLR 2026
Thomas G. Draper. Addition quantum computer, 2000.
Saatt-ph00000333
Yuxuan Du, Xinbiao Wang, Naixu Guo, Zhan Yu, Yang Qian, Kaining Zhang, Min-Hsiu Hsieh, Patrick Rebentrost, and Dacheng Tao. A Gentle Introduction to Quantum Machine Learning.
Springer Nature Singapore, 2025. doi: 10.1007/978-981--1 981-7988-8819555 1284-3. URL hetps://da
org #tg/10.1 10..1007/778-0 981 90----95-1------- 1284-3
Xiaobo Fan, Wolf-Dietrich Weber, and Luiz Andre Barroso. Power provisioning for warchouse- sized computer. SIGARCH Comput. Archit. News, 35(2):13-23, June 2007. URL https
1250665
Alhussein Fawzi, Matej Balog, Aja Huang. Thomas Hubert, Bernardino Romera-Paredes, Moham- Mohamm madamin Barckatain, Alexander Novikov, Francisco J. R. Ruiz, Julian Schrittwiese,, Grzegorz Swirszez, David Silver, Demis Hassabis, and Pushmeet Kohli. Discovering faster matrix multipli- cation algorithms with reinforcement learning. Nature, 610(7930):47-533 October 2022. URL 1222-5172-
wrg.10. 101.0.1130844410
Richard P. Feymman. Simulating physics with computers. International Journal of Theoretical
Physics, 21(6-7):467-485 June 1982. URL http://://///1.../0001.11100.100 0F0/01022757999
Richard P. Feynman. Quantum mechanical computers. Foundations of Physics, 16(6):007-331, June
1986. Ut//stppss///o...rr//0001111///1
Sevag Gharibian and François Le Gall. Dequantizing the quantum singular value transformation: Hardness and applications to quantum chemistry and the quantum PCP conjecture. SIAM Journal Computing, 52(4): 2023. URL (ttts::: oog//.oorr//01. 111..11.11111111111111
András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pp. 204, New York, NY, USA, 2019. Association for Computing Machinery. URL httpp:: /tttps://doi.org/10 org/10 1145/33 32 76. 331 6366
Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Architectures for quantum random access memory, Phys. Rev. A, 78:052310, Nov 2008a. URL httph:tt///tttt aps. ort/orogg///oooo. httg/doo/100 1103/PhysReva. 78. 052310
Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Phys. Rev. Leu. 100:160501, Apr 2008b. doi: 10.1103/PhysRevL.tt 10. 160501. URL https
aww.kkap....//////111 http:///w...111///yeeeiettt..... 100. 160501
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016. URL
org
Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael J. Cree. Regularisation of neural
Lipschitzzcontiinity networks by enforcing Lipschitz continuity. Machine Learning, 110(2):393-416, December 2020.
URL
Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions, 2002. URL/httpe:s//rriii..rr//bbb/ pph0000111100011111111
Naixu Guo, Kosuke Mitarai, and Keisuke Fujii. Nonlinear transformation of complex amplitudes
via quantum singular value transformation. Phys. Rev. Res., 6:043227, December 2024a. URL
wtwpr///////// hittps://1imm aps ottp
6.043227
Naixu Guo, Zhan Yu, Matthew Choi, Yizhan Han, Aman Agrawal, Kouhei Nakaji, Alán Aspuru- Guzik, and Patrick Rebentrost, Quantum transformer: Accelerating model inference via quantum linear algebra, 2024b. URL
16714
Connor T Hann. Practicality of quantum random access memory. PhD thesis, Yale University, 2021.
URL httpt:::///.m.. ///pps://e.... https://eiischhhhlo wscholarrr......ooo wttpoollaa.bbbrryyrr
di http:///gsssasssssaaaattt......a ssertations/
14

---

Published as a conference paper at ICLR 2026
Connor T. Hann, Gideon Lee, S.M. Girvin, and Liang Jiang. Resilience of quantum random access memory to generic noise. PRX Quantum, 2:020311, Apr 2021. URL httts::/ aps org/doi/10.n 1tt.:..1113//PPO1e....
2 020311
Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 103: October 2009. URL https: aps org/
105/100.100//Pyysseeee
1035550022
Vojtéch Havlíček, Antonio D. Córcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow, and Jay M. Gambetta. Supervised learning with quantum-enhannced feature spaces. Nature, 567(7747):209-212 March 2019. URL
111586-119-0980
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings the IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 770-778, 2016. URLhttps http://a....gg..111///////// 2016.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neu- ral Information Processing Systems, volume 33, pp. 6840-6851. Curran Associates, Inc., 2020. URL htttps: ottp://ceeeeccoooo..o.ooo...eeaa /ttp://ppper_illeepppe////020 hash/ haca//ccbccccc8888a2000111113.11
neur ptpp
Fang-Yu Yu Hong, Yang Xiang, Zhi-Yan Zhu, Li-zhen Jiang, and Liang-neng Wu. Robust quantum random access memory. Phys. Rev. A, 86:010306, Jul 2012. URL htttps://link. aps org/
do1/10.1103/Pay
86. 010306
Po- Huang and Patrick Rebentrost Partavariational quantum neural networks, 2024. URL
htttps://axiv> org 2307.10560
Petr Ivashkov, Wei Huang, Kelvin Koor, Lirandë Pira, and Patrick Rebentrost. QKAN: Quantum Kolmogorov-Amoll networks, 2024. URL hol.atttt..//aar....rrr/////////
04435
Samuel Jaques and Arthur G. Rattew. QRAM: A survey and critique. Quamtum, 9:1922, December 2025. ISSN 2521-327X. doi: 10.22331/q- 2025- 12-02- 1922.
22331/q-2025-1222 12
David Jennings, Matteo Lostaglio, Robert Lowrie, Sam Pallister, and Andrew Sornborger. The cost of solving linear differential equations on quantum computer: fast-forwarding to explicit resource counts. Quantum, 8:1553, 2024. URL
q 2024-12-10-155.
John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Zidek, Anna Potapenko, Alex Bridgland, Clemens Meyer, Simon A. A. Kohl, Andrew J. Ballard, Andrew Cowie, Bernardino Romera- Paredes, Stanislav Nikolov, Rishub Jain, Jonas Adler, Trevor Back, Stig Petersen, David Reiman, Ellen Clancy, Michal Zielinski. Martin Steinegger, Michalina Pacholska, Tamas Berghammer, Sebastian Bodenstein, David Silver, Oriol Vinyals, Andrew W. Senior, Koray Kavukcuoglu, Pushmeet Kohli, and Demis Hassabis. Highly accurate protein structure prediction with al- phafold. Nature, 596(7873):583-588) July 2021. URL httpp:://dol.org/00...
s4158 2415866-2 021 03810-11111 9-2
Ashish Kapoor, Nathan Wiebe, and Krysta Svore. Quantum perceptron models. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016. d47 d1224eeeu22933333223333bbb
URL
neurips pcc/paper/201//hatt .tmal.thttmmmml
Iordanis Kerenidis and Anupam Prakash. Quantum recommendation systems. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 49: 49:21. Schloss Dagstuhl- weeiiini-Zeetnnne fuer
Informatik, 2017. h / www.://////..//////////o/ 4230 ITCS. 2017.49
15

---

Published as a conference paper at ICLR 2026
lordanis Kerenidis and Anupam Prakash. Quantum gradient descent for linear systems and least squares. Phys. Rev. A, 101(2), February 2020. URL lttph:: /it::://ikik..... aps org//oo//.//////
1103/PhysReva, 101. 022316
lordanis Kerenidis, Jonas Landman, and Anupam Prakash. Quantum algorithms for deep convolu- tional neural networks. In International Conference on Learning Representations, 2020. URL
htttps://ppenrettt
net fo
Hari Krovi. Improved quantum algorithms for linear and nonlinear differential equations. Quantum, 7:913, February 2023. URL httthh:tp//db../ httpp///......22///0000202222222
Martin Larocca, Supanut Thanasilp, Samson Wang, Kunal Sharma, Jacob Biamonte, Patrick J. Coles, Lukasz Cincio, Jarrod R. McClean, Zoë Holmes, and M. Cerezo. Barren plateaus in variational quantum computing. Nature Reviews Physics, 7(4):174- March 2025. URL
022442254--5500000 025-0081---9
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. Nature, 521(7553) 444,
2015. http:/tts.///b...rr/11.....
Tsung- Yu Lin, Aruni RoyChowdhury, and Subhransu Maji. Bilinear CNN models for fine-grained visual recognition. 2015 IEEE International Conference on Computer Vision (ICCV), pp. 1449. 1457. IEEE, December 2015. (ttLhhtt::////t
org/10...o..ooooooooooooo 1109/ICCV. 2015.11
Jin-Peng Liu, Herman Øie Kolden, Hari K Krovi, Nuno F Loureiro, Konstantina Trivisa, and Andrew M Childs. Efficient quantum algorithm for dissipative nonlinear differential equations. Proceedings of the National Academy of Sciences, ( 18, 2021a. URL https
// //www, wnwsppasssoom org/ doi abs 1et.1073//paae 202.aas.22888000 2825511
Jin-Peng Liu, Dong An, Di Fang, Jiasu Wang, Guang Hao Low, and Stephen Jordan. Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation. Communications in Mathematical Physics, 404(2):933-1020, 2023.
/it::://iiikkk.. www.inkssriing....mm com/
Junyu Liu, Minzhao Liu, Jin-Peng Liu, Ziyu Ye, Yunfei Wang, Yuri Alexeev, Jens Eisert, and Liang Jiang. Towards provably efficient quantum algorithms for large-scale machine-learning models. Nature Communications, 15:434, 2024. URL https: /ttts:://doi.org/0...10.
941467-023-43957-2
Yunchao Liu, Srinivasan Arunachalam, and Kristan Temme. A rigorous and robust -ueed-p in supervised machine learning. Nature Physics, 17:1013-100 1017, 2021b. URL https://doi
2xcp/10.1033//34117-02211-
Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost. Quantum principal component analysis. Nature Physies, 10(9):631 663, July 2014. htR.sttss: doi. www.oorggr..... 1038 1ttp://000000/mm//33332223 /nphys309
Guang Hao Low and Isaac L. Chuang. Hamiltonian simulation by uniform spectral amplification, httpg//aba/777.0000
2017. /ttpsttss://aaattttttttt
Aqeel Mahesri and Vibhore Vardhan. Power consumption breakdown on modern laptop. In Power-Aware Computer Systems, pp. 165-180. Springer Berlin Heidelberg, 2005. URL https:
//doi 000000000//0.10001111444555
Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren platcaus in quantum neural network training landscapes. Nature Communications, 9(1), November 2018. URL htt.:tttts:::.......
Hela Mhiri, Ricard Puig, Sacha Lerch, Manuel S. Rudolph, Thiparat Chotibut, Supanut Thanasilp. and Zoë Holmes. A unifying account of warm start guarantees for patches of quantum landscapes, 2025. wittps://ardee
orgg abs 22020 07889
Kosuke Mitarai, Masahiro Kitagawa, and Keisuke Fujii. Quantum anglog-digital conversion. Phys. Rev A, 99:012301, Jan 2019. URL https:://///......pt. /winkiiik./....///.. aps. wwtp/oiiggoooooooooo 1103///yeee/ 99. 013011
16

---

Published as a conference paper at ICLR 2026
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In International Conference on Learning Representations, 2018.
Ashley Montanaro. Quantum algorithms an overview. overi npj Quantum Information, 2(1), January 2016.
URL httpp://bbbl.ooo///0000/////pp.2
Gordon E. Moore. Cramming more compoments onto integrated circuits. Electronics, 38(8)114-1177,
1965.
Danial Motlagh and Nathan Wiebe. Generalized quantum signal processing. PRX Quantum, 5: 020368, Jun 2024. doi: 10.1 10.1100/PRQQuaatm....220 doi/10 11l.1110/BBB0 1ttp11100///
org/
020368
Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cam- bridge University Press, 2010. URL /tt.tposs/ooo...r......./////111
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style. high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bus Buc. E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32. Curran Asso- ciates, Inc., 2019. URL wwtp::ttttstccc http::pppp/pppcppppppppppeoe ings www. wwtp:cpppppepeeeeeeee www.ffllspppaeeee res/paper/ httml
201
Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter Love, Alán Aspuru-Guzik, and Jeremy L. O'Brien. A variational eigenvalue solver on a photonic quantum processor. Nature Communications, 5:4213, 2014. URL /ttt:stt:///o...r/////////
7038/ncomms5211
Martin Plesch and Časlav Brukner. Quantum-state preparation with universal gate decompositions. Phys. Rev. A, 83:032302, March 2011. URL Inttps://inkk aps crtp////////..11////
PhysRevA, 83, 032302
Anupam Prakash. Quantum algorithmss for linear algebra and machine learning. PhD thesis. University of Californi,, Berkeley, 2014. U htt.hhtss///diccoll111 wiw....bl....................... wew.eerreeyyy edu/
record/136504
John Preskill. Quantum computing in the NISQ era and beyond. Quantum, 2:79, August 2018. URL 2232222331331 2018- 08-08-088--73
https://doi. h
Arthur G. Rattew and Bálint Koczor. Preparing arbitrary continuous functions in quantum registers
with logarithmic complexity, 2022. htsl//tt:://aaavv.oor//aa/////// 00150 00519
Arthur G. Rattew and Patrick Rebentrost. Non-linear transformations of quantum amplitudes:
Exponential improvement, generalization, and applications, 2023. URL htt.h:h//aaxittt
org/abs/ 23099 09839
Patrick Rebentrost, Masoud Mohseni, and Seth Lloyd. Quantum support vector machine for big
data classification. Phys. Rev. Lent 113:300503, September 2014. (tRt::/ttt:///nkk.a
org/doi/10.1 1101 http://......//tttsseeeettttt..
Patrick Rebentrost, Thomas R. Bromley, Christian Weedbrook, and Seth Lloyd. Quantum Hopfield neural network. Phys. Rev. A, 98:042308, October 2018. URL httpss///iikk aps org/
doi /01/100.1 1tt.:.110////yeeeeeeeeee 0w2.e/..800222000 042308
Manuel S. Rudolph, Sacha Lerch, Supanut Thanasilp, Oriel Kiss, Oxana Shaya, Sofia Vallecorsa, Michele Grossi, and Zoë Holmes. Trainability barriers and opportunities in quantum generative modeling. upj Quantum Information, 10(1), November 2024. URL /tttps:://ol..og///// 1038/6 0138/s415344 -22-44024-00000 10.8/844533--02-00000022
17

---

Published as a conference paper at ICLR 2026
Sushant Sachdeva and Nisheeth K Vishnoi. Faster algorithms via approximation theory. Foundations and Trends@ in Theoretical Computer Science, 9(2):125-210) URL UtLptttss://dii.oo /z// 10 05.1151104400000
Mehdi Saeedi and Massoud Pedram. Linear-depth quantum circuits for n-qubit Toffoli gates with ancilla. Phys. Rev. A, 87:062318, Jun 2013. http:://: aps. org/ /doi//o
1103/PhysRevA. 87 062318
Maria Schuld and Nathan Killoran. Quantum machine learning in feature Hilbert spaces. Phys. Rev. Lett., 122:040504, February 2019. URL httph:h//h/iiiiti app hwtp://.ggooooo////eoe/o 1103/
PhysRevLett. 122. 040504
Maria Schuld and Francesco Petruccione. Machine Learning with Quantum Computers. Springer In- ternational Publishing, 2021.
Hanie Sedghi, Vineet Gupta, and Philip M. Long. The singular values of convolutional layers. In International Conference on Learning Representations, 2019. URL /tR/tttss////peeeev//
net/ feet/oorum?hddrrevvvyyoo 9Fm
Zhong-Xu Xia Shang, Naixu Guo, Dong An, and Qi Zhao. Designing a nearly optimal quantum algorithm for linear differential equations via Lindbladians. Phys. Rev. Letr., 135:120604, Sep 2025. URL
htttps://iimt aps org http///oo/o1.//11 110.:.1111/11//01000000 http://w........o//////0/0000010
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittieser, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of Go with deep neural networks and tree search. Nature, 529:484-493 2016. URL attps://doi.o.m org/ 10. 1 www/////tuueeee 1696
Ewin Tang. A qqantum-insspiee classical algorithm for recommendation systems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pp. 217-228, New York, NY, USA, 2019. Association for Computing Machinery. URL http::://oi.......
10. 10.1145/33132 3316310
Supanut Thanasilp, Samson Wang. M. Cerezo, and Zoë Holmes. Exponential concentration in quantum kernel methods. Nature Communications, 15(1), June 2024. URL https: //doi
1egg/10.133/// 44637//44466--10 024 000--2222-----222202220222222020
Joran van Apeldoorn, Arjan Cornelissen, András Gilyén, and Giacomo Nannicini. Quantum tomogra- phy using state-prepand prepaarrpaatioon unitaries. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1265 1318. Society for Industrial and Applied Mathematics, January 2023. httpttss:///aii orr.
9781 611 2111197554.cc. ch47
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In I. Guyon, U, Von Luxburg, Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Ad- vances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https::/t//tt httptp///pppooocceeneeeeeeeeneop hasth
Absttsaaaabbttttttt..aa html
Kaito Wada, Naoki Yamamoto, and Nobuyuki Yoshioka. Heisenberg-limited adaptive gradient estimation for multiple observables. PRX Quantum, 6:020308, Apr 2025. URL httpt::tt//tnn
aps. wwt.:o/g//ooo.oooo 1ttp://aa..1..1110//A.uuuuauumm 6. 020308
Yunfei Wang, Ruoxi Jiang, Yingda Fan, Xiaowei Jia, Jens Eisert, Junyu Liu, and Jin-Peng Liu.
Towards efficient quantum algorithms for diffusion probability models, 2025. URL https
14222 14252
Nathan Wiebe, Daniel Braun, and Seth Lloyd. Quantum algorithm for data fitting. Phys. Rev. Lett., 109:050505, Aug 2012. htRpst :os:://in //1ink aps wwtp//i/oo..ooooooooo/tooo.oooot htt.://bi....1110////eeeeeettt 109. 050505
18

---

Published as a conference paper at ICLR 2026
Nathan Wiebe, Ashish Kapoor, and Krysta M. Svore. Quantum deep learning. Quantum Information and Computation, 16(7 & 8):541-558 May 2016. URL
0IC16.7-8-1
Hsuan-Cheng Wu, Jingyao Wang, and Xiantao Li. Quantum algorithms for nonlinear dynamics: Revisiting carleman linearization with no dissipative conditions. SIAM J. Sci. Comput., 47(2): A943-A970, 2025. hotthttt: /tw..//oii.cc org/10....ooooo...oo.o..
Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural networks. In 2017 IEEE Conference Computer Vision and Puttern Recognition (CVPR), pp. 5987-5995, 2017. URL ftttp:://doi.or//1000
CVPR.2017.0 634
Siyi Yang. Naixu Guo, Miklos Santha, and Patrick Rebentrost. Quantum Alphatron: quantum advantage for learning with kernels and noise. Quantum, 7:1174, November 2023. URL https
7/doi. 10. 22331/ 11002-111000 1174
Yuichi Yoshida and Takeru Miyato. Spectral norm regularization for improving the generalizability http://////axxxv.oor////////////
of deep learning, 2017.
10941
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In Procedings of the British Ma- chine Vision Conference 2016, BMVC 2016, pp. 87.1-87.12 British Machine Vision Association, 2016. htt.:ttp:e//ool..orr/00.02444 5244//
19

---

Published as a conference paper at ICLR 2026
TECHNICAL APPENDICES AND SUPPLEMENTARY MATERIAL
In Appendix A we present a summary of Quantum Random Access Memory (QRAM), which we subsequentyy use. In Appendix B we present number of existing techniques which we require to manipulate vectors and matrices with quantum computers, and then use them to develop a number of new useful results for quantum matrix-vector arithmetic. In Anppenddi C we the techniques developed in Appendix B to construct quantun-implementttions of key architectural blocks. In|Appendix D blocks obtained in Appeppdii Cito derive end-to-end complexities for a number of architectures under different QRAM assumptions.
we discuss the feasibility of QRAM. In Appendix we use the architectural
A QUANTUM RANDOM ACCESS MEMORY (QRAM)
Quantum Random Access Memory (Giovannetti et al. 2008b) is widely assumed mechanism in the quantum computing litcrature for accessing data in a quantum computer. In this paper, we make range of QRAM assumptions under different regimes of assumed feasibility. With the aim of enabling practical end-to-end speed-ups, it is important to explicitly state the different assumptions and consider the feasibility of each of these regimes.
In this section, we will formally define QRAM, and state the assumed complexities. In Appepddix D dive into deeper discussion of the feasibility of our various QRAM assumptions, with the aim of providing a clear understanding of what sorts of end-to-end speed-ups our results can offer in practice.
Definition A.1 (QRAM for Classical Data). Let N = 2n and D = 24, Lel 1x), be any n-qubit standard basis vector, and let r; [D]. Then, QRAM with OdN log N) total qubits can implement the mapping,
Upb) 10) = 10)
(A.1)
with Od N) circuit depth.
As mentioned in a number of sources, e.g., Hann al. (2021); Giovannetti al. 2008a) N qubit QRAM can be implemented with Olog N depth complexity. Consequently, performing sequence of d of these (to implement each of the d-bits in each memory register), circuit depth complexity of (d N) trivially follows.
Definition A.2 (QRAM for Quantum Data (Prakash 2014 Kerenidis Prakash 2017; Kerenidis et al. 2. Let N = 2", M 2" Let 10)m be any n-qubit standard basis vector. Allow W)) m to be an arbitrary m-qubit normalized quantum states. Then, QRAM with ((MN) total qubits, and Ö(MN) classical pre-processing construct the sata-sttuctture can implement the mapping.
Ult) 10 (() mi
(A.2)
with Ollog (M) circuit depth.
Importantly, per Prakash (014);; Kerenidis & Prakash (2017); Kerenidis et al. (2020) QRAM for quantum data can be implemented by a circuit (based on Grover & Rudolph (2002)) with depth and width (polylog (M) with access
QRAM data structure (as per Definition A. containing all the entries of each state in the quantum data (along with Ollo M) copies for each of the sets of partial norms). Thus, if QRAM for classical data is feasible (as discussed in [Appendix D). QRAM for quantum data is as well (with pre-processing to construct the appropriate data-structures).
In this work, we will use QRAM describe QRAM for both quantum and classical data, and will make the distinction clear when it is relevant.
B QUANTUM MATRIX- VECTOR ARITHMETIC
In this section, we formally derive a number of tools for quantum matrix-vector arithmetic.
Lemma B.1 (Product of block encodings (Gilyén et al. 2019). Uf U is (a, o. 5) bblock--encddiin of an s-qubit operator A, and V is an b...ce)-llock-encoddi of an s-qubit operator B then (To s U)(Ta & V) is an (a.8 a + b, ar + -60--block-encodiie of AB.
20

---

Published as a conference paper at ICLR 2026
In Lemma B.1 we adopt the tensor product notation used in Gilyén et al. (2019); the tensor product in this lemma is used differently than it is used anywhere else in this paper.
We now present standard result (sce Lemma 1 of Carpp & Van Becumen (2020) or Lemma 21 of Chakraborty et al. (2023)), and we include the proof for completeness, as it is the basis of a subsequent proof Lemma 3 In partieular, our derivation closely follows that of Lemma of of(amms
& Van Beeumen 2020).
Lemma B.2 (Tensor Product of Block-Encoded' Operators). Given a unitary UA which is an (a, a, co)- block-encoding, n-qubit operator A with O(Ta) circuit complexity, and unitary UB which is (3, b, e1 (i)-block-enoodnng for mn-qubit operator B with ((TB) circuit complexity, we can obtain an (aB, a + b, co.8 + +1 + E061) dellocinn for & with (maxx TB) max(n, b)) circuit complexity.
Proof. The main idea is that UA @ UB almost directly implements a block-encoding of A @ B, but the ancillas and the main computation registers are in the wrong order. To correct this, we need to swap the ancilla register of UB with the main register of UA-
Consequently, define the operator II such that it swaps the n-qubit register with the b-qubit register (and leaves the other registers unchanged), so that all the ancilla registers precede the main registers. If n 2 b, II can be implemented by a sequence of (n/bb) swaps, with each swap swapping O(b) qubits in parallel. If n < b, then it can be implemented with Obb/n) swaps. Thus, IT has a circuit depth bounded by O(max(n//b /b)b//))) E O (n, b)). Then, IT( IT((0)+bb & In+m) =
(10), @ In) & (10)s @ m, and ((0)+4 @ [n+m III (10)a @ I,) & (10) @ Im).
Following Camps & Van Beeumen 2020 define Ā = ((0)a 8 (,)UA(10). @ In), and B = (10)& mm U B (m). Let EA
A aA, and let E'g B - BB. Define V = (U (UAUUU) &UB))L Then, A B (aÀ EA) @ (3B @0 En). and (10)a+b & I a( @ (ntm) = À B, so
| B - (0(((0)a+0) mm+m) ((10)++ @ 4n+m)ll
(B.1)
= =I(aA + +EA) @ (BB @ EB) a3A
(B.2)
2
S cn3 + c1a + coE1
(B.3)
We now present a result from the literature allowing a block- clock-encoding to have all of its singular values scaled by a constant value. We present the result nearly verbatim from Lemma 5 of Wada et al.) (2025) (with trivial modifications to make easier to invoke our context), which presents the results of Low & Chuang| 2017); Gilyén et al. (2019) cleanly in the language of block-encodings.
Lemma B.3 (Uniform Singular Value Amplification (Wada et al. 2025 Low & Chuang 2017 Gilyén
ct al. 2019)). ). Let e, E (0, 1/2). and let > 1. Let A be an (1, a, 0)- bblock-encoding of the n-qubii operator A with O(T) circuit depth. Suppose ||A]]] < (1 8)/7. Then, we can obtain quantum circuit V which is a (1, a+ 1, c)-bblock-encdding for 7 with O log((/<)(T + a)) circuit depth, and with (poly(( & log(r/<))) classical computation to determine the QSVT rotation angles.
Proof. This is taken directly from Wada et al. (205 Low & Chuang (017)): Gilyén et al. (2019). simply noting that an a-controlled X gate can be implemented by a sequence of O(a) single and two-qubit gates.
We now present simple result which is just a special case of uniform singular value amplifica- tion (Wada et al., 2025) Low & Chuang 2017 Gilyén et al.) 2019) in the case where all the singular values of an encoded operator are either 0 or 1/2. This is done following the ideas of oblivious amplitude amplification (see Gilyén et al. (2019)).
Lemma B.4 L/ Oblivious Amplitude Amplification). We are given a matrix E NNN with singular values either 1 or O. Assume have access to U (2,a, 0) BE of A with O(T) circuit depth. One can construct (1, a + 1, 1,0)-BE of A with OTT) circuit depth, and with 3 calls to a controlled-U circuit.
21

---

Published as a conference paper at ICLR 2026
Proof. Note that Tz(x) 4x 3r satisfies the condition that [Tx()) - for [-1,1] and Ts(5) -1. Therefore, one can achieve the task by implementing the function -Ta via QSVT and the block encoding. The first kind of the Chebyshev polynomial can be directly achieved without any classical processing to determine angle rotations, so one can construct the block encoding with no error.
For completeness, we now re-derive an existing result on the linear combination of block-encoded matrices, directly following Gilyén et al. (2019) (which presents the result of Childs & Wiebe (0122) in the context of block- block-encodingg),
Lemma B.5 (Linear Combination of Block-Encodings (Childs & Wiebe 2012
Gilyén et al. 2019)
Suppose we are given a set of D = 24 unitaries {Ui]s such that each U. is an (a, a, -block- encoding for qubit operator Ag, and each Ug has total of (TT) single and two qubit gates. Define the vector b CD such that b b (by b1
bD-1)". Define - Vbgli)a and 3= |11b)a112 |6||]- We are given the d-qubit unitary Ub, with O(Ti) single and two qubit gates, such that Ug 0) d = a all2) Define == E bz Then, we can obtain a unitary V with OdDDT, + Ti) circuit depth which is an (a.3 + d, --Bc)-locckkeee-e block-ennodiingggg for A.
Proof. For each j E [D], let A; ((0)a @ (10), @ In), and let Ej Aj - aAj. Define : Ef= liMila @ Uj. Note that S can be implemented by a sequence of D multi-controlled Uj operators. Note that by using Saeedi & Pedram (2013), a d controlled gate targeting 1 or 2 qubits can be decomposed into sequence of O(d) single and two qubit gates. Consequently, each d-controlled Ug has (dTo) circuit depth in terms single and two qubit gates. Thus, S consists of total of OdDDT) single and two qubit gates. Then, define V == (Uß @ Satn)S(Us & latn).
Noting that ((0)a @ ((+)) @ Jata) 8 Ep byU,. Using the fact that 10)add & In (10)a & (1+a)(00) @ I.), we then obtain
(10h) & I,) (00) & (1)) add 8 1L)
(1U,)(1),, @ I.)
1
Σ
A
(B.4)
1=0
j=0
Consequently,
| a:(( & T.)V( 1.)l22
Σ by(ad + R.j)
Σ
aby Ag
(B.5)
j=0
Σ byaeyi
5 Σ
1b11
(B.6)
j=0
S a,ee.
(B.7)
Thus, V gives a (a3, --cc)- for A, and has OddDT, + Ti) circuit depth.
The following is a standard result which has been used in various contexts, and is included for completeness.
Lemma B.6 (Block Encoding of Rank Projector of Basis Vectors). Let E N20. and let N = 2" Define i E [N] and j E [N]. Then, we can get a unitary U which is a (1,2, blobkkkk-nnnooingg of the qubit operator bi) (j). Moreover, U has O(n) circuit depth.
Proof. Following Jaques & Rattew 2025 a (1,2, block-encoding of the matrix [0)(0)] call it V. can be obtained with O(n) circuit complexity. This follows by constructing a (1, block- encoding of the Grover reflection operator, / - 2 (0), and taking a linear combination with via the sum of block-encoding result of Gilyén et al. (2019). The circuit complexity is dominated by reflection operator, which can be implemented by applying a
controlled XZX gate the most significant qubit, controlled on the state of the other n qubits. Using (Sacddi & Pedram (2013) this can be decomposed into sequence of O(n) two-qubit gates. Decompose
22

---

Published as a conference paper at ICLR 2026
i and into bits as, 1o 2n-1, 1. and j = john ... In-1- We now define two operators,
M2 == X x g... ...... 8 and M, := xx 8x 1. Clearly, (O = | (il-
Then, since (I2 @ M,) V @ M,) = (1) :) Thus, (12 @ M.) 8 M,) is a (1, 0) block- encoding for (i).
We now present simple result which helps intuitively visualize VEs as encoding vectors in subspace.
Lemma B.7 (Intuitive Picture of VE as a Vector Subspace Encoding). Let Up be an (a, a, c)-VE
for I Define En (x)n al (0), @ In) 1p)0p01)tmm Define the a-qubit operator p/ = (5) Then,
Ue 10) 10)lk))) - 0) Epp) +
2
1)) Eu
Σ (of @ 1n)Up/00atn
a
(B.8)
a
Proof. |Egin 1,)n a(()), @ 1,))p(0))++ 10)at implies that ())=E)))) 10)al
apd X
1, The result follows trivially by algebraic maniuplation of U210)a+n 12)== (,)0v(0))tm
2"
Pj
X
Intuitively, in the absence of error, the first 2n entries of Up 10)att will contain the sub-normalized vector /
We now state the following result from Rattew & Rebentrost (2023) nearly verbatim, slightly improv-
ing the complexity. The following result is a tool essentially implementing & layer normalization. follows directly from oblivious amplitude amplification (see e.g.. Gilyén et al. (2019), and is taken nearly verbatim from Rattew Rebentrost (2023).
Lemma B.8 (Vector Normalization, Lemma 18 of Rattew & Rehentrost 2023)) ) Let cn 10,1.
> 1, E N. e O. Let a' be known bound such that a' 2 a. Given a unitary US., (a, a, Ea)- VE for the fy-normalized quantum state (6)n with circuit complexity ( ), we can construct a (1, a + 4, 2(cu + v1))-VE for W),, with circuit complexity O(T + + n)aa log(1/c1)) and with O(a' 1og(1/e1) queries to a Ug and U. circuit.
This implements vector normalization by boosting the scaling factor so the norm of the encoded vector is 1, and all the padding entries are (up logarithmic error).
Proof. Define (d), == (10)a & Un) 10) (0) No = ا Io 1)n, n Then, Up is
equivalently a (Na. a, -)E for ///a/ Using Lemma B.6 we can get Un a 21,2, -bllokk- encoding of the n n+ qubit projector (0) (0) with O a circuit depth. Then, V= (T2 )U, is a (1,2, bloccccc-nnnoiing for Uv (0) (0), with OTT +a a n) circuit complexity. Noting that (0) 8 la-n) V (10)2 @ lltn) Up (0) (0). then (10)2-a
2- @ (.) V In) ((0)a @ 12) ())(0)
I, ) = (0), so
Il (O).- (0|2ta @ (O) @ Tn) = 0.
(B.9)
Thus, we have (1, + 2, (ll.)))boo--eeooooeee of (Ø) (0), =Na (0). This object has singular value Ng. Thus, we want to apply a polynomial approximation to this block-encoding, such that the error of the polynomial approximation is at most é on the interval [Na, 1). From Corollary 6 Low & Chuang (2017), we know that there exists odd polynomial (x with degree k O log (1/a)) such that
max =E(-1. rE(-I.-4lU,7/2.11 /2.11
(P((z) sign(x) S1
(B.10)
and max [Pa()) < 1. Since N₂. > 2a
> 20 we can set 2, guaranteeing that
P(N,) 2 1- 61. Consequently, we can invoke quantum singular value transformation (QSVT)
(Gilyén et al. 2019) with Pk. yielding V, (1, a 44.4446) (1).a+,,,).bbbcc-eenneee block--ennnn for P(A/ ()) (0)) (0)
23

---

Published as a conference paper at ICLR 2026
where 1 2 c2cl é1. Moreover, Vy has O log(1/<))TT + + n)) circuit complexity. Noting that
[]]))/0| P( () (0)1l= = [|]b) - ( (0) + [0] - cl (0
(B.11)
< Illx) [0) - (0) + [1 [0) - (01l2
(B.12)
I Illv), (1),.112 +
(B.13)
Moreover,
I1lv), 12)1 <11v/m al0)m112 + ||al)),
No l0)
_
1
(B.14)
1 |aNold) 10) = co + No.
-/
loNg - 1
Sca
Il
(B.15)
No.
Sco + 1aN6 - 1/.
(B.16)
Moreover, using the reverse triangle incquality with (1 alo)nl12 S En, get 1-a [1
[1 - -o I 61, which implies that - cu I aNo S 1 + co. Consequently, laNo
1 S co and so
I1lv), - (2), l1 S 2eg-
(B.17)
Thus,
Moreover, since Vy is a (1, I| (0) p)) (0))l Ze0 +
(B.18)
for P(Vo)))(0))
|P (0)( ((0)a+1 @ L,)V)((1))++ @ 4n)ll2 61.
(B.19)
Thus.
[0) ((0) @ [,)V @ In)l22 s 2 11).
(B.20)
Sometimes it is necessary to increase the norm of the vector encoded in the subspace of a VE. This equivalent to multiplying all of the entries in the encoded vector by a constant with value greater than or equal to one. The following lemma achieves the opposite: it allows the norm of the encoded vector to be shrunk by an arbitrarily large amount. This is equivalent to dividing all the entries in the encoded vector by constant greater than equal to one. It is worth noting that the following result trivial and can almost certainly be further optimized, e.g., by removing the additional ancillary qubits added.
Lemma B.9 (Vector De-Amplification) Let t 2 1, 2 1, 6 2 0. Given Up an (a, a, c)-VE for 11) with circuit complexity O(T),, obtain U an (at,a c) for (+), with circuit complexity (T + a).
Proof. Let 16,)n == ((0)a & I,)U=10) Then, note that Up. (0)00aa = 2- 15)a @ 10,)..
By Definition 3) we know that I|[v),, a al)o),.l S
We introduce two single-qubit ancillas as the most significant bits, and then apply a muutiple-controller X gate (with controls each activated by the 0 state of each of the previous a ancilla qubits) targeting the first newly added ancilla qubit. Using Saeedi & Pedram| (2013) this can be implemented with
O(a) two-qubit gates. We then apply controlled R1/r2 (as per Definition B. gate targeting the second new ancilla qubit, controlled on the first new ancilla. This yields the state,
11) 1 + +V1 - 11))) (p)) + 10)
Σ li)alds)m.
(B.21)
We then apply X gate to the first ancilla qubit, and we call the 2 + a-qubit unitary containing all the preceding operations V. Then, U/= := (V 8 (,)(22 @ U Simple analysis thus shows that ((0)2+ & L,)U [0) = (00) /T. Then,
||w), - ar((0)2+a & U, 0/24atol1z = )) al0o) c.
(B.22)
24

---

Published as a conference paper at ICLR 2026
10)1
R
R
10) n+c
UPP
U
Figure 3: Circuit for addition of VE encoded vectors. Given two unitary matrices, Uy which is (a, a, 6o)-VE for the n--ubit state (ı5), and Ug which is (3, b, e1 --VE for the n-qubit state (o), define e max(a, b). We define Uz. by appropriately tensoring Up with le-a and we define Ug by appropriately tensoring Ug with Ic-b. such that U2 and Ug both act on n + e qubits. Then, the given circuit yields VE of the sum of the encoded vectors, shown in Lemma I
Definition B.1 (Real Rotation Single Qubit Gate), Let 0 S T S 1. Then, define the following single-qubit gate:
VT Rr ( VT,
-V1-
(B.23)
Sum). This result follows using common techniques, see e.g., LCU (Childs & Wiebe 2012), the sum of block-encodings result (Gilyén al., 2019). As per Figure 3 we will augment Ug and Ug so that they both act on c = max(a + b) ancilla qubits. Then, define the + qubit states, 18)n+e == 10 We will drop the subscripts on these states for the rest of the proof, as their dimension clear from the context. This block-encoding will be obtained with the circuit shown in Figuur 3] and so we will now analyze the action of that circuit. First, we start with the state 10)+ which we will write as (0)]0); where the first register has one qubit, and the second register has the remaining n n qubits. We then apply Rt (as defined in Definittin B.I) to the first qubit, yielding the state (vF10) + / -|1))])), Next, we apply the controlled Up and U
Proof Lemma 1 (Vector
gates, yielding, v () v T))) Next, we apply R (-X-- VT
vI 7
on the first note that ||| || I 61 As result, we can determine the properties of this VE by bounding the following.
VF
qubit, yielding the output of the new VE, VI0) = () + ())) Define (Ex) = (xb ax((0) (0))))) & w) and note that || ll I cp. Similarly define Eg), and
+ -
N (10 (.) +000
(B.24)
N (10 0c 8 (T)(( (1 -)1(3))
(B.25)
[T) N (T (11) - (Ea)) +
1- (1Ø) - |EE)))
(B.26)
B
1 1- (ba) ||
Teo + (1 T)
Ex) +
< N
(B.27)
N
B
< ED +
(B.28)
N
N
where the final inequality comes from the definition of VE imposing that 2 1 and 3 2 1. Thus, the unitary circuit V is (A-1, a b, G))-VE for [T).
Proof Lemma 2 (Matrix Vector Product). We now require a result allowing for matrix-vector products with vector-encodings. This result is essentially a special case of the product of the standard product of encok-nns result (Lemma 53 of Gilyén et al.) (201))) As result, the following proof closely follows that in Gilyen al. (2019).
In this lemma, again following the notation of Gilyen et al. (2019) for tensor products, it is assumed that UA and Up act trivially the other's ancillas. To be explicit, the tensor products in (Tn e
25

---

Published as a conference paper at ICLR 2026
(T) Uv) special definition only in this lemma. Let == ||A1))))l2- We wish to upper-bound,
Alw)) aB
ç: :
N (10)ato @ (1) @ Ua)(Ea @ Up))0)
(B.29)
N
N 11A1v))
a -
(4 @ Ua) @ Up)( mn)l
(B.30)
Then, directly from the proof of Lemma in Gilyén et al. (2019)
1 N |1 a3 [((0), @ ( @ L.) [((0], @ ())),(()) @ 10)all
(B.31)
Let A= = a(10aa @ A @ I.)) and let (2b) := 3((0), @
Then,
< = N Al1b), - -//3)m112 =
1 1| A/00 - (lp) + Al)) - A1(3)ml1
(B.32)
< N (I - =11 + |/ (1/6))-11/))) (02m(12)
1
A||--A)
(B.33)
Noting that | a, we then get
S (co ac)//N. Consequently, (4, Ul) @ Uv) gives (a3/N, + b, (eo + ae1)/N) for AWD),/NN
(B.34)
In the following lemma we derive a technical result handling the case where you have a vector encoding for some vector (gb), and another vector of interest (o) sub-encoded as (xb) (10)/3)
Our result also handles the case where each vector is imperfectly encoded (i.e., encoded with error).
Lemma B.10 (Vector Sub-Encodings). Let m, n be integers such that m > n. Let Up be an (ax, a, VV- for (1)m and let (v) Vol0), (precisely, Illy) Vol0),ll I where Vo is
(B, m n. 8)- VE for (6)n. Then, Up is an (a,, a + m n, 8 + 3(c + VE) (0)
Proof: Let b- = m n. First, define Em = (mb) a (0))a @ I. U (0) a and Eghn = 16)n a ((0)s @ I,,) Up 10) By Definition 3 ||| S c and E S 6. Let Ex)m
(1)) - Vo Now observe,
(10/ @ 4n) (10)a @ 1m) a0)mm = ((0) @ In) (I.) Exlm)/a
(B.35)
((0), I.) (0) m + |Ee) - mma)
(B.36)
((1)), [B)) (10), @ (l)( - [Bx))) (am)))))/
/a.
(B.37)
Consequently, since (10), & (0), @ Im.) (0la+0 @ In.
|| - a,3(10) Ue 000-bx)ll
(B.38)
< || B Im + 8 En.) m 1l2 < B(c+
(B.39)
Lemma B.11 (Tracing Out Qubits in Vector Sub-Encodings). Let U be an (a, a, VV- for (0)
Then, is an (a, a + b, for (m)
Proof. Let E+ == 10),|(>, - (l a) Since (0a+t004, = 8 (1)
Iotn), (00)+bb @ I,, 21(1)) (10) E)) Thus,
IIlv), a110)a+b & 4n)U11))4otmlll
11((0) 1,) Se.
(B.40)
26

---

Published as a conference paper at ICLR 2026
Proof of Lemma 3/ (Vector Tensor Product). This result closely follows the derivation of the tensor
product of elock-ens (Lemma B.2), which was a rederivation of Lemma of Camps & Van Beeumen (2020).
Up acts on an a-qubit ancilla register and a n--uuiit main register, while Ug acts on an b-qubit ancilla register and a m-qubit main register.
As per Lemma B.2 define II to swap the n-qubit register with the b-qubit register acting trivially on the other two registers. Again, II has circuit depth bounded by ((max(n/b, /b, b/n)) E (maxx(n, b)).
Then, ((0) 4+ @ (n+mm) Ill = ((0)a @ In) @ ((0), @ Im). Let V = (U & U&). Let {Eş)n =
[sb) (0)a @ U,) (0) ann and Epp 10)m B(10)b (0)02 Then,
((0)a+b In+ (U a and so,
a (1b), -
(Bp)aa (10) [Ba)m), (B.41)
l11v)_lo - aB((aaa & Ixt (U @ U2))0) S (B.42)
Proof of Lemma 4 (Vector Concatenation). We now present the proof of a simple result on the concatenation of vectors stored in VEs. This result follows from simple modification of LCU (Childs & Wiebe 2012). In essence, given a set D = 2d vectors {1a Jn we first create vector encodings of (15)))))))) and then take the resulting sum of the encoded vectors following LCU,
yielding an encoding of ((voll
(WD-1l))
For all j. define |Fwy)) lxby) ae (0)a @ I,) 0)
First, let be d bits, and let j = joJn bo.ji...j---.............. j8-1- li)a = ( and thus that X, a (1, 0, -VE for Li)a Then, we can invoke Lemma with Uj and X, to obtain V, an (aj, a, c)-VE for li)a (y)) with O(T + n) circuit complexity. Moreover, by inspecting Lemma 3 we find that ((0), @ V Vyl0))+ttnn = 1 (1)) - 1))al kn).
Define X, == X 2 X @ X X Note that
ag
Additionally, define := = -E li) & VG. This can be implemented by sequence of O(D) multi-controlle gates, each enacting V, when the control register is [j) a (in the standard fashion of LCU (Childs & Wiebe, 2012) First, note that by using Saeedi & Pedram (2013) a multiple-controlled gate with ((d) controls can be split into sequence of O(d) single and two-qubit gates. By splitting each of the d control qubits into a + d + n copies (with (alog(a+dd+e
depth), we can control each gate in each layer of U, in parallel with (d) eircuit depth. Since these ancillas can be uncomputed and traced out, we ignore them in the complexity analysis. Thus, each multi-controlled Vj gate can be decomposed into a sequence of (dT) single and two-qubit gates. Thus, has a total circuit depth of OdDT). Let A == ad @ Iatnta- Using (Olata & Intd = ((0)a @ IIa @ (0)a @ Idta).
(10)24 Inta) Hi (0) 24
(B.43)
= -(+la @ [Ia 8 (0), @ lota) Σ (1i) & v)))+) o+nn
(B.44)
1 b)llvs) - 15) Ev,)a
(B.45)
D
aj
Then, noting that N2 Ej 1-1 oz. and that DPp bital Ne.
1) V)ann
N N ((0lata & I In+a) HSA () 2)
D
1
Σ
D
1b)
C.. (B.46)
N
2
1=
Thus, ASH is (D/N, a. for
Mhet N=
with (dDT) circuit complexity.
27

---

Published as a conference paper at ICLR 2026
B.1 GENERAL MATRIX-
PRODUCT
In this subsection, we will derive a procedure which given an arbitrary matrix W and quantum state (6), allows for state proportional the product of (I to be obtained with complexity independent of the Frobenius norm (and thus rank), and sparsity, of W. To the best of our knowledge, this is the first result which allows such a product without either a rank or sparsity condition on W. The key insight is to avoid ever constructing a block-encoding of the operator W, and directly query its columns weighted by the entries of the vector it is being applied to. In particular, at high-level we construct two objects. Define the columns of W (wo the column norms aj == [ 21l. and the normalized versions the columns (wy)n = wj/aj. Additionally, define the state we are applying it to as [vb), Σ, dyli)nn First, we construct the normalized state Σ, thy ( Clearly, this object has Frobenius norm dependence. We would like to map all the vectors in the first register to the (0) state so that have something resembling the metrix-vector product, and to do this we construct another operator. Note that the (00 In
wx-1), define
1n (i.c., the first N rows are non-zero, and the rest are all zero)
matrix Q =
when applied to 16)2n - E, (byl5) lu,)n yields Q) 10), @ (WI However, this object
has a spectral norm (([[ Instead, we define M == [o bo
aN-1UN-14, and note
that M can be shown to have ||M]| S 1, and moreover, we subsequently show how block-encoding of this operator can be efficiently obtained. Consequently, since M ())2 = 10),, @ (WW)),,)))) the result follows. The rest of this section simply derives the ingredients necessary to rigorously prove this intuition.
Definition B.2 (t) Gate), Let E IR, and let be the standard single-qubit Pauli-Y gate. Then, define
cos (t)
sin(t) cos(t)
(t) == -i0 = issint))))) =
(B.47)
sin(t)
For completeness, we will now present a standard result allowing one to transfer digitally represented information to the amplitudes of quantum state.
Lemma B.12 (y (L) Gate), Let I E R. Let Y be a standard Pauli-Y gate. Let laya be a d-bit standard basis vector, and let (bb) be an arbitrary single-qubit quantum state. Then, define the gate (yy(t) by the following action,
CBr (1)))) (e-ia W)
(B.48)
In the event that (()) = 10),, this action can be simplified to
C (t)(0) la) = (cos(at))O), sin(a))l1)))aaa
(B.49)
Moreover, the CRy (t) gate is implemented with (dd) circuit depth.
Proof. This is a standard result. This proof is included for completeness, and follows the one in Rattew & Koczor (2022). Let D 2d. First, note that CRy (t) DD1 e -iay @ (a).
Additionally, let ad-1ad ... 0100 ad-12 + 012 2 ag. Then,
iotY = -iaa--1112 4.. ta12 iin 2
iartY e iinnt
(B.50)
Then, CRy can implemented by applying a sequence of d controlled e -2 gates Defini tion B.2), targeting the first register, controlled on the jth bit of the second register.
We now present a result on obtaining a block-encoding of an arbitrary diagonal matrix whose entries are stored in QRAM. This is essentially special case of Lemma 48 of Gilyen et al. (2019) but by considering this special case moderate improvements in complexity can be obtained.
Lemma B.13 (Quantum Block- bonck--n of Diagonal Matrices from QRAM). Let = 2n. We are given a set of N real coefficients, {aj}; such that Vj, layl < 1. Assume that each aj can be represented exactly in binary encoding with d-bits of precision, and define D = 2d. Define
28

---

Published as a conference paper at ICLR 2026
b, := arccos(a;) D D/T, n, and for simplicity assume that each by can also be implemented with exactly d-bits of precision R and note that by E [D] Assume that we are given an oracle, implemented via QRAM, such that T (0)ali)n = al,)a Then, we can obtain UA, a (1, + for A = diag(an (4o, aN with (dd) circuit depth.
Proof. Define the circuit V == (I, 8 (T) 8 (1) @ U). with CRy( defined as per Lemma B.12 First, since for any (o) and basis vector (5), ()) 1b> ((o)ls)) observe that
N
N-1
(11 @ ()0))4+1 8 In)=
Σ
[111 2
Σ [100)11))aa0)))01.
(B.51)
Then, since cos(b, = arccos(a)).
N-1 Σ
(CRy ( 1 @ a0) &b)
(agy0)) + (1-1)11))b))dbb) Gh.
1=
(B.52)
Then, since ((0)++1 @ (11 @ Ut) = [(4 @ ())( d+1 @ 4,)*= = (0)2 ((i)))), we readily find that
N-1
(10/241 (,)V((0))+1 d+1 2 (n)
Σ
ayهر>(i diag(ao (00 ................................ aN- A.
(B.53)
Thus, V is a (1,d + block-blcc--nncoddng for A. The circuit depth of implementing U is the depth of making a QRAM query, and is thus (d N)) O(nd) (see Definition A.I). The cost of implementing the CRy gate is simply ((d) as per Lemma 1.12 and thus the overall circuit complexity of this block-encoding O(nd).
In the case where each 0j E C, the complex and real parts need to be specified separately. A diagonal block-encoding of the real and imaginary parts can then be obtained using [emma B.13) and can then be summed by adding ancilla to obtain a (2, d + 2, 0) blockk-ennoodi with the same overall circuit complexity. One might wonder why, given a QRAM assumption, a Saate-preparation unitary yielding state proportional to Σ, a,y' can't be used instead, in combination with the diagonal block-encoding of state amplitudes result of Rattew & Rebentrost (2023). If each aj represent the column norm of some matrix W, doing so would result in a normalization factor of avoids.
E, E, |ay = [[]]] yielding Frobenius norm-dependence which this approach
The following data-structure is useful in situations where you are willing to pay pre-processing cost linear (up to polylogarithmic factors) in the number of non-zero matrix elements, but want a fast algorithm at runtime. This is the case with accelerating neural network inference. The following data structure is very similar to the one given in Kerenidis & Prakash| (2017). Definition B.3 (Preprocessed Matrix QRAM Data Structure). Let N = 2n, and let =2
Lef W E CNN and let ||W]|| S 1. Let the columns of W be represented as W (wo 1N)-1). Additionally, define (wy) = w// //w and aj = =Iw, Let by := For simplicity, we assume that by can be exactly written with d-bits, and thus that by will be an integer between [0, D O0.D-1) 1]. We say we have access to a Preprocessed QRAM Data Structure for W if we have QRAM oracle Uw (as per Definition A.2 such that
arccos(a,)
Uwli)) 10), = 1i') (
(B.54)
and we also have access to a QRAM yielding the mapping.
al) 1bz)al5)n-
(B.55)
Uw can be implemented with O(log N) circuit depth, and with Ö(N2) total qubits (as per Defini tion A. A. U can be implemented with O(d N) circuit depth, and with ((dN) total qubits (as per Definition A.7)
In practice this will result in an additional logarithmic source of error, which we neglecting, as it is akin finite-precision arithmetic error which is usually neglected in classical algorithm analysis.
29

---

Published as a conference paper at ICLR 2026
We are now ready to present a somewhat surprising result matrix-vector multiplication with arbitrary (potentially full-rank and dense) matrices and the element-wist wise square of a given vector. The following uses ideas similar to importance sampling.
Theorem B.1 (Product of Arbitrary Matrix with a Vector Element- -iiee Squared), Let N 2".
We are given matrix W E CNXN through the data-structure in Definition B.3 Let d be the number of bits required to represent the function of the column norms of W. by, as per Definition B.3 Additionally, we are given the unitary Uy with circuit complexity ( (a, C) for the quantum state (r) Define the function g C IR. as g(x) = lol? and N == (Wo(l))))l Then we can construct the unitary U which a (x= 2a + d + + n, N -VE for W Wy(lV)))//) and has a circuit depth OT, + dn + n²))
Proof. Noting that a; [ 2-2 it is easy to show || [W]] max=: [ W a 112 = |ill2 S 1. Consequently, by Lemma B.13 we can immediately get U. a (1,d + 1,0))bllockeencoddng for A = diag( .......,.......... with O(dn) circuit depth.
2 <
Vj.az S <1 1 1| | -
we can combine UA and Up to obtain Vi, a (a/N1, a + d + 1, 1///N)) for ( /M) This has circuit complexity
Let 1 == Alp),. = Σn= ولاود5)) Mi == I1l2))all2- By Lemma 2.
OTT + dn).
we can get Uo. (1, 2bo0)))booc-ccoodig for the n + a + 1-qubit projector [0) (0). Let E == Nr X (0) @ (1)) Then, by Definition 3. (n S
By Lemma B.6
Wil
c/MG. Moreover, (0la+d+1 @ (1)) = (191))
Then, observe that V22 == Uo(12 60 VJ)) is a (1, 2.00-bblock-ennooding for (0)(0] Let = a + d + Noting that (10),+2 @ In) = (10)2 @ (c+n)(10) x I,), then,
((0) 2 @ v2) 24 @ I,) = ((0), @ (002 @ Lotn) @ Im @ In) = ((0). @ (1)]0) (01)) @ In)
(B.56)
(B.57)
(10)..((11n - (F
(B.58)
The third inequality follows by noting that (10). @ Lx) ()) n+c 10),.. and that by Definition 2
((0)2 @ Ic-n) V2 (0)2 2 @ lc-n)= = 0) (O)VT Then, letting (0) be 2" x 2" projector,
[1)) - al (0) 2 @ V2))) c @ La) l2 Mi I10) (E llle S..
(B.59)
Consequently, 1/2 is a (a, a a 3, b-bboc--encodingg for the 2n x 2nh projector [O) Moreover, the circuit complexity of 1/2 is dominated by the circuit complexity of V1, and thus is O + dn). Then, 1/3 : 1/2 @ In a (a, a + d 3, ---b-l--eecodiig for (10) (1) @ In-
Let Uw be defined as in Definition B.3] i.e., it enacts Uwl5),,00) 10), 1wy))..
Define (0)2n Σラ
N
Then, let S := (Lo @ Uw (U, @ Ln). We will now show that S is an (a, a, e)-VE for (0)2..
Let Expn == 11)n - (0), U (0) a+a thus, ((0)a @ Un) 10)atn = (1v),, (Ew)n)
Moreover, define the a-qubit projector, pf = bi}() Then, Ja-n = E/n0 P2 @ In. Finally, define
I1s)n := -Lila @ Un) 10) Of course.
2d -1
2
Up10)atn= =
Σ 1=0
DS
In
Up 1010))+
_ a (10)))())) - -EE))a)) + Σ 1i)alsi (B.60)
Consequently,
((0)a s T2n) = (10)a s0 (Ta @ (U 80 1,))0))+22
(B.61)
2a
-(10) @ Uw)
- [Ea)a)) +
Σ
1i hisn
10), (B.62)
j=1
1 (10)2n Uw(
(B.63)
30

---

Published as a conference paper at ICLR 2026
Thus,
1l - aa @ 12n))(0) ln)) 10)x112 c.
(B.64)
Thus, is an (a, e)-VE for 16)2.. Moreover, the circuit complexity of S comes from summing the circuit complexity Up and Uw. As per periniiitoo B.3, the circuit complexity of Uw is O giving overall circuit complexity for S of O(T n*).
Define n == Wg(W)) m.. and note that
N-1 [(10) (wh1 @ 2. 10)m Σ | (yylayl 10)mnLT)...
(B.65)
We now have Vg, (o,, + d bloock--ooock for (10) (t/1) @ In. and S an (a, a, e)-VE for (0)2n. We will now invoke Lemma 2 to take the product of the matrix encoded in Va with the vector encoded in S, and then will invoke Lemma B.1l to remove the (0,, tensored register. This yields Uy. a an (N 2a + d - 3 n, 20z >-VE for //) with circuit complexity O(Ty + dn + n²).
B.2 CONVOLUTION BLOCK- -NCCDIIGG
In this section, will first provide matrix-form of 2D multi-filte convolution (with stride 1 and 0 padding to ensure the input and outputs have the same dimension). We then derive quantum block-encoding of the matrix form of the convolution.
As a note, some popular deep learning frameworks such as PyTorch (Paszke et al. 2019) actually implement cross-correlation rather than convolution. However, in the pre-processing stage, our con- volutional block-encoding immediately gives a cross-correlation block-encoding by simply switching the Q operator (Definition B.6) with a Q" operator. Finally, in this section, assume that all addition on basis vectors is mod the dimension of the vector. Le., for integers i, 1 1)) = I(++j) mod N),. (with N ).).
Definition B.4 (Permutation Matrix). Define the following N dimensional unitary permutation matrix that maps an input basis vector to the basis vector (i + 1) mod N.
0
0
P :
i 1)
0
1 0
0
(B.66)
1=0
Definition B.5 (Rz Phase Gate). Define the single-qubit phase gate, Rz(()) = eitZ
Eitt E ei
0
We now derive a block-encoding the permutation matrix P acting on m qubits. We include this result for completeness, and similar results may be found in the literature (see e.g., Motlagh & Wiebe 2024).. where they derive ID circulant convolution via QSP, or Camps et al. (2024)). Our implementation of pm is identical to +m adder implemented with QFT, see e.g., Draper (2000).
Lemma B.14 (Permutation Matrix Block-Encoding). Let E N Let N 2 The mhth power of the permutation matrix P is given by pm ΣØ=o li m) Then, can get -1,1,,)-blockkennoo with O(n²) circuit complexity for pm
Proof. Drawing inspiration from Motlagh & Wiebe 2024]; Sedghi et al. 2019), let F = QFT represent the Quantum Fourier Transform on n qubits. Define w'y
== eii//N Noting that = (i) it is easy to show that pm Flj) W mj Flj). Consequently, we can N ΣN En= N-1
VN
write pm FDF-1 where D d w ;.... ;...,, WN
mmN (N1)). Thus, by getting block- encoding of D, we can implement pn by taking a product of FDF-1 Let [/), be a basis vector, and let = 2n jn-1 +.. 2 + jo. We will now give unitary Vn, which implements the mapping Vn 15) = (0) 15) Noting that w 7m e 2nijm/N
n-- 2xxmmm(2")))//
31

---

Published as a conference paper at ICLR 2026
can apply sequence of n controlled Rz (f) gates, where the 1th gate is controlled on bit ji and applies Rz (m22 /N) on the ancilla qubit. This implements the desired mapping, and can be easily shown to be (1, 1, block-encoding for D. The Quantum Fourier Transform (Coppersmith 2002) can be implemented with (n²) circuit complexity (Nielsen & Chuang 2010), and so we can get a trivial (1, 0, block-nnnnn for both F and Ft, Thus, (71 & F)Vm @ FT) is a (1, 0)-block- encoding for pr, with (n²²) circuit depth. Its worth noting that since the ancilla qubit in Vm is separable after the computation, this could be equivalently considered (1, O, boock-nnnn... [
Definition B.6 (Discrete Unilateral Shift Operator). Define Q be the N-dimensional discrete unilateral shift operator,
0
0
1 0
0 1
0
N 2 Q = Σ li + 1)61 j=0
0
0
(B.67)
:
0
1 0
This is just the permutation matrix P without wrap-around.
Lemma B.15 "Slock-Encodiin of Q). Let = 2n, Define Q as per Definition B.6 Then, we can
obtain (1,4, 0) blo--bboo-noooiiggg for Q with On circuit complexity.
Proof. By Lemma B.14
we can obtain Up a (1, 1, (0-00)))-boo block--enooonnn Pf = = i ++ (1)
of the n--ubit projector [0) (N - 1| with (n) circuit depth. Following LCU (Childs Wiebe 2012 Gilyén eet al. 2019), we can get the sum of these two block-encodings, introducing
with (n²²) circuit complexity. Lemma B.6 we can obtain V a (1, (.l..))-locck-enooooe
additional ancilla, with the circuit U, == (H @ (10))(0) (0)2 @ [ @ Up (1/2 @ V) @ 12+x). Then, Uy is
a (1,3,0) (.330))-block-ecoodme that Q'Q = In - IN 1) - 1/. is clear that |[Q1 < 1. Moreover, since all the singular values of Q/2 are either 0 or 1 1/2, we invoke Lemma B.4 special case of oblivious amplitude amplification (Gilyén et al. 2019), to immediately convert this to a (1, 4,0 (oe----oo-eenodeeleeee for Q with only 3 calls to Uy.
for (P)
(NV 11) 1Q, with Onn²) circuit complexity. Noting
= 2". Define the N N-dimensional Lemma B.16 (Block-Encoding of "T).. Let E No and let N
operator Q as per Definition B.6 Then, we can obtain a (1, 4m, 0)-bllock-ncoodiin of Qt with Omm?²) circuit complexity.
Proof. As per Lemma 1.15 we can obtain UQ (1, 4, -)bblock-encodingg for Q with On circuit complexity. Invoking Lemma 53 (Product of Block-Encoder Matrices) of Gilynn et al. (2019) with Uo m times directly yields (1, 4m, Dy-block-encodingg of Q" with Omm")) circuit complexity
Now, we present a standard well-known result giving the matrix form of a 2D multi-filter convolution (see e.g.. Sedghi et al. (201)) Kerenidis et al. (2020).
Lemma B.17 (Matrix Form of 2D Multi-Filter Convolution). Let M 2mm let n = 2m, let N = 2", and let D = 2d. Let C = 2 represent the number of input and output channels. Let X represent the rank-3 3 input tensor, which in vectorized (stored in column-majon order for each lee., X)nte is of dimension MCC NC. Define X... Xi,,k i 0 and 2 O, and X otherwise. We can define the convolutional kernel K to be rank-4 tensor containing each of the C, C D D filters where the first index represents the output channel, the second index represent the input channel, the third index represents the row index, and the fourth index represents the column index. Then, entry y, z of the th output channel after convolution with K is given by.
input channel) is given by. X)n+t= = -.--1 -M-1 En-1 X (.)x,)())((j)m) (m)))))))kk..) (k)
C-1D-1D-1
X * x.y.Z =
ΣΣ J= T=
K K
(B.68)
*This can likely he optimizing by using QSVT GGilynn ct al. 2019
'If the number of channels is (i.e., C = 1), then the kernel D x D dimensional.
32

---

then yields (1, 3 8D 2 log(CD) 0) --bllc--enncdingg for C with O [1 D²mm) राí Published as a conference paper at ICLR 2026
Defining as per Definition 6.6
can give the matrix form of the convolution.
C-IC-ID-1D-1
C: >E 5=0
(B.69)
Le., C|X)atc= = X K).
Proof. We will verify that C indeed implements the mapping specified in Equation (B.68) by comput- ing the following, (x) (ylm (2|mC) C' X))+e. Note that for all i <<< 1, (ilQ* 0. and that for all i 2 I (ilQ' (i 11. Consequently, if y 12 0, h 0, then (jle (Vyl (= mn [ X
X3 -w--- and if < or= 2 - k < 0 then (ile @ (6ymm (2 Q @ Q*) = 0. Thus, (ile @ (=)mm @ Q*)
Nj t. Therefore.
(l) 00 00000))X))+ (2lo(Ulm(21m)
Σ 1=0
Σ
(B.70)
j=0
As result,
C-1 C-10-1P4 1-11
(olo(u)m (0m0mmmmmmmm))mmmmm
ΣΣΣ 3=0 A=D 1=0
K K [X KJ Klaga
(B.71)
Proof of Lemma 5 Define [XX K, and as per Lemma B.17
As a result, obtaining a block- encoding of C allows to implement the desired 2D convolution in the vectorized setting.
First, for a given j, k. I, we will show how to obtain a block-encoding of (li, @ Q*).
Using Lemma B.6, we can obtain U, (1, 2, blockkk--nnnoing of the c-qubit projector (i) (ile. with (cc) circuit depth. Then, using Lemma B.16 we can obtain UQi a (1, 4f, 0)) qubit Q' with Olm²) circuit complexity. We similarly obtain UQu a (1, 4k, Oj-block-encoding of m qubit Q* with O circuit complexity. We can then invoke Lemma B.2 with U,, and UQi. and again with Uqe. to obtain U.J.A.k, (1, + 41 4k, o)-block-encoding of (t) (jle @ Q' @ Q* with O(c + Dm²) circuit complexity. To make each operator act the same number of qubits, will augment each with the appropriate number of tensored identities to yield a 21,2 + SD, -lockock encoding for the corresponding operator.
of m
Define KK)2+2a Ei Σ5 EnD (.j.:1 and define |v K 2e+2d
VIK) (with the square-root applied element-wise). Then, define Nx == || K 20 =
|| ()) 22)l 1/2 and [K)o+2d == /K)2c4a//NK Noting that this vector is C2 C² dimensional, we can brute-force construct a unitary UK. with a total of O D²) single and two qubit gates, such that UK 20)2042 = |v 22c4244//N 2 (Plesch & Brukner 2011). We can then invoke Lemma B.5 obtain- for C with O(cdC D3mm circuit complexity.
ing (N 2 + 8D + log -)boo.)-blccckencoodd This is equivalent to (1, 2 + 8D + (CD), O)-block-encodiigg concerned with accelerating inference, will ignore classical pre-computation costs that must only be paid one time to construct this datastructure. We can then invoke Lemma B.3 setting 2T0
for C/ [|| ()2-22el1 Since we
y 2||a|l /2 [CIl2 and 8 1/2, since ||C/ (| S 21 2 Neglecting the logarithmic error-terms incurred by Lemma B.3 (as these will not dominate complexity), this
[C
circuit depth. We will now show that [1 < DC3/2, and thus that the overall circuit depth is bounded by O
[Cll2
We will now upper-bound ||K))c+2all, Define the basis vector (2)+22m = (ez))l(2))mm (la)) Then, the thth row of C is given by (alet2mC. Simple analysis shows that (xle+2mC = E5= Ed-1 D-1 K Kajsaallle @ (x2 1m @ (wa kmm where (I2 1| = 0 if 02 0
33

---

Published as a conference paper at ICLR 2026
and (xg kmm 0 if D3 - k 0. Then it can be readily shown that [[
2-11 Ei= KK......... For any operator A with ||A]|2 I 1, the maximum column norm m) || SS [=xx));||000,,=-- || S 1. Similarly, since || = =|| 1| the max- imum row norm cannot exceed the spectral norm of the matrix. Therefore, any row of C must have 22-norm bounded by ||C||2, thus, D E D [Kan.jaul < ||C||2 Consequently,
2j= 2x
|
I| (2)222l22 E Ej= ED-1 Ei=0 &K - C C Moreover, for an n-dimensional vector 2, ||>||| S vn |2ا|| and thus, ([ I VCDDVV [[CI|, = 3C ||C||p- Conse- quently, ||| (2)422lll / /|[]2 S DC
To see a set of related block-encoding circuits, see Camps et al. 2024
It is also worth noting that the preceding result can be made substantially more efficient by utilizing a eirculant convolution to implement the non-cireulant convolution. We will now quickly sketch this idea for future optimization. For simplicity, we assume that the convolution has one input channel and one output channel, and that the input a rank-2 tensor (e.g., a black and white image). Let M = 2mh Then, if the input image is X E TR. M we can add ( padding with the Mx M projector, |0) (0) (0)mm.... & X. Then, enacting a eirculant convolution on this augmented operator and projecting onto the zero-star state of the first register yields the desired non-circulant convolution. Moreover, we can define circulant -k-n
2D convolution as [X KJ,,- > D 1=0 Ka.IXi 1. The following sketch generalizes the 1D circulant convolution given in Motlagh & Wiebe (2024), and also follows the ideas discussed in Sedghi et al. (2019). Consequently, the operator C' := Σ -5 Pi @ p implements X K in the vectorized setting (using column major vectorization for X). Le == exp((xi//M) be the Mth root of unity. Let F := QFT represent the Quantum Fourier Transform on m qubits. It is (M 1)). Consequently, P = F FDF-1, and so C- (F @ F) (E Ej= D @ D (F- & F-1). Clearly, since implementing the QFT is efficient on a quantum computer, the key to implementing C is in implementing block-encoding of the diagonal matrix I' := E/= ΣØ=0 Kr, D @ D' Noting that this is a 1-sparse matrix with efficiently computable entries, a technique such as Gilyén et al.) (2019) can be immediately used to obtain the desired block-encoding (replacing QRAM assumptions with arithmetic oracles computing the locations and values of the non-zero elements). This can be further optimized by replacing the arithmetic with QRAM. In the multi-filter case, the diagonal matrix becomes a block-diagons matrix (with blocks of height and width given by the number of input and output channels), and the sparse block-encoding techniques can still be used.
easy to show that pk Flj) WM kj Flj). Thus, let D == FF-PPP-- = diag(w WM ..... W
d-1
B.3 NON-LINEAR TRANSFORMATION OF VECTOR-ENCODINE
We now present an essential result on transforming the amplitudes of a state encoded as a VE. This result is direct translation of the ideas in the result given in Rattew & Rebentrost (2023) (which in turn builds on Guo et al. (2024a); Mitarai et al. 2019)) to the setting of VEs. While Rattew & Rebentrost (023) also give similar result in the setting of VE (called an SPBE in that paper), they obtain it by treating the whole unitary VE as a state- snte-preparation unitary, and then invoke their non-linear amplitude transformation (NLAT) result on that, which gives slightly worse complexity than just directly re-deriving the whole transformation result in the framework of VEs. We include the following for completeness and simplicity, and do not claim novelty on this result.
Lemma 1.18 (NLAT of VE (Rattew & Rebentrost 2023)). Let N = 2 Let 0 < < 1, and Z 1. We are given a unitary matrix Up which is an (ax, a. eVE for the n-qubit real quantum state (w),, with circuil complexity OT)), and a function ʃ R + I with Lipschitz constant L such that f(0 O. Define E such that 0 61 S L. Define N := [[[([)) //)n// Define the interval of approximation [-T,T], where 0 < T S which can be set to either T = 1 or any value such that 2 It if a smaller region of approximation yields a better complexity. Define the
polynomial P + E, such that with degree k, maxxel-T:7] [P(x) f(x)) I Lag Suppose 2/N"
we are given a bound Fy satisfying 5 Z max /P(x)/zl) and require that P(0) = O. Then, we can obtain a unitary circuit Uy that is [ n 2a + 4, $o (eo + +e)))- -VE for [(W)n/a)/N.
34

---

Published as a conference paper at ICLR 2026
and which requires (kk) calls controlled U and U circuit, and has total circuit depth of O(k(n+a++ This circuit can be obtained with Oppoly(k, log( classical time complexity.
Proof. We will begin by considering the domain we require for the polynomial approximation. Essentially, by noting that > 1, the function being applied to a sub-component of an é2- normalized vector, and thus the maximum value of its imput will be strictly less than -- In some cases, this could yield a more efficient polynomial approximation, and so we will write our result both in the setting where the interval of approximation is [-1, and [- - a J. In particular, the function will be applied to ((0)a @ 1 a+) and so we must upper-bound the maximum amplitude in this quantity. Define E R such that 0 < c S 1. Define the un- un-normalized vector 1m)n := (10)a @ up 0) Define |F = w), a 2. and note that ll la S 1, and thus that [1 - - |Ep) 212 I 1. Additionally, by Definition 3 Illl,) S co. Define {øylı such that N
(6) 1 0yli)n Thus, |0,| - |1 1ll2 (1 + 60). Detine e = min (1 + +o), 1).
Let Ne := N. Let Np == IIP(())/a) I1. Define the degree k polynomial Q(x) == P(z)/2. and define E2 such that ma,,e [xx) f(x)] 62.
Using Lemma 6 of Rattew & Rebentrost (2023). we can get a (1. + n + 2, 2,0) (l)-bbock-ennoddnn UA of A :- diag(U,, (v,,((00w)))))) with Ola n) circuit depth, and 6 additional calls controlled Up circuit. Invoking Theorem 56 of Gilyén et al. 2019) with (xx) we get the unitary Ug. a (1,a + n + 4, J-block-encoding for Q(A77 47, requiring O((a n))k) single and two-qubit gates, O(k) calls to a controlled UA circuit, and O(poly (k. log 1/e))) classical computation to determine the QSVT rotation angles implement the degree k polynomial. We can equivalently call UQ a (1,a a + n + 4,
for some matrix V, such that VV - Q (A)/45ll, S 6. Additionally, define Eq == V (44) Since for any vector æ, Q(diag(z) (z))== P(z). we get, V \Up|0)a+n 10)+ + Ev 10) Additionally, noting that (10), @ P(x) P(((0). @ Ln)x), and that 49
((0)a @ I, 10)0 I we get ((0)a I,) (0) a/tn
p(())a) ((0)a Ev a)
49
Define U == I Tatnt4 3 Up-
First, note that (,)0)/222244
(10)ntat & 0) Then, note that ((0),, n-2a+44 X I,) = (10)a & (n)( 2 lata). Consequently, by Definition 2. since ((0) n+o+4 X (Q00)) +a+4 @ Tatn) V,
(10) @ (0) 20 = (10)a @ VU, 10)a.n
(B.72)
P(()),) + (10)a 8 U,)
(B.73)
44
We will now show that Up is a VE for Ne f(1))/a) Precisely, we must uppper-bunnl
& = | ((1))
47 (10 24+4 1 UQ) 10)
(B.74)
No
2
1 (II(IW)n/a) P(()) 45 (1) Lv)
$ No.
(B.75)
Let (11E)) = eg. We will now prove sequence of simple facts. Since [fxx) -f(x + b)l <
LIbb, and using 10)n = EEgin we have that [l - f(( = En lf((b)
f((b,, e²) < 3 En lepp = 3 >m < Lag0 Then, llf())).) p((Ø)
ΣN [))1)((0))- - -(())) s maxx 1f(x) - P(x) < SN Then,
[I((I))n/a) P((0))))l2 -1/((v)m//)) f()))) + f(()),) P(1)))))22
(B.76)
< LED + +
(B.77)
At this point, the proof branches into two cases. The first case is where we simply use the uniform approximation to the function on the entire interval |-1, 1]. The second case, which should only be used when approximating the function on [-T, 7] yields a better asymptotic approximation, will be proven after.
35

---

Published as a conference paper at ICLR 2026
Noting that II((0), @ Ln) 5 6, can now get the overall bound of
( LEo + + + +55) Ei S No.
1
1 +Loo+e2VN + 456).
1
S
(B.78)
No.
Thus, we have shown that UqUivis is ( 2a+n+4, N (LeottovN++555) To get the overall error-bound, we will set E2 N N L and 476 Le1 yielding e2 2/N' and Lea. This gives - 2a 4, N (co + + for N f((v))//a) and requires (Ak) calls to a controlled Up and U circuit, and has a total circuit depth (k + + This circuit can be obtained with O(poly(k, log( (,, ))) classical time complexity.
N.. f(lv)n/a).
Ler
87
To make the preceding result easier to use, we provide a special case for transformation by the error function, and again do not claim novelty.
Vector Encoding). Let = 2n, let 2 1/2, let 1 2 co 2 O and let 0 < 61 S 2. We are given a unitary matrix Up with circuit complexity ((T) which is an (ar, a, (0, -VE for the n-qubit quanttum state w)),, and we are also given the error function fulz)
Lemma B.19 (Application of erf (var)
(rf). Let N := (lfu(ll))//)) 1/) Then, can obtain
2a + T. + 4, 2vo(Eo + E1) - VTN
16v
for fo fu(l))n/a)//) with O log( vN queries to controlled Us and U circuit, and with a total (a + + T)), Moreover, 2 2a
circuit depth of Oyy log(
//N a
Proof. From Lemma F.1 we know that the Lipschitz constant L of erf(vx) is L
Define e = ((1 /a). Using Lemma F.1 we can obtain a degree h E O(vlog(v/aee) polynomial PR,,, such that (0) = and max (x) fx(x)) S d' Since we need e' S Le
2/N"
we can set é' polynomial approximation.
M51 in accordance with Lemma B.18 we have a degree & E O(vlog( vN 10./
From Lemma F.1 for v 2 1/2, we know that V E (-1,0))(0,, 1], (or((v)) 2 |x/2]. Consequently, A/2
4e jj=1 [(()//a))² 2 )2 Additionally, we know that 7 = maxxe[-1,1] (1) <
v then gives the
Invoking Lemma 1.18 setting with all of the above facts and setting 7 = complexity.
4u Vir
C GENERAL ARCHITECTURAL BLOCKS
The architectural blocks we present in this paper are intended to demonstrate how the different operations on encoded matrices and vectors can be combined to coherently implement various architectures on quantum computers. There is rich set of possibilities, and we are only exploring small but elucidating set.
Two of the most important concepts governing the complexity of the quantum implementation of any classical architecture are: (1) the number of non-linear activation layers, and (2) the Eg norm of the vectorized input tensor as it propagates through the network.
In order for a unitary matrix (a linear operator) to enact a non-linear transformation on a vector, its definition must depend on the vector it is being applied to. Consequently, techniques which enact non- non-linear transformations on aatteaamllsteees (c.g., Rattew & Rebentrost (2023); Guo et al. (2024a)) must have circuit definitions which depend on the vector-encoding circuit they are being applied to. Thus, if the unitary circuit implementing the transformation requires even two calls to the input vector encoding, then the circuit complexity will grow exponentially with the number of non-linear activations. Consequently, wide but shallow multi-layer architectures are ideal for quantum acceleration. Finally, an alternative to fully coherent quantum acceleration is to periodically read-out the vector in intermediate layers of the network. As discussed in the introduction, several quantum computing papers have proposed this approach. However, in general, since reading out a quantum state incurs dimension-dependent cost (Cramer et al. 2010) van Apeldoorn al. 2023) (and incurs
36

---

Published as a conference paper at ICLR 2026
polynomial (ror-dependdece) this either imposes significant constraints the types of architectures that can be accelerated (requiring frequent mappings to very low-dimensional spaces where readout is cheaper), incur asymptotically dominating eπror accumulation. Nevertheless, there are certain settings where periodic state readout may be desirable, and our techniques are fully compatible with these ideas.
The second key concept governing the complexity of a quantum implementation of an architecture relates to the norm of the encoded vector as it propagates through the network. Whenever a sample is drawn from an encoded vector, a cost inversely proportional to the norm of the encoded vector must be paid. Similarly. whenever an encoded vector is normalized, an inverse norm-cost must be paid. Consequently. to obtain provable end-to-end complexity results, we need to be able to lower-bound the norm of the encoded vector whenever we apply a layer norm (or draw a sample from the output of the network). A key tool in doing this is the skip connection, as it allows the norm from the previous layer to be preserved in the output of the next layer. Additionally, if the weight layers are normalized (i.e., if W represents the matrix form of any parameter layer, then || activation function is scaled so that its Lipschitz constant on the interval [-1, 1] is at most 1, this results in provable norm- norm-preserve preservation bounds. Requiring weight-layers to be sub-normalized has been extensively explored in the classical deep learning literature (Miyato et al.) [0188] Yoshida & Miyato 2017 Gouk al. 2020), sub-normalization can help prevent network norm explosion as deeper networks are trained.
1), and the
It is worth briefly noting that, in certain cases, the sub-normalization condition on the weight layers can be removed (i.c., for matrix W, 0 < ||W||2 S с where e > 1). This is done by implementing W/||W|lz 2l, and then scaling the input of the subsequent activation function by || If using the error function activation, this increases the cost of the polynomial approximation by an amount proportional to c. We do not consider this regime as it makes it more challenging to prove norm preservation properties after the skip connection, but stress that quantum computers can actually implement such regimes. Numerical studies examining norm preservation for such networks could shed light into their efficiency.
We will now formally define our no-m squared pooling; this is essentially just an f--morm pooling operation followed by element-wise square. Throughout we will assume that dimensions neatly line-up, noting that if they don't 't padding can be used to easily and efficiently ensure alignment.
Definition C.1 (Squared & Norm Pooling). Given an N-dimensional vector (0) > @elk),
and positive integer C such that N is divisible by C, define fj (j 1) j 1. Then, we define fz-norm squared pooling by (lolc(lo)) = = Ete Ril)), where {li)} is the set of C-dimensional basis vectors.
Lemma C.1 (Error Propagated Through &g Norm Squared Pooling). Define the N N-dimensional vectors (6) and (ő), such that [10) - 10) S c. Then, defining a positive integer C such that N is di-
visible by C, and defining poole as per Definition C.I we have that [poooc(lo)) - poolc(()))
2Ne vC
Proof. Let (0) Σn"1 أ51ر), and let (0) = Σكح T511). Then,
(0) - (0)
S c implies that
2
Vj. ر, < Then, additionally using that (Ø, + أ5ه S 2,
2
(lo)) - (10) =
Σ Σ
C
JNJC
(őr - 3)(( + 2i)
< 4
Ne
2
2 (C.1)
C
#=1
1=1
Proof of Lemma 6 The parameter k in the lemma is designed for situations where we don't 't have a perfect block-encoding of the matrix would like. For instance, in cases where we want to apply some matrix A, but we are only able to get a block-encoding of A/2. We can fix this when applying the activation function by scaling its input remove the 1/2 factor.
37

---

Published as a conference paper at ICLR 2026
P2-0
Figure 4: Full-rank linear-pooling output block.
Figure 5: This figure shows the final output architectural block used in our neural networks for Regimes and Here, g(x) = x² and W is sub-normalized (potentially full-rank and dense) matrix.
Let = 4k/5. Let (61) == W // Ni == (n and ( = (a)))a/M. Using 2 get U1 a (NT a b, coNTT V-V for (1),. with O T2) circuit complexity.
Let 122)n = ((W()))) N₂. == I1 and (22n == 102)n/N2. Define < 61 I
1. Invoking Lemma 19 with U1 and f(xx erf(4kx/5) erf(uz), obtain U2
16 2( + b) + 4, N - (Ea + +e))) VGNg;
-VE for I((I)),N)) (I(())) (22) U2
N (a + has circuit complexity O log
So as to invoke Lemma 1 to implement the skip connection and obtain a state proportional to b
we will need to factor out a common factor of vTT Consequently, we invoke Lemma B.9 on Up to I6
obtain U/ a (16 a + 2, co)-VE for (V), with O + a) circuit complexity. VF
Define (7)n = hia//N Then, we can invoke Lemma (setting 7 1/2) with 0% and U2. yielding U3
320 (1v)) (2) L (l f(Wlv)))) Nr := Ill7), and [T),,
L
1.(a, (NG) 2(a + b) + n 15, N,
f 16r
+
Nova (2wN) (co + =i]] - for [T),, with circuit com-
16r
plexity O(v log( N (a + +n Ti + T2)). statement.
We will now simplify the error component of this VE
First, define (z)n = Σ, 1)) = W Then, using the fact that f(x = erf(4x/5) has
Lipschitz-constam of 5V- (as per Lemma B.19 AZ (L((W)))))l s Σ, (xx)) <
8
(5 )2 E. nyp (
| pl) Since [[]] 2l, 1, [W] 12 I 1, and thus N2 S 5VF I 0.91. Next, we must lower-boumt N₁. Thus, N? = ( ? (1 + N+ - (22 2
(32v (1 2 (V)) (0000)3) Consequently, using that 8/5 (since
2) get
that Nr, 2 1/400. Additionally, it is straight-forward to show that Ne/M1 I 0.91x I
Inserting all of these values and performing simple algebra, find that Ug is equivalently (W-1 2(a + b) + n + 5, 355(cc + +G)) for (T),.
Let 0 < 62 S 1. Then, invoking Lemma B.8
we get (1
+(1 + +2))
VE for [[),, with circuit complexity O(log(
v e 1o+ +T)). If we let e2 = El. then we can simplify this to (1,2(a + b) + n + (1 +-)--V with circuit complexity
log( + + Ti T2)). Ollog( /N [log(
Proof of Lemma 7 This result comes from repeatedly invoking Lemma 6, with the output of each application becoming the input of the next.
We will first give a bound on the total number of ancilla qubits of the block-encoding giving the final output after i residual block layers. Let dg the residual block, the number of ancillas is given by a; = 2ag + c. Then, the general form for the number of ancillas is given by the recurrence d; 20;-1 1 + We can obtain upper-bound by
2b
9. After one application of
38

---

Published as a conference paper at ICLR 2026
instead setting a, 2(a,-1 cc. Clearly, a; = (a c) 2a 2b + 9). Thus, we have (1,2% 2b + n 9), -noccccinn......
We will now determine bound on the resulting error, e. Note that the 7th residual block introduces a new arro--aramettr& & which controls the error in the activation function and the normalization of that block. After the first iteration, the error 61 is given by 61 712(co + (1). After the second iteration, the error from the previous iteration becomes the new co. and so the error after the second iteration is given by 82 = 712(0) + +2). We can set 6 _, giving the general form of the error after the 7dh residual layer of 6; = 14248;
724 1424 e1 1424' /2. Noting that we want final error of at most e, we must set 6g I c. Le.. we can set c 1424 / = 6 2e/1424.. 1424'
Thus, for > 1, each = 6 = 1424''1/2 T424 e/ 1
Define h(4) log( NN/NNe/ /c,) log /c,) Let the circuit complexity of the block-encoding after
applying residual blocks be ((R)). Noting that R1 E ((h(c)(ao + b+ n + T1 + T2)). ) R3
asymptomatically dominates 7i, T2, ai- 1, n and b. Then, the eircuit complexity after block + 1 will be O(h(Ec+))(a, + b+ n - Rg + Ti)) E O(h(E++1)(a) + R.)). Then, we can simplify to
find that Rg O(aa + II] h(e)) O((22(a + 26 + n)) + + I2 h(e/14244-)) ')). Noting that II. h(e)) E O 1-1 log( (og(v//e))))
hl=//(ee44224 ()) E O(II,, (k
log( v / /e.))))) E O((k+log( /N)(e) 2h). Since is an asymptotic constant, O(k-log(VN/ee) e Olog( /et)) Thus, the overall circuit com-
Olog( (oog(VN/e)) /e))., and so I h(e/1424--)
plexity is given by O(log( (lllog///c)2*(cc + 2b + T + T2)).
Lemma C.2 (Full-Rank Linear Pooling Output Block). Consider the architecture block shown in Figure 5) Let the dimension of the input vector be N 2", and let the dimension of the output of the network block be C' = 2 (i.e., the number of classes). Let the output of the network be given by the vector ly)e. Suppose we have Up an Eg)VE for the N- N-dimensional input vector [+)) with O(T..) circuit complexity. Here, Teo makes explicit that the complexity of the input circuil will be dependent on the desired error of the vector encoding of the layer imput to this architectural block. Suppose we are given access to an arbitrary matrix W such that [| I 1 as per Theorem B.1 Then, if the weight on the skip hhip-path&e is 0.51, we can draw a sample from a vector (6)c such that |10)- - lw))|12 S with Ologg Vce) (Te. + + n²)) circuit complexity and with O(a + n) total
ancilla qubits.
Proof. Let d represent the number of bits part of the QRAM encoding of W, as per Theorem B.1 Note that d is assumed to be an asymptotic constant. Let ( == W o( .)) = [ and ( = / Using Theorem B.1 we can get (NT 2a + d + 3 + n, 2e ) for
( with OTe, + dn + n²) circuit complexity. Here is a constant specifying the precision in the representation of the elements of the matrix stored as per Definiitiio B.3
Let [7)n = -l + (1 - T) P)NN = T|bb), + (1 - - >) Wy(()),). and let Net == 1112)
Then, Lemma yieldd V/2 a (V₂1, 2a + d+4+ 3e0 V-E for hn), with OTe,, +dn n²) circuit complexity.
We will now lower-bound N₁. The main idea is that if you are summing two vectors, one with norm 1, and the other with norm at most 1, if you put arbitrarily more mass on the constant-norm vector (8). you are guaranteed that the vectors cannot fully cancel out, and thus that some norm is preserved the sum. Note that M
|[W a(1)),)ll2 < [|i]| E3 13b5)mm = <|<E, 13,6)%1 = 1. Consequently,
11)| < 1, and so
N² || nn + (1- 7)
= (1 ()- + 27(1 (w)1))
(C.2)
2 7² + (1 - N)? (1-
+ (1 (r (1-((17)))
(C.3)
For some parameter 8 [0, 1], assuming that 7 (1+ 8)/2 we then get that N₂ 2 8.
Then, define E E (0, 1J. We can then invoke Lemma B.8 8.8 yielding V (1, 2a + d n, VE for I7),/N, with 0(3 (g((1/e)(TT,
+ 2-1)- Gea
dn + n² circuit complexity.
39

---

Published as a conference paper at ICLR 2026
Define poolş as per Definition C.1
Noting that poolc(())./NN)) 19)c.
We equivalently define some fg-normalized state (T),, such that V33 is a (1, (1,2a d 8 n, OV-VE ||i',,
for (I'),. Then, since
l1 - aga 2E,, we can invoke Lemma C.I which shows that
N
p (1F))) -w)))) - vc
Bra 2
Consequently, get an error of at most e, set 2N Gén 2e1) e, by setting é1 vC
vC
and
8.
cvC8 = Then, we can simply draw a sample e-close to lu)e in f--norm distance by sampling the 60 24N
state prepared by V3 and then assigning it to the appropriate bin.
Setting = 0.02 gives T = 0.51. Then, V is a (1, 2a + d + 8 + n, c,c)-VE for ht/,N,, with circuit complexity. Consequently, we can draw a sample from some
Ollog( VCc (Te, +
vector (o)e such that | - w///// s e with ( (())), +a+da++2)) E Ollog( /Ce (T.o + a + n²)) circuit complexity, and with (aa + n) ancilla qubits, noting that d is an asymptotic constant.
D FEASIBILITY OF QRAM ASSUMPTIONS
In this section, we consider the feasibility of different QRAM assumptions to help motivate our discussion in Appendix El In InCcctioon D.I we consider the feasibility of our QRAM assumptions. In SSection D.2 we summarize how arbitrary quantum states can be prepared by using a QRAM data-structure, in service of our subsequent discussion of the different architectural regimes.
D.1 PASSIVE AND ACTIVE QRAM
clear that, if a fault-tolerant quantum computer can be constructed, that a QRAM based on the various quantum circuit constructions (see]aques & Rattew (2025): Giovannetti al. (2008);; Hann 2221)) can be directly implemented. Moreover, these circuit constructions have log-depth access costs. However, laid out in Jaques Rattew (2025), the fundamental issue regarding the practicality of QRAM comes down to the opportunity cost of the total energy required to implement query the QRAM. Precisely, given QRAM with N bits of memory, a QRAM is considered passive if and only if each query to the QRAM requires o(N) total energy input. If the query instead then the QRAM is
requires (2(N) energy input (even if the time complexity is (ppolyoog(N) active. Importantly, this means that any QRAM implemented in the crror-correctd circuit-model must be active, as each qubit requires (1) classical resources to run the error-correction, resulting in ((N) total energy cost per QRAM query. Even if ernor-correction is not used, if enacting the gates in the system requires constant energy input (e.g., by enacting the gates as laser pulses) then the QRAM will be active. If the QRAM is active, then Jaques & Rattew (2025) show that a wide-range of quantum linear algebra applications lose quantum speedup. Moreover, there are additional challenges such as how noisy (non-error corrected) quantum memory could be interfaced with an error-corrected quantum processor.
However, noted in Jaques & Rattew (025) there is some hope in practice, and we will now outline their arguments. As an example, consider classical Dynamic Random Access Memory (DRAM). DRAM requires a constant power draw for each bit in memory, and thus an N-bit memory requires ((N) energy input. This makes DRAM active. Nevertheless, because the energy expenditure of DRAM is often dwarfed by the energy expenditure of the CPU accessing it usually treated as being a passive component in classical algorithm design. For instance, Carrrll & Heiser (2010) demonstrates that for mobile phones, "RAM power insignificant in real workloads" and Mahesri & Vardhan (205)) draws similar conclusion for laptops. At larger server-scales, the asymptotics of active memory become more noticeable, but memory still usually draws less power than the
controlling CPU (Ahmed et al.) 2021 Fan et al. 2007). Analogously, consider regime where QRAM is active, but its constant energy costs are extremely small relative to the energy costs of the crror-corrected quantum computer it is being interfaced with. Given the substantial expected overheads of quantum error-correction (Babbush et al., 202I). the ratio of energy consumption for an error-corrected QPU to active QRAM could be even more favourable than in the classical setting.
40

---

Published as a conference paper at ICLR 2026
Then, if there is some way interface this noisy device with the error-correcte QPU, for moderate scales (e.g., terabytes of memory), it is conceivable that the QRAM could be practically treated as passive. We will call this a "practically passive QRAM". Nevertheless, even though practically passive QRAMs are asymptotically active, they are unlikely to allow full error-correction without losing their constant advantages (unless, for some reason, the structure of QRAM allows for extremely efficient custom-made error-correcting codes). Consequently, it is important that the QRAM implementation is resilient errors. Indeed QRAMs based on the bucket-brigade architecture (Giovannetti et al. 2008b), are intrinsically exponentially (in terms of the number of memory registers) robust to errors (Hann Hong et al. 2012).
al. 2021 Hann
2021
In this paper, for simplicity. when making a QRAM assumption we treat the QRAM as passive. We stress that substantially more work needed to fully understand the feasibility of QRAM, but that is plausible that the QRAM assumptions made in this paper could be physically realized in practice. In particular, assuming that truly passive QRAM M is impossible, we outline the following questions (building on Jaques& & Rattew (2025) ) which could result in our results being practically useful. How can a noisy QRAM system be interfaced with an error-corrected quantum computer? If such an interface is possible, how do errors in the QRAM propagate through the error-correction in the QPU? Recent promising work (Dalzell et al.] (025a) provides answers to these two preceding questions, and offers path forward for research aiming to construct practically passive and useful QRAM. Additional questions which need to be investigated to help realize a practically passive QRAM include some of the following. What is the ratio in energy consumption for plausible practically passive QRAM systems to the energy consumption of the controlling fault-tolerant QPUs for different crror-correcting codes? Given potential active (practically passive) QRAM architectures, what the total expected energy consumption for different sized memories?
D.2 INPUT PREPARATION VIA QRAM
The data-structure due to Kerenidis & Prakash 2017) can allow for an arbitrary quantum state to be prepared, so long as the state amplitudes are made available through specific QRAM data-structure. Lemma D.1 (Input Data QRAM
(Kerenidis & Prakash (0177). Let N 2n Given vector x E RR,,, we can define data-structure utilizing a QRAM with O(N) total qubits storing æ. Then: (1) the cost to update (insert, delete, or modify) an entry x is O(n)), (2) using the QRAM data-structure, the state (x)- = = |0l12 can be prepared by a circuit with depth O(n²), acting on (nn) qubits.
This is just a special case of the more general result in Kerenidis & Prakash (2017) giving a similar data-structure for arbitrary matrices (which we presented as QRAM for quantum data in Appendix A). Intuitively, the state can be prepared by following Grover-Rudolph (Grover & Rudolph 20022, using the QRAM data structure containing the tree of binary partial norms of the vector to compute the controlled rotation angles for each additional qubit.
E ARCHITECTURES IN DIFFERENT REGIMES
As summarized in the main text, the results presented thus far can used to construct a range of architectures in number of different settings. In particular, we consider three regimes characterized by the QRAM assumptions they make. In the first regime, we assume that both the input to the network and the weights in the network are made available via QRAM. In the second regime, we assume that the network may use QRAM (since its QRAM data-structure may be pre-computed prior to (iference-time), but that the input to the network is received classically and entirely on-the-fly, fly, and thus that the input cannot be provided with QRAM (so a cost linear in the dimension of the input must be paid to load into the quantum computer). In the third regime, we assume QRAM. We will now expand on the arguments presented in the main text in greater detail.
E
REGIME 1: INPUT AND NETWORK USE QRAM
Here we expand on the argument presented in Section 4.J
Neglecting the finite precision error due to storing vector elements (and their partial squared sums) in binary representations
41

---

Published as a conference paper at ICLR 2026
Online Input Construction Noting that perfSection D.2 data structurss can be efficiently updated, we note that there are a number of settings where it might be realistic for the imput vector to be provided via QRAM. For example, in any setting where inference needs to be repeatedly performed on a slowly-changing input (e.g.. in an interactive chat with an autoregressive L.M,, where each output token becomes part of the new input), or where the input is the result of some other quantum algorithm. For example, in the context of auto-regressive interactive LLM (where the output would be a probability distribution over tokens instead of classes), the initial vector æ might be an encoding of the hidden prompt to the network (and so the associated data- can be pre-computed). As user queries the LLM, small number of tokens are added to æz and these updates can be efficiently performed to the data structure. Then, the network is run, and the new output token is added to æ again efficiently. This process can then continue to repeat, and so the cost of loading the data is either entirely precomputed, or amortized on-the-fly. We can envision similar applications in the classification of video, where a very large, but slowly-changing video needs to be analysed one frame at time. Here, cost would need to be paid proportional to the number of changing pixels between each frame, and so the input data-structure could be efficiently updated. Additional settings where it might be reasonable for the input be provided efficiently could be if the input corresponds to some combination of continuous function (via Rattew & Koczor (2022)), or if it was prepared as the output of some other quantum algorithm.
Receptive Field To understand the importance of the final linear layer in the architecture for this regime, we must first summarize the receptive field problem of multi-layer convolutional architectures.
For simplicity, consider 2D convolution with one input channel and one output channel, and consider a sequence of & such convolutional layers. Let the kernel be D x D. Since convolutional layer can map the information in location j to, at the furthest, the location i + D + D, after k layers the information in any given entry will come from local information in the input at most R kD pixels away. Consequently, the final layer which input to the output Inear-layer-residual block will contain features with &D local information, which the linear layer then combines in global fashion. We conjecture that having a full-rank layer at this stage is more effective for merging the local information than similar dimension, but low-rank, linear layer. Since the cost of the quantum algorithm grows expomentially with depth, without the final linear layer, with such an architecture no learning could occur which requires global information from the input image.
Moreover, there are other approaches which could be taken to make the local information globally accessible to the earlier convolutional layers, potentially improving the power of such quantum- amenable architectures in practice. For instance, after a set number of convolutional layers, a linear layer could be added to make local information global (however, this damages the nice algebraic properties of convolutional layers). Alternatively, a sequence of convolutions can be implemented in each residual block (without activation functions between them) as this would not increase the complexity exponentially, potentially allowing for many more convolutions in sequence. Most appealingly. a solution can be found in the popular classical architecture of bilinear neural networks (Lin et al. (015)) (which forms the basis of the architecture presented for Regime 2). Here, paths of convolutional-
residual blocks are passed into a Kronecker product. which is followed by more layers. Via Lemma 3] can efficiently do this in a quantum computer. Since the Kronecker product makes all local information globally available, it immediately solves the receptive field problem. However, while Kronecker product makes local information globally accessible, it loses positional information. This can be resolved by enacting a positional encoding along one of the paths of the network prior to the product, e.g., as is done when Tokenizing the inputs transformer architectures /Vaswani et al. 2017).
Dequantization A number of quantum algorithms which were believed to have exponential speed- ups over their classical counterparts lost their exponential speedup after new classical randomized algorithms were developed which mirrored the quantum input assumptions. For example, see the works of Kerenidis & Prakash (2017) and Tang 2019). Indeed, it seems likely that, as was the case with the quantum CNN implementation in Kerenidis et al. (2020), that the convolutional residual blocks in our architectures could be dequantized (even though they make no QRAM assumptions). However, new techniques enables the final linear-residual block to contain an arbitrary full- rank and dense matrix. Since known dequantization techniques require the matrix to be either low-rank (Chia al. 2022 Tang 2019) sparse (with certain strong caveats) (Gharibian & Le Gall
42

---

Published as a conference paper at ICLR 2026
2023), existing techniques appear insufficient to dequantize our full architecture. Moreover, as previously discussed, removing the final linear layer introduces receptive field problems, highlighting that it is not purely artificial addition to the network. Nevertheless, it would be interesting to exploring dequantizing the architecture without the final linear layer (or perhaps replacing it with a low-rank one), and this could result in some interesting techniques to classical accelerate inference for certain architectures.
E.2 REGIME 2: NETWORK STORED IN QRAM, INPUT LOADED WITHOUT QRAM
See the discussion in Section 4.
E.3 REGIME 3: No QRAM
To reiterate, in this regime, both the matrix weights and the network input are not given by QRAM. We will now prove the complexity of the Regime architecture shown in Figuue (c), as discussed in [Section 4.1 We note that there are many simple modifications which could be made to this architecture, for example by having a final low-rank linear layer with ((V) parameters. Adopt the notation used in Theorem 2) Let the input be 4 x M x M tensor, and define N M m = Logg(M) Thus, the vectorized input is of dimension O Let be the number of paths into the input tensor (i.e., the latent dimension will be O(N))), per Figure 1 (c). Tx is the access cost of the input: in the QRAM- free regime we assume a worst-case of Tx E E(N). Let C' be the number of output classes (or set of possible output tokens).
loga (NV),
Assume d = 2. Let 5 > 0 be an error parameter used only in the proof. Directly from the proof of Theoormm 2 we have U a (1, 2* (63- 5) (vector encoding) for the fz-normalized output of the convolutional/residuall block layers. Ucamy has Olog((N/8) (n22 + Tx)) circuit depth. Note that in that proof, N corresponds the vectorized dimension of the latent space (i.e., if there is input and output channel, N corresponds to the dimension of the vector acted upon by the matrix-form of the 2D convolution), and thus corresponds to N' here.
Let (o) represent the exact vector output after the sequence of l convolutional layers. This VE corresponds to state (ø) such that ll - (क) ll < 8. Consequently, by Lemma C.1 sampling this VE (and applying the (aaming-protooo) yields sample from vector (lo) such that vC
[poolc<(1)) - (1))il I 2N2g Noting that the correct output of the network is given by y = (l)), we can get an overall error of e, such that the vector sample from satisfies ly - (1o)_ S by setting e = 2N'8 complexity of U and noting that here we assume we pay the full input dimension cost (since there is no QRAM). Tx E O(N), and so this simplifies to O(N log(N2 /evC)22) E Ö(N (og(1/e)2) total circuit cost. As stated in the main text, since the dimension of the vector acted on by the 2D convolution is O(N2) (when d=2), the classical cost to compute this is 2 2N2): showing quadratic speedup over an exact classical implementation. The speedup can be made asymptotically larger by increasing d.
vC = = e/CC
2NT. By plugging this into the circuit
Possible Limitations Here we will outline some of the possible limitations of the architecture shown in Figure (c). Since there is no final linear layer (in the architecture as directly presented), the receptive field problems outlined in /Section 4.1 may appear to apply. However, by virtue of taking the tensor product of the input paths, local information becomes immediately globally accessible circumventing this limitation. Moreover, another way that local information could be made global is from the processing that occurs along each path prior to the tensor product, since there is no limit on the classical processing that can occur (so long as the total compute is linear in the dimension of the input).
Moreover, our argument against dequantization in the first regime (see (see [Section 4.1p relies on the final dense and full-rank linear layer. However, since this layer is not feasible without QRAM, this argument does not apply here. However, as we are only suggesting a polynomial speedup in Regime 3, we do not expect dequantized algorithm to completely close the performance gap past quadratic, as we benefit from amplitude amplification. However, exploring dequantized algorithms based on the ideas in this paper appears be interesting subsequent work.
43

---

Published as a conference paper at ICLR 2026
Finally, if the network only contains the convolutional layers, it will likely be very under- parameterized making training challenging (see e.g., AAllen-Zhu et al. (2019) for a discussion on overparameterizee neural networks). However, where the dimension of the vectorized input is N, would be easy to add ((N) parameters, either in the classical paths prior to the tensor product, or final low-rank residual output block (prior to the f2-norm-pooling) long the number of parameters in that block are ((N).
Parameterized Quantum Circuits as Network Layers Alternatively, one could use parameterized quantum circuits network layers (Peruzzo et al. [014 [enedetti et al.) 2019b) Cerezo et al., 2021), as the number of parameters in such circuits are usually polylogarithmic in the dimension of the operator. However, such circuits are often hard train even on classical machines, due to under-parameterizztion the barren plateau problem (McClean et al.] 2018 Larocca et al. 2025), and the exponential amount of bad local minima the optimization landscape (Anschuetz & Kiani 2022). However, given good enough initializations and warm start assumptions (Mhiri et al. 2025
Alternative:
may still possible to train such architectures, leading to potential speed-ups in inference.
Other Possible Sources of Speedup In some cases, where the input can be efficiently prepared cost (e.g., the input comes from quantum states which are easy to prepare, either via some other quantum algorithm, or via techniques like Rattew & Koezor (2022) it may be possible to obtain better than quadratic speedups. However, we leave this as topic for future investigation.
without paying dimension-depente
F TECHNICAL RESULTS
We now report a result on the efficient polynomial approximation to the error function due to Low Chuang (017), which builds on the results [Sachdeva & Vishnoi (2014). This result is an improvement over the approximation obtained by integration of the series expansion for the Gaussian distribution.
Lemma F.1 (Polynomial Approximation to Error Function due to Corollary of Low & Chuang (2017). Let m 2 1/2, 2 e > 0. There exists degree k O0 polynomial Pk.m (x) such that
Pr.m (x) = 2me m
(--1)/2
(22++1(r)
T2j 12)-
1o(m²/2)cx +
1, (2)
V
2j +
2j
(F.I)
and maxxe(-111) |er((ma) Pa.m (2)) < Let 1 >>>>>>> 0. Alternatively, if E O0 (r)) S Additionally, for all max PP (x)/2l and Pk.m (0) = O. Finally, mingel-1.11 erf(mx))/x) 2 1/2, and erf has Lipschitz constant
then maxxel-e.e] (ef((m)) Ps. Pm
4m
V
L = 2m
V
Proof. For the case where max /.t.1///rrr(mmm crf(mz)) Pk. S C, the result on the polynomial
approximation is directly taken from Low & Chuang (2017). We will now prove the bound when the
function is constrained to the interval [-c, cl. Let = maxzel-c.e (er((mr)
(x)((x)) From
Equation (71) of Corollary 4 of Low & Chuang (017)) for degree k polynomial approximation, we have the following error- bourdbound.
2me m²/2
12)++(2)
T2j- (x)
61 &
Σ
(F2)
T
2j
+1
2j
j j=(k1)//2
Using the identity
12))(()) 25+1
Th 1 (w)
20 (I)dt, and using the fact that all Cheby-
23
shev polynomials of the form T2j are even, we can get the bound that [a)+
Tz)=
<
2j+1
25-1
2 2 (2)(1))dt < 2/ll & maxxell-oe] |or|
2c, since max [2)5(x) < 1.
44

---

Published as a conference paper at ICLR 2026
Then, applying the triangle inequality, Equation (F.2)
becomes,
4cme m2212
e1
VT
15(mm/2))
(F.3
J= (=+1///2
Define Eganss,y,k as per Corollary of Low & Chuang 2017 Define some e' > Note that Cgause,7,k = 2e 2/ /2
Ej 2+=3+1 115(79/2), and that Cgauss,7.k c' if k E
((2(22 + log////))) Thus, 61
To get overall error-bound of most Thus, we set E O(m cm )), we are guaranteed that maxxze[-eec |P (x) erf(mx)] e.
2ome'
v
e, we can set 2ome' = e, and so vie 2cm
vi
Next, da crf(mx) = 2m e (ma)" and consequently the maximum value of the derivative of the vT
function is when x = O, i... max
de erf(maz)] V
2m
We will now prove that Pa (x)/al v and min (ef((m)))/// 1/2.
Noting that Pm (0) = O, (since for x = 0, T25(x) = cos((2) + 1) arccos(O)) = cos( (2j 1) 0), by Lipschitz continuity we have that (P (x))/z) S de Pm,m(()) Noting that
L Tar+1(z) Ty-1(()) (25(2),
de 2 25+1 2-
d
(m.m(())aa max =E|-1,1]
max
Pk.
.m (x))
(F.4)
xE(-1,1]
dr
2me m²/1
(k-1)/2
1o(m²/2)+2 +2 Σ 1/ (2]((1)\TT))
max x =E(-1.1)
V
(F.5)
A common identity for modified Bessel functions of the first kind states for f. * 0, e c
Σ 0o (v). Setting & 1, we find et Eズ Iz()). Moreover, since [v() 2 for all
y > Σラ=1 (k-1)/2 (m /2) S m Thus, using that max [x) S.
PR (x)/xl 4me mm² 11/2
4m
max
Σ
15(m² (2)//2)) -
(F.6)
j=1
Thus, it is clear that this upper- bound is independent of the degree of the polynomial approximation,
and thus applies to the whole interval x E [-1,1] and not just x E [[c,c]] c].
Finally, must show that min crf(mm)) 2 1/2. First, note that eef(mmx) /=| is symmetrical, so we can simply consider the interval æ [0, 1]. Moreover, it is monotonically decreasing, so we can take the endpoint minze!-1.11 [er(mm))/a) erl(m). Since m 2 1/2,
crf(m) 2 erf(1/2) /2) 0.52 > 1/2.
45


Reviews:
[{"review_id": "5ckwtrKi4l", "reviewer": "Reviewer_GrZJ", "summary": "This paper presents a theoretical framework for accelerating inference in multi-layer neural networks, specifically those with ResNet-like architectures, using a fault-tolerant quantum computer. The authors introduce a set of quantum subroutines to coherently implement key components of modern deep neural networks, including multi-filter 2D convolutions, non-linear sigmoid activations, skip-connections, and layer normalizations. The work analyzes the inference complexity under three different quantum data access regimes, determined by the availability of Quantum Random Access Memory (QRAM) for inputs and weights. The main results claim a polylogarithmic cost in the input dimension. when QRAM is available for both inputs and weights, and polynomial (quartic and quadratic) speedups over classical methods in regimes with limited or no QRAM access.", "questions": "The paper's key contribution is reducing the dependency on the input dimension. However, this appears to come at the cost of an exponential scaling with respect to the number of network layers. To enhance the paper's theoretical depth, could the authors provide a dedicated discussion on this critical trade-off?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper makes a significant theoretical contribution by providing a quantum algorithm for a highly relevant classical task—deep neural network inference—and offering rigorous proofs of an asymptotic speedup. This directly addresses the core goal of Quantum Machine Learning (QML).\n\nA major achievement of this work is the construction of a fully coherent multi-layer architecture. By designing primitives that avoid intermediate measurements, the algorithm circumvents the readout and re-encoding bottleneck that has plagued previous proposals for deep QNNs. \n\n The authors' development of the vector-encoding (VE) framework is a key innovation. Critically, this framework enables the implementation of complex operations like 2D multi-filter convolutions without QRAM, directly addressing one of the most significant feasibility concerns surrounding many proposed quantum algorithms.", "weaknesses": "The framework presupposes a large-scale, fault-tolerant quantum computer, which is decades away. Therefore, an estimate of the quantum overhead of this algorithm for a specific application is critical for assessing its practical feasibility.\n\nThe paper is mathematically dense, making it challenging for a broader audience to grasp its core mechanics. The lack of high-level intuition and illustrative explanations of the core algorithmic mechanics hinders the work's ability to convey its conceptual breakthroughs and limits its overall impact.\n\nAlthough the model reduces the dimension dependence, this comes at the cost of exponential scaling with respect to the number of layers. A discussion on the trade-off between system dimension and model depth could enhance the paper's theoretical depth.\n\nThe paper's analysis is asymptotic, and it lacks numerical simulation to validate the algorithm's behavior or performance characteristics. Some approximation of the model performance will significantly improve this paper.", "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": "", "extra_scores": {}}, {"review_id": "aFDcmGxNUO", "reviewer": "Reviewer_LfKb", "summary": "This paper presents a fully coherent quantum implementation of a multilayer neural network architecture inspired by classical ResNets. The authors design a family of quantum residual blocks that include multi-filter 2D convolutions, sigmoid activations, skip connections, and layer normalization. The key contribution is a fault-tolerant inference algorithm that, under different assumptions about quantum data access (inputs and weights), achieves up to a quartic speed-up over classical inference.\n\nThe analysis formalizes the quantum complexity of inference in three settings:\n1. No quantum data access (quadratic speed-up).\n2. Efficient quantum access to weights (quartic speed-up).\n3. Efficient access to both weights and inputs (polylogarithmic scaling in N/ϵ).\n\nThe work focuses on theoretical algorithm design and complexity proofs, without empirical quantum-hardware demonstrations.", "questions": "No empirical validation: While the results are theoretical, even small-scale simulations or resource estimates (for near-term or logical qubit counts) could help contextualize the practical significance of the proposed speed-ups.\n\nCould this framework generalize beyond ResNet-style architectures, for example, to transformers or graph networks?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Strong theoretical grounding: The paper is mathematically rigorous and develops clear proofs for each claimed speed-up regime.\n\nNovel construction: Presents, to my knowledge, the first coherent quantum implementation of a multilayer residual network with nonlinear activation and skip connections.\n\nSolid literature placement: The work situates itself appropriately relative to prior quantum neural network and quantum linear-algebra algorithms, clarifying how block-encoding techniques generalize to deep architectures.\n\nPotentially broad impact: The modular framework could be extended to other neural architectures or used as a building block for hybrid quantum–classical learning pipelines.\n\nClear organization: The text is logically structured, with well-defined assumptions and computational models.\n\nDespite being theoretical, this paper is a well-constructed and rigorous contribution to the quantum machine learning literature. The results are technically sound, clearly presented, and potentially influential for future algorithmic developments in quantum deep learning.\nWhile its immediate practical relevance is limited, the conceptual advancement—showing coherent quantum analogues of residual networks with formal complexity guarantees—justifies acceptance at ICLR, provided the venue continues to welcome high-theory work at the intersection of ML and quantum computation.", "weaknesses": "High theoretical abstraction: The paper is highly formal and primarily relevant to researchers in quantum algorithms. It lacks discussion of practical feasibility, especially the resource requirements for realistic network sizes.\n\nLimited accessibility: The work assumes familiarity with block-encoding, and fault-tolerant quantum computation. This makes it difficult for deep-learning practitioners to appreciate its implications or limitations.\n\nNo discussion of training: The paper only treats inference and does not address how such quantum architectures could be trained, even conceptually. Since training dominates the computational cost in deep learning, the absence of any consideration of gradients, parameter updates, or trainability significantly narrows the scope and impact of the contribution.", "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": "", "extra_scores": {}}, {"review_id": "ST8XDCaPs5", "reviewer": "Reviewer_yibn", "summary": "The paper studies the important task of constructing quantum implementations of neural networks, with the goal of achieving provable speed-ups in neural network inference due to quantum phenomena. The paper considers convolutional ResNets and provides an extensive theoretical study, covering different types of assumptions about quantum data access.", "questions": "- Could you obtain the same results for more common choices of activation functions? \n- Lemma 5: the Lemma requires that the convolutional matrix is normalized, which is rarely the case in practice. Is there a way of absorbing this, e.g., into the input? \n- Can you provide more insights on what the Assumptions on the input mean in Theorem 2? \n- From the statement of Theorem 2 it appears that for each new data point, you would need to construct a new circuit. Can you comment on this? \n- Can you clarify on what you mean by \"return a sample from some probability vector\"? This is very important, otherwise the main statement is not clearly understandable. \n- Can you clarify in Theorem 2 how the sample is obtained from the circuit?\n- The neural network sizes assumed in Theorem 2 are very specific (you assume 16 input channels, output channels etc.) Why is this needed? It would be more convincing  to have a result for general sizes of channels. \n\nA few minor points on clarity: \n\n- The legend of figure 1 is a bit confusing, as it says \"The figure shows the architectures we consider ... under thre different regimes of quantum data access assumptions\". However, the figure does not contain any clues about how quantum data access differs in the different subfigures. Could you clarify this? \n- The legend also states that \"the input is assumed to be a rank-3 tensor (e.g. images with 4 channels)\". Wouldn't this correspond to images with 3 channels?\n- In lines 108/109 epsilon appears without having been introduced. \n- In Definition 1 the role of the error epsilon is not mentioned.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "While several previous works have studied this problem for different types of architectures (Kerenidis et al. for CNNs, Guo et al. for transformers), the paper provides important advances by allowing \"coherent\" multi-layer archiectures and non-linearities, where no readout or tomography is required. Employed methods build on previous work by Rattew & Rebentrost on Quantum Vector-Encodings, but extend these in various directions. Considered ResNet architectures are mostly practically relevant, thereby contributing to the building quantum subroutines for provable speed-ups for neural network-based learning. \nIn terms of presentation, the paper is mostly very well-written and clearly presented (except for some ambiguous mathematical statements).", "weaknesses": "There are still several important points related to relevance of assumptions and soundness of the claims / mathematical statements that I think need to be discussed thoroughly: \n\n- Choice of activation function: the introduction and abstract state that the deep learning architectures use sigmoid activation functions. However, throughout the paper (Lemma 6, Theorem 2 and Figure 1) it seems that only \"erf\" is used as activation function. This is not a commonly used activation function due to lack of closed-form expression. \n- Circuits depend on input: a fundamental issue appears to be that the circuits depend on $x$. This issue already appears in the problem statement in Definition 1. The statement suggests that for a fixed $x$ you aim to find $\\hat{y}$ with $|y-\\hat{y}| \\leq \\epsilon$? But in practice you would want to vary $x$. This seems to become a central issue in the main result in Theorem 2: the unitary matrix $U_X$ there depends on the value of the input, which then also seems to affect the overall circuit construction. Looking at the proof, lines 397-399 suggest that the circuit would need to change whenever a new input data point is processed in the network.  \n- Clarity of mathematical statements: the main findings of the paper are weakened by some unclear mathematical statements. For example,  in Definition 1 it is not clear what is meant by \"return a sample from some probability vector $\\hat{y}$ ...\". Is this a random vector from which you randomly sample a realization? If yes, then with a certain probability the sample may not have the desired property. Can you quantify this probability? The same issue appears in the main result in Theorem 2: the statement does not relate the constructed quantum circuit with the vector $\\tilde{y}$. Can you be more clear on how this vector is drawn? And what do you mean here by \"we can draw a sample\" (same question as before)? \n- Assumptions on input: In Theorem 2, the input matrix is assumed to have a representation by a unitary matrix (see lines 378-380). Can you comment on this assumption? Is it easy to shown to be satisfied in certain situations?", "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": "", "extra_scores": {}}, {"review_id": "gtJFbH6t4y", "reviewer": "Reviewer_JGKB", "summary": "This paper proposes a fully quantum method for simulating the inference process of multi-layer neural networks. The authors claim that their approach can achieve exponential speedup when using QRAM, while still maintaining a quadratic speedup in QRAM-free scenarios. The work provides a potential pathway for leveraging fault-tolerant quantum computers to perform inference tasks. However, for the reasons outlined in the Weaknesses section, I do not believe this paper merits acceptance at the ICLR conference.", "questions": "Please refer to the weakness section.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The authors address one of the most interesting topics in the field of quantum computation—using quantum computers to accelerate classical AI. They also provide a clear summary of previous results and explain how their work relates to them.", "weaknesses": "1. The manuscript is not well written: many complex definitions and results are deferred to the appendix. The paper would be more suitable for a journal without strict page limits.\n\n2. Since the QRAM is a very strong assumption, which may require 2^n circuit depth to prepare a target state or the block-encoding of the matrix, all quantum speed-up results based on the QRAM assumption have very limited practical significance. For example, if a practical quantum computer with error-correction function were provided, can authors provide an analysis on how many single- double- quantum gates are required to achieve a QRAM oracle? Moreover, if the QRAM assumption is permitted, classical L2-norm based sampling methods (dequantization algorithm proposed by E. Tang, Nat. Rev. Phy. 4, 692–693, 2022) may achieve similar speedups for low-rank cases. Consequently, I am not convinced that the QRAM-based theoretical results in this paper make a sufficiently strong contribution to the community.\n\n3. Following the above concern, the only potentially valuable contribution of the paper appears to be the QRAM-free scenario discussed in Lemma 5 and Section 4.1.3. However, I cannot follow the argument justifying this claim. In section E.3, the authors claimed that quantum circuit U_{conv} has approximate  O(log(N)T_X) circuit depth, which is central to the claimed quadratic speedup. Tracing this statement back to Theorem 2, I still find the justification unclear: the authors do not provide a convincing derivation or explanation for this depth bound. Please clarify the derivation and state precisely which assumptions are required.\n\n4. A minor error: the author list for this reference is not correct: Towards provably efficient quantum algorithms for large-scale machine learning models. Nature Communications, 15:434, 2024.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)