arXiv CSopen access

Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry

· arxiv_cs

arXiv CS · Papers · License: Open Access

cryptography cybersecurity privacy security

cryptography, security, privacy, cybersecurity

Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry Frédéric Magniez∗ and Sebastian Zur†

arXiv:2609.10808v1 [quant-ph] 9 Sep 2026

CNRS, Université Paris Cité, IRIF, France September 11, 2026

Abstract How much memory is needed to retain the quantum speedup for collision finding? For a uniformly random function f : [N ] → [N ], the BHT algorithm [BHT97] finds a collision using 1/3 O(N 1/3 ) queries and a quantumly accessible classical table √ containing O(N ) input-output pairs, whereas a logarithmic-space Grover search uses O( N ) queries. Determining the optimal query-space tradeoff between these extremes remains a major open problem. We resolve this equation within the class of label-symmetric algorithms, which treat the function f ’s output labels as interchangeable. We prove that such algorithm that makes T queries, uses S qubits, and finds a collision in a uniformly random function f : [M ] → [N ] with constant probability satisfies T = Ω(N 1/3 )

and

T 2 S = Ω(N log N ).

For the setting where M = N , these bounds are matched by a space-efficient implementation of the BHT algorithm. As a consequence of our tradeoff, any label-symmetric algorithm for the search version of Element Distinctness on f : [n] → [n2 ] must satisfy T = Ω(n2/3 )

and

T 2 S = Ω(n2 log n),

matching Ambainis’s quantum walk [Amb07]. Thus, both tradeoffs are optimal within the class of label-symmetric algorithms. To prove these results, we develop a space-sensitive version of the compressed oracle technique. The compressed oracle records the information learned by the algorithm in an evolving superposition of databases. Using label symmetry and representation theory, we show that an algorithm using S qubits can effectively retain information about only O(S/ log N ) collisionfree database entries. Substituting this estimate into the compressed oracle technique yields the stated tradeoffs. The key step identifies the relevant subspace of collision-free compressed databases with the least eigenspace of an arrangement graph, whose vertices are injective stuples and whose edges join tuples that differ in precisely a single coordinate. Of separate technical interest, we sharpen the previous analyses of the bottom of the spectrum of these arrangement graphs, identifying the exact spectral gap above the least eigenvalue. ∗ †

Email:[email protected] Email:[email protected]

Contents 1 Introduction 1.1 Context and motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Related works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Open problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Technical overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 1 3 4 5 5

2 Preliminaries 8 2.1 Linear algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Representation theory of the symmetric group . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Quantum query complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.4 Space complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3 The compressed oracle technique for collision finding 12 3.1 The compressed oracle technique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 Application to collision finding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4 Space bounds in the compressed oracle technique 4.1 Symmetry restrictions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Collision-free compressed databases . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Representations in Cs⊥ ∩ W ⊗s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Alternating projections onto Cs⊥ and W ⊗s . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Space bounds for collision-free database states . . . . . . . . . . . . . . . . . . . . . . 4.6 Time-Space tradeoff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

18 18 20 21 23 26 29

5 Examples of label-symmetric algorithms 32 5.1 BHT and Ambainis’s quantum walk . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.2 Equality-query algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6 Bottom spectrum of the arrangement graphs

Introduction

1.1

Context and motivation

Post-quantum cryptography. One of the most dramatic potential applications of quantum computing is its ability to compromise widely used cryptographic tools. Shor’s algorithm [Sho97], for example, factors integers and computes discrete logarithms in quantum polynomial time. These problems form the main pillars of many of today’s public-key cryptosystems, while the best-known classical algorithms for them require sub-exponential or exponential time. This threat has prompted an international effort in post-quantum cryptography to identify new fundamental primitives that would remain secure against quantum computers [PQC06, Ber09b]. Note that an alternative approach to strengthen our current classical cryptographic primitives is to shift to quantum technology and use quantum primitives such as the BB84 quantum key distribution [BB14]. Even though this technology is much more mature and currently being tested via satellites and telecom fibres, it still relies on classical cryptosystems in order, for instance, to authenticate classical channels of communication. A less spectacular, but still serious threat comes from the BHT algorithm [BHT97] for finding collisions in hash functions. Hash functions are also a pillar of modern symmetric-key cryptography. A basic security requirement for any hash-based cryptosystem is resistance to finding distinct inputs on which the hash function takes the same value, since many attacks begin by finding such a collision pair. Even an ideal hash function is vulnerable to the generic randomised attack based on the birthday paradox, which gives a quadratic improvement over deterministic exhaustive search. Security parameters are therefore chosen with this attack in mind. The BHT algorithm gives a further quantum improvement, finding a collision in a random function with a cubic-root quantum query complexity. Consequently, resisting quantum attacks requires larger security parameters than resisting classical attacks. The quantum advantage for collision finding, however, strongly depends on the memory available to the algorithm. In particular, the BHT algorithm relies on a large memory with quantum access. This makes the role of memory in quantum collision-finding algorithms especially important. Bottleneck of quantum memory. Quantum memory will probably be a major bottleneck for future quantum computers, especially when it must be accessed in quantum superposition in a single unit of time, as in a quantum analogue of random-access memory (RAM). Such memory has been formalised and used in several quantum algorithms, including the BHT algorithm and Ambainis’s quantum walk algorithm for Element Distinctness [Amb07]. In the former, the memory itself remains classical but allows quantum access and is therefore called QRACM; in the latter, the memory itself is quantum and is called QRAM (or a random-access gate). An early proposal and physical-architecture study of QRAM appears in [GLM08]. In the Turing model, access to memory is sequential and thus takes linear time to address one cell of the memory. In the Random Access Memory (RAM) model, access is direct and can be done in basically one unit of time. The RAM model is closer to actual computers, but it has limitations when processing, for instance, massive data. Note that in the circuit model, a multiplexer can implement the analogue of a RAM operation, but it costs linear circuit size, since it uses a linear number of Boolean gates with constant fan-in. Thus, (quantum) polynomial-time algorithms usually do not explicitly require (Q)RAM, since they can simulate it with a polynomial overhead. Nonetheless, this remains critical for other 1

algorithms, in particular those processing massive data. So algorithms such as Shor’s algorithm do not explicitly require QRAM, but for those based on Grover Search [Gro96], which provides a quadratic speed-up that is often significant for massive data, the quest for QRAM is fundamental. Based on those facts, some criticisms were made against the BHT and Grover algorithms [Ber09a]. A 2D-grid architecture of N classical processors with log N memory has been compared to a quantum computer with log N memory but with quantum access to a large classical memory (QRACM) of size N . In particular, it has been shown that the 2D-grid architecture proceeds as well as the quantum computer, and even better in some cases [Ber09a, Jef11]. To answer this criticism, another quantum algorithm was designed in [CNS17] which uses only logarithmic-size quantum memory, but polynomial classical memory, while still providing a significant but smaller quantum advantage in its time complexity. This illustrates the importance of understanding the role of memory in quantum algorithms. Since it is still unclear which memory model (QRAM, QRACM, or more restricted quantum memory) will be realistic in future quantum computers, it is natural to study how the time complexity depends on the available space, independently of the particular memory model. This leads to the study of time-space tradeoffs. Time-space tradeoffs. Time-space tradeoffs quantify how the running time of an algorithm depends on the available memory. Their study has two complementary parts: algorithms provide upper bounds, while limitations on all algorithms provide lower bounds. Because unconditional lower bounds on computational time are generally out of reach, one needs further assumptions such as the exponential time hypothesis (ETH) [IP01], or, as in this work, one can use the querycomplexity model, where access to the input is restricted to a specified oracle. In that model, one input query is supposed to take one unit of time. Then, given some space-bound restriction, we prove a lower bound on the query complexity instead of the time complexity. For instance, given comparison access to an array of size N , sorting the array requires at least Ω(N log N ) (classical or quantum) comparisons [HNS02]. If instead space is limited to at most S bits, then the number of comparisons T satisfies T S = Θ(N 2 ) (when S = Ω(log N ) and S = O(N log N )) [BFK+ 81, PR98] for randomised algorithms. In the case of quantum algorithms, one can show that T 2 S = Θ̃(N 3 ) [KŠDW07]. Other such randomised and quantum tradeoffs have been established for a range of linear algebra problems including matrix-vector product, matrix inversion, matrix multiplication and powering [KŠDW07, BKW26]. However, in the context of collision finding, the situation is much more complex. First, in the classical evaluation model, when one has access to some random hash function f : [N ] → [N ] by querying f (x) for any x, there exist methods, such √ as the parallel collision search algorithm [vOW99], that succeed in finding a collision within Õ( N ) queries and only √ polylogarithmic memory, ruining the hope of any time-space tradeoff. Together with the Ω( N ) query lower bound for collision finding in a random function, even without a space restriction, this shows that additional memory cannot yield a substantial query-complexity improvement in this setting. When the function is no longer random, the situation is quite different. This problem is known as Element Distinctness and consists of deciding whether the function f is injective. The bestknown algorithm satisfies the tradeoff T 2 S = Õ(N 3 ) [BCM13, CJWW22, LZ23]. However, the best lower bound is barely superlinear [Ajt05, BSSV03]. One can interpret this as a consequence of the short output size. Still, in the comparison model, the situation is a bit easier, and by an amazing

tour de force, a line of work has established the almost tight classical tradeoff of T S = Ω(N 2−o(1) ) (the upper bound T S = Õ(N 2 ) comes from sorting algorithms). Due to the inherent difficulty in establishing time-space tradeoff limitations for short-output problems, such as collision finding, the quest for such a tradeoff for finding a collision in a random function took some inspiring detours. One of them consists of finding K collision pairs in a random hash function f : [N ] → [N ]. Classically, Dinur [Din20] proved the tight lower bound T 2 S = Ω̃(K 2 N ), matching the upper bound of [vOW99]. The problem was subsequently considered in the quantum setting by Hamoudi and Magniez [HM23]. Their work popularised the compressed oracle technique, also known as the recording queries technique, of Zhandry [Zha19], as a method for proving strong quantum query lower bounds in the low-success-probability regime, which in turn yield strong direct product bounds and time-space lower bounds. In particular, they proved e 2 N ) throughout the T 3 S = Ω(K 3 N ) and, by adapting the BHT algorithm, obtained T 2 S = O(K 2/3 1/3 e e range Ω(log N ) ≤ S ≤ O(K N ). However, determining the optimal quantum time-space tradeoff for finding a single collision remains today a major open problem, highlighted by Aaronson in [Aar21] as quoting below: Open Problem [Aar21, Problem 3] What are the optimal tradeoffs between the number of queries used by a quantum algorithm to solve the collision or the element distinctness problems, and the number of qubits or classical bits of memory?

1.2

Contributions

In this work, we solve the above open problem for a restricted class of quantum algorithms. We establish the first quantum time-space lower bound for finding a single collision in a random function f : [M ] → [N ], for the class of label-symmetric algorithms, and show that the resulting tradeoff is tight in the standard case M = N . Informally, an algorithm is label-symmetric if its strategy does not depend on the labels assigned to the range elements: the strategy is similar for f and σ ◦ f , for any permutation σ of [N ]. The formal definition is stated in Definition 4.4. Result 1 (Informal version of Theorem 4.18). Any label-symmetric algorithm that finds a collision in a uniformly random function f : [M ] → [N ] with constant probability and uses T queries and S qubits of space must satisfy T = Ω(N 1/3 ) and T 2 S = Ω(N log N ). √ It is natural to assume M = Ω( N ), in which case a uniformly random-function contains a √ collision with probability bounded away from zero. If M = ω( N ), this probability tends to one. Neither assumption is needed for the correctness of the lower bound. Taking the domain size to be n and the range size to be n2 gives a tight consequence for the search version of Element Distinctness, because a uniformly random function f : [n] → [n2 ] contains a collision with constant probability. Result 2 (Informal version of Corollary 4.19). Any label-symmetric quantum algorithm that finds a collision in every non-injective function f : [n] → [n2 ] with bounded error satisfies T = Ω(n2/3 )

T 2 S = Ω(n2 log n).

and

It is natural to ask ourselves whether our restriction is too strong. In fact, both the uniform input distribution and the condition that an output pair forms a collision are already invariant under permutations of the range labels. The labels therefore carry no intrinsic meaning, and there is no evident reason for an algorithm to benefit from treating particular labels differently. This motivates our focus on label-symmetric algorithms. Indeed, both the BHT algorithm and Ambainis’s quantum walk for Element Distinctness satisfy this condition (Lemma 5.3 and Lemma 5.3). More generally, any algorithm whose only input-dependent operations are pairwise equality queries asking whether f (x) = f (x′ ) is automatically label-symmetric (Lemma 5.4). Result 3 (Informal versions of Lemma 5.3 and Lemma 5.4). The following algorithms are labelsymmetric: • BHT algorithm for Collision Finding; • Ambainis’s quantum walk for Element Distinctness; • Any algorithm whose only input-dependent operations are pairwise equality queries. For random collision finding with M = N , BHT with table size r uses r N T =O r+ and S = O(r log N ). r For 1 ≤ r ≤ N 1/3 this gives T 2 S = O(N log N ), while r = N 1/3 gives T = O(N 1/3 ). For Element Distinctness, Ambainis’s quantum walk with 1 ≤ r ≤ n2/3 gives T 2 S = O(n2 log n). Thus, our tradeoffs for random collision finding and the search version of Element-Distinctness bounds are tight. Of separate technical interest, we obtain a sharp analysis of the bottom of the spectrum of arrangement graphs. An arrangement graph may be viewed as an ordered analogue of a Johnson graph: its vertices are injective s-tuples (y1 , . . . , ys ) ∈ [N ]s , and two vertices are adjacent if and only if they differ in exactly one coordinate. We sharpen previous spectral results for these graphs [CGW13, AB17] throughout the full regime N ≥ 2s, determining both the least eigenspace and the exact spectral gap above it. Result 4 (Arrangement Spectral Gap, informal version of Lemma 4.9). Assume N ≥ 2s. The smallest eigenvalue of AN,s is −s, and the gap above the least eigenvalue is N − 2s + 2. This spectral estimate is a key ingredient in our space lower bound: it allows us to control the collision-free part of a compressed database that can be retained by an S-qubit label-symmetric algorithm. We give the precise spectral statement and explain its connection to the collision problem in the technical overview below.

1.3

Related works

The quest for quantum time-space tradeoff limitations for finding a collision for random hash functions was initiated for the lower bound part in [HM23], but for the case of finding multiple collisions only. The compressed oracle technique was introduced by Zhandry in [Zha19], mostly for studying the security of classical cryptosystems. Since then, its applications were developed for various settings including query complexity. 4

The quantum query complexity of symmetric algorithms has been studied before, for example for insertion into an ordered list [FGGS99] and for ordered search [CCKDS26], but these works use a different notion of symmetry (translation invariance). In our work, we consider the symmetry for which the algorithm’s strategy is unchanged when the range labels are permuted. This symmetry is more relevant for the collision finding problem.

1.4

Open problems

The main open problem is to remove the label-symmetry assumption. Because both the uniform input distribution and the collision success condition are invariant under range relabelling, it is difficult to imagine how treating particular labels asymmetrically could help. Nevertheless, the usual method of symmetrising an arbitrary algorithm stores a random permutation and can require Θ(N log N ) additional space, so it does not preserve the parameter that our lower bound tracks. A space-preserving symmetrisation argument, or a proof that avoids symmetry altogether, would extend the tradeoff to all algorithms.

1.5

Technical overview

The main difficulty in proving time-space tradeoffs for quantum collision finding is that the usual analysis only measures how much information the algorithm has learned, but does not directly capture how much of this information can be stored in a limited amount of quantum memory. Our proof overcomes this difficulty by combining three ingredients: the compressed oracle technique, the label symmetry of algorithms that treat output labels as interchangeable, and a representationtheoretic analysis of the linear spaces in the aforementioned compressed oracle technique. Together, these tools show that an algorithm using only S qubits cannot maintain a large collision-free database, which limits how quickly it can create a collision. Compressed-oracle progress. Our proof is based on the compressed oracle technique [Zha19, HM23], which we introduce in Section 3. In this technique, we represent what the algorithm knows about a uniformly random function f : [M ] → [N ], by a superposition of databases. These databases are initially filled with ”empty“ cells (x, ⊥), representing that the algorithm has no information about the value f (x), but after t queries, each branch of the superposition contains a database with at most t cells of the form (x, f (x)). The unitary evolution of these database branches through queries is quite subtle, but it was formally shown in the seminal work by Zhandry [Zha19] that we can think of a query (to x) adding a random fresh cell (x, f (x)) to the database. The progress of the algorithm can now be tracked by defining projections onto these databases, such as Π≥1 , which projects onto all branches such that there exist entries (x1 , y), (x2 , y), i.e. a collision, or Π=0 which projects onto all databases that contain no collision. More formally, if |ψet ⟩ is the superposition of our databases after t queries, ∆t := ∥Π≥1 |ψet ⟩∥ denotes the amplitude on such databases that contain at least one collision. A new query can create a collision only by adding new cell whose label f (x) is already present at another occupied position. This intuition allows one to bound the increase of ∆t , formalised in Lemma 3.5, in terms of the

number of occupied entries in the collision-free part of the database. Write Λs for the projection onto databases with exactly s occupied positions, then 1/2 X t 4 2 e s∥Π=0 Λs |ψt ⟩∥ . ∆t+1 ≤ ∆t + √ N s=0 Since s is always bounded by t and that {Π=0 Λs }s form a set of mutually √ orthogonal projections, 3/2 using Cauchy-Schwarz we obtain the standard estimate ∆T = O(T / N ). Since the probability of success of our algorithm is approximately equal to ∆T , we recover the usual T = Ω(N 1/3 ) quantum query lower bound, if we require that ∆T = Ω(1). Our main task is to replace this crude bound by one that also depends on the available space. The space restriction from label symmetry. In Section 4.1, we introduce label symmetry at the level of the reduced state of the input register ρI , obtained by tracing out the algorithm’s register in the joint state on the algorithm and the input. Label symmetry implies that the support of ρI is invariant under permutations of the N range labels. However, any quantum algorithm that uses at most S qubits, the Schmidt rank across the joint state is at most 2S , and hence the reduced state ρI has a rank of at most 2S . Those two observations imply that the orbit (under the symmetric group SN ) of every vector |β⟩ in the support of ρI spans a space of dimension at most 2S , leading to the following orbit bound that we state formally in Lemma 4.3: dim span{σ|β⟩ : σ ∈ SN } ≤ 2S . In Section 5, we verify that this label-symmetry assumption is satisfied by both the BHT collision-finding algorithm and Ambainis’s quantum walk for Element Distinctness, as well as by the broader class of equality-query algorithms. This shows that label symmetry captures natural quantum algorithms and, together with the BHT upper bound, establishes the tightness of our tradeoff in the standard case M = N . Collision-free compressed databases. To exploit the orbit bound, in Section 4.2 we introduce a representation-theoretic model for a database with s occupied positions. After fixing these positions and omitting all ⊥ entries, the recorded values may be identified with vectors in C[N ]⊗s . Two subspaces of this tensor space arise naturally. The first is 1 X W := span{|b 0⟩}⊥ ⊆ C[N ], |b 0⟩ := √ |y⟩. N y∈[N ] Each |b 0⟩ intuitively represents ‘knowing nothing’ about the function value, and is mapped to a ⊥ cell in the compressed oracle technique. Thus, valid databases with s non-⊥ cells lie precisely in W ⊗s . The second is the collision-free subspace Cs⊥ := span{|y1 , . . . , ys ⟩ : y1 , . . . , ys are pairwise distinct}. Consequently, the central space in our analysis is Cs⊥ ∩ W ⊗s , which consists of states that are simultaneously collision-free and compatible with a database in the compressed-oracle representation. 6

Representation theory and arrangement graphs. We next determine the SN -representation L carried by our space Cs⊥ ∩ W ⊗s . To achieve this, we define the deletion map D := sr=1 dr |Cs⊥ , obtained by, for each coordinate r ∈ {1, . . . , s}, applying dr which deletes the r-th coordinate. On the one hand (Claim 4.7), this map D is related to Cs⊥ ∩ W ⊗s through the identity ker D = Cs⊥ ∩ W ⊗s . On the other hand, the operator D† D has a natural graph-theoretic interpretation, D† D = AN,s + s · Id, where AN,s is the adjacency operator of the arrangement graph. This graph may be viewed as an ordered analogue of a Johnson graph: its vertices are the injective s-tuples in [N ]s , and two vertices are adjacent when they differ in exactly one coordinate. It follows that the space of collision-free compressed databases is precisely the (−s)-eigenspace of the arrangement graph: Cs⊥ ∩ W ⊗s = ker(AN,s + s · Id), Our spectral analysis, stated in Lemma 4.9 and proved in Section 6, shows, for every N ≥ 2s, the space ker(AN,s + s · Id) decomposes into irreducible representations that are all of high dimension, namely at least N N − . s s−1 This exceeds 2S whenever s > 2S/ log2 N , meaning that a vector accessible to an S-qubit labelsymmetric algorithm cannot have a nonzero component in ker(AN,s + s · Id) = Cs⊥ ∩ W ⊗s for such large values of s. This will be crucial for establishing our time-space tradeoff. The noncommuting projections difficulty. One difficulty is that the two natural conditions on a database, being collision-free and being a valid compressed database, are described by projections in the computational basis and the Fourier basis, respectively, and hence do not commute. The spectral gap of the arrangement graph controls precisely this discrepancy. In Lemma 4.10, we prove ∥ΠCs⊥ ΠW ⊗s − ΠCs⊥ ∩W ⊗s ∥2 ≤

2s − 2 . N

(1)

Consequently, once the component in Cs⊥ ∩ W ⊗s has been ruled out, the squared norm of the projection onto the collision-free subspace Cs⊥ ΠW ⊗s is at most (2s − 2)/N times the squared norm of the original state. From the database space bound to the tradeoff. In Section 4.5, we combine all our aforementioned intermediary results to obtain a tighter bound, one that involves the space S, on the quantity t X s∥Π=0 Λs |ψet ⟩∥2 . s=0

We bound the quantity s∥Π=0 Λs |ψet ⟩∥2 , depending on whether s is larger than 2S/ log2 N or not. If s is smaller, the bound is straightforward and we obtain 2S 2 e ∥Λs |ψet ⟩∥2 . s∥Π=0 Λs |ψt ⟩∥ ≤ min t, log2 N 7

For s > 2S/ log2 N , we know from our representation-theoretic analysis of the space Cs⊥ ∩ W ⊗s , that |ψet ⟩ can not have any overlap with Cs⊥ ∩ W ⊗s . Note that (1) implies that, for any normalised vector v orthogonal to Cs⊥ ∩ W ⊗s , we have ∥ΠCs⊥ ΠW ⊗s v∥2 ≤

2s − 2 . N

Therefore, by formally identifying the projection Π=0 with the projection ΠCs⊥ ΠW ⊗s in Claim 4.12, we can bound 2s − 2 s∥Π=0 Λs |ψet ⟩∥2 ≤ s∥Λs |ψet ⟩∥2 . N √ Assuming that t ≤ N and S ≥ log2 N , this obtain the space-sensitive bound 4 ∆t+1 ≤ ∆t + √ N

X t

s∥Π=0 Λs |ψet ⟩∥2

1/2

s=0

4 ≤ ∆t + √ N

2S min t, log2 N

1/2 ,

which for ∆T = Ω(1) and T = Ω(N 1/3 ) requires T 2 S = Ω(N log N ), proving Theorem 4.18.

Preliminaries

2.1

Linear algebra

For a positive integer n, we write [n] := {0, . . . , n − 1}. We consider finite-dimensional complex inner product spaces H = Cd for some dimension d. We use standard bra-ket notation for column and row vectors in Cd . We consider all bra-ket vectors to be normalised unless specified otherwise. For a finite set S, we let C[S] := span{|s⟩ : s ∈ S}, and, for a positive integer n, we abbreviate C[[n]] as C[n]. For any two Hermitian operators A, B, we write A ⪰ B if their difference A − B is positive semidefinite. Definition 2.1 (Spectral norm). Let A ∈ Cd×d be a matrix. Then the spectral norm (also known as the operator norm) of A is ∥A∥ := sup ∥A|v⟩∥, |v⟩∈Cd

where ∥A|v⟩∥ is the standard vector ℓ2 -norm. Since we consider all bra-ket vectors to be normalised, the above supremum is implicitly over normalised vectors. Definition 2.2 (Fourier basis). Let {|y⟩}y∈[N ] be the computational basis for C[N ]. Then {|b y ⟩}y∈[N ] is the Fourier basis of C[N ], where each |b y ⟩ is defined as 1 X −yz |b y ⟩ := √ ωN |z⟩. N z∈[N ] 2πι

Here ωN = e N , where ι denotes the imaginary unit to prevent ambiguity with the variable i.

2.2

Representation theory of the symmetric group

We introduce the representation-theoretic preliminaries of the symmetric group that are used in the rest of this section. Let Sn denote the symmetric group of degree n. Throughout this subsection, all representations are finite-dimensional complex representations, and group actions are on the left unless stated otherwise. A representation (V, ρ) of Sn is a complex vector space V equipped with a homomorphism ρ : Sn −→ GL(V ). When the representation homomorphism is clear from context, we suppress it from the notation and identify the representation (V, ρ) with V . In this case, we write σv for ρ(σ)v. A subrepresentation W of V is given by a subspace W ⊆ V such that σw ∈ W for every σ ∈ Sn and w ∈ W . A representation V is called irreducible if its only subrepresentations are {0} and V itself. Let (V, ρV ) and (U, ρU ) be representations of Sn . A linear map B : V −→ U is Sn -equivariant if B(ρV (σ)v) = ρU (σ)B(v) for every σ ∈ Sn and v ∈ V . The character of a representation (V, ρ) is the function χV : Sn → C,

χV (σ) := Tr(ρ(σ)).

Thus, χV (1) = Tr(ρ(1)) = Tr(IdV ) = dim V, where 1 ∈ Sn denotes the identity element. The irreducible complex representations of Sn are indexed by partitions λ of the integer n, denoted by λ ⊢ n, that is, weakly decreasing sequences of positive integers λ = (λ1 , . . . , λr ),

|λ| := λ1 + · · · + λr = n.

We denote the corresponding irreducible representation by S λ , and call it the Specht module of shape λ. Its character is denoted by χλ := χS λ . Thus, in particular, χλ (1) = dim S λ . Each partition λ has an associated Young diagram Y (λ), a collection of left-aligned rows of boxes with λi boxes in row i. For example, the partition (4, 2, 1) ⊢ 7 has Young diagram

We also regard the empty partition ∅ as the unique partition of 0, with |∅| = 0 and Y (∅) = ∅. A standard Young tableau of shape λ, denoted by the symbol t, is a filling of the boxes of Y (λ) with the numbers 1, . . . , n, each used exactly once, such that the entries increase along rows and down columns. For instance, a standard Young tableau of shape (4, 2, 1) is 1

6 since the entries increase from left to right in each row and from top to bottom in each column. We write SYT(λ) for the set of standard Young tableaux of shape λ. Theorem 2.3 (Theorem 2.5.2 in [Sag01]). |SYT(λ)| = dim S λ .

2.3

Quantum query complexity

In this work, the input is a function f : [M ] → [N ]. The memory of a quantum algorithm A is described, without loss of generality, by registers W, X , and Y. The input oracle acts on X ⊗ Y, while W is an additional workspace register. The algorithm accesses f ∈ [N ]M through the following oracle. Definition 2.4 (Oracle). An oracle Of , encoding the input function f ∈ [N ]M , is a unitary transformation that acts on span{|x⟩X |y⟩Y : x ∈ [M ], y ∈ [N ]}, with its action on the basis state |x⟩X |y⟩Y defined as Of |x⟩X |y⟩Y = |x⟩X |(y + f (x)) mod N ⟩Y . The input f is typically drawn from some (hard) input distribution δ on [N ]M , denoted by f ∼ δ. Consequently, Of is a random variable. In adversary methods and the compressed-oracle technique, this randomness is purified by introducing an additional input register I that stores a superposition of function tables. If f ∼ δ, the register I is initialised as X p |δ⟩ := δ(f )|f ⟩I . f ∈[N ]M

Here, |δ⟩ represents the initial state of the input register. It is important to note that this should not be confused with the initial state of the algorithm, which is the all-zero state. This purification of the input leads to the following purified oracle: Definition 2.5 (Purified Oracle). A purified oracle O is a unitary transformation that acts on span{|x⟩X |y⟩Y |f ⟩I : x ∈ [M ], y ∈ [N ], f ∈ [N ]M }, with its action on the basis state |x⟩X |y⟩Y |f ⟩I defined as O|x⟩X |y⟩Y |f ⟩I = |x⟩X |(y + f (x)) mod N ⟩Y |f ⟩I . 10

From the perspective of the algorithm, it is indistinguishable whether it interacts with the random variable Of or the purified oracle O with input register initialised to |δ⟩. The relationship between the two is captured by the following expression: X Of ⊗ |f ⟩⟨f |I . O= f ∈[N ]M

It is equivalent, and in this work more convenient, to encode the query into the phase by viewing the Y register in the Fourier basis {|b y ⟩}y∈[N ] instead of the computational basis {|y⟩}y∈[N ] . In this Fourier basis, the oracle from Definition 2.5 acts on any basis state |x⟩X |b y ⟩Y |f ⟩I as yf (x)

O|x⟩X |b y ⟩Y |f ⟩I = ωN

|x⟩X |b y ⟩Y |f ⟩I .

Definition 2.6 (T -Query Quantum Algorithm). A T -query quantum algorithm A on [N ]M is a sequence of unitaries U0 , . . . , UT acting on HWX Y = HW ⊗ C[M ] ⊗ C[N ], where HW is an arbitrary finite-dimensional workspace. For a fixed input f : [M ] → [N ] and t ∈ [T + 1], define |ψtf (A)⟩ := Ut Of Ut−1 Of · · · Of U0 |0⟩WX Y . Thus, for t < T , |ψtf (A)⟩ is the state immediately before the (t + 1)-st query, while |ψTf (A)⟩ is the final state of the algorithm. For an input distribution δ on [N ]M , define the corresponding purified joint state by X p |ψt (A, δ)⟩ := δ(f )|ψtf (A)⟩WX Y |f ⟩I . f ∈[N ]M

Equivalently, |ψt (A, δ)⟩ = Ut OUt−1 O · · · OU0 |0⟩WX Y |δ⟩I . Finally, we define the reduced state of the input register, ρtI (A, δ) := TrWX Y [|ψt (A, δ)⟩⟨ψt (A, δ)|] . In the definition of the joint state |ψt (A, δ)⟩, the unitaries U0 , . . . , Ut act on a larger Hilbert space than originally defined, but each operator is implicitly understood to be tensored with the identity operator on I. Observe from the definitions in Definition 2.6 that the reduced state of the input register can alternatively be written as X p ρtI (A, δ) = δ(f )δ(g)⟨ψtg (A)|ψtf (A)⟩|f ⟩⟨g|. (2) f,g∈[N ]M

In this work, we consider search problems for which an input may have multiple valid outputs, or possibly no valid output at all. We therefore use average-case quantum query complexity, defined with respect to an input distribution δ, rather than the worst-case quantum query complexity. 11

Definition 2.7 (ϵ-error Average-Case Quantum Query Complexity). Let Σ be a finite set of possible outputs, and let F : [N ]M → 2Σ be a search problem, where F(f ) ⊆ Σ denotes the set of valid outputs on input f . For an input distribution δ on [N ]M , the ϵ-error average-case quantum query complexity of F with respect to δ, is the minimum number of queries needed by any quantum query algorithm A such that Pr A outputs some z ∈ F(f ) ≥ 1 − ϵ. f ∼δ

Here the probability is over both the choice of f ∼ δ and the measurement outcomes of A. This choice of metric is discussed in depth in [JZ26]. For collision finding, without the promise that the input contains a collision, no algorithm can solve the corresponding search relation on every input. This is why we work with average-case complexity under the uniform input distribution. For collision finding, we take Σcoll := {(x1 , x2 , y) ∈ [M ]2 × [N ] : x1 < x2 } and define Coll(f ) := {(x1 , x2 , y) ∈ Σcoll : f (x1 ) = f (x2 ) = y}.

(3)

Thus, Coll(f ) is the set of valid collision certificates of f , and it may be empty if f is injective. This formulation is asymptotically equivalent, up to one additional query and ⌈log2 N ⌉ additional qubits, to the usual formulation where the algorithm only has to output the collision pair (x1 , x2 ), as the algorithm may query f (x1 ) and output the resulting common value y = f (x1 ). Thus the two formulations have the same asymptotic query and space complexities. This alternative formulation is more convenient in this work because it interfaces directly with the compressed oracle readout bound in Lemma 3.6.

2.4

Space complexity

In this work, by quantum time-space lower bounds we mean lower bounds that relate the query complexity T of an algorithm, as in Definition 2.6, to its space complexity S. Such bounds show that an algorithm solving the problem cannot simultaneously use few queries and little space. This reflects the standard convention in the query-complexity model that each query takes one unit of time. Consequently, a query lower bound also yields a time lower bound, relativised to oracle access to the input. The space complexity S is the number of qubits in the algorithm’s workspace registers (i.e. the qubits on which the circuit operates throughout the computation). Equivalently, since HWX Y denotes the algorithm’s Hilbert space, dim(HWX Y ) ≤ 2S .

The compressed oracle technique for collision finding

3.1

The compressed oracle technique

In the compressed oracle technique [Zha19], also known as the recording query technique, the input distribution δ is initialised to the uniform distribution over all functions from [M ] to [N ], which we 12

denote by U: O 1 X √ |y⟩Ix . |f ⟩I = |U⟩I := √ N y∈[N ] N M f ∈[N ]M x∈[M ] 1

(4)

This construction also extends to product distributions, although we do not need that generality here. Such an extension appears in [HM23]. For background on the technique, see [Zha19, HM23, CFHL21]. The input register I holding a computational basis state |f ⟩I , where f ∈ [N ]M , is the tensor product of the function values of f for the different values of x ∈ [M ]: O |f (x)⟩Ix . |f ⟩I = x∈[M ]

We enlarge the Hilbert space of every cell Ix to C[[N ] ∪ {⊥}]. We continue to write |f ⟩ for a computational basis state in C[[N ] ∪ {⊥}]⊗M , so that f (x) may equal ⊥. For every x ∈ [M ], define the isometry X Compx := |⊥⟩⟨b 0| + Compx : C[N ] −→ C[[N ] ∪ {⊥}], |b z ⟩⟨b z |. z∈[N ]\{0}

Thus, the uniform state |b 0⟩, which represents having no information about the value in cell Ix , is mapped to |⊥⟩, while every nonzero Fourier state remains unchanged. In particular, Comp†x Compx = IdC[N ] ,

Compx Comp†x = IdC[[N ]∪{⊥}] − |b 0⟩⟨b 0|.

Taking the tensor product over x ∈ [M ] and extending it by the identity on the algorithm registers gives the isometry O Comp := IdWX Y ⊗ Compx . (5) x∈[M ]

e be the unitary recording query operator obtained by extending the restriction of Let O CompOComp† to im(Comp) locally: it acts only on the queried database cell and acts as the identity when the Y register is |b 0⟩. Its explicit basis action is given in Lemma 3.3. This extension preserves im(Comp) and satisfies e Comp = ΠComp O e = CompOComp† , OΠ

e OComp = CompO,

(6)

where ΠComp := CompComp† is the orthogonal projector onto im(Comp); its explicit form appears in (7). Remark 3.1. Our formulation differs slightly from the recording-query formalism of Hamoudi and Magniez [HM23]. There, the corresponding change of representation is implemented by a unitary on the enlarged space C[[N ] ∪ {⊥}]: locally, it exchanges |⊥⟩ with |b 0⟩ and fixes every |b z ⟩ with z ̸= 0. The map Compx above is precisely the restriction of this unitary to the original subspace C[N ]. Thus, the two formulations give equivalent descriptions of the recording query dynamics. We instead follow the isometric viewpoint of Jeffery and Zur [JZ26], in which Comp maps the standard input space into the enlarged database space and one explicitly keeps track of its image im(Comp). Although the two viewpoints are equivalent at the level of the recording query dynamics, making this image explicit is convenient for our space-sensitive analysis. In particular, all 13

compressed states remain in im(Comp), and later, after restricting to the occupied database cells, this image condition becomes the Fourier-space constraint that enters our representation-theoretic analysis of collision-free databases. In the compressed oracle technique, we study a modified version of the joint state |ψt (A, δ)⟩. Since the rest of this work only considers the case δ = U, we omit the distribution parameter and e and the input is simply write |ψt (A)⟩. In this modified state, each oracle call is replaced by O M initialised to |⊥ ⟩ instead of |U⟩: e t−1 O e . . . OU e 0 |0⟩WX Y |⊥M ⟩I . |ψet (A)⟩ = Ut OU Note that since |0⟩WX Y |⊥M ⟩I lies in im(Comp), it is immediate from (6) that all intermediate compressed states remain in this image. These two perspectives are almost identical: Lemma 3.2 (Theorem 3.3 in [HM23]). Fix a T -query algorithm A with inter-query unitaries U0 , . . . , UT . Then, for every t ∈ [T + 1], the states e t−1 O e . . . OU e 0 |0⟩WX Y |⊥M ⟩I . |ψet (A)⟩ = Ut OU

|ψt (A)⟩ = Ut OUt−1 O . . . OU0 |0⟩WX Y |U⟩I ,

obtained from the standard and compressed oracle models, respectively, satisfy Comp|ψt (A)⟩ = |ψet (A)⟩. As in Definition 2.6, we write h i ρetI (A) = TrWX Y |ψet (A)⟩⟨ψet (A)| for the reduced state of the input register in the compressed oracle model. The reason for studying the compressed oracle model is that by correctly tracking the ⊥ symbols in the I register of |ψet (A)⟩ with every query, we are able to record what the algorithm has learned e only changes the about the input. First of all, when applied to a basis state |w, x, p̂⟩WX Y |f ⟩I , O value of f (x) stored in register Ix : e Lemma 3.3 (Lemma 4.1 in [HM23]). Fix p ∈ [N ] \ {0} and apply the recording query operator O M to a basis state |w, x, p̂⟩WX Y |f ⟩I with |f ⟩ ∈ C[[N ] ∪ {⊥}] . Then the content of the cell register Ix transforms as X (p) |f (x)⟩Ix 7−→ γy,f (x) |y⟩Ix , y∈[N ]∪{⊥}

where, for y, z ∈ [N ] with y ̸= z ω py (p) γy,⊥ = √N , N

(p) γy,z =

ω pz (p) γ⊥,z = √N . N

(p)

γ⊥,⊥ = 0,

py pz 1 − ωN − ωN , N

(p) γy,y =

If p = 0, then none of the registers are changed. 14

py 1 + ωN (N − 2) . N

Since we start with the input initialised to |⊥M ⟩I , Lemma 3.3 implies the following consequence, which is the cornerstone of the compressed oracle technique: Lemma 3.4 (Fact 3.2 in [HM23]). For any T -query algorithm A and every t ∈ [T + 1], the state |ψet (A)⟩ is a linear combination of basis states |w, x, p̂⟩WX Y |f ⟩I where f contains at most t entries different from ⊥. For any |f ⟩ ∈ C[[N ] ∪ {⊥}]⊗M , we write |f | = s if f contains precisely s entries different from ⊥.

3.2

Application to collision finding

We define the following projectors by giving the computational basis states on which they project: • Π≥1 and Π=0 : all basis states |w, x, p̂⟩WX Y |f ⟩I such that f does or does not contain a collision (excluding ⊥), respectively. • Λs , where s ≥ 0: all basis states |w, x, p̂⟩WX Y |f ⟩I such that f contains exactly s non-⊥ entries. Recall from (6) the projection O

ΠComp := CompComp† = IdWX Y ⊗

(Id − |b 0⟩⟨b 0|),

(7)

x∈[M ]

i.e. the orthogonal projector onto the image of the isometry Comp from (5). Here each identity inside the tensor product acts on C[[N ] ∪ {⊥}]. Let η = (w, x, pb) denote a basis value of the algorithm registers, using the chosen computational bases of W and X and the Fourier basis of Y. Let I ⊆ [M ]. We write Λη,I ⪯ Λ|I| for the orthogonal projector onto all basis states with algorithm registers η and occupied set I. Suppose that I = {i1 < · · · < is }, and let Hη,I denote the image of Λη,I . Progress measure. We follow the standard compressed oracle progress argument for finding collisions [LZ19, HM23]. Recall that, for t < T , |ψet ⟩ denotes the state immediately before the (t + 1)-st query, while |ψeT ⟩ is the final state, and that |ψet ⟩ = Comp|ψt ⟩,

ΠComp |ψet ⟩ = |ψet ⟩,

(8)

and define ∆t := ∥Π≥1 |ψet ⟩∥. The unitary Ut+1 applied after the (t + 1)-st query acts trivially on the database register. Therefore, e ψet ⟩∥ = ∥Π≥1 O| e ψet ⟩∥. ∆t+1 = ∥Π≥1 Ut+1 O| e is unitary, we Separating the part of the state that already contains a collision and using that O obtain e =0 |ψet ⟩∥. ∆t+1 ≤ ∆t + ∥Π≥1 OΠ (9) We first upper bound the maximal progress made with a single query.

Lemma 3.5. Let ϕ be a not necessarily normalised collision-free vector, i.e. Π=0 ϕ = ϕ. Then e ≤ √4 ∥Π≥1 Oϕ∥ N

X X

|I|∥Λη,I ϕ∥

1/2 .

(10)

η I⊆[M ]

e acts as the identity when the Y register is in the state |b Proof. The recording query operator O 0⟩. This component cannot create a collision from a collision-free database. Hence, we may assume in the remainder for the proof that ϕ has no support on the subspace where |p̂⟩Y = |b 0⟩Y . For y ∈ [N ] ∪ {⊥}, define Λη,y,I := |y⟩⟨y|Ix Λη,I and decompose X

ϕ=

ϕη,y,I ,

ϕη,y,I := Λη,y,I ϕ.

y∈[N ]∪{⊥} η,I

where fx←z is obtained from f by setting the value at x equal to z. The output states on the righthand side are pairwise orthogonal, since the values f (j) are pairwise distinct. Moreover, outputs arising from different input basis states in the same block are orthogonal, since the input database √ (p) is recovered by replacing the value at x by ⊥. Using |γz,⊥ | ≤ 1/ N by Lemma 3.3, we obtain e η,⊥,I ∥2 ≤ ∥Π≥1 Oϕ

s ∥ϕη,⊥,I ∥2 . N

(11)

Now fix y1 ∈ [N ]. For a computational-basis state |η, f ⟩ in the support of ϕη,y1 ,I , a collision can only be created if the new value at x agrees with the value at one of the other occupied positions. Hence, X (p) e f⟩ = Π≥1 O|η, γf (j),y1 |η, fx←f (j) ⟩. j∈I\{x}

The output states are again pairwise orthogonal. Outputs arising from different input basis states in the same block are also orthogonal, since the input database is recovered by replacing the value (p) at x by the fixed value y1 . Using |γz,y1 | ≤ 3/N for z ̸= y1 by Lemma 3.3, we obtain e η,y ,I ∥2 ≤ ∥Π≥1 Oϕ 1

9s 9(s − 1) ∥ϕη,y1 ,I ∥2 ≤ 2 ∥ϕη,y1 ,I ∥2 . 2 N N

(12)

For fixed y, the outputs belonging to different pairs (η, I) are orthogonal. Indeed, the algorithm registers are unchanged by the query. If y = ⊥, then the final occupied set is I ∪ {x}, from which I can be recovered because x is contained in η. If y ∈ [N ], then the occupied set remains equal to I. It follows from (11) that e ∥Π≥1 O

1 ϕη,⊥,I ∥ ≤ √ N η,I

X 1/2 |I|∥ϕη,⊥,I ∥2 . η,I

Similarly, for every fixed y1 ∈ [N ], (12) gives e ∥Π≥1 O

X η,I

3 ϕη,y1 ,I ∥ ≤ N

|I|∥ϕη,y1 ,I ∥

1/2 .

η,I

Using the triangle inequality over y1 ∈ [N ] ∪ {⊥} and then Cauchy-Schwarz, we obtain e ≤ √1 ∥Π≥1 Oϕ∥ N

X 1/2 X 1/2 3 X 2 2 |I|∥ϕη,⊥,I ∥ + |I|∥ϕη,y1 ,I ∥ N η,I

y1 ∈[N ]

η,I

X 1/2 X X 1/2 3 1 2 2 |I|∥ϕη,⊥,I ∥ +√ |I|∥ϕη,y1 ,I ∥ ≤√ N η,I N y ∈[N ] η,I 1 X 1/2 4 ≤√ |I|∥Λη,I ϕ∥2 . N η,I From progress to success probability. We finally relate ∆T to the actual success probability of the algorithm. Recall that U denotes the uniform distribution over functions f : [M ] → [N ] and that for the collision finding problem, the set of valid outputs is defined in (3) as Coll(f ) := {(x1 , x2 , y) ∈ [M ]2 × [N ] : x1 < x2 and f (x1 ) = f (x2 ) = y}. Let pU succ denote the probability that the algorithm outputs a triple (x1 , x2 , y) in Coll(f ) on an input f ∼ U. Lemma 3.6. Let A be a T -query quantum algorithm. Then, r 2 2 pU . succ ≤ ∆T + N Proof. We apply the compressed oracle readout bound of [Zha19, Lemma 5] with k = 2. Zhandry states the result for a random oracle with range {0, 1}n . The same proof applies to range [N ] ∼ = ZN by replacing the n-fold tensor-product Hadamard transform with the quantum Fourier transform p over ZN , giving an error term of 2/N . More precisely, we identify an output (x1 , x2 , y) of A with the tuple (x1 , x2 , y1 , y2 ) = (x1 , x2 , y, y), and consider the relation R := {(x1 , x2 , y1 , y2 ) ∈ [M ]2 × [N ]2 :: x1 < x2 , y1 = y2 }. The success event in Zhandry’s lemma is therefore precisely the event x1 < x2

and

f (x1 ) = f (x2 ) = y,

which occurs with probability pU succ .

Now run A with the compressed/recording oracle and measure the compressed database after the algorithm produces its output. Let prec denote the probability that the output (x1 , x2 , y) satisfies x1 < x2 and that the measured database D contains D(x1 ) = D(x2 ) = y. By [Zha19, Lemma 5], √

2 . N Whenever the event defining prec occurs, the recording database contains two distinct positions with the same recorded value, and hence contains a collision. Therefore q

pU succ ≤

prec +

prec ≤ ∥Π≥1 |ψeT ⟩∥2 = ∆2T . Consequently, r q 2 U psucc ≤ ∆T + . N Squaring both sides proves the claim. Known query lower bound. Even before incorporating the space restriction, Lemma 3.5 already recovers the standard query lower bound. Indeed, by Lemma 3.4, every database in the support of Π=0 |ψet ⟩ has at most t occupied positions, and hence X X |I|∥Λη,I Π=0 |ψet ⟩∥2 ≤ t∥Π=0 |ψet ⟩∥2 ≤ t. η I⊆[M ]

Therefore, (9) and Lemma 3.5 give r ∆t+1 ≤ ∆t + 4

t , N

T −1

and thus

4 X√ 4T 3/2 ∆T ≤ √ t≤ √ , N t=0 N

where ∆0 = 0. Together with Lemma 3.6, this yields, for T ≥ 1, the standard bound pU succ = O(T 3 /N ) and hence T = Ω(N 1/3 ) for constant success probability. In the next section, we refine precisely the crude estimate above: label symmetry and the S-qubit space bound allow us to replace the factor t by min{t, 2S/ log2 N }, which yields the optimal time-space tradeoff.

Space bounds in the compressed oracle technique

4.1

Symmetry restrictions

In our setting, both the uniform input distribution and the collision-finding success condition are invariant under arbitrary permutations of the range labels. Thus, no range label has intrinsic significance, making it natural to expect that treating particular labels asymmetrically offers no advantage. We formalise the corresponding symmetry at the level of the algorithm’s reduced input state, and we call it label symmetry. Although this motivates our restriction, label symmetry cannot presently be imposed without loss of generality under a space bound: symmetrising an arbitrary algorithm by explicitly storing 18

a permutation can require Θ(N log N ) additional qubits [Amb10, AMRR11], which would obscure the time-space tradeoff. Related invariant-algorithm restrictions have been studied for insertion into an ordered list [FGGS99] and for ordered search [CCKDS26]. We first define symmetry for a general group action. Definition 4.1. Let (HI , π) be a unitary representation of a finite group G. Let A be a T -query algorithm whose algorithm registers use at most S qubits, and let δ be an input distribution. We say that (A, δ) is G-symmetric with respect to π if, for every t ∈ [T + 1], π(g)ρtI (A, δ)π(g)† = ρtI (A, δ)

for every g ∈ G.

In our application, SN is the symmetric group on the N range labels. We extend every σ ∈ SN to [N ] ∪ {⊥} by setting σ(⊥) = ⊥, and define its unitary actions on the standard and compressed input registers by Vσ |f ⟩ := |σ ◦ f ⟩, (13) both for f : [M ] → [N ] and f : [M ] → [N ] ∪ {⊥}. We further extend this action to the algorithm’s registers by tensoring with the identity; thus, range relabelling acts trivially on all algorithm registers, including the query registers X and Y. Because the uniform state |b 0⟩ is fixed by every permutation, these actions satisfy (IdWX Y ⊗ Vσ )Comp = Comp(IdWX Y ⊗ Vσ ).

(14)

In particular, (IdWX Y ⊗ Vσ ) commutes with ΠComp . Since the action fixes ⊥ and only permutes the remaining labels, it also commutes with Π=0 , Π≥1 , Λs , and every Λη,I . A direct consequence of (2) and the invariance of U under SN -symmetry is the following fact. Fact 4.2. Under the uniform distribution U, SN -symmetry is equivalent to the Gram-matrix condition ⟨ψtf (A)|ψtg (A)⟩ = ⟨ψtσ◦f (A)|ψtσ◦g (A)⟩ for all f, g ∈ [N ]M , σ ∈ SN , and t ∈ [T + 1]. Symmetric algorithms satisfy the following key space bound. Lemma 4.3. Let A be an algorithm whose algorithm registers use at most S qubits, and suppose that (A, δ) is G-symmetric with respect to π. Then, for every t ∈ [T + 1] and every |β⟩ ∈ supp(ρtI (A, δ)), dim span{π(g)|β⟩ : g ∈ G} ≤ 2S . Proof. By assumption, ρtI (A, δ) is G-invariant, and therefore span{π(g)|β⟩ : g ∈ G} ⊆ supp(ρtI (A, δ)). Since the joint state |ψt (A, δ)⟩ is pure, its Schmidt rank across the algorithm-input cut gives rank ρtI (A, δ) ≤ dim(HWX Y ) ≤ 2S , which proves the claim. Definition 4.4 (Label-symmetric algorithm). A quantum query algorithm A is label-symmetric if (A, U) is SN -symmetric with respect to the range-label representation σ 7→ Vσ in (13). 19

Every algorithm whose only input-dependent operation asks whether f (x) = f (x′ ) is automatically label-symmetric: such an equality query is unchanged by any permutation of the range labels. We state and prove Nthis formally in Lemma 5.4. Let CompI := x∈[M ] Compx . The reduced standard and compressed input states obey ρetI = CompI ρtI Comp†I . By (14), label symmetry therefore transfers to the compressed reduced state without changing its rank. In particular, for every basis value η of the algorithm registers, the projected part (|η⟩⟨η|WX Y ⊗ IdI )|ψet ⟩ has an SN -orbit span of dimension at most 2S . In the rest of this section, we identify the components of a collision-free compressed database whose nonzero vectors have high-dimensional SN -orbits. The orbit bound above then forces every state in the reduced state of the input register of a space-bounded, label-symmetric algorithm to be orthogonal to those components.

4.2

Collision-free compressed databases

We view C[N ] as the permutation representation of SN by making it permute the labels: σ|y⟩ = |σ(y)⟩

(σ ∈ SN , y ∈ [N ]).

This induces a diagonal action of SN on C[N ]⊗s : σ|y1 , . . . , ys ⟩ = |σ(y1 ), . . . , σ(ys )⟩. We also let Ss act on C[N ]⊗s by permuting the tensor factors. Since we later multiply by seminormal idempotents on the right, we use the right-action for this action: |y1 , . . . , ys ⟩ · π = |yπ(1) , . . . , yπ(s) ⟩

(π ∈ Ss ).

The left SN -action and the right Ss -action commute. We introduce the space n o W := ker(⟨b 0|) = |ψ⟩ ∈ C[N ] : ⟨b 0|ψ⟩ = 0 ,

(15)

and, for s ≥ 1, we define the collision subspace Cs := span{|y1 , . . . , ys ⟩ : yi = yj for some i ̸= j} ⊂ C[N ]⊗s

(16)

Its orthogonal complement is Cs⊥ := span{|y1 , . . . , ys ⟩ : y1 , . . . , ys are pairwise distinct} ⊂ C[N ]⊗s .

(17)

The spaces Cs⊥ and W ⊗s have a simple interpretation. The space Cs⊥ describes s-tuples with no collisions, while W ⊗s describes the s recorded entries of a compressed database after the ⊥-entries are omitted. Their intersection Cs⊥ ∩ W ⊗s can therefore be identified with the space of collision-free compressed databases with s recorded entries. We make this correspondence precise in Section 4.5. A related subtlety is that the operator ΠW ⊗s ΠCs⊥ is in general not equal to the projection ΠCs⊥ ∩W ⊗s , because a product of orthogonal projections need not coincide with the orthogonal projection onto the intersection, unless the two projections commute. In Lemma 4.10 we show that, although these two operators are not identical, they are nevertheless close in operator norm. 20

4.3

Representations in Cs⊥ ∩ W ⊗s

In this section we analyse the SN -irreducible representations appearing in Cs⊥ ∩ W ⊗s . We show that only Specht modules of shape λ whose first row has length exactly N − s occur in Cs⊥ ∩ W ⊗s , that is, λ = (N − s, µ), when N is large enough. The proof is postponed to the end of this section, and naturally breaks into two intermediate results we will present shortly. Theorem 4.5. Assume s ≥ 1 and N ≥ 2s. Then M Cs⊥ ∩ W ⊗s ∼ |SYT(µ)|S (N −s,µ) . = µ⊢s

The Specht modules appearing in this decomposition have large dimension (if s is large), which will be important later to show that the space Cs⊥ ∩W ⊗s is not reachable by our quantum algorithm if it has limited space at its disposal. Theorem 4.6 (Theorem E in [Ras77]). Assume s ≥ 1 and N ≥ 2s. Then N N min dim S (N −s,µ) ≥ − . µ⊢s s s−1 By combining these two theorems, we show in the next section that for every nonzero vector in Cs⊥ ∩ W ⊗s , the dimension of the span of its SN -orbit is large. ⊥ )⊕s , whose We now set out to prove Theorem 4.5 by constructing a linear map D : Cs⊥ → (Cs−1 ⊗s ⊥ (see Claim 4.7), but on the other hand, whose kernel is also isomorphic to kernel is Cs ∩ W L (N −s,µ) (see Lemma 4.9). |SYT(µ)|S µ⊢s For each r ∈ {1, . . . , s}, define the deletion map dr : C[N ]⊗s −→ C[N ]⊗(s−1) ,

dr |y1 , . . . , ys ⟩ = |y1 , . . . , yr−1 , yr+1 , . . . , ys ⟩.

(18)

For s = 1, we use the convention that the zeroth tensor power is identified with C, so in particular C0⊥ := C and d1 |y⟩ = 1 ∈ C. By taking the direct sum of these maps for the different values of r, we obtain the operator D :=

s M r=1

⊥ dr C ⊥ : Cs⊥ −→ (Cs−1 )⊕s .

(19)

Claim 4.7. ker D = Cs⊥ ∩ W ⊗s . Proof. Recall from (15) that W := ker(⟨b 0|). Hence, W ⊗s =

s \

ker Id⊗(r−1) ⊗ ⟨b 0| ⊗ Id⊗(s−r) .

r=1

On the other hand, each contraction in the r-th tensor factor is related to the deletion map dr by r 1 ⊗(r−1) ⊗(s−r) b Id ⊗ ⟨0| ⊗ Id = dr . N 21

Thus, these two maps have the same kernel, and therefore s \

ker dr = W ⊗s .

(20)

r=1

Since D is the map obtained by restricting

⊥ r=1 dr to Cs , we have

ker D = Cs⊥ ∩ W ⊗s . We now look at D from a different perspective. Let Ωs := {(y1 , . . . , ys ) ∈ [N ]s : y1 , . . . , ys are pairwise distinct}.

(21)

Then by (17) it is immediate that the orthonormal basis of Cs⊥ is precisely given by |y1 , . . . , ys ⟩ : (y1 , . . . , ys ) ∈ Ωs . Consider the adjoint of the restriction of the deletion map dr to Cs⊥ , which is a ⊥ to C ⊥ , acting as linear map from Cs−1 s

(dr C ⊥ )† |y1 , . . . , ys−1 ⟩ =

|y1 , . . . , yr−1 , y, yr , . . . , ys−1 ⟩.

(22)

y∈[N ] y ∈{y / 1 ,...,ys−1 }

Let AN,s be the adjacency matrix of the arrangement graph on the basis vectors {|y1 , . . . , ys ⟩ : (y1 , . . . , ys ) ∈ Ωs } of Cs⊥ , where two basis vectors are adjacent if and only if the corresponding (injective) s-tuples differ exactly in one coordinate. So AN,s is a linear operator from Cs⊥ to Cs⊥ , acting as s X X AN,s |y1 , . . . , ys ⟩ = |y1 , . . . , yr−1 , y, yr+1 , . . . , ys ⟩. (23) r=1 y ∈{y / 1 ,...,ys }

The following claim means that ker D is the −s-eigenspace of AN,s , and we can analyse ker D by studying the spectrum of AN,s . Claim 4.8. ker D = ker(D† D) = ker(AN,s + s · Id). Proof. We verify that D† D = AN,s + s · Id.

(24)

Indeed, by (22) for each r, (dr C ⊥ )† dr C ⊥ |y1 , . . . , ys ⟩ = |y1 , . . . , ys ⟩ + s

|y′ ⟩,

y′ ∈Ωs y′ differs from (y1 ,...,ys ) only at index r

so summing over r ∈ {1, . . . , s} counts each neighbour in the arrangement graph exactly once, recovering (23) and additionally contributes the diagonal term s|y1 , . . . , ys ⟩. Since for every linear map ker D = ker(D† D), we conclude by (24) that ker D = ker(D† D) = ker(AN,s + s · Id).

Chen, Ghorbani, and Wong showed that −s is the least eigenvalue of AN,s for N ≥ 2s, obtained a lower bound on its multiplicity, and conjectured that it is eventually the unique negative eigenvalue [CGW13]. Araujo and Bratten subsequently determined the spectrum through character ratios and proved uniqueness under the sufficient condition N > s(s + 1)(s + 5)/6 [AB17, Theorem 3.5, Proposition 4.1, and its proof]. The following lemma determines the entire bottom of the spectrum for every N ≥ 2s. Lemma 4.9 (Arrangement Spectral Gap). Assume s ≥ 1 and N ≥ 2s. The smallest eigenvalue of AN,s on Cs⊥ is −s, and its eigenspace is, as an SN -representation, M |SYT(µ)|S (N −s,µ) . µ⊢s

Moreover, the next distinct eigenvalue is exactly N − (3s − 2). Consequently, the gap above the least eigenvalue is N − 2s + 2, and −s is the unique negative eigenvalue exactly when N ≥ 3s − 2. Proof. See Section 6. We end this subsection by combining our results together in order to prove Theorem 4.5. Proof of Theorem 4.5. From Claim 4.7 and Claim 4.8, we have that the kernel of D coincides with both Cs⊥ ∩ W ⊗s and the (−s)-eigenspace of AN,s . Furthermore, Lemma 4.9 tells us that the (−s)-eigenspace of AN,s is isomorphic to M |SYT(µ)|S (N −s,µ) . µ⊢s

Thus, in summary, Cs⊥ ∩ W ⊗s = ker D = ker(AN,s + s · Id) ∼ =

|SYT(µ)|S (N −s,µ) .

µ⊢s

4.4

Alternating projections onto Cs⊥ and W ⊗s

The product ΠW ⊗s ΠCs⊥ is not necessarily equal to the orthogonal projection onto Cs⊥ ∩ W ⊗s . In general, the comparison of these three projections is related to the literature on alternating projections (see, e.g., [KW88]). In particular, the operator-norm error is exactly the cosine of the Friedrichs angle between the two subspaces (the angle between their components orthogonal to the intersection). In our case, we derive a direct upper bound on this error without computing the angle and show, in the following lemma, that these two operators are close. Lemma 4.10. Assume s ≥ 1 and N ≥ 2s. Then ∥ΠCs⊥ ΠW ⊗s − ΠCs⊥ ∩W ⊗s ∥2 = ∥ΠW ⊗s ΠCs⊥ − ΠCs⊥ ∩W ⊗s ∥2 ≤ In particular, if u ∈ C[N ]⊗s satisfies u ⊥ (Cs⊥ ∩ W ⊗s ), then ∥ΠCs⊥ ΠW ⊗s u∥2 ≤ 23

2s − 2 ∥u∥2 . N

2s − 2 . N

(25)

Proof. The equality in (25) follows from taking the adjoint, so it is sufficient to bound ∥ΠW ⊗s ΠCs⊥ − ΠCs⊥ ∩W ⊗s ∥2 . We first consider the case s = 1. Then, C1⊥ = C[N ],

C1⊥ ∩ W = W.

Consequently, ΠW ΠC ⊥ − ΠC ⊥ ∩W = ΠW − ΠW = 0, 1

and the result is immediate. Henceforth, assume s ≥ 2. Let u ∈ C[N ]⊗s and consider v := (ΠW ⊗s ΠCs⊥ − ΠCs⊥ ∩W ⊗s )u. We first prove that v ∈ W ⊗s , v ∈ (Cs⊥ ∩ W ⊗s )⊥ . For the first containment, observe that v ∈ W ⊗s , since the images of both projectors ΠW ⊗s and ΠCs⊥ ∩W ⊗s lie in W ⊗s . For the second containment, we prove the more general statement ΠCs⊥ ∩W ⊗s (ΠW ⊗s ΠCs⊥ − ΠCs⊥ ∩W ⊗s ) = 0, leading to ΠCs⊥ ∩W ⊗s v = 0, that is, v ∈ (Cs⊥ ∩ W ⊗s )⊥ . Indeed, ΠCs⊥ ∩W ⊗s (ΠW ⊗s ΠCs⊥ − ΠCs⊥ ∩W ⊗s ) = (ΠCs⊥ ∩W ⊗s ΠW ⊗s ΠCs⊥ − ΠCs⊥ ∩W ⊗s ) = (ΠCs⊥ ∩W ⊗s − ΠCs⊥ ∩W ⊗s ) = 0, where for the second equality we have used that Cs⊥ ∩ W ⊗s is a subspace of both Cs⊥ and W ⊗s , and therefore ΠCs⊥ ∩W ⊗s ΠW ⊗s = ΠCs⊥ ∩W ⊗s and ΠCs⊥ ∩W ⊗s ΠCs⊥ = ΠCs⊥ ∩W ⊗s . We now decompose v ∈ (Cs⊥ ∩ W ⊗s )⊥ into its Cs⊥ - and Cs -components (see (16) and (17)). Observe first that, since Cs ⊆ (Cs⊥ ∩ W ⊗s )⊥ , the decomposition lies in fact inside (Cs⊥ ∩ W ⊗s )⊥ . So we let v = z + c with z ∈ Cs⊥ ∩ (Cs⊥ ∩ W ⊗s )⊥ and c ∈ Cs ⊆ (Cs⊥ ∩ W ⊗s )⊥ . We relate the norm of v to u as follows, using that v ∈ W ⊗s and v ∈ (Cs⊥ ∩ W ⊗s )⊥ : D E ∥v∥2 = v, ΠW ⊗s ΠCs⊥ − ΠCs⊥ ∩W ⊗s u D E = ΠCs⊥ ΠW ⊗s − ΠCs⊥ ∩W ⊗s v, u (26) D E = ΠCs⊥ v, u = ⟨z, u⟩. For now, assume the following claim about z and c, which we prove separately below. Claim 4.11. (N − 2s + 2)∥z∥2 ≤ (2s − 2)∥c∥2 , The proof then concludes as follows: N − 2s + 2 N ∥v∥ = ∥z∥ + ∥c∥ ≥ 1 + ∥z∥2 = ∥z∥2 . 2s − 2 2s − 2 2

Combining this with (26) and applying Cauchy-Schwarz gives r 2s − 2 2 ∥v∥∥u∥. ∥v∥ = |⟨z, u⟩| ≤ ∥z∥∥u∥ ≤ N Dividing by ∥v∥ (assuming v ̸= 0, as otherwise the inequality is trivially true) yields the desired r 2s − 2 ∥u∥ . ∥v∥ ≤ N Proof of Claim 4.11. For r ∈ {1, . . . , s}, recall the deletion map dr from (18): dr : C[N ]⊗s −→ C[N ]⊗(s−1) ,

dr |y1 , . . . , ys ⟩ = |y1 , . . . , yr−1 , yr+1 , . . . , ys ⟩.

Thanks to (20) in the proof of Claim 4.7, we have seen that dr (W ⊗s ) = {0} for every r ∈ {1, . . . , s}. In particular, for our v ∈ W ⊗s , dr (z) = −dr (c) = −ΠC ⊥ dr (c).

(27)

s−1

⊥ . By the first equality of (27), For the second equality, we used z ∈ Cs⊥ , which implies dr (z) ∈ Cs−1 ⊥ as well, so it is invariant under Π and we may insert this projection. dr (c) ∈ Cs−1 ⊥ Cs−1 Taking direct sums of dr and ΠC ⊥ dr over r gives the following operators, the first of which s−1 was already defined in (19):

D :=

s M r=1

⊥ dr C ⊥ : Cs⊥ −→ (Cs−1 )⊕s , s

B :=

s M

⊥ )⊕s . ΠC ⊥ dr Cs : Cs −→ (Cs−1 s−1

(28)

r=1

By (27), these operators satisfy ∥Dz∥2 = ∥Bc∥2 . We now study these operators in more detail and prove the following, which will conclude the proof: ∥Dz∥2 ≥ (N − 2s + 2)∥z∥2 , ∥Bc∥2 ≤ (2s − 2)∥c∥2 . We start with the lower bound on ∥Dz∥2 . By (24) and Lemma 4.9, D† D = AN,s + s · Id is positive semidefinite. Its kernel is Cs⊥ ∩ W ⊗s by Claim 4.7, and its smallest positive eigenvalue is ⊥ s + N − (3s − 2) = N − 2s + 2. Therefore, on Cs⊥ ∩ W ⊗s ∩ Cs⊥ , the operator D† D is bounded ⊥ below by (N − 2s + 2)Id. Thus, for any z ∈ Cs⊥ ∩ W ⊗s ∩ Cs⊥ , ∥Dz∥2 ≥ (N − 2s + 2)∥z∥2 .

(29)

With respect to the standard orthonormal bases, the matrix entries of B lie in {0, 1}. Starting with a non-injective s-tuple in Cs , deleting one coordinate through dr either yields an injective tuple, in which case ΠC ⊥ acts as the identity, or leaves a non-injective tuple, in which case the projection s−1 acts as 0. Since deleting one coordinate from a non-injective s-tuple can yield an injective (s − 1)tuple for at most two choices of the deleted coordinate, each column of B contains at most 2 nonzero entries. Each row contains at most s − 1 nonzero entries, since for fixed r ∈ {1, . . . , s} and fixed injective tuple (z1 , . . . , zs−1 ), the preimages under dr P are obtained by inserting at position r one of the s − 1 entries z1 , . . . , zs−1 . Therefore, for any c = j cj ej ∈ Cs we have, by Cauchy-Schwarz, XX X X ∥Bc∥2 = | Bij cj |2 ≤ (s − 1) Bij |cj |2 ≤ 2(s − 1) |cj |2 = 2(s − 1)∥c∥2 . i

i,j

4.5

Space bounds for collision-free database states

We now apply the results from the previous subsection to states in the recording query model. In particular, we will now be working both on (tensor products of) C[N ], as well as C[[N ] ∪ {⊥}]. Define Vη,I : Hη,I −→ C[N ]⊗s , Vη,I |η, f ⟩ = |f (i1 ), . . . , f (is )⟩. This map is unitary, because it maps the computational basis of Hη,I bijectively onto the computational basis of C[N ]⊗s . Moreover, the map Vη,I is SN -equivariant with respect to the action of SN on Hη,I , since for every σ ∈ SN and every |η, f ⟩ ∈ Hη,I , Vη,I σ|η, f ⟩ = Vη,I |η, σ ◦ f ⟩

(30)

= |σ(f (i1 )), . . . , σ(f (is ))⟩ = σVη,I |η, f ⟩.

Here range relabelling fixes ⊥, so it preserves the occupied set I and hence the subspace Hη,I . The map Vη,I allows us to define the following commutative diagrams, as stated by the next claim: Π ΠComp Hη,I −−−=0 −→ Hη,I Hη,I −−−−−→ Hη,I Vη,I ↓

↓ Vη,I

and

Vη,I ↓

↓ Vη,I

ΠC ⊥

ΠW ⊗s

C[N ]⊗s −−−−−→ C[N ]⊗s

s → C[N ]⊗s C[N ]⊗s −−−−

Claim 4.12. On Hη,I , the map Vη,I relates ΠComp to ΠW ⊗s as follows: Vη,I ΠComp Λη,I = ΠW ⊗s Vη,I Λη,I .

(31)

Moreover, restricting to collision-free databases corresponds to projecting onto Cs⊥ : Vη,I Π=0 Λη,I = ΠCs⊥ Vη,I Λη,I .

(32)

Proof. It suffices to verify both identities on a computational basis vector |η, f ⟩. If |η, f ⟩ ∈ / Hη,I , then Λη,I |η, f ⟩ = 0, so both sides of both identities vanish. Assume therefore that the occupied set of f is I = {i1 < · · · < is }. First, f is collision-free if and only if f (i1 ), . . . , f (is ) are pairwise distinct. Consequently, ( |f (i1 ), . . . , f (is )⟩, f (i1 ), . . . , f (is ) are pairwise distinct, Vη,I Π=0 |η, f ⟩ = 0, otherwise, which is exactly ΠCs⊥ Vη,I |η, f ⟩. This proves (32). For (31), observe that (Id − |b 0⟩⟨b 0|)|⊥⟩ = |⊥⟩. Thus, the cells outside I remain equal to |⊥⟩, while on each occupied cell ij the operator ΠComp acts as Id − |b 0⟩⟨b 0|. After applying Vη,I , we therefore obtain Vη,I ΠComp |η, f ⟩ =

s O j=1

(Id − |b 0⟩⟨b 0|)|f (ij )⟩.

Since ΠW ⊗s = (Id − |b 0⟩⟨b 0|)⊗s , the right-hand side equals ΠW ⊗s Vη,I |η, f ⟩. This proves (31). We now state a general fact that we will use for the following theorem. Fact 4.13. Let V be a finite-dimensional representation of SN , let v ∈ V , and let λ ⊢ N . Suppose that there is an SN -equivariant linear map B : V −→ S λ such that B(v) ̸= 0. Then dim (span{σv : σ ∈ SN }) ≥ dim S λ . Proof. Let W = span{σv : σ ∈ SN } ⊆ V . By the equivariance of B, B(W ) = span B σv : σ ∈ SN = span {σB(v) : σ ∈ SN } . Thus, B(W ) is an SN -invariant subspace of S λ . Since S λ is irreducible, either B(W ) = {0} or B(W ) = S λ . Since v ∈ W and B(v) ̸= 0, the first case can be excluded. Hence, we obtain the desired result, since dim W ≥ dim B(W ). In particular, if V = U ⊕ U′ is a direct sum of SN -subrepresentations of V , then the projection B : V −→ U is SN -equivariant. In this case, B(v) ̸= 0 means that v has a nonzero component in U with respect to this decomposition. √ Theorem 4.14. Assume N ≥ 9, S ≥ log2 N , and let t be a nonnegative integer such that t ≤ N . Let ϕ ∈ HWX Y ⊗ HI be a not necessarily normalised vector satisfying ΠComp ϕ = ϕ, and suppose that every database in the support of ϕ has at most t entries different from ⊥. Assume that, for every product-basis value η = (w, x, pb) of the algorithm registers, dim (span {σ(|η⟩⟨η|WX Y ⊗ IdI )ϕ : σ ∈ SN }) ≤ 2S . Then, for every s ∈ [t + 1],

∥Π=0 Λs ϕ∥2 ≤

  2  ∥Λs ϕ∥ , 2s − 2    ∥Λs ϕ∥2 , N

2S , log2 N 2S s> . log2 N

s≤

2S is immediate, because Π=0 is an orthogonal log2 N projector. √ Suppose now that s > log2SN . Since s ≤ t ≤ N and N ≥ 9, we have N ≥ 2s and thus, 2 Theorem 4.5, Theorem 4.6, and Lemma 4.10 are applicable. Proof. Fix s ∈ [t + 1]. The first case where s ≤

For every η and every I ⊆ [M ] with |I| = s, set ϕη,I := Λη,I ϕ. The rest of the proof consists of proving the statement for each ϕη,I ∈ Hη,I , since the Pythagorean identity then proves the theorem after summing over η and I. Since ΠComp acts independently on each database cell and preserves both span{|⊥⟩} and C[N ], it preserves every sector Hη,I . Hence, Λη,I commutes with ΠComp and we have ΠComp ϕη,I = ϕη,I . It follows from (31) that Vη,I ϕη,I ∈ W ⊗s . Define φη,I := ΠCs⊥ ∩W ⊗s Vη,I ϕη,I . The map ϕη,I 7→ φη,I is SN -equivariant: relabelling does not change η or the occupied set I, the map Vη,I is equivariant by (30), and Cs⊥ ∩ W ⊗s is SN -invariant because relabelling preserves pairwise distinctness and fixes |b 0⟩. Therefore, dim (span{σφη,I : σ ∈ SN }) ≤ dim (span {σ(|η⟩⟨η|WX Y ⊗ IdI )ϕ : σ ∈ SN }) ≤ 2S . By Theorem 4.5, Cs⊥ ∩ W ⊗s ∼ =

|SYT(ν)|S (N −s,ν) .

ν⊢s

If φη,I ̸= 0, then it has a nonzero component in some Specht module S (N −s,ν) . By Fact 4.13 and Theorem 4.6, N N dim (span{σφη,I : σ ∈ SN }) ≥ − . s s−1 √ Since s > log2SN ≥ 2, we have s ≥ 3, and since s ≤ t ≤ N , 2

N N N N − 2s + 1 − = s s−1 s N −s+1 s N s(N − s + 1) N − 2s + 1 ≥ s N N −s+1 ≥ N N s/2 > 2S . ≥ s This is a contradiction, and hence Vη,I ϕη,I ⊥ Cs⊥ ∩ W ⊗s . Using (32), the fact that Vη,I ϕη,I ∈ W ⊗s , and Lemma 4.10, we obtain ∥Π=0 ϕη,I ∥2 = ∥ΠCs⊥ Vη,I ϕη,I ∥2 = ∥ ΠCs⊥ ΠW ⊗s − ΠCs⊥ ∩W ⊗s Vη,I ϕη,I ∥2 ≤

2s − 2 ∥ϕη,I ∥2 . N 28

The following corollary of Theorem 4.14 will be useful in our collision finding application in the next section. Corollary 4.15. Under the assumptions of Theorem 4.14, t X 2S 2 ∥ϕ∥2 . s∥Π=0 Λs ϕ∥ ≤ min t, log2 N s=0

Proof. The proof follows from the inequality

2S s∥Π=0 Λs ϕ∥ ≤ min t, log2 N 2

∥Λs ϕ∥2 .

P Indeed, we can then conclude by summing over 0 ≤ s ≤ t and using s ∥Λs ϕ∥2 ≤ ∥ϕ∥2 because of the orthogonality of the projectors Λs . Let us now prove the claimed inequality. For s ≤ log2SN , Theorem 4.14 gives 2 2S 2 2 ∥Λs ϕ∥2 , s∥Π=0 Λs ϕ∥ ≤ ∥Λs ϕ∥ ≤ min t, log2 N where we used that s ≤ t. Now suppose that s > log2SN . Then Theorem 4.14 gives 2 2s(s − 1) 2S 2 2 s∥Π=0 Λs ϕ∥ ≤ ∥Λs ϕ∥ ≤ min t, ∥Λs ϕ∥2 , N log2 N √ where we first used s ≤ t ≤ N to get 2s(s−1) ≤ 2 and then s > log2SN ≥ 2 and s ≤ t to obtain N 2 o n 2S 2 ≤ min t, log N . 2

4.6

Time-Space tradeoff

We now apply Corollary 4.15 to bound the progress of the algorithm towards finding a collision. Lemma 4.16. Let A be a label-symmetric algorithm. Assume N ≥ 9,S ≥ log2 N , and T ≥ 0. Then s 4T 2S √ min T, . ∆T ≤ log2 N N √ Proof. If T > N , then, since S ≥ log2 N and N ≥ 9, 2S min T, ≥ 2. log2 N Hence the right-hand side of the claimed inequality is greater than 1, whereas ∆T ≤ 1. Thus, the result is immediate in this case. √ It remains to consider the case where T ≤ N . We have ∆0 = 0, since the empty database contains no collision. We show that, for every 0 ≤ t < T , s 2S 4 ∆t+1 ≤ ∆t + √ min t, . (33) log2 N N 29

By (8), we have ΠComp |ψet ⟩ = |ψet ⟩, and, by Lemma 3.4, every database in the support of |ψet ⟩ has at most t non-⊥ positions. We next verify the orbit-span hypothesis of Corollary 4.15. We expand the compressed state in the chosen product basis η of the algorithm registers as X αη,t |η⟩WX Y |ψη,t ⟩I , |ψet ⟩ = η

Then ρetI =

|αη,t |2 |ψη,t ⟩⟨ψη,t |,

so every |ψη,t ⟩ belongs to supp(e ρtI ). By label symmetry of ρtI and (14), this support is also invariant under the range-label action. Moreover, since CompI is an isometry, we have by the orbit span bound of Lemma 4.3 that rank(e ρtI ) = rank(ρtI ) ≤ 2S . Therefore, for every η, n o dim span σ(|η⟩⟨η|WX Y ⊗ IdI )|ψet ⟩ : σ ∈ SN ≤ 2S , and we may apply Corollary 4.15 to |ψet ⟩, which gives X X 2S 2S 2 2 e e |I|∥Π=0 Λη,I |ψt ⟩∥ ≤ min t, ∥|ψt ⟩∥ = min t, . log2 N log2 N η

(34)

I⊆[M ]

The vector Π=0 |ψet ⟩ is collision-free, so by applying Lemma 3.5, using that Π=0 commutes with every Λη,I , and then using (34), we obtain e =0 |ψet ⟩∥ ≤ √4 ∥Π≥1 OΠ N

X X

4 =√ N

X X

4 ≤√ N

|I|∥Λη,I Π=0 |ψet ⟩∥2

1/2

η I⊆[M ] 2

1/2

|I|∥Π=0 Λη,I |ψet ⟩∥

η I⊆[M ]

min t,

2S . log2 N

Combining this with (9) proves (33): s s T −1 2S 2S 4 X 4T ∆T ≤ √ min t, ≤√ min T, . log2 N log2 N N t=0 N Combining Lemma 3.6 with Lemma 4.16 gives the following bound on the actual success probability.

Corollary 4.17. Let A be a label-symmetric algorithm. Assume N ≥ 9, S ≥ log2 N , and T ≥ 0. Then s r !2 4T 2S 2 U + . psucc ≤ √ min T, log N N N 2 In particular, for T ≥ 1 36T pU succ ≤

2S min T, log2 N

Proof. The first inequality follows immediately from Lemma 4.16 and Lemma 3.6. Set 2S m := min T, . log2 N Since T ≥ 1 and S ≥ log2 N , we have m ≥ 1, and hence √ √ √ 4T m + 2 ≤ 6T m. Squaring proves the second inequality. Theorem 4.18. Let M, N be positive integers with N ≥ 9, and let f : [M ] → [N ] be chosen uniformly at random. Let A be a label-symmetric quantum algorithm that makes T queries to f and uses S qubits of space. If A outputs a triple (x1 , x2 , y) ∈ [M ]2 × [N ] satisfying x1 < x2 and f (x1 ) = f (x2 ) = y with probability at least 2/3, then T = Ω(N 1/3 )

T 2 S = Ω(N log N ).

and

Proof. Since the range-value register Y has dimension N , our definition of space implies S ≥ log2 N. If T = 0, then the first inequality of Corollary 4.17 gives pU succ ≤

2 2 < , N 3

since N ≥ 9. Thus, T ≥ 1. By Corollary 4.17 and the assumption that the success probability is at least 2/3, 2S N 2 T min T, ≥ . log2 N 54 Since

min T,

2S log2 N

we obtain T3 ≥

N 54

≤ T,

2S min T, log2 N T 2S ≥

and

≤

N log2 N . 108

2S log2 N

For the problem of Element Distictness, the task is to decide whether a given function f : [n] → [q] is injective or not. We instead prove a lower bound for the search version, where the full collision triple (x1 , x2 , y) must be output. The decision and search versions have the same asymptotic bounded-error quantum query complexity [AS04, Amb07]. Since a uniformly random function f : [n] → [n2 ] contains a collision with constant probability, we can take the domain size to be n and the range size to be n2 in Theorem 4.18 to obtain the following result. Corollary 4.19. Let n ≥ 9 be a positive integer, and let A be a label-symmetric quantum algorithm such that, for every non-injective function f : [n] → [n2 ], the algorithm outputs a triple (x1 , x2 , y) ∈ [n]2 × [n2 ] satisfying x1 < x2 and f (x1 ) = f (x2 ) = y with probability at least 2/3. If A makes T queries and uses S qubits, then T = Ω(n2/3 )

T 2 S = Ω(n2 log n).

and

Examples of label-symmetric algorithms

We verify that the BHT collision-finding algorithm [BHT97] and Ambainis’s quantum walk for Element Distinctness [Amb07] with their usual list-based implementations are in fact label-symmetric, and we additionally show that label symmetry is guaranteed in the equality-query oracle model. The following criterion will be convenient. Lemma 5.1. Let A be a T -query algorithm, let |ψtf (A)⟩ denote its pure state at the checkpoint after exactly t oracle calls on input f : [M ] → [N ], with t = 0 denoting the initial state, and let f be drawn from the uniform distribution U on [N ]M . Suppose that, for every σ ∈ SN and every t ∈ {0, . . . , T }, there is a unitary Rσ,t on HWX Y , independent of f , such that |ψtσ◦f (A)⟩ = Rσ,t |ψtf (A)⟩

for every f : [M ] → [N ].

(35)

Then A is label-symmetric. Proof. For every f, g : [M ] → [N ], unitarity of Rσ,t and (35) give ⟨ψtσ◦g (A)|ψtσ◦f (A)⟩ = ⟨ψtg (A)|ψtf (A)⟩. The uniform distribution is invariant under the bijection f 7→ σ ◦ f , so the Gram-matrix characterization from Fact 4.2 proves the claim.

5.1

BHT and Ambainis’s quantum walk

We use the oracle from Definition 2.4 in its addition form: Of |x, y⟩X Y = |x, y + f (x) mod N ⟩X Y

(x ∈ [M ], y ∈ ZN ).

Recall from (13) that Vσ |f ⟩ = |σ ◦ f ⟩ denotes the relabelling action on the input register. We use the same notation for the permutation unitary Vσ |y⟩ = |σ(y)⟩ on a single label valued register and for its tensor powers on several such registers. This is consistent with (13), where Vσ acts on all M values of f . We now describe implementations of the BHT algorithm and Ambainis’s quantum walk. Since we are concerned only with query complexity, not time complexity, we omit the time optimal implementation, which sorts the data structure by label value and thereby breaks the necessary label symmetry. 32

The BHT collision-finding algorithm. tation proceeds as follows.

Fix a parameter r. A convenient unitary implemen-

1. Prepare a uniform superposition over tuples K = (x1 < · · · < xr ) ⊆ [M ]r in the index fields of the table. 2. Query the indices x1 , . . . , xr and store r Df (K) := (xi , f (xi )) i=1 . 3. Reversibly compute a flag cK indicating whether Df (K) contains a collision and, when cK = 1, compute the lexicographically least pair (xi , xj ) with i < j and f (xi ) = f (xj ). 4. Perform the prescribed fixed number of Grover or amplitude-amplification iterations over [M ] \ K with marking predicate hf (x) := 1 [∃i ∈ [r] such that f (x) = f (xi )] .

(36)

A phase query for hf loads f (x) into a clean temporary register, computes hf (x) using equality tests against the stored values, applies the phase, uncomputes the equality tests, and erases the temporary value. 5. Load the value of the candidate index x, reversibly verify that it is marked, and select the least xi satisfying f (x) = f (xi ). If cK = 1, copy the internal collision from Step 3 to the output; otherwise copy the verified pair (xi , x). Finally, uncompute all flags and measure only the output registers. Ambainis’s quantum walk for Element Distinctness. Fix a parameter r. A list-based implementation of the walk on the Johnson graph J(M, r) proceeds as follows. 1. Prepare a uniform superposition over tuples R = (x1 < · · · < xr ) ⊆ [M ]r in the index fields of the table. 2. Query the indices x1 , . . . , xr thereby store r Df (R) := (xi , f (xi )) i=1 . 3. Implement the checking reflection using the marking predicate mf (R) := 1 [∃i < j such that f (xi ) = f (xj )] .

(37)

The predicate is computed and uncomputed using reversible equality tests among the stored values. 4. Implement the Johnson graph update using labels x ∈ R and y ∈ / R. With R′ := R\{x}∪{y}, the data update is the map |R, x, y, Df (R)⟩ 7−→ |R′ , y, x, Df (R′ )⟩.

(38)

Concretely, move the slot (x, f (x)) to the update register, erase f (x), replace x by y, load f (y), swap the two vertex labels, and apply a reversible index-controlled permutation of complete slots to restore increasing order; any comparison or swap-history workspace is uncomputed before the shift ends. 33

5. Apply the quantum walk from the checking reflection, the shift, and input-independent reflections. At the end, select the lexicographically least colliding pair in Df (R), copy it to the output, uncompute all flags, and measure only the output registers. Remark 5.2. Our lower bound assumes that the algorithm must output the collision value y, whereas in both the algorithms above, the collision output label y value is already stored in the table. Thus outputting the label requires only a ⌈log2 N ⌉-qubit output field and no additional oracle call. Equivalently, starting from only a collision pair (x1 , x2 ) output implementation, one final ordinary query obtains the common value with the same asymptotic query and space complexities. Lemma 5.3. The fixed-query unitary implementations of the BHT algorithm and Ambainis’s quantum walk described above are label-symmetric. Proof. Fix σ ∈ SN . First, observe that an input-independent unitary requires no separate symmetry argument at the level of the reduced input state, since it acts only on the algorithm registers. In terms of the sufficient criterion (35), if |ϕσ◦f ⟩ = Rσ |ϕf ⟩ before an input-independent unitary U , then U |ϕσ◦f ⟩ = (U Rσ U † )U |ϕf ⟩, and the new relating unitary is still independent of f . The only points of interest are are therefore the input-dependent Grover and quantum walk blocks and the ordinary oracle calls. Ordinary oracle calls are used to load and erase values in the table, for example in Step 2 in both algorithms. Whenever a table contains r queried values, Vσ⊗r denotes the application of Vσ to its r value fields and the identity on all index and auxiliary registers. By definition, Vσ⊗r |Df (K)⟩ = |Dσ◦f (K)⟩,

Vσ⊗r |Df (R)⟩ = |Dσ◦f (R)⟩.

(39)

BHT. Let Mf denote the Grover marking reflection, where the temporary query and workspace registers have returned to zero. On every reachable basis state it acts as Mf |K, Df (K), x⟩ = (−1)hf (x) |K, Df (K), x⟩,

(40)

where hf is defined in (36). Since σ is injective, hσ◦f (x) = 1 [∃i ∈ [r] such that σ(f (x)) = σ(f (ki ))] = 1 [∃i ∈ [r] such that f (x) = f (ki )] = hf (x).

(41)

Combining (39), (40), and (41) gives, on the reachable subspace, Mσ◦f Vσ⊗r = Vσ⊗r Mf .

(42)

Since the rest of the Grover iterate, i.e. the diffusion step, acts trivially on the registers storing labels, (42) also holds for the entire Grover iterate. Lastly, the collision flag and output indices are invariant under σ, because f (xi ) = f (xj ) if and only if σ(f (xi )) = σ(f (xj )), whereas the output collision label y is mapped by Vσ .

Ambainis’s quantum walk. Let Cf denote the checking reflection. On every reachable basis state it acts as Cf |R, Df (R)⟩ = (−1)mf (R) |R, Df (R)⟩, where mf is defined in (37). Since equality of range values is preserved by σ, we have mσ◦f (R) = mf (R), and hence, on the reachable walk subspace, Cσ◦f Vσ⊗r = Vσ⊗r Cf .

(43)

Let Sf denote the Johnson graph update. For x ∈ R, y ∈ / R, and R′ := R \ {x} ∪ {y}, (38) gives Sσ◦f Vσ⊗r |R, x, y, Df (R)⟩ = Sσ◦f |R, x, y, Dσ◦f (R)⟩ = |R′ , y, x, Dσ◦f (R′ )⟩ = Vσ⊗r |R′ , y, x, Df (R′ )⟩ = Vσ⊗r Sf |R, x, y, Df (R)⟩. Therefore, on the reachable walk subspace, Sσ◦f Vσ⊗r = Vσ⊗r Sf .

(44)

Every remaining reflection in the walk acts trivially on the registers storing labels and therefore it follows from (43) that (44) holds for the full quantum walk operator. The collision flag and the collision output are the same as for BHT. Ordinary oracle calls. It remains to check the ordinary queries used to load and erase values. Let J|z⟩ = | − z mod N ⟩, and let |d⟩ contain ℓ other stored values. On the reachable subspace, Oσ◦f Vσ⊗ℓ |d⟩|x, 0⟩ = (Vσ⊗ℓ ⊗ Vσ )Of |d⟩|x, 0⟩, Oσ◦f (Vσ⊗ℓ ⊗ JVσ J)|d⟩|x, −f (x)⟩ = (Vσ⊗ℓ ⊗ Id)Of |d⟩|x, −f (x)⟩. Thus, loading a label a factor Vσ on its target, while erasing a label removes it. Equality tests preserve this action, since f (x) = f (xi ) if and only if σ(f (x)) = σ(f (xi )). We can therefore conclude that, after each query in the algorithm, we can define a unitary Rσ,t independent of f satisfying (35) and the lemma follows from Lemma 5.1. Query and space complexities. For BHT in the standard case M = N , the table is prepared with p r queries and each Grover iteration uses O(1) ordinary queries. The standard analysis gives O( N/r) iterations, and hence r N TBHT = O r + r queries [BHT97]. For Ambainis’s walk, preparing the initial table uses r queries, checking uses no queries once the table is stored, and each shift uses O(1) queries. The standard walk analysis therefore gives M Twalk = O max r, √ , r 35

which becomes O(M 2/3 ) for r = Θ(M 2/3 ) [Amb07, Theorem 4]. For both algorithms, the r explicit index slots use Θ (r(log M + log N )) qubits. All additional auxiliary registers fit within the same asymptotic bound and therfore both implementations use Θ (r(log M + log N )) qubits. When M = N O(1) , this is Θ(r log N ), so fitting either implementation into S qubits requires r = O(S/ log N ).

5.2

Equality-query algorithms

Pairwise equality access is a classical restricted query model in which the algorithm may ask only whether two input positions contain identical values. For f : [M ] → [N ], the coherent equality oracle is defined by Ef |x, x′ , b⟩ = |x, x′ , b ⊕ 1[f (x) = f (x′ )]⟩

(45)

for x, x′ ∈ [M ] and b ∈ {0, 1}. We call an algorithm an equality-query algorithm if its only inputdependent operation is Ef . In particular, comparing f (x) with a fixed range label is not an equality query in this sense. One equality query has a clean implementation using the standard oracle. Load f (x) and f (x′ ) into two clean value registers, compute their equality into b, and erase both values using Of† = JOf J. Thus one equality query uses four ordinary queries and O(log N ) additional qubits; the two temporary value registers are returned to zero and reused. Lemma 5.4. Every equality-query algorithm is label-symmetric. Proof. For every σ ∈ SN and x, x′ ∈ [M ], (σ ◦ f )(x) = (σ ◦ f )(x′ )

⇐⇒

f (x) = f (x′ ),

so Eσ◦f = Ef . Since the initial state and every inter-query unitary are independent of f , induction gives |ψtσ◦f (A)⟩ = |ψtf (A)⟩ for every t ∈ {0, . . . , T }. Thus (35) holds with Rσ,t = Id, and Lemma 5.1 proves the claim.

Bottom spectrum of the arrangement graphs

In this section, we prove Lemma 4.9, which gives a complete description of the bottom of the spectrum of the arrangement graph AN,s (in the regime N ≥ 2s). Building on the previous spectral analyses of Chen, Ghorbani, and Wong [CGW13] and Araujo and Bratten [AB17], we identify the full (−s)-eigenspace and determine the exact next distinct eigenvalue. The proof combines the representation-theoretic decomposition of Cs⊥ with the character-ratio formula for the eigenvalues of AN,s . We begin by recalling the required facts about skew diagrams, horizontal strips, and Young’s seminormal idempotents. If λ and µ are partitions with λi ≤ µi for all i, then we write λ ⊆ µ. The skew diagram µ/λ is the set of boxes of Y (µ) not contained in Y (λ): µ/λ := Y (µ) \ Y (λ). 36

A skew diagram is called a horizontal strip if it contains at most one box in each column. We write λ≺µ if µ/λ is a horizontal strip. Equivalently, one can check that λ ≺ µ if and only if µ1 ≥ λ1 ≥ µ2 ≥ λ2 ≥ µ3 ≥ λ3 ≥ · · · . We will also use the following standard facts about Young’s seminormal idempotents, see, e.g., [GE20, Sections 2.2-2.3]. For every partition λ ⊢ n and every standard Young tableau t ∈ SYT(λ), there is a seminormal idempotent et ∈ C[Sn ]. These idempotents form a complete family of pairwise orthogonal idempotents: X X et = 1. (46) e2t = et , et et′ = 0 (t ̸= t′ ), λ⊢n t∈SYT(λ)

Since every element of C[Sn ] is a linear combination of permutations, a right action of Sn on V allows such an element to act on V by linearity. Under this action, the map v 7→ vet is an idempotent projection onto V et := {vet : v ∈ V }. Moreover, (46) gives the direct-sum decomposition M M V =

V et .

λ⊢n t∈SYT(λ)

We are now ready to prove our Arrangement Spectral Gap lemma, that we restate here for clarity. Lemma 6.1 (Arrangement Spectral Gap). Assume s ≥ 1 and N ≥ 2s. The smallest eigenvalue of AN,s on Cs⊥ is −s, and its eigenspace is, as an SN -representation, M |SYT(µ)|S (N −s,µ) . µ⊢s

Moreover, the next distinct eigenvalue is exactly N − (3s − 2). Consequently, the gap above the least eigenvalue is N − 2s + 2, and −s is the unique negative eigenvalue exactly when N ≥ 3s − 2. Proof. We first consider the case s = 1. Then C1⊥ = C[N ], and AN,1 is the adjacency operator of the complete graph on N vertices. Hence AN,1 = N |b 0⟩⟨b 0| − Id. It follows that AN,1 has eigenvalue N − 1 on span{|b 0⟩} and eigenvalue −1 on W = ker(⟨b 0|) ∼ = S (N −1,1) . Since (1) is the unique partition of 1 and has exactly one standard Young tableau, this is precisely the claimed (−1)-eigenspace. Moreover, the only other eigenvalue is N − 1 = N − (3 · 1 − 2), 37

so the claimed bound on the remaining eigenvalues also holds. Henceforth, assume that s ≥ 2. Fix a partition µ ⊢ s and a tableau t ∈ SYT(µ). Recall that et ∈ C[Ss ] is the corresponding seminormal idempotent of the standard Young tableau t, and let ⊥ Cs,µ,t := Cs⊥ et ,

meaning Cs⊥ =

⊥ Cs,µ,t .

µ⊢s t∈SYT(µ) ⊥ In [NTV19, Example 2], it is shown that each of these subspaces Cs,µ,t satisfies M ⊥ ∼ Cs,µ,t S (N −|λ|,λ) . = λ:λ≺µ

Here λ = ∅ is allowed. This occurs when µ = (s), in which case the corresponding summand is understood as S (N −|∅|,∅) = S (N ) . Among these summands, S (N −s,µ) is the only one whose first row has length exactly N − s; every other summand has a strictly longer first row. By the proof of [AB17, Theorem 3.5], more specifically by [AB17, Lemma 3.2, Proposition 3.3, and Theorem 3.4], each summand S (N −|λ|,λ) (where λ ≺ µ) is contained in an eigenspace of AN,s , and the corresponding eigenvalue is given by N χ(N −|λ|,λ) (τN ) s χµ (τs ) N −s Eµ,λ = − − , 2 χ(N −|λ|,λ) (1) 2 χµ (1) 2 where τN and τs are transpositions in SN and Ss , respectively. For any partition α ⊢ m, it is known (see, e.g., [GE20, Eq. (2.4.9)]) that these character ratios can be rewritten as X m χα (τm ) = (j − i) =: γ(α). 2 χα (1) (i,j)∈α

Therefore, the eigenvalues of AN,s are given by N −s Eµ,λ = γ((N − |λ|, λ)) − γ(µ) − . 2

(47)

We first compute the value for λ = µ, meaning (N − |λ|, λ) = (N − s, µ). The first row of (N − s, µ) contributes N −s X N −s (j − 1) = 2 j=1

to γ((N − s, µ)). The remaining rows are obtained by moving the Young diagram of µ down by one row, which subtracts 1 from the quantity j − i for each of the s boxes of µ. Therefore N −s γ((N − s, µ)) = + γ(µ) − s. 2 Substituting this into the eigenvalue formula gives Eµ,µ = −s, 38

meaning S (N −s,µ) lies in the −s-eigenspace of AN,s . Now let λ ≺ µ with λ ̸= µ. Then Eµ,λ = Eµ,µ + γ((N − |λ|, λ)) − γ((N − s, µ)) = −s + γ((N − |λ|, λ)) − γ((N − s, µ)).

(48)

To compute Eµ,λ , we therefore only have to compute the difference γ((N − |λ|, λ)) − γ((N − s, µ)). To aid in this, we define the following: X δi = s − |λ|. δi := µi − λi , q := i≥1

Since λ ⊆ µ, we have δi ≥ 0, and since λ ̸= µ, we have q ≥ 1. In terms of these new quantities, the partition (N − |λ|, λ) is obtained from (N − s, µ) by deleting δi boxes from the end of row i + 1 for each i ≥ 1, and adding all of them, i.e. q, to the end of the first row. The q extra boxes in the first row of (N − |λ|, λ) have a total contribution of q−1 X q (N − s + a) = q(N − s) + 2 a=0

to the difference γ((N − |λ|, λ)) − γ((N − s, µ)). For each i ≥ 1, the deleted boxes from row i + 1 have positions (i + 1, µi ), (i + 1, µi − 1), . . . , (i + 1, µi − δi + 1). Since a deleted box (i + 1, j) contributes −(j − (i + 1)) to the difference, the contribution from these deleted boxes to the difference γ((N − |λ|, λ)) − γ((N − s, µ)) is −

δX i −1 a=0

δi (µi − a − (i + 1)) = −δi µi + (i + 1)δi + . 2

Combining these added and deleted contributions gives γ((N − |λ|, λ)) − γ((N − s, µ)) =

δi (N − s − µi + i + 1) +

i≥1

X q δi + . 2 2

(49)

i≥1

We now lower bound the right-hand side of (49). Observe that when δi > 0 we have µi > 0. In those cases, since µ ⊢ s, we have µi ≤ s − i + 1 and hence N − s − µi + i + 1 ≥ N − s − (s − i + 1) + i + 1 = N − 2s + 2i ≥ N − 2s + 2.

(50)

The binomial terms in (49) are also nonnegative, so using q ≥ 1 we obtain γ((N − |λ|, λ)) − γ((N − s, µ)) ≥ q(N − 2s + 2) ≥ N − 2s + 2. Substituting this into (48) yields Eµ,λ ≥ −s + N − 2s + 2 = N − (3s − 2),

(51)

meaning that the eigenvalue of AN,s for every S (N −|λ|,λ) with λ ̸= µ is at least N − (3s − 2), which, by the assumption N ≥ 2s, is strictly larger than −s. This means that the (−s)-eigenspace of 39

AN,s consists solely of the Specht modules S (N −s,µ) for µ ⊢ s. Summing over all |SYT(µ)| standard tableaux of shape µ shows that the (−s)-eigenspace of AN,s is M |SYT(µ)|S (N −s,µ) . µ⊢s

The lower bound in (51) is attained for the partitions µ = (s),

λ = (s − 1).

Indeed, in that case one can verify that λ ≺ µ, q = 1, δ1 = 1, and δi = 0 for all i ≥ 2. Thus, equality holds in (50) and the two binomial terms in (49) become zero.

Acknowledgements. The authors thank Dmitry Grinko for helpful discussions and explanations concerning the representation theory of the symmetric group. This research was supported in part by the French PEPR integrated project EPiQ (ANR-22PETQ-0007, part of Plan France 2030) and the ERC Advanced Grant PARQ. AI statement. The main ideas and proofs in this work were developed by the authors, with the exception of the connection made by ChatGPT 5.3 between Cs⊥ ∩ W ⊗s and arrangement graphs, via the deletion map D defined in (19). AI tools were also used for supplementary verification of results, editing the manuscript and the discussing of ideas.

References [Aar21]

Scott Aaronson. Open problems related to quantum query complexity. ACM Transactions on Quantum Computing, 2(4):14:1–14:9, 2021. arXiv: 2109.06917 3

[AB17]

José O Araujo and Tim Bratten. The spectra of arrangement graphs. Linear Algebra and its Applications, 530:461–469, 2017. arXiv: 1612.04747 4, 23, 36, 38

[Ajt05]

Miklós Ajtai. A non-linear time lower bound for Boolean branching programs. Theory of Computing, 1(8):149–176, 2005. Preliminary version: ECCC TR99-026. 2

[Amb07]

Andris Ambainis. Quantum walk algorithm for element distinctness. SIAM Journal on Computing, 37(1):210–239, 2007. Earlier version in FOCS’04. arXiv: quant-ph/0311001 i, 1, 32, 36

[Amb10]

Andris Ambainis. A new quantum lower bound method, with an application to a strong direct product theorem for quantum search. Theory of Computing, 6(1):1–25, 2010. arXiv: quant-ph/0508200 19

[AMRR11] Andris Ambainis, Loı̈ck Magnin, Martin Roetteler, and Jérémie Roland. Symmetryassisted adversaries for quantum state generation. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, pages 167–177, 2011. arXiv: 1012.2112 19 [AS04]

Scott Aaronson and Yaoyun Shi. Quantum lower bounds for the collision and the element distinctness problems. Journal of the ACM, 51(4):595–605, 2004. arXiv: quant-ph/0112086 32

[BB14]

Charles H. Bennett and Gilles Brassard. Quantum cryptography: Public key distribution and coin tossing. Theoretical Computer Science, 560(Part 1):7–11, 2014. Reprint of the original 1984 paper. arXiv: 2003.06557 1

[BCM13]

Paul Beame, Raphaël Clifford, and Widad Machmouchi. Element distinctness, frequency moments, and sliding windows. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 290–299, 2013. arXiv: 1309.3690 2

[Ber09a]

Daniel J. Bernstein. Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete? In Workshop Record of SHARCS’09: Special-Purpose Hardware for Attacking Cryptographic Systems, pages 105–116, 2009. Author’s manuscript: https://cr.yp.to/hash/collisioncost-20090823.pdf. 2

[Ber09b]

Daniel J. Bernstein. Introduction to post-quantum cryptography. In Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen, editors, Post-Quantum Cryptography, pages 1–14. Springer, Berlin, Heidelberg, 2009. 1

[BFK+ 81]

Allan Borodin, Michael J. Fischer, David G. Kirkpatrick, Nancy A. Lynch, and Martin Tompa. A time-space tradeoff for sorting on non-oblivious machines. J. Comput. Syst. Sci., 22(3):351–364, 1981. 2

[BHT97]

Gilles Brassard, Peter Høyer, and Alain Tapp. Quantum algorithm for the collision problem. ACM SIGACT News, 28(2):14–19, 1997. arXiv: quant-ph/9705002 i, 1, 32, 35

[BKW26]

Paul Beame, Niels Kornerup, and Michael Whitmeyer. Quantum time-space tradeoffs for matrix problems. SIAM J. Comput., 55(3):469–519, 2026. arXiv: 2401.05321 2

[BSSV03]

Paul Beame, Michael E. Saks, Xiaodong Sun, and Erik Vee. Time-space trade-off lower bounds for randomized computation of decision problems. J. ACM, 50(2):154– 195, 2003. Preliminary version: ECCC TR00-025. 2

[CCKDS26] Joseph Carolan, Andrew M. Childs, Matt Kovacs-Deak, and Luke Schaeffer. Translation-invariant quantum algorithms for ordered search are optimal. ACM Transactions on Quantum Computing, 2026. To appear. arXiv: 2503.21090 5, 19 [CFHL21]

Kai-Min Chung, Serge Fehr, Yu-Hsuan Huang, and Tai-Ning Liao. On the compressedoracle technique, and post-quantum security of proofs of sequential work. In Proceedings of the 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2021, Part II, pages 598–629, 2021. ePrint: 2020/1305 13

[CGW13]

Bai Fan Chen, Ebrahim Ghorbani, and Kok Bin Wong. Cyclic decomposition of kpermutations and eigenvalues of the arrangement graphs. The Electronic Journal of Combinatorics, 20(4):P22, 2013. arXiv: 1308.5490 4, 23, 36

[CJWW22] Lijie Chen, Ce Jin, R. Ryan Williams, and Hongxun Wu. Truly low-space element distinctness and subset sum via pseudorandom hash functions. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 1661–1678, 2022. arXiv: 2111.01759 2 [CNS17]

André Chailloux, Marı́a Naya-Plasencia, and André Schrottenloher. An efficient quantum collision search algorithm and implications on symmetric cryptography. In Proceedings of the 23rd International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2017, Part II, pages 211–240, 2017. ePrint: 2017/847 2

[Din20]

Itai Dinur. Tight time-space lower bounds for finding multiple collision pairs and their applications. In Proceedings of the 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020, Part I, pages 405–434, 2020. ePrint: 2020/229 3

[FGGS99]

Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Invariant quantum algorithms for insertion into an ordered list, 1999. arXiv: quant-ph/9901059 5, 19

[GE20]

Adriano M Garsia and Ömer Eğecioğlu. Young’s seminormal representation, murphy elements, and content evaluations. In Lectures in Algebraic Combinatorics: Young’s Construction, Seminormal Representations, SL (2) Representations, Heaps, Basics on Finite Fields, volume 2277 of Lecture Notes in Mathematics, pages 35–95. Springer, Cham, 2020. 37, 38 42

[GLM08]

Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum random access memory. Physical Review Letters, 100(16):160501, 2008. arXiv: 0708.1879 1

[Gro96]

Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th ACM Symposium on the Theory of Computing (STOC), pages 212–219, 1996. arXiv: quant-ph/9605043 2

[HM23]

Yassine Hamoudi and Frédéric Magniez. Quantum time–space tradeoff for finding multiple collision pairs. ACM Transactions on Computation Theory, 15(1–2):3:1–3:22, 2023. arXiv: 2002.08944 3, 4, 5, 13, 14, 15

[HNS02]

Peter Høyer, Jan Neerbek, and Yaoyun Shi. Quantum complexities of ordered searching, sorting, and element distinctness. Algorithmica, 34(4):429–448, 2002. arXiv: quant-ph/0102078 2

[IP01]

Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367–375, 2001. 2

[Jef11]

Stacey Jeffery. Collision finding with many classical or quantum processors. Master of mathematics thesis, University of Waterloo, Waterloo, Ontario, Canada, 2011. Available at https://hdl.handle.net/10012/6200. 2

[JZ26]

Stacey Jeffery and Sebastian Zur. The compressed oracle is a worthy (multiplicative) adversary. In Proceedings of the 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026), pages 118:1–118:23, 2026. arXiv: 2509.07876 12, 13

[KŠDW07] Hartmut Klauck, Robert Špalek, and Ronald De Wolf. Quantum and classical strong direct product theorems and optimal time-space tradeoffs. SIAM Journal on Computing, 36(5):1472–1493, 2007. arXiv: quant-ph/0402123 2 [KW88]

Selahattin Kayalar and Howard L. Weinert. Error bounds for the method of alternating projections. Mathematics of Control, Signals, and Systems, 1(1):43–59, 1988. 23

[LZ19]

Qipeng Liu and Mark Zhandry. On finding quantum multi-collisions. In Proceedings of the 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), Part III, pages 189–218, 2019. ePrint: 2018/1096 15

[LZ23]

Xin Lyu and Weihao Zhu. Time-space tradeoffs for element distinctness and set intersection via pseudorandomness. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, pages 5243–5281, 2023. arXiv: 2210.07534 2

[NTV19]

P. P. Nikitin, N. V. Tsilevich, and A. M. Vershik. On the decomposition of tensor representations of symmetric groups. Algebras and Representation Theory, 22(4):895– 908, 2019. arXiv: 1712.03356 38

[PQC06]

PQCrypto 2006: International Workshop on Post-Quantum Cryptography. https: //postquantum.cr.yp.to/, 2006. Katholieke Universiteit Leuven, Leuven, Belgium, May 23–26, 2006. 1 43

[PR98]

Jakob Pagter and Theis Rauhe. Optimal time-space trade-offs for sorting. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, FOCS 1998, pages 264–268, 1998. Full version: BRICS Report RS-98-10. 2

[Ras77]

Richard Rasala. On the minimal degrees of characters of Sn . Journal of Algebra, 45(1):132–181, 1977. 21

[Sag01]

Bruce Sagan. The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, volume 203 of Graduate Texts in Mathematics. Springer, New York, 2nd edition, 2001. 10

[Sho97]

Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509, 1997. arXiv: quant-ph/9508027 1

[vOW99]

Paul C. van Oorschot and Michael J. Wiener. Parallel collision search with cryptanalytic applications. J. Cryptol., 12(1):1–28, 1999. 2, 3

[Zha19]

Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In Proceedings of the 39th Annual International Cryptology Conference, CRYPTO 2019, Part II, pages 239–268, 2019. ePrint: 2018/276 3, 4, 5, 12, 13, 17, 18

Record · ID 673431 · SHA-256 38c7ca0447dd8b6c
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.