Maxime Remaud

André Schrottenloher

Jean-Pierre Tillich

Time and Query Complexity Tradeoffs for the Dihedral Coset Problem

Keywords: Dihedral Hidden Subgroup Problem, Subset-sum, Dihedral Coset Problem, Quantum Algorithms

The Dihedral Coset Problem (DCP) in ZN has been extensively studied in quantum computing and post-quantum cryptography, as for instance, the Learning with Errors problem reduces to it. While the Ettinger-Høyer algorithm is known to solve the DCP in O (log N ) queries, it runs inefficiently in time O (N ). The first time-efficient algorithm was introduced (and later improved) by Kuperberg (SIAM J. Comput. 2005). These algorithms run in a subexponential amount of time and queries Õ 2

The sieving algorithms à la Kuperberg admit many trade-offs between quantum and classical time, memory and queries. Some of these trade-offs allow the attacker to reduce the number of queries if they are particularly costly, which is notably the case in the post-quantum key-exchange CSIDH. Such optimizations have already been studied, but they typically fall into two categories: the resulting algorithm is either based on Regev's approach of reducing the DCP with quadratic queries to a subset-sum instance, or on a re-optimization of Kuperberg's sieve where the time and queries are both subexponential.

In this paper, we introduce the first algorithm to improve in the linear queries regime over the Ettinger-Høyer algorithm. We then show that we can in fact interpolate between this algorithm and Kuperberg's sieve, by using the latter in a pre-processing step to create several quantum states, and solving a quantum subset-sum instance to recover the full secret in one pass from the obtained states. This allows to interpolate smoothly between the linear queries-exponential time complexity case and the subexponential query and time complexity case, thus allowing a fine tuning of the complexity taking into account the query cost. We also give on our way a precise study of quantum subset-sum algorithms in the non-asymptotic regime.

Introduction

Hidden Subgroup Problem. Let G be a known group and H be an unknown subgroup of G. Finding H is a problem known as the Hidden Subgroup Problem (HSP). To solve it, we can query a function f which satisfies a certain property with respect to H: Definition 1 (HSP). The hidden subgroup problem is defined as:

-Given: a function f : G → S that is constant and distinct on the left cosets of an unknown subgroup H of a group G, S being a finite set, -Find: (a generating set of ) H.

Many problems used to construct primitives can be reduced to an HSP instance, for example the Discrete Logarithm and Shortest Vector problems. Shor's algorithm [START_REF] Shor | Algorithms for quantum computation: discrete logarithms and factoring[END_REF], which solves the DLP and breaks the RSA cryptosystem [START_REF] Rivest | A method for obtaining digital signatures and public-key cryptosystems[END_REF] in polynomial time, can actually be extended to solve the HSP for an abelian group G. In the general case, it is well known that the problem requires only a polynomial (in log 2 |G|) number of queries to the function f [START_REF] Ettinger | The quantum query complexity of the hidden subgroup problem is polynomial[END_REF]. However, time-efficient quantum algorithms are only known for very specific instances, including abelian groups, and it is widely admitted that the generic problem remains difficult for quantum algorithms.

Dihedral Hidden Subgroup Problem (DHSP). While the HSP in an abelian group is quantumly easy to solve, many post-quantum primitives are related to the HSP in the dihedral group. In this case, even if the group is very close to be abelian (it has namely an abelian subgroup of index 2) no polynomial-time algorithm is known. This is the case of cryptosystems based on the Unique Shortest Vector Problem (uSVP) in lattice-based cryptography (such as [START_REF] Ajtai | A public-key cryptosystem with worst-case/average-case equivalence[END_REF][START_REF] Regev | New lattice-based cryptographic constructions[END_REF]) or on any problem that can be reduced to the uSVP (because of a chain of reductions between several problems [START_REF] Regev | Quantum computation and lattice problems[END_REF][START_REF] Lyubashevsky | On bounded distance decoding, unique shortest vectors, and the minimum distance problem[END_REF][START_REF] Stehlé | Efficient public key encryption based on ideal lattices[END_REF]). More concretely, the security of several primitives reduces to the DHSP. The most prominent example is the isogeny-based post-quantum key-exchange CSIDH [START_REF] Castryck | Csidh: An efficient post-quantum commutative group action[END_REF], which is similar to the Diffie-Hellman protocol [START_REF] Diffie | New directions in cryptography[END_REF] except that it does not rely on the period-finding problem in an abelian group (which is solvable in quantum polynomial time), but on the difficulty to invert the group action. Several related constructions [START_REF] Alamati | Cryptographic group actions and applications[END_REF] such as the signature schemes SeaSign [START_REF] De Feo | Seasign: Compact isogeny signatures from class group actions[END_REF][START_REF] Decru | Faster seasign signatures through improved rejection sampling[END_REF] and CSI-FiSh [START_REF] Beullens | Csi-fish: Efficient isogeny based signatures through class group computations[END_REF] also rely on the same problem. It should be noted that these isogeny-based cryptosystems are the only major contenders for which the quantum attacker enjoys more than a quadratic speedup, as opposed to the lattice-and hash-based finalists of the NIST post-quantum standardization process [START_REF]NIST: Submission requirements and evaluation criteria for the postquantum cryptography standardization process[END_REF][START_REF] Alagic | Status report on the third round of the nist post-quantum cryptography standardization process[END_REF].

As it has been shown in [START_REF] Bonnetain | Quantum security analysis of CSIDH[END_REF][START_REF] Peikert | He gives c-sieves on the csidh[END_REF][START_REF] Chávez-Saab | The SQALE of CSIDH: sublinear vélu quantum-resistant isogeny action with low exponents[END_REF], a better understanding of the security of CSIDH comes from a careful analysis of quantum DHSP algorithms. This is the motivation of our work.

From the DHSP to the DCP. Solving the HSP for the dihedral group of order 2N is known to reduce to the specific case where the hidden subgroup is {(0, 0), (s, 1)}, where s ∈ Z N , which can in turn be reduced to a problem known as the Dihedral Coset Problem (see [START_REF] Ettinger | On quantum algorithms for noncommutative hidden subgroups[END_REF]).

Definition 2 (DCP). The dihedral coset problem is defined as:

-Given: an oracle outputting coset states of the form 1

√ 2 (|0 |x + |1 |x + s ) for random x ∈ [[0, N ]], -Find: s ∈ [[0, N ]]
While the Ettinger-Høyer algorithm [START_REF] Ettinger | On quantum algorithms for noncommutative hidden subgroups[END_REF] solves the DCP with a linear number of queries (O (log N )), it runs in exponential time O (N ). This algorithm basically consists in measuring O (log N ) coset states and then classically looking among all possible values for the secret s the one that matches the best a statistical test. It is possible to improve over this running time by reducing the resolution of the DCP to a subset-sum problem, as described by [START_REF] Bonnetain | Quantum security analysis of CSIDH[END_REF][START_REF] Bonnetain | Improved low-qubit hidden shift algorithms[END_REF], at the cost of squaring the query complexity. Though it remains exponential, the time complexity becomes Õ (N c SS ), where c SS is a constant smaller than 1 that depends on the invoked subset-sum subroutine.

In a seminal work [START_REF] Kuperberg | A subexponential-time quantum algorithm for the dihedral hidden subgroup problem[END_REF], Kuperberg initiated a family of sieving algorithms which reach subexponential time complexities (at the cost of a subexponential query complexity). The idea here is to iterate a process of combining states to build new ones with a stronger and stronger structure, until building a very specific state that allows us to guess a bit of the secret when measured. The first algorithm [START_REF] Kuperberg | A subexponential-time quantum algorithm for the dihedral hidden subgroup problem[END_REF] requires subexponential quantum time and space, but it was quickly followed by an algorithm of Regev [START_REF] Regev | A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space[END_REF] which requires only polynomial space. Later, Kuperberg proposed his second algorithm [START_REF] Kuperberg | Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem[END_REF], which generalized Regev's while improving its exponents, giving in the end a complexity in time (classical and quantum) and classical space of Õ 2 Our contributions. Let n def = log 2 N . We first propose a new algorithm using a linear number of queries. It is somewhat analogous to Regev's algorithm where instead of reducing the DCP to a classical subset-sum problem, it reduces the DCP to a quantum subset-sum problem. In the first case, the algorithm makes O (n) queries to find one bit of the secret, meaning it has to be iterated O (n) times. With this new algorithm, which is inspired by [START_REF] Regev | Quantum computation and lattice problems[END_REF][START_REF] Stehlé | Efficient public key encryption based on ideal lattices[END_REF], we only need O (1) quantum subset-sum instances, i.e., O (n) queries, to find the whole secret.

Second, we present a simple and natural method of interpolation between Kuperberg's second algorithm (which is the state of the art) and the new algorithm we mentioned above. It consists in using Kuperberg's algorithm to more or less preprocess the states given as input to our algorithm. The difficulty of solving the inherent quantum subset-sum problem instance will depend on the preprocessing step.

Finally, as a building block of our algorithms, we study quantum subset-sum algorithms when the problem to solve is partially in superposition. We show here that we can still improve over Grover's search even under the constraint of a polynomial quantum memory, using an exponential classical memory, with or without quantum access. Specifically, we show that the QRACM-based algorithm of [START_REF] Bonnetain | Improved classical and quantum algorithms for subset-sum[END_REF] adapts to this case and reaches a complexity Õ 2 0.2356n . Without QRACM, we reach a quantum time Õ 2 0.4165n using O 2 0.2334n bits of classical memory, improving over a previous algorithm by Helm and May [START_REF] Helm | The power of few qubits and collisions -subset sum below grover's bound[END_REF]. In both cases, we also give non-asymptotic estimates of their complexity.

All together, we can summarize the complexity exponents of the different algorithms for solving the DCP in Table 1, including the new one we propose. We propose two versions of our algorithm, one with QRACM and one without, both using polynomial quantum space. Note that our algorithm with QRACM outperforms other algorithms using a linear number of queries when we look at the complexity in classical time + quantum time.

Impact on CSIDH. Although Kuperberg's second algorithm is the one with the best time complexity for solving the DCP, it is still interesting to look at algorithms that only use a linear number of queries, since for example, CSIDH cryptanalysis via the resolution of the DCP involves the use of a very expensive oracle.

We give in Table 2 a few examples of complexity exponents for parameters of CSIDH. Organization of the Paper. In Section 2, we give some preliminaries on sieving algorithms for the DCP, and subset-sum algorithms that we will use as black boxes afterwards. In Section 3, we recall the reduction from the DCP to the subset-sum problem, and introduce our new idea of using a quantum subsetsum solver. Our interpolation between the sieving and subset-sum approaches is detailed in Section 4. Finally, our contributions on quantum subset-sum algorithms, and the details of the black boxes that we used throughout the paper, are provided in Section 5.

Preliminaries

In this section, we cover the main principles of sieving algorithms for the DCP, including Kuperberg's and Regev's algorithms [START_REF] Kuperberg | A subexponential-time quantum algorithm for the dihedral hidden subgroup problem[END_REF][START_REF] Kuperberg | Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem[END_REF][START_REF] Regev | A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space[END_REF][START_REF] Childs | Constructing elliptic curve isogenies in quantum subexponential time[END_REF]. We assume knowledge of the quantum circuit model, i.e., the |• notation of quantum states, and basic quantum operations such as CNOT, Toffoli, the Quantum Fourier Transform (QFT), etc. We estimate the time complexity of a quantum algorithm in the quantum circuit model, as a number of n-bit arithmetic operations. That is, instead of counting precisely the quantum gates, we count the n-bit XORs, additions, subtractions, comparisons, QFTs, depending on the complexity parameter n.

We work with different types of memory:

quantum memory (i.e., qubits): some DCP algorithms (e.g., Kuperberg's first algorithm [START_REF] Kuperberg | A subexponential-time quantum algorithm for the dihedral hidden subgroup problem[END_REF]) need to store many coset states, which creates a subexponential quantum memory requirement; classical memory with quantum random-access (QRACM): the QRACM (or qRAM, QROM in some papers) is a specialized hardware which stores classical data and accesses this data in quantum superposition. That is, we assume that given a classical memory of M bits y 0 , . . . , y M -1 , the following unitary operation:

|x |i Access ----→ |x ⊕ y i |i can be implemented in time O (1)
. QRACM is a very common assumption in quantum computing, and it appears in several works on the DCP [START_REF] Kuperberg | Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem[END_REF][START_REF] Peikert | He gives c-sieves on the csidh[END_REF] but also on collision-finding [START_REF] Brassard | Quantum cryptanalysis of hash and claw-free functions[END_REF] and subset-sum algorithms [START_REF] Bonnetain | Improved classical and quantum algorithms for subset-sum[END_REF]. classical memory without quantum random-access: the Access operation can be implemented in M arithmetic operations using a sequential circuit. This removes the QRACM assumption, and we fall back on the basic quantum circuit model. Some algorithms using QRACM can be re-optimized in a non-trivial way when memory access is costly, and this is the case of subsetsum [START_REF] Helm | The power of few qubits and collisions -subset sum below grover's bound[END_REF].

Phase Vectors and Kuperberg's First Algorithm

We will consider in what follows that we have access to an oracle outputting phase vectors denoted by |ψ k and defined as:

|ψ k def = 1 √ 2 |0 + ω sk N |1
where ω N = exp(2ιπ/N ), ι = √ -1, and k is a known uniformly distributed random element of Z N . They are obtained from coset states (the input states of the DCP) by applying a QFT on Z N on the first register and then measuring this register, since we have

(QF T N ⊗ I) 1 √ 2 (|x |0 + |x + s |1 ) = 1 √ N k∈Z N ω kx N |k |ψ k . Finding s ∈ [[0, N -1]
] from a collection of phase vectors |ψ k for known uniformly distributed random k ∈ [[0, N -1]] solves both the DCP and the DHSP.

Subexponential Algorithms. We will now give more details on the algorithms solving the DCP in subexponential time. Until the end of this section, it can be assumed that N = 2 n for the sake of simplicity, but the algorithms discussed here work for any value of N . Kuperberg's initial observation is that one can combine two phase vectors |ψ p and |ψ q to construct a new phase vector. Indeed, we have:

|ψ p , ψ q CNOT ----→ 1 √ 2 (|ψ p+q , 0 + ω yq N |ψ p-q , 1 ) .
A measurement of the second qubit will leave the first one either in the state |ψ p-q , or |ψ p+q , depending on the bit measured. With probability 1/2, we get |ψ p-q . By noticing on the other hand that ψ N/2 = H |lsb(s) (lsb(s) being the least significant bit of s), Kuperberg designed a quite simple algorithm which groups the phase vectors according to their last non-zero bits. They are then combined two by two using CNOT gates. Half of the time, the difference is obtained, and it contains as many zeroes as there were bits in common. The resulting phase vectors are regrouped and the process is reiterated. As proven in [START_REF] Kuperberg | A subexponential-time quantum algorithm for the dihedral hidden subgroup problem[END_REF], the target state ψ N/2 is then obtained in subexponential time.

Regev's Algorithm

Kuperberg's first algorithm requires to store, at each time, a subexponential number of phase vectors; thus, it has subexponential quantum memory complexity. Regev [START_REF] Regev | A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space[END_REF] modified the combination routine to reduce the number of qubits to polynomial, while keeping the time complexity subexponential.

The new routine combines m phase vectors for a well-chosen m (to minimize the overall complexity).

Let B be some chosen, arbitrary value. We start with m phase vectors |ψ k1 , . . . , |ψ km . We tensor the vectors, i.e., we obtain a sum:

i |ψ ki = b∈{0,1} m ω s b,k N |b
We compute b, k /B into a new qubit register, and measure a value V . This projects the state on the vectors b such that b, k /B = V . We choose m and the size of B such that on average two solutions b and b occur. The state becomes proportional to:

|b + ω s( b,k -b ,k ) N |b .
Finally, we remap b, b to 0, 1 respectively. We have obtained a phase vector |ψ k with a label k = b, kb , k ≤ B. Then, step by step, we can make the labels decrease until we obtain the label 1. As remarked in [START_REF] Bonnetain | Quantum security analysis of CSIDH[END_REF], we can also obtain any label whose value is invertible modulo N , by multiplying all initial labels by their inverse, and applying normally the algorithm afterwards. In particular, when N is odd, we can obtain all powers of two.

Regev [START_REF] Regev | A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space[END_REF] and later Childs, Jao and Soukharev [START_REF] Childs | Constructing elliptic curve isogenies in quantum subexponential time[END_REF] used this combination routine to get an algorithm with Õ 2

√ 2n log 2 n
queries and O (n) quantum memory.

Kuperberg's Second Algorithm

Like the two previous ones, Kuperberg's collimation sieve [START_REF] Kuperberg | Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem[END_REF] is a hybrid quantum/classical procedure starting from the initial phase vectors, where we need to perform both quantum computations which create new vectors, and classical computations which give their description. The difference is that phase vectors are now multi-labeled:

|ψ k1,...,k = 1 √ i ω ski N |i .
In order to control these new phase vectors, we need to know the list of all their labels. These lists will become of subexponential size, although the vector itself requires only a polynomial amount of qubits. This is why the algorithm combines a polynomial quantum memory with a subexponential classical memory. The combination subroutine is similar to Regev's, except that it does not necessarily reduce the list of labels down to 2. Instead, the two phase vectors are combined into a new one holding a similar number of labels, as shown in Algorithm 1.

Originally, Kuperberg uses classical memory with quantum random-access (QRACM), an approach later followed by Peikert [START_REF] Peikert | He gives c-sieves on the csidh[END_REF]. However it only improves the trade-offs with respect to the total quantum time, and it is not necessary to reach the optimal complexity. Also, the collimation procedure presented here Algorithm 1 Combination routine in the collimation sieve.

Input: |ψ k 1 ,...,k , . . . , ψ k 1 ,...,k
such that ∀i ≤ , ∀j ≤ , ki < 2 a , k j < 2 a , the lists of the labels Output: ψv 1 ,...,v such that ∀i, vi < 2 a-r 1: Quantum: Tensor the vectors: i≤ ,j≤ ω

s(k i +k j ) N
|i |j 2: Quantum: Compute the function i, j → (ki + k j )/2 a-r into an ancilla register 3: Quantum: Measure the register, obtain a value V . The state collapses to: is from later works such as [START_REF] Peikert | He gives c-sieves on the csidh[END_REF], as it allows to easily deal with arbitrary group orders.

i,j| (k i +k j )/2 a-r =V ω s(k i +k j ) N |i |j 4: Classical: Compute {(i, j)| (ki + k j )/2 a-r = V },
Without QRACM, Steps 2 and 5 in Algorithm 1 require a time complexity O (max( , , )). This is also the classical time complexity required by Step 4, assuming that the lists of labels are sorted.

The Algorithm as a Merging Tree. Starting from a certain set of multi-labeled phase vectors, we can identify them with the classical lists of their labels. The combination step operates on these lists like a purely classical list-merging algorithm, in which new lists of labels are formed from the pairs of labels satisfying a certain condition. This algorithm can be represented as a merging tree in which all nodes are lists of labels (resp. phase vectors).

On the classical side, Kuperberg's algorithm is thus similar to Wagner's generalized birthday algorithm [START_REF] Wagner | A generalized birthday problem[END_REF], which is a binary merging tree of depth √ n. In Wagner's algorithm, the goal is to impose stronger conditions at each level which culminate in a full-zero sum. Here, the same conditions are imposed on the labels in the phase vectors. A success in the list-merging routine is equivalent to a success in the collimation routine (we obtain a phase vector with the wanted label).

The query, time and memory complexities depend on the shape of the tree. Even though the conditions are actually chosen at random at the measurement step in Algorithm 1, we can consider them chosen at random before the combination to analyze the algorithm.

Example: Optimal Time. The optimal time complexity is obtained with a tree with √ 2n levels. It starts with lists of size 2, i.e., two-labeled phase vectors. At level i starting from the leaves, the lists have (expected) size 2 i , and they are merged pairwise into a list of size 2 i+1 . This means that we can eliminate 2i -(i + 1) = i -1 bits. So we should use h levels, where:

1 + . . . + h -1 = n =⇒ h √ 2n .
Since each level of merging doubles the number of lists, there are in total 2 √ 2n leaves (hence queries). The (classical) cost of merging, over the whole tree, is equal to the sum of all list sizes. It is also the (quantum) cost of the relabeling

operations: i 2 √ 2n-i × 2 i = O √ 2n2 √ 2n .
To compute the memory complexity, one must note that it is not required to store whole levels of the merging tree. Instead, we compute the lists (resp. the phase vectors) depth-first, and store only one node of each level at most, i.e. √ 2n phase vectors. For the same reason, the classical memory complexity is

O 2 √ 2n .
Precise Analysis. The analysis above is only performed on average, and in practice, there is a significant variance in the list sizes. More precise analyses were performed in [START_REF] Peikert | He gives c-sieves on the csidh[END_REF][START_REF] Chávez-Saab | The SQALE of CSIDH: sublinear vélu quantum-resistant isogeny action with low exponents[END_REF]. It follows from them that the list size after merging should be considered smaller than the expected one by an "adjusting factor" 3/(2π). Furthermore, the combination may create lists that are too large, which must be discarded. The empirical analysis of Peikert [START_REF] Peikert | He gives c-sieves on the csidh[END_REF] gives a factor (1 -δ) of loss at each level, with δ = 0.02.

The smaller factor in list sizes simply means that at level i, we will not exactly eliminate i -1 bits, but i -c where c = log 2 1 +

3 2π
0.76. (We can control the interval size in Algorithm 1 very precisely.) Thus h is solution to:

h i=1 (i -c) = n =⇒ h 2 2 -ch = n =⇒ h c + 2n + 4c 2 .
Finally, the loss at each level induces a global multiplicative factor (1-δ) -h = 2 -log 2 (1-δ)h 2 0.029h on the complexity. Therefore, accounting for the adjusting factor and discards, the query complexity of the sieve is:

2 1.029(0.76+ √ 2n+2.30) (1)
and the quantum time complexity multiplies this by a factor 0.76 + √ 2n + 2.30. The difference with the exact 2 √ 2n is not negligible, but not large either. At n = 4608, the two exponents are respectively 99.6 and 96.

Obtaining All the Bits of the Solution. The analysis above applies if we want to obtain a specific label, e.g., the label 1. Afterwards, the algorithm can be repeated n times. For a generic N (not a power of 2), one typically produces all labels which are powers of 2 and uses a QFT to directly recover the secret. This is done for example in [START_REF] Bonnetain | Quantum security analysis of CSIDH[END_REF]. Peikert [START_REF] Peikert | He gives c-sieves on the csidh[END_REF] proposed a more advanced method to recover multiple bits of the secret with each phase vector.

Lemma 1. Let α > 0 and n be a positive integer. We have

n i=1 2 α √ i = O √ n2 α √ n .
Proof. When i is a perfect square, let say i = j 2 , we have that 2 α √ i = 2 αj . Now for any i between the two perfect squares (j -1) 2 and j 2 , we have the upper bound 2 α √ i < 2 αj . In order to use this, we rewrite the sum:

n i=1 2 α √ i ≤ √ n -1 j=0 (j+1) 2 k=j 2 +1 2 α √ k ≤ √ n -1 j=0 (j+1) 2 k=j 2 +1 2 α(j+1) = √ n -1 j=0 (2j + 1)2 α(j+1)
Using the formula for geometric series, we obtain:

n i=1 2 α √ i ≤ 2 α+1 (2 α -1) √ n 2 α √ n -2 α (2 α √ n -1) (2 α -1) 2 + 2 α 2 α √ n -1 2 α -1 = 2 α 2 α -1 (2 √ n + 1)2 α √ n - 2 α+1 2 α -1 (2 α √ n -1) -1 ≤ 2 α 2 α -1 (2 √ n + 1)2 α √ n .
which allows us to conclude the proof, α being fixed.

Obtaining Partially Collimated Labels. In this paper, we will consider the task of obtaining labels which, instead of reaching a prescribed k, match k on a certain number of bits only (we can say that the phase vectors are partially collimated ), let say i: this complexity is of order 2 √ 2i . By Lemma 1, we can obtain a sequence of i phase vectors collimated on 1, . . . , i bits with a query complexity:

i j=1 2 √ 2j = O √ i2 √ 2i .

The Subset-Sum Problem

As we will see in Section 3, the DCP can be reduced to the Subset-sum problem; this leads to the most query-efficient algorithms, and depending on the cost of queries, to the best optimization for some instances.

Definition 3 (Subset-sum). A subset-sum instance is given by (v, k), v ∈ Z N , k ∈ Z m N for some modulus N and integer m. The problem is to find a vector (or all vectors) b ∈ {0, 1} m such that b, k = v mod N .

When m n = log 2 N , there is one solution on average. The instance is said to be of density one. Heuristic classical and quantum algorithms based on the representation technique [START_REF] Howgrave-Graham | New generic algorithms for hard knapsacks[END_REF][START_REF] Becker | Improved generic algorithms for hard knapsacks[END_REF] allow to solve it in exponential time in n.

In the following, we will use these algorithms as black boxes. We first need a classical subset-sum solver.

Fact 1. We have a classical algorithm S C which, on input a subset-sum instance (v, k) of density one, finds all solutions. It has a time complexity in Õ (2 c cSS n ) where c cSS < 1.

Here, the parameter c cSS is the best asymptotic exponent that we can obtain for classical subset-sum algorithms. If there are no constraints on the memory, we can take c cSS = 0.283 which is the best value known at the moment [START_REF] Bonnetain | Improved classical and quantum algorithms for subset-sum[END_REF].

In this paper, we will also need (quantum) algorithms solving a more difficult problem, in which k is fixed, but the target v is in superposition. We will call this type of algorithm a quantum subset-sum solver.

Fact 2. We have a quantum algorithm S Q which has a complexity cost in Õ (2 c qSS n ) (where c qSS < 1), which, given an error bound ε, given a known (classical) k ∈ Z m N and on input a quantum v, maps:

|v |b → |v b ⊕ S Q (v)
where, for a proportion at least 1 -ε of all v admitting a solution, S Q (v) is selected u.a.r. from the solutions to the subset-sum problem, i.e., from the set {b| b, k = v}.

Notice that in the way we implement the solver, we can only guarantee that it succeeds on a large proportion of inputs (there remains some probability of error). However, it depends on some precomputations that we can redo, to obtain a heuristically independent solver which allows to reduce ε and / or to ensure that we get more solutions.

Though we could implement the function S Q by running an available classical (or quantum) subset-sum algorithm, it would then require exponential amounts of qubits. Using only poly(n) qubits, we know for sure that c qSS ≤ 0.5, because we can use Grover's algorithm to exhaustively search for a solution b. This search uses poly(n) qubits only. In Section 5, we will show that we can reach smaller values for c qSS , which differ depending on whether we allow QRACM or not.

Reducing DCP to a Subset-sum Problem

Recall that we note n = log 2 N , where N is not necessarily a power of 2. We will focus in this section on two algorithms to solve the DCP: the first one (from Regev [START_REF] Regev | A subexponential time algorithm for the dihedral hidden subgroup problem with polynomial space[END_REF]) uses a classical subset-sum solver and the other (ours) uses a quantum one.

Using a Classical Subset-sum Solver

By reducing Regev's algorithm to a single level, as described in [START_REF] Bonnetain | Quantum security analysis of CSIDH[END_REF], we can directly produce lsb(s) from n phase vectors. This is detailed in Algorithm 2.

It can be proven that in Step 4, the number of solutions is quite small but generally enough for our purpose. In Step 5, the solution vectors we want to project our superposition on are marked in an ancillary register which is then measured. Either we will get what we want, or we will end up with a superposition of the solution vectors that were not marked, in which case we start the process again with two other solution vectors. For more details, we refer to the extensive study of Regev's algorithm by Childs, Jao and Soukharev [START_REF] Childs | Constructing elliptic curve isogenies in quantum subexponential time[END_REF].

The following lemma gives us the complexity of Algorithm 2, derived from Regev's algorithm.

Lemma 2 (Subsection 3.3 [9]

). There exists an algorithm which finds lsb(s) with O (n) queries and quantum time and space. It has the same usage in classical time and space as the subset-sum solver S C . Algorithm 2 finds one bit of the secret. In order to retrieve the whole secret, we will have to repeat this procedure n times. Thus, we get an algorithm using a quadratic number of calls to the oracle, exponential classical time and space because of the subset-sum solver, linear quantum space and quadratic quantum time.

It turns out that we could solve the classical subset-sum problem on the side with a quantum computer, leading to some tradeoffs described in [START_REF] Bonnetain | Improved low-qubit hidden shift algorithms[END_REF]. But we show hereafter that we can also build an algorithm which directly uses a quantum subset-sum solver instead of having to measure the ancillary register to get a classical instance of a subset-sum problem.

Using a Quantum Subset-sum Solver

The main observation that led to the design of the algorithm we introduce hereafter is that on one hand, we would like to build the superposition

1 √ N j∈Z N ω sj N |j (2)
since applying the inverse QFT on Z N on it would directly give the secret s, and on the other hand, we know that it would be possible, thanks to a quantum subset-sum solver, to prepare the state

1 Z(k) b∈F m 2 ω s b,k N | b, k mod N (3)
where Z(k) is a normalizing constant depending on k. Indeed, preparing this state is done by using Regev's trick (see [START_REF] Regev | Quantum computation and lattice problems[END_REF][START_REF] Stehlé | Efficient public key encryption based on ideal lattices[END_REF]), i.e., (i) by tensoring m phase vectors

1 √ M b∈F m 2 ω s b,k N |b |0 n ,
(ii) then computing the subset-sum in the second register to get the entangled state

1 √ M b∈F m 2 ω s b,k N |b | b, k mod N ,
(iii) and finally disentangle it thanks to a quantum subset-sum algorithm which from b, k mod N and k (which is classical) recovers b and subtracts it from the first register to get the state we want.

As one can see, if we could take m = n and have an isomorphism between the vectors b and the knapsack sums b, k mod N , the prepared state (3) would be exactly the superposition (2).

Algorithm 3 Ideal algorithm

1 √ N j∈Z N   1 Z(k) b∈F m 2 ω (s-j) b,k N   |0m |j 5:
Measure the state and output the resulting j.

However, there would be many cases in which multiple solutions to the subsetsum problem exist. Thus we take m < n and define M def = 2 m < N . This is different from Algorithm 2, where such collisions are needed. We obtain Algorithm 3, which uses Regev's trick with a quantum subset-sum solver in Step 3.

Despite M being smaller than N , some cases still yield multiple solutions, and furthermore the subset-sum solver (as given by Fact 2) fails on some instances. This is why we distinguish between Algorithm 3 in which we consider the quantum subset-sum solver to be ideal (i.e., it finds back b from b, k and k with certainty), and the algorithm that we actually build in practice: Algorithm 4.

The analysis of Algorithm 4 is related to the set of b on which the quantum subset-sum solver succeeds: S Q ( b, k ) = b for a fixed k.

G (k) def = {b ∈ F m 2 : S Q ( b, k ) = b}
and let G(k) be the size of the set G (k).

We apply in Step 4 a measurement in order to disentangle the superposition we have, so we can apply an inverse QFT in the same natural way as in the ideal algorithm. We show that the probability of success of the measurement (i.e., of Algorithm 4 Finding s using a quantum subset-sum solver S Q Require: A parameter m < n and phase vectors |ψ k i for i ∈ [ [1, m]]. Ensure: An element j ∈ ZN .

1: Tensor the phase vectors and append a register on ZN m i=1

|ψ k i |0n = 1 √ M b∈F m 2 ω s b,k N |b |0n
2: Compute the inner product of b and k in the ancillary register

1 √ M b∈F m 2 ω s b,k N |b | b, k mod N 3: Apply S Q to uncompute b 1 √ M b∈F m 2 ω s b,k N b ⊕ S Q ( b, k ) | b, k mod N 4:
Measure the first register. If the result is not 0m, abort and restart with new coset states. Otherwise, we obtain

1 G(k) b∈G ω s b,k N |0m | b, k mod N 5:
Apply the inverse QFT on ZN on the second register

1 √ N j∈Z N 1 G(k) b∈G ω (s-j) b,k N |0m |j
6: Measure the state and output the resulting j.

measuring 0) is good enough for our purpose when taking m close to n. We also prove under the same assumption that the algorithm outputs the secret with good probability. All in all, these two properties lead to our main result.

Theorem 4. There exists an algorithm which finds s using O (n) queries and the same usage in time and space as the subset-sum solver S Q .

In order to analyze Algorithm 4 and prove Theorem 4, we will proceed in two steps.

Step 1. The first step is to give a lower bound on E k [G(k)]. This lower bound is given by estimating the number of vectors which admit more than one possible solution.

To arrive here, we first take a look at the normalization constant Z(k) and we compute E k [Z(k)] (the average over all choices of k). This can be done by simply looking at the measurement step in Algorithm 3.

Lemma 3. We have

E k [Z(k)] = M 1 + M -1 N . Proof. Fix k = (k 1 , • • • , k m )
. For all j ∈ Z N , the measurement in Algorithm 3 returns j with probability:

P ideal [j|k] = 1 N Z(k) b∈F m 2 ω (s-j) b,k N 2 = 1 N Z(k) m i=1 1 + ω (s-j)ki N 2 = 1 N Z(k) m i=1 1 + ω (s-j)ki N 2 = 1 N Z(k) m i=1 4 cos 2 πk i s -j N = M 2 N Z(k) m i=1 cos 2 πk i s -j N .
Furthermore, we have j∈Z N P ideal [j|k] = 1, so we can write:

Z(k) = M 2 N j∈Z N m i=1 cos 2 πk i s -j N (4)
It follows that

E k [Z(k)] = M 2 N j∈Z N E m i=1 cos 2 πk i s -j N
and since the k i are i.i.d., we have

E k [Z(k)] = M 2 N   1 + j∈Z N \{s} m i=1 E cos 2 πk i s -j N   = M 2 N 1 + (N -1) m i=1 1 2 = M N (N + M -1) .
Next, we give a relation between G(k) and Z(k).

Lemma 4. For any k:

G(k) ≥ (1 -ε) (2M -Z(k)) .
Proof. Fix k. Let B(j) be the set of vectors whose knapsack sum is j:

B(j) def = {b ∈ F m 2 | b, k = j mod N }
and let C i be the set of vectors b that have i collisions:

C i def = {b ∈ F m 2 | #B( b, k ) = i}.
We denote by C i the size of the set C i .

If we take a closer look at Z(k), we have that

Z(k) = j∈Z N b∈B(j) ω s b,k N 2 = j∈Z N ω sj N 2 b∈B(j) 1 2 = j∈Z N b∈B(j) b ∈B(j) 1 = j∈Z N b∈B(j) b ∈B( b,k ) 1 = j∈Z N b∈B(j) #B( b, k ) = b∈F m 2 #B( b, k ) = i≥1 b∈F m 2 : #B( b,k )=i i = i≥1 iC i
Letting C >1 be the number of vectors b with at least one collision (i.e., for which there exists b = b such that they have the same knapsack sum), we have

C >1 = i>1 C i . From Z(k) = i≥1 iC i = C 1 + 2 i≥2 C i + i≥3 (i -2)C i ,
it follows that we have the lower bound:

Z(k) ≥ C 1 + 2C >1 .
Injecting twice the equation C 1 = M -C >1 in this inequality and using the trivial bound G(k) ≥ (1 -ε)C 1 , we conclude the proof.

From Lemma 3 and 4, we immediately deduce:

Lemma 5. E k [G(k)] ≥ (1 -ε)M 1 - M -1 N .
Step 2. The second step in our proof computes the probability of success of the "real" algorithm by relating it to

E k [G(k)].
Lemma 6. Algorithm 4 outputs the secret s with probability

≥ (1-ε) M (N -M +1) N 2 .
Proof. We compute the probability of measuring j ∈ Z N at the end of Algorithm 4. In particular, we have for s

P real [s|k] = 1 N G(k) b∈G ω 0 N 2 = G(k) N We have by Lemma 5 that E [G(k)] ≥ (1 -ε)M 1 -M -1 N
. We finish the proof by observing that

P real [s] = E [P real [s|k]] ≥ (1 -ε) M (N -M +1) N 2 .
Finally, we can prove Theorem 4.

Proof.

Step 4 of Algorithm 4 succeeds with average probability Lemma 5). The final measurement of the algorithm outputs the secret with probability

E[G(k)] M which is greater than (1 -ε) N -M +1 N (by
≥ (1 -ε) M (N -M +1) N 2
(by Lemma 6). We will thus have to repeat the algorithm an expected number smaller than

N 3 (1-ε) 2 M (N -M +1) 2 times
. By letting m be equal to n -1, we obtain that the algorithm will have to be repeated less than 8/(1 -ε) 2 times. Thus, we can conclude that our algorithm needs O (n) queries and has complexity costs identical to the ones of the subset-sum solver, since the subset-sum resolution is the only exponential step of the algorithm.

Interpolation algorithm

If we take a look at the ideal algorithm and consider that there is no collision, we can see that we would like 2 m to be as close to N as possible in order for the sum

1 √ M b∈F m 2 ω (s-j) b,k N
to contain as many as possible elements of the sum

1 √ N b∈F n 2 ω (s-j) b,k N .
In the mean time, it is clear that the closest M gets to N , the more likely collisions b 1 , k = b 2 , k for b 1 = b 2 become. We thus have to find a compromise on the value m or more interestingly play with the values k i used in the algorithm, to avoid collisions and to simplify the resolution of the subset-sum problem.

In fact, we can reduce the size of the subset-sum problem we have to solve by pre-processing the states to get values of k i that will allow us to solve the subsetsum problem on some bits by Gaussian elimination. Constructing these k i 's can be achieved by Kuperberg's second algorithm (or any improvement). Given a threshold parameter t ∈ [ [1, m]], we can consider the following configuration for the k i to use as inputs in Algorithm 4 (dots represent unknown bits and the i-th bit of the j-th row is the j-th bit of the binary expansion of k i ):

             1 2 • • • m -t m -t + 1 • • • n k 1 1 • • • • • • • • • • k 2 0 1 . . . • • • • • • . . . . . . . . . . . . . . . . . . • • • • k m-t 0 0 • • • 1 • • • • • k m-t+1 0 0 • • • 0 • • • • • . . . . . . . . . . . . . . . • • • • k m 0 0 • • • 0 • • • • •              (5)
In Algorithm 4, it turns out that we can keep a good probability of finding the secret s by letting m be equal to n -1 so that is what we will assume afterwards.

To build phase vectors that satisfy the configuration in ( 5), we will approximately have to query the oracle

n-t i=1 2 √ c DCP i + t2 √ c DCP (n-t)
leading to a query and time complexities of

O ( √ n -t + t)2 √ c DCP (n-t)
(by Lemma 1), where c DCP is the constant of the algorithm used to construct the states (c DCP = 2 for Kuperberg's second algorithm). For the subset-sum problem, solving it on the first n -t bits is easy (thanks to a Gaussian elimination), the difficulty comes from the last t bits, leading to a complexity in O (2 c qSS t ) time, where c qSS is the complexity exponent of the quantum subset-sum solver. This parameter t can be used in a natural way to obtain an interpolation algorithm, since it allows to obtain a tradeoff between the preparation of the states and the resolution of the problem (which amounts to solving a quantum subset-sum problem).

We can now give an interpolation algorithm derived from Algorithm 4. We note that letting q be the query complexity exponent, it is possible to determine t from n and the value q we can afford. Using Kuperberg's second algorithm (or any improvement) to compute suitable phase vectors as described before and then giving them as inputs to Algorithm 4, we can retrieve the secret s as described by Algorithm 5 with the complexities given by Section 5.

Algorithm 5 Interpolation algorithm (using a quantum SS solver)

Require: q such that 2 q is the number of queries we are allowed to do. Ensure: The secret s.

1: Use Kuperberg's second algorithm (or any improvement) to create states |ψ k i for i ∈ [ [1, m]] satisfying the configuration represented by Matrix [START_REF] Bernstein | Quantum algorithms for the subset-sum problem[END_REF], where t ≈ q c SS . 2: Apply Algorithm 4 on these m states to obtain a value j ∈ ZN . 3: Check if j is the secret. If not, return to Step 1. Otherwise, output j.

Theorem 5. Let t ∈ [[1, m]]. Algorithm 5 finds s with O ( √ n -t + t)2 √ c DCP (n-t) queries in O ( √ n -t + t)2 √ c DCP (n-t) + 2 c qSS t quantum time, classical space O 2
√ c DCP (n-t) + 2 c qSS t and O (poly(n)) quantum space.

We notice that when t = m, the k i are kept random and we have to solve the "full rank" subset-sum, matching with Algorithm 4. On the other side, when t = 1, we fall back on Kuperberg's second algorithm since we have in this case to construct a collection of states divisible by all the successive powers of 2, see Section 2.3. Finally, when 1 < t < m, we have new algorithms working for any number of queries between O (n) and Õ 2 √ c DCP n .

5 Quantum Subset-sum Algorithms

In this section, we consider quantum algorithms solving the quantum subset-sum problem introduced in Section 2.4. We give both asymptotic complexities and numerical estimates.

Recall that we consider a subset-sum instance (v, k), k ∈ Z m N , where v is in superposition, and k will remain fixed. The problem is to find b such that b, k = v mod N for a given (fixed) modulus N . For a given v, if there are many solutions, we want to find one selected uniformly at random (under heuristics). If we want all solutions, then we can run multiple instances of the solver (we will have to redo the pre-computations that we define below). A given solver, defined for a specific k, is expected to work only for some (large) proportion 1 -ε of v. We can check whether the output is a solution or not and measure the obtained bit to collapse on the cases of success.

Algorithms Based on Representations

The best algorithms to solve the subset-sum problem with density one are listmerging algorithms using the representation technique [START_REF] Howgrave-Graham | New generic algorithms for hard knapsacks[END_REF][START_REF] Becker | Improved generic algorithms for hard knapsacks[END_REF]. The best asymptotic complexities (both classical and quantum) are given in [START_REF] Bonnetain | Improved classical and quantum algorithms for subset-sum[END_REF]. We detail the representation framework following the depiction given in [START_REF] Bonnetain | Improved classical and quantum algorithms for subset-sum[END_REF]. To ease the description, we start with the case v = 0, i.e., the homogeneous case, and we will show below how to extend it easily to v = 0.

Guessed Weight. We assume that the solution b is of weight m/2 . This is true only with probability: p m := 2 -m m m/2 = 1/poly(m). If not, we re-randomize the subset-sum instance by multiplying b by a random invertible matrix. Thus if we manage to solve an instance of weight m/2 , the total complexity to solve any instance will introduce a multiplicative factor 1 pm that we will have to estimate.

Distributions. We consider distributions of vectors having certain relative weights:

D m [α] ⊆ {0, 1} m is
1 ∈ D m [α 1 ], b 2 ∈ D m [α 2 ] and α 1 + α 2 = 1 2 .
In this paper, we consider only representations with coefficients 0 or 1. Extended representations can be considered, using more coefficients (which have to cancel out each other). However, the advantage of using extended representations becomes quickly insignificant in practice. It is also harder to compute the number of representations, or the filtering probabilities that we define below.

Lemma 9 (Lemma 4 in [START_REF] Bonnetain | Improved classical and quantum algorithms for subset-sum[END_REF]). Let L 2 be a sorted list stored in QRACM. Assume given a unitary U that produces, in time t L1 , a uniform superposition of elements of L 1 . Then there exists a unitary U that produces a uniform superposition of elements of L, in time O

t L 1 √ pf(α1,α2) max( 2 cm /|L 2 |, 1) .
Since the goal is only to sample u.a.r. from the root list, only half of the lists in the tree need actually to be stored in QRACM. The others are sampled using the unitary operators given by Lemma 9. In short, the obtained subsetsum algorithm is a sequence of Grover searches which use existing lists stored in memory to sample elements in new lists with more constraints.

Heuristics. The standard subset-sum heuristic assumes that the elements of all lists in the tree (not only the leaf lists) behave as if they were uniformly sampled from the set of vectors of right weight, satisfying the modular condition. This heuristic ensures that the list sizes are very close to their average: for each L obtained by merging and filtering L 1 [ 1 , α 1 , c 1 ] and L 2 [ 2 , α 2 , c 2 ], we have:

|L| |L 1 ||L 2 | 2 m(c-min(c1,c2)) PF(α 1 , α 2 , m) ,
where the approximation is exact down to a factor 2. This is true with overwhelming probability for all lists of large expected size via Chernoff-Hoeffding bounds, and even if the root list is of expected size 1, the probability that it actually ends up empty is smaller than e -0.5 0.61.

From Asymptotic to Exact Optimizations

As the time and memory complexities of a subset-sum algorithm are determined by its merging tree, we seek to select a tree which minimizes these parameters. Given a certain subset-sum problem, we first select a tree shape. As an example, the best subset-sum algorithm with low qubits (using QRACM) is the "quantum HGJ" algorithm of [START_REF] Bonnetain | Improved classical and quantum algorithms for subset-sum[END_REF], whose structure is reproduced in Figure 1. At level 3, it splits the vectors into two halves, and merges without filtering. While all lists are obtained via quantum merging/filtering, the main computation is performed after obtaining L 3 1 , L 2 1 , L 1 1 , where the main branch is explored using Grover's algorithm: we search through the lists L 3 0 , L 2 0 L 1 0 without representing them in memory. The quadratic speedup of Grover search makes the tree unbalanced, which is reflected on the naming of its parameters in Figure 1.

The asymptotic time complexity of the algorithms has the form Õ 2 βm , and is the result of summing together the costs of all merging steps. Through the approximation of binomial coefficients, the list sizes are approximated in log 2 and relatively to m. The parameters (relative weights, modular conditions and sizes) are numerically optimized. The optimization of Figure 1 in [START_REF] Bonnetain | Improved classical and quantum algorithms for subset-sum[END_REF] yields the complexity Õ 2 0.2356m .

In this paper, we also perform non-asymptotic optimizations for a given m. Since we use only {0, 1}-representations, the filtering probability is well known and has a simple expression (Lemma 7). Since the binomial coefficients can be extended as functions of R 2 , we can perform an exact numerical optimization of list sizes for a given m. Afterwards, the numbers obtained are rounded, in particular the weights of representations, and we take the point which gives us the best results: smallest complexity and biggest average size for L 0 .

L 0 L 1 1 with condition c 1
Example. Let us take n = log 2 N = 256, m = n -1 = 255, and the structure of Figure 1. We adapt the optimization code of [START_REF] Bonnetain | Improved classical and quantum algorithms for subset-sum[END_REF] by taking the exact exponents (not relative to n) and optimize numerically under the constraint |L 0 | = 2 2 (to ensure that there are solutions). The asymptotic formula would give 2 0.2356n 2 60. 31 . Numerical optimization gives us a time 2 63.81 , but this admits non-integer parameters and it is only the maximum between all steps. By rounding the parameters well, we obtain Figure 2.

To compute the quantum time complexity, we consider the list sizes to be exact and use the formula of Lemma 9 without the O. The subtrees on the right can be computed in 2 65.71 operations; the slight increase is due to the fact that we take a sum of their respective terms and not a maximum. In the left branch, we sample from L 0 in 2 63.48 operations.

The actual time complexity is slightly bigger, due to the variation in list sizes, and the constant complexity overhead (π/2) of Grover search. More importantly, these operations require: • to recompute a sum, using m (controlled) additions modulo N ; • to test membership in some distribution; • to sample from input distributions D n . The latter can be done using a circuit given in [START_REF] Esser | An optimized quantum implementation of ISD on scalable quantum resources[END_REF], which for a weight k and n bits, has a gate count Õ (nk) and uses n + 2 log(k + 1) qubits. All of this boils down to m arithmetic operations or O m 2 quantum gates.

Finally, this sampler works only for a proportion 1 pm = 2 -5.33 of subset-sum instances, so we need to re-randomize accordingly. After running the optimization for 128 ≤ m ≤ 1024 and n = m + 1, we found that the subset-sum solver would use approximately 2 0.238m+9.203 arithmetic operations, for a final list L 0

2 √ 2 log

 22 space of O (polylog N ) and Õ N queries, which is the state of the art so far.

of size 5 :

 5 Quantum: Apply to the state a transformation that maps the pairs (i, j) to [[0, -1]]. 6: Return the state and the vector of corresponding labels ki + k j .

Algorithm 2 1 : 2 : 4 : 6 :s b 1 7 :

 2124617 Finding lsb(s) using a classical subset-sum solver S C Require: |ψ k 1 , . . . , |ψ kn with k def = (k1 . . . kn) ∈ Z n N . Ensure: lsb(s). Tensor the phase vectors and append a register on F n-1 Compute the inner product of b and k in the ancillary register Search for vectors b i such that b i , k = z mod 2 n-1 using S C 5: Project the superposition onto a pair of solutions, e.g., (b1, b2) Relabel the basis states to (|0 , |1 ), resulting in ω Apply a Hadamard gate on the qubit, measure it and output the result.

1 :|ψ k i |0n = 1 √ M b∈F m 2 ω s b,k N |b |0n 2 : 1 √ M b∈F m 2 ω 3 : 2 ω

 11221232 Require: A parameter m < n and phase vectors |ψ k i for i ∈ [[1, m]]. Ensure: An element j ∈ ZN . Tensor the m phase vectors and append a register on ZN m i=1 Compute the inner product of b and k in the ancillary register s b,k N |b | b, k mod N Uncompute b thanks to k and | b, k mod N 1 Z(k) b∈F m s b,k N |0m | b, k mod N 4: Apply the inverse QFT on ZN on the second register

Notation 3 .

 3 Let us denote by G (k) the set of b's that are correctly found back by S Q for a given k:

  the set of vectors having weight αm. The basic idea of representations is to write the solution b as a sum of vectors of smaller relative weights, e.g., b = b 1 + b 2 where b

Fig. 1 .

 1 Fig. 1. Quantum HGJ algorithm. Dotted lists are search spaces (they are not stored). Bold lists are stored in QRACM. The first level uses a left-right split of vectors, without filtering.

Table 1 .

 1 Costs of algorithms for finding the whole secret s.

	Algorithm		Queries	Classical Time	Quantum Time	Classical Space
	Kuperberg II	√	2n + 1 2 log n + 3	√	2n + 1 2 log n + 3	√ 2n + 1 2 log n + 3	√	2n
	Regev		2 log n + 3		0.283n	2 log n + 3	0.283n
	Ettinger-Hoyer		log n + 6.5		n	log n + 6.5	log n
	Alg. 4 w/ QRACM Alg. 4 w/o QRACM		log n + 3 log n + 3		0.238n + 12 < 0.2324n	0.238n + 3 2 log n + 12 0.418n + 3 2 log n + 15.5 < 0.2324n 0.238n

Table 2 .

 2 Complexity exponents for some parameters of CSIDH. The quantum space is polynomial in n.

		Algorithm	Queries	Classical Time	Quantum Time	Classical Space
	CSIDH-512	Regev	15	80	15	73
	(n = 256)	Alg. 4 w/ QRACM	11	73	85	61
	CSIDH-1024	Regev	17	153	17	145
	(n = 512)	Alg. 4 w/ QRACM	12	134	148	122
	CSIDH-1792	Regev	18	262	18	254
	(n = 896)	Alg. 4 w/ QRACM	13	226	240	214
	CSIDH-3072	Regev	19	443	19	435
	(n = 1536)	Alg. 4 w/ QRACM	14	378	394	366
	CSIDH-4096	Regev	20	589	20	580
	(n = 2048)	Alg. 4 w/ QRACM	14	500	516	488

Acknowledgments. This work has been partially supported by the French Agence Nationale de la Recherche through the France 2030 program under grant agreement No. ANR-22-PETQ-0008 PQ-TLS.

Merging Tree. A subset-sum algorithm is defined by a merging tree. A node in this tree is a list L[ , α, c], which represents a set of vectors drawn from {0, 1} m under several conditions: 1. the size of the list is 2 m ; 2. the vectors are sampled u.a.r. from a prescribed distribution D m [α]; 3. the vectors satisfy a modular condition of cm bits. With v = 0, the following condition can be used: e, k mod N ∈ [-N/2 cm ; N/2 cm ] for some number c. More generally, the modular conditions can be chosen arbitrarily, as long as they remain compatible with the target v.

Once the tree structure is chosen, its parameters are optimized under several constraints. First, the lists have a certain maximal size. A distribution D m [α] has size m αm , which is asymptotically estimated as

is the Hamming entropy. This creates the constraint ≤ h(α) -c. Second, we expect the root list to contain the solution of the problem, i.e., = 0 (one element), α = 1 2 and c = 1. Finally, each non-leaf list L has its parameters determined by its two children L 1 , L 2 . Indeed, it is obtained via the merging-filtering operation which selects, among all pairs of vectors (e 1 , e 2 ) ∈ L 1 × L 2 , the pairs such that: e 1 + e 2 satisfies the modular condition (merging) and satisfies the weight condition (filtering). The parameters are:

Here, pf is the probability that two vectors chosen u.a.r. in their respective distributions will not have colliding 1s.

Lemma 7 (Lemma 1 in [START_REF] Bonnetain | Improved classical and quantum algorithms for subset-sum[END_REF]). Let e 1 , e 2 be drawn u.a.r. from

where pf(α

Classical Computation of the Tree. To any correctly parameterized merging tree corresponds a classical subset-sum algorithm that runs as follows: it creates the leaf lists by sampling their distributions at random. It then builds the parent lists by merging-filtering steps. The merging operation is efficient, since elements can be ordered according to the modular condition to be satisfied.

Lemma 8 (Lemma 2 in [START_REF] Bonnetain | Improved classical and quantum algorithms for subset-sum[END_REF]). Let L 1 , L 2 be two sorted lists stored in classical memory with random access. In log 2 , relatively to m, the parent list L can be built in time:

Quantum Computation of the Tree. While the more advanced quantum subsetsum algorithms use quantum walks [START_REF] Bernstein | Quantum algorithms for the subset-sum problem[END_REF][START_REF] Helm | Subset sum quantumly in 1.17 n[END_REF][START_REF] Bonnetain | Improved classical and quantum algorithms for subset-sum[END_REF], we want to focus here on algorithms using few qubits, which at the moment, rely only on quantum merging with Grover search. They replace the classical merging operation by the following. of size 2 on average. Under the subset-sum heuristic, we assume an independence between all tuples of elements in the initial lists. Using Chernoff-Hoeffding bounds the probability that the final list is empty is smaller than e -1 0.37. To reduce it to a smaller constant ε, we may simply run multiple independent instances of the solver. This increases the asymptotic complexity by a factor O (-log ε).

Solving Subset-Sum in Superposition

We now show that we can reuse the structure of the QRACM-based subset-sum algorithm of Figure 1 to solve the problem in superposition over the target v, while still keeping the number of qubits polynomial.

The basic idea is to reduce the problem with a given v = 0 to v = 0: k , b = 0 mod N , where k is a length m + 1 vector where we append -v to k. We can then modify any existing tree-based subset-sum algorithm solving this instance to force all vectors in the leftmost leaf list to have a 1 in the last coordinate, and all vectors in the other leaves to have 0 in this coordinate. Then only the lists in the left branch of the tree depend on v. The complexity is unchanged.

Following the tree structure of Figure 1, we create the lists L 3 1 , L 2 1 , L 1 1 in a precomputation step. Then we define a quantum algorithm that outputs an element in L 0 (or a superposition of such elements), and we run this algorithm in superposition over v.

Subset-Sum without QRACM. Helm and May [START_REF] Helm | The power of few qubits and collisions -subset sum below grover's bound[END_REF] showed that quantum subsetsum algorithms using a small classical memory (without quantum access) can have better time-memory tradeoffs than classical ones. They obtained a time Õ 2 0.428m for a memory O 2 0.285m , however their algorithm does not have an unbalanced structure like ours. We improve on this time-memory tradeoff by adapting the tree of Figure 1 as follows: we remove L 3 0 and L 3 1 and their parameters, and directly sample in L 2 0 . Assuming that the lists L 2 1 and L 1 1 are precomputed classically, we sample from L 0 with the same algorithm, except that it replaces each QRACM access (in time 1) by a sequential memory access (in time |L The difference between asymptotic and non-asymptotic optimization is bigger here. For m = n -1 = 127, with the constraint |L 0 | = 2 2 , we obtain a time 2 60.01 > 2 128×0.4165 = 2 53.31 and a memory 2 26.82 < 2 128×0.2324 = 2 29.75 . On top of this, we must also take p m into account.

After running optimizations for n = 128 to 1024, we obtained a count of about 2 0.418m+12.851 blocks of m arithmetic operations (m 2 quantum gates). The point at which the algorithm starts improving over Grover search lies around n = 157.


Julie J H Nati
email: julienati3@gmail.com

Felipe R Blasco

Charles Rodde

Alain Vergnet

François Allal

Marc Vandeputte

David J Mckenzie

In a marine teleost, the significance of oxygen supply for acute thermal tolerance depends upon the context and the endpoint used

Keywords: critical thermal maximum, fish, oxygen uptake, swimming

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Global warming will cause a rise in sea surface temperatures of up to 4°C by 2100, accompanied by increased frequency and severity of acute heat waves [START_REF] Frölicher | Marine heatwaves under global warming[END_REF] . Temperature has direct thermodynamic effects on the physiology of ectotherms, so there has been extensive research to investigate thermal tolerance limits in fishes, and the underlying mechanisms. The Fry paradigm and Oxygen and Capacity Limited Thermal Tolerance hypothesis (Fry-OCLTT) have been proposed as a universal principle underlying thermal tolerance in ectotherms [START_REF] Fry | The Effect of Environmental Factors on the Physiology of Fish[END_REF][START_REF] Pörtner | Oxygen-And capacity-limitation of thermal tolerance: A matrix for integrating climate-related stressor effects in marine ecosystems[END_REF].

According to the Fry-OCLTT, oxygen demands of metabolism are accelerated inexorably by warming until they exceed cardiorespiratory capacity for oxygen supply, causing functional collapse [START_REF] Eliason | Differences in thermal tolerance among sockeye salmon populations[END_REF][START_REF] Fry | The Effect of Environmental Factors on the Physiology of Fish[END_REF][START_REF] Pörtner | Oxygen-And capacity-limitation of thermal tolerance: A matrix for integrating climate-related stressor effects in marine ecosystems[END_REF][START_REF] Pörtner | Physiology and climate change[END_REF][START_REF] Schulte | The effects of temperature on aerobic metabolism: Towards a mechanistic understanding of the responses of ectotherms to a changing environment[END_REF]. Empirical evidence for the Fry-OCLTT paradigm is, however, mixed [START_REF] Farrell | Pragmatic perspective on aerobic scope: Peaking, plummeting, pejus and apportioning[END_REF][START_REF] Jutfelt | Oxygen-and capacity-limited thermal tolerance: blurring ecology and physiology[END_REF][START_REF] Lefevre | Are global warming and ocean acidification conspiring against marine ectotherms ? A meta-analysis of the respiratory effects of elevated temperature , high CO 2 and their interaction[END_REF][START_REF] Lefevre | The role of mechanistic physiology in investigating impacts of global warming on fishes[END_REF][START_REF] Pörtner | Climate impacts on organisms, ecosystems and human societies: integrating OCLTT into a wider context[END_REF].

There is particular uncertainty about the role of oxygen limitation in tolerance of acute warming in fishes. Acute thermal tolerance is typically measured with the critical thermal maximum (CTmax) protocol, where fish are warmed in steps until loss of equilibrium (LOE) [START_REF] Lutterschmidt | The critical thermal maximum: history and critique[END_REF]. The LOE at CTmax is an incipient lethal endpoint due to dysfunction of critical organs, brain and heart [START_REF] Andreassen | Brain dysfunction during warming is linked to oxygen limitation in larval zebrafish[END_REF][START_REF] Lefevre | The role of mechanistic physiology in investigating impacts of global warming on fishes[END_REF][START_REF] Rezende | Estimating the adaptive potential of critical thermal limits: methodological problems and evolutionary implications[END_REF]. In some fish species, environmental oxygen availability and/or blood oxygen carrying capacity have little or no effect on CTmax, indicating that LOE is not oxygen dependent [START_REF] Brijs | Experimental manipulations of tissue oxygen supply do not affect warming tolerance of European perch[END_REF][START_REF] Ern | Oxygen dependence of upper thermal limits in fishes[END_REF][START_REF] Mcarley | Fish and hyperoxia-From cardiorespiratory and biochemical adjustments to aquaculture and ecophysiology implications[END_REF]. In other species, measurements of rates of oxygen uptake (ṀO2) during a CTmax protocol found an initial exponential increase up to a maximum that was comparable to their maximum metabolic rate measured at initial acclimation temperature. This was then followed by a plateau and/or decline, which preceded LOE and which might indicate a limitation in capacity for tissue oxygen supply prior to the endpoint [START_REF] Mcarley | Chronic warm exposure impairs growth performance and reduces thermal safety margins in the common triplefin fish (Forsterygion lapillum)[END_REF][START_REF] Norin | Thermal biology and swimming performance of Atlantic cod ( Gadus morhua ) and haddock ( Melanogrammus aeglefinus )[END_REF]. The contrasting evidence indicates that LOE at CTmax may have many underlying mechanisms, which may or may not be linked to oxygen limitation, and which differ among species, methodology and context [START_REF] Andreassen | Brain dysfunction during warming is linked to oxygen limitation in larval zebrafish[END_REF][START_REF] Ern | Physiological mechanisms of acute upper thermal tolerance in fish[END_REF][START_REF] Lefevre | The role of mechanistic physiology in investigating impacts of global warming on fishes[END_REF][START_REF] Rezende | Tolerance landscapes in thermal ecology[END_REF].

In a study to investigate effects of acute temperature increases on cardiorespiratory performance of sockeye salmon (Oncorhynchus nerka), [START_REF] Steinhausen | The effect of acute temperature increases on the cardiorespiratory performance of resting and swimming sockeye salmon (Oncorhynchus nerka)[END_REF] warmed fish progressively while they swam aerobically in a swim tunnel. A number of salmon showed a gaittransition to an anaerobic swimming mode and then fatigued at warm temperatures, which the authors attributed to an inability to meet the combined oxygen demands of swimming plus warming [START_REF] Steinhausen | The effect of acute temperature increases on the cardiorespiratory performance of resting and swimming sockeye salmon (Oncorhynchus nerka)[END_REF]. [START_REF] Blasco | Using aerobic exercise to evaluate sub-lethal tolerance of acute warming in fishes[END_REF] proposed that a similar protocol could be used to evaluate acute thermal tolerance in fishes, warming in steps with fatigue as the endpoint. In two tropical freshwater teleosts exercising aerobically in a swim tunnel, progressive warming caused profound increases in ṀO2, to levels very significantly higher than the individuals' maximum metabolic rate during a critical swimming speed (Ucrit) test at their acclimation temperature. At a certain warm temperature, however, all individuals transitioned from a steady aerobic to an unsteady anaerobic gait and then fatigued, at temperatures significantly lower than their LOE at CTmax [START_REF] Blasco | Using aerobic exercise to evaluate sub-lethal tolerance of acute warming in fishes[END_REF]. Dubbed the critical thermal maximum for swimming (CTSmax) by [START_REF] Blasco | Tolerance of an acute warming challenge declines with body mass in Nile tilapia: evidence of a link to capacity for oxygen uptake[END_REF], the mechanism underlying fatigue would presumably be oxygen supply limitation, an inability to meet the combined oxygen demands of swimming plus warming [START_REF] Blasco | Using aerobic exercise to evaluate sub-lethal tolerance of acute warming in fishes[END_REF][START_REF] Blasco | Tolerance of an acute warming challenge declines with body mass in Nile tilapia: evidence of a link to capacity for oxygen uptake[END_REF][START_REF] Steinhausen | The effect of acute temperature increases on the cardiorespiratory performance of resting and swimming sockeye salmon (Oncorhynchus nerka)[END_REF].

Here, we investigated the general hypothesis that capacity for tissue oxygen supply can play a role in acute upper thermal tolerance in fishes, but that this depends upon the prevailing level of aerobic metabolic activity and consequent oxygen demand, and the tolerance endpoint used. We studied the European seabass Dicentrarchus labrax, a temperate marine teleost that has been the focus of investigations into the role of oxygen supply in defining CTmax (Anttila et al., 2023;[START_REF] Wang | Anaemia only causes a small reduction in the upper critical temperature of sea bass: is oxygen delivery the limiting factor for tolerance of acute warming in fishes?[END_REF]. We compared ṀO2 during a CTSmax and CTmax protocol in the same individuals, in particular the maximum ṀO2 achieved prior to each tolerance endpoint, fatigue or LOE. We reasoned that, if in the CTSmax protocol the seabass transitioned to unsteady anaerobic swimming at a certain warm temperature, and then fatigued, then capacity for tissue oxygen supply would underly this thermal tolerance endpoint in this species, as for the species studied by [START_REF] Blasco | Using aerobic exercise to evaluate sub-lethal tolerance of acute warming in fishes[END_REF]. We expected that LOE at CTmax would occur at a significantly higher temperature than fatigue at CTSmax, as observed previously [START_REF] Blasco | Using aerobic exercise to evaluate sub-lethal tolerance of acute warming in fishes[END_REF][START_REF] Blasco | Tolerance of an acute warming challenge declines with body mass in Nile tilapia: evidence of a link to capacity for oxygen uptake[END_REF]. We, however, investigated the specific hypothesis that maximum ṀO2 elicited by the CTmax would be significantly less than those in the CTSmax, indicating that the LOE endpoint was not caused by limitations in capacity for systemic tissue oxygen supply in this species [START_REF] Wang | Anaemia only causes a small reduction in the upper critical temperature of sea bass: is oxygen delivery the limiting factor for tolerance of acute warming in fishes?[END_REF].

Material and Methods

Juvenile seabass were obtained from a population at the Station Ifremer de Palavas-les-Flots (France), reared in seawater at 18 -19 °C and tagged (PIT, under benzocaine anaesthesia) for individual identification. Fish were held in a 1 m 3 tank supplied with biofiltered seawater at 18 °C for at least two weeks prior to experimentation, fed a maintenance ration with commercial pellets but fasted for 24 h before experiments. Prior to the main trials, a control was performed at 18 °C on six seabass of mean (± SE) mass 111.4 ± 9.1 g and forklength 202 ± 6 mm, which were swum at the speed of the CTSmax (2.5 BL s -1 ) for 8 h. For the CTSmax and CTmax, eight seabass were studied, of mean mass 74.2 ± 8.0 and forklength 181 ± 6 mm at the CTSmax, then mean mass 75.3 ± 8 g at the CTmax,.

Swimming trials were performed in a plexiglass Steffensen-type swim tunnel (volume 30 l) provided with biofiltered aerated seawater at 18 °C. Fish were measured for mass, width, height, and fork length, to calculate relative swimming speed in body length per second (BL s -1 ) corrected for solid blocking effect [START_REF] Bell | Water tunnel design for fisheries research[END_REF], then acclimated overnight at a low swimming speed of 1 BL s -1 . The next day, current speed was increased by 0.25 BL s -1 every 2 min until 2.5 BL s -1 . In the control trial, the fish then swam for 8h. In the CTSmax, after 30 min at 18 °C the temperature was increased by 1°C each 30 min until fish fatigued, resting their tails for at least 10 s against the rear grid. Fish were immediately removed from the tunnel into a tub of aerated seawater at 18°C for 30 min, then returned to their holding tank. CTSmax was calculated as the last temperature step fully completed plus the proportion of the ultimate step prior to fatigue [START_REF] Blasco | Using aerobic exercise to evaluate sub-lethal tolerance of acute warming in fishes[END_REF]. The experiments were performed over three weeks, with the last individual studied 24h before measurement of its CTmax (below).

The CTmax was performed in eight individual respirometry chambers (volume 3 l) that were supplied with aerated seawater at 19 °C, due to an overnight increase in the surface temperature of the local seawater supplying the facilities. Fish were acclimated to the chambers overnight then, the next morning, temperature was increased by 1°C every 30 min until LOE [START_REF] Mcarley | Chronic warm exposure impairs growth performance and reduces thermal safety margins in the common triplefin fish (Forsterygion lapillum)[END_REF][START_REF] Penney | Cardiorespiratory responses of seawater-acclimated adult Arctic char (Salvelinus alpinus) and Atlantic salmon (Salmo salar) to an acute temperature increase[END_REF]. Chambers were screened from view with an opaque plastic sheet containing a small observation hole, to monitor fish throughout. As soon as fish lost dorso-ventral equilibrium, they were removed and placed in aerated water at 19 °C for 30 min, then returned to their holding tank. CTmax was calculated as for CTSmax but using LOE as endpoint [START_REF] Blasco | Using aerobic exercise to evaluate sub-lethal tolerance of acute warming in fishes[END_REF].

The ṀO2 was measured in mgO2 kg -1 h -1 over the last 10 min of each temperature increment, in both protocols, by intermittent-flow respirometry [START_REF] Blasco | Using aerobic exercise to evaluate sub-lethal tolerance of acute warming in fishes[END_REF][START_REF] Steffensen | Some errors in respirometry of aquatic breathers: How to avoid and correct for them[END_REF]. ṀO2 was corrected for body mass with a scaling coefficient of b = 0.8 for metabolic rate in European seabass [START_REF] Rodde | An investigation of links between metabolic rate and feed efficiency in European sea bass Dicentrarchus labrax[END_REF]. The maximum ṀO2 achieved in each protocol was identified for each individual.

Absolute thermal scope for CTmax and CTSmax was calculated as maximum ṀO2 minus the relevant ṀO2 at 19°C. The proportional change in ṀO2 was calculated as a Q10 value over 19 -29°C.

A two-way ANOVA with repeated measures was used to evaluate effects of temperature on ṀO2, with one factor protocol (CTSmax versus CTmax), repeated factor the temperature increments, each fish as an individual, and an interaction term between protocol and temperature steps. Data were considered for a range of 19 to 30°C, which was measured on all individuals in both protocols.

An error function was included to correct for repeated tests on the same individual. Tukey post hoc tests, with Holm correction for multiple comparisons, were used to identify the temperature at which ṀO2 first increased significantly from the value at 19 °C, and to compare ṀO2 between protocols at each temperature. Single variables, such as CTSmax and CTmax, maximum ṀO2, thermal scope, and Q10 were compared by pairwise Welch t-tests. All statistical analyses were performed in R 4.0.2 within the lsmeans package (version 2.27-61), with significance accepted at p < 0.05.

Results

At a speed of 2.5 BL s -1 , the seabass swam with a sustained aerobic body-caudal swimming gait. In the control trial the seabass swam for 8h with no sign whatsoever of fatigue. During CTSmax, all individuals eventually transitioned in swimming gait, from an entirely steady aerobic gait with rhythmic beating of the tail, to increasing engagement of unsteady anaerobic 'burst-and-coast' episodes. This led to fatigue within less than one temperature increment (30 min). No fish lost equilibrium in the swimming trials. During CTmax, the fish exhibited erratic behaviour, rolling sideways, then complete loss of dorsoventral orientation. The mean CTSmax was 30.3 ± 0.4°C, significantly and almost 4°C lower than mean CTmax at 34.0 ± 0.4°C (Figure 1A).

In the control swim, ṀO2 remained stable for 8h (Figure S1, supplementary materials). caused There were marked increases in ṀO2 in both thermal ramping protocols (Figure 2), that became significant from 19 °C at 25°C in both cases. There was, however, a significant interaction between protocol and temperature (Two-way ANOVA, F11,74 =13.71, p < 0.001). All measures of ṀO2 in CTSmax, irrespective of temperature, were higher than any measure of ṀO2 in the CTmax (Two-way ANOVA, Holm p < 0.001, Table S1, supplementary materials). Consequently, the maximum ṀO2 achieved and absolute thermal scope were significantly higher in the CTSmax (Figure 1). Despite these differences in ṀO2 and absolute thermal scope, Q10 did not in fact differ between protocols (Figure 1).

Discussion

The results demonstrate that capacity for tissue oxygen supply can be significant for upper thermal tolerance in this teleost species, but this depends upon the physiological context and the tolerance endpoint used. When warmed while exercising aerobically, all individuals eventually transitioned to unsteady anaerobic swimming, evidence of limitations in capacity for tissue oxygen supply [START_REF] Steinhausen | The effect of acute temperature increases on the cardiorespiratory performance of resting and swimming sockeye salmon (Oncorhynchus nerka)[END_REF], leading to fatigue at CTSmax. When warmed under static conditions, the animals eventually lost equilibrium at a CTmax that was significantly higher than their CTSmax but, in line with our specific hypothesis, maximum ṀO2 in the CTmax was very significantly less than achieved in the CTSmax. Therefore, the full cardiorespiratory capacity for oxygen supply was not exploited during thermal ramping in the static CTmax, indicating that LOE is not linked to limitations in systemic oxygen delivery in this species [START_REF] Wang | Anaemia only causes a small reduction in the upper critical temperature of sea bass: is oxygen delivery the limiting factor for tolerance of acute warming in fishes?[END_REF].

Fatigue in the CTSmax was not due to limited aerobic endurance because, at their acclimation temperature, seabass swam at 2.5 BL s -1 for longer than the duration of the warming challenge. Similar aerobic endurance was observed in Nile tilapia Oreochromis niloticus and pacu Piaractus mesopotamicus [START_REF] Blasco | Using aerobic exercise to evaluate sub-lethal tolerance of acute warming in fishes[END_REF]. This confirms that the fatigue endpoint in the CTSmax is due to the progressive warming. The swimming responses to the CTSmax protocol, gait transition followed by fatigue, were also very similar in tilapia and pacu [START_REF] Blasco | Using aerobic exercise to evaluate sub-lethal tolerance of acute warming in fishes[END_REF]. The gait transition is qualitatively indistinguishable to that observed prior to fatigue in a critical swimming speed (Ucrit) protocol, where it is stimulated by increments in current velocity rather than temperature. This indicates that the transition occurs due to a similar mechanism. In the Ucrit, it is typically assumed that gait transition and then fatigue occur because a fish has reached its maximum cardiorespiratory capacity for oxygen supply [START_REF] Brett | The respiratory metabolism and swimming performance of young sockeye salmon[END_REF][START_REF] Claireaux | Linking swimming performance, cardiac pumping ability and cardiac anatomy in rainbow trout[END_REF][START_REF] Farrell | Cardiorespiratory performance during prolonged swimming tests with salmonids: a perspective on temperature effects and potential analytical pitfalls[END_REF][START_REF] Webb | Swimming. In The Physiology of Fishes[END_REF]. Although it is not known what causes the gait transition in a Ucrit test, one plausible theory focuses on the heart. An aerobic organ, the teleost heart receives much of its oxygen supply from venous return in the single circulation, after the blood has unloaded oxygen to respiring tissues [START_REF] Farrell | The heart[END_REF][START_REF] Jones | The respiratory and circulatory systems during exercise[END_REF]. It has been suggested that during an incremental swim challenge, fishes engage the gait transition towards anaerobic swimming when tissue oxygen extraction outstrips capacity for supply, and oxygen levels in venous blood returning to the heart drop below a critical level. By engaging the white muscle, the fish reduces rates of oxygen extraction by the working red muscle and so venous oxygen supply to the heart is assured [START_REF] Farrell | On-line venous oxygen tensions in rainbow trout during graded exercise at two acclimation temperatures[END_REF][START_REF] Mckenzie | The effects of environmental factors on the physiology of aerobic exercise[END_REF]. The gait transition preceding fatigue in the CTSmax may reflect a similar decline in venous oxygen levels, that risked compromising oxygen supply to the working heart [START_REF] Blasco | Using aerobic exercise to evaluate sub-lethal tolerance of acute warming in fishes[END_REF]. [START_REF] Steinhausen | The effect of acute temperature increases on the cardiorespiratory performance of resting and swimming sockeye salmon (Oncorhynchus nerka)[END_REF] found that fatigue from exercise during acute warming in the sockeye salmon coincided with cardiac pumping capacity reaching its maximum. Cardiac performance plays a major role in defining acute thermal tolerance in many fish species [START_REF] Ekström | Effects of autonomic blockade on acute thermal tolerance and cardioventilatory performance in rainbow trout, Oncorhynchus mykiss[END_REF][START_REF] Ekström | Cardiac oxygen limitation during an acute thermal challenge in the European perch: effects of chronic environmental warming and experimental hyperoxia[END_REF][START_REF] Farrell | Cardiorespiratory performance during prolonged swimming tests with salmonids: a perspective on temperature effects and potential analytical pitfalls[END_REF][START_REF] Gilbert | Autonomic cardiac regulation facilitates acute heat tolerance in rainbow trout: in situ and in vivo support[END_REF], so represents a focus for future studies regarding the mechanisms for the CTSmax endpoint. Other mechanisms may also contribute, progressive warming can impair locomotor coordination in fishes, possibly as a consequence of limitation in oxygen supply to the brain [START_REF] Andreassen | Brain dysfunction during warming is linked to oxygen limitation in larval zebrafish[END_REF]. Further research is therefore required to understand what causes gait transition and fatigue in a CTSmax but it is interesting that the test solicits similar physiological responses in multiple species [START_REF] Blasco | Using aerobic exercise to evaluate sub-lethal tolerance of acute warming in fishes[END_REF].

Although the CTSmax results provide evidence that tissue oxygen supply can play a role in thermal tolerance in swimming seabass when fatigue is the endpoint, the CTmax data support the hypothesis that LOE is not due to limitations in systemic oxygen supply in this species [START_REF] Wang | Anaemia only causes a small reduction in the upper critical temperature of sea bass: is oxygen delivery the limiting factor for tolerance of acute warming in fishes?[END_REF]. The mean CTmax of 34.0 °C in our juvenile seabass reared at 18° C, was comparable to previous reports of 34.7 and 35.6 °C for juveniles acclimated for 30 days to 15 or 20 °C, respectively [START_REF] Kır | Thermal tolerance and standard metabolic rate of juvenile European sea bass (Dicentrarchus labrax, Linnaeus, 1758) acclimated to four temperatures[END_REF]. The slightly higher CTmax reported by Kir and Demirci (2018) may also be linked to a more rapid thermal ramping of 0.3 °C min -1 compared to 0.033 °C min -1 in this study, as more rapid ramping is known to lead to higher CTmax values in fishes [START_REF] Desforges | The ecological relevance of critical thermal maxima methodology (CTM) for fishes[END_REF][START_REF] Ern | Physiological mechanisms of acute upper thermal tolerance in fish[END_REF]. We ramped at 1°C every 30 min to ensure that fish core temperature was equilibrated with the water at each step, and that we could measure MO2 over the last 10 min. While MO2 increased markedly with warming in the static CTmax, as observed in other studies [START_REF] Mcarley | Chronic warm exposure impairs growth performance and reduces thermal safety margins in the common triplefin fish (Forsterygion lapillum)[END_REF][START_REF] Norin | Thermal biology and swimming performance of Atlantic cod ( Gadus morhua ) and haddock ( Melanogrammus aeglefinus )[END_REF], and the Q10 was similar in both protocols, the actual rates were always significantly lower than at any temperature in the CTSmax. That is, LOE occurred at MO2 levels lower than those of the same individuals exercising at 2.5 BL s -1 at 19 °C. Static respirometry does not constrain gas exchange in seabass, juveniles achieved similar high maximum rates of oxygen uptake when either swum in a Ucrit test or chased to exhaustion and then placed in a static chamber [START_REF] Killen | Do method and species lifestyle affect measures of maximum metabolic rate in fishes?[END_REF]. Therefore, warming did not challenge capacity for oxygen supply in stationary fish, it caused LOE by an oxygenindependent mechanism. There are a variety of possible contenders, particularly direct temperatureinduced effects on critical organs such as heart and brain, which cause their dysfunction. There is evidence of this in fishes, including that such effects can interact with oxygen limitation within these organs [START_REF] Andreassen | Brain dysfunction during warming is linked to oxygen limitation in larval zebrafish[END_REF][START_REF] Friedlander | Effects of cold and heat on behavior and cerebellar function in goldfish[END_REF][START_REF] Vornanen | Feeling the heat: source-sink mismatch as a mechanism underlying the failure of thermal tolerance[END_REF]. Overall, the consensus is that LOE can have multiple causes and that systemic oxygen limitation is not a universal mechanism across fish species [START_REF] Andreassen | Brain dysfunction during warming is linked to oxygen limitation in larval zebrafish[END_REF][START_REF] Ern | Physiological mechanisms of acute upper thermal tolerance in fish[END_REF][START_REF] Mcarley | Fish and hyperoxia-From cardiorespiratory and biochemical adjustments to aquaculture and ecophysiology implications[END_REF].

The Fry-OCLTT argues that capacity for oxygen supply is a mechanism underlying thermal tolerance in fishes [START_REF] Fry | The Effect of Environmental Factors on the Physiology of Fish[END_REF][START_REF] Pörtner | Oxygen-And capacity-limitation of thermal tolerance: A matrix for integrating climate-related stressor effects in marine ecosystems[END_REF], the CTSmax test indicates that it can be in multiple species, if fatigue from aerobic activity is the tolerance endpoint. Here we show that this is true for a species where LOE in a CTmax protocol appears to occur by an oxygen-independent mechanism. The CTmax is easy and rapid to perform but the endpoint has a complex multitude of potential mechanisms. The CTSmax is more technically demanding but the mechanism underlying tolerance may be similar across fish species.

Figure 1 .

 1 Figure1. Boxplots of data for critical temperature of endpoint (A); maximum rate of oxygen uptake achieved (B); thermal scope, calculated as maximum rate of oxygen uptake minus rate at 19 °C (C), and Q10 for effects of temperature on oxygen uptake between 19 °C and 29 °C (D). Two thermal ramping protocols are compared in n = 8 European seabass, either critical thermal maximum for swimming (CTSmax) exercising aerobic with fatigue as endpoint, or critical thermal maximum (CTmax) under static conditions with loss of equilibrium as endpoint. Each point is an individual, the lines connecting the two protocols show how that individual responded to each. Boxplot lower and upper hinges represent the 25 th and 75 th percentiles. The horizontal line within the box is the median. The length of whiskers represents the range of data points between each hinge and 1.5× the difference between the 25 th and 75 th percentiles. Data beyond these limits are outliers.

Figure 2 .

 2 Figure 2. Rate of oxygen uptake in n = 8 European seabass during exposure to two thermal ramping protocols, either critical thermal maximum for swimming (CTSmax) exercising aerobic with fatigue as endpoint (19 °C to 31 °C, orange symbols and curve), or critical thermal maximum (CTmax) under static conditions with loss of equilibrium as endpoint (19 to 35°C, red symbols and curve). Each point represents an individual, the temperature ranges are those for which oxygen uptake data was collected on all individuals, the shaded area shows the 95% confidence interval.

Acknowledgements

We are grateful to two anonymous referees for comments that significantly improved the presentation of this manuscript.

Ethics.

Experimental procedures were approved by the ethics committee for animal experimentation n° 036 of the French Ministère de l'Enseignement Superieur, de la Recherche et de l'Innovation, with reference number APAFIS#19567-2018100910598940 v2.

Data accessibility. Data are available in the electronic supplementary material

Author contribution. All authors contributed to study conception, design, securing funding, animal husbandry. J.J.H.N., F.R.B. and C.R. carried out the experiments and completed the data analyses. J.J.H.N and D.J.M. drafted the initial manuscript; all authors then reviewed and revised the manuscript.

Competing interests. We declare no competing interests.