Tight Analysis of Grover-Meets-Simon and Alg-PolyQ2 Attacks via Formalizing Quantum Rank-Solving under Deferred Measurement

A circuit consisting of a series of quantum gates applied to a group of qubits is called a quantum circuit, which can be used to describe the change of quantum state in Hilbert space. Each quantum logic gate can be represented by a unitary matrix. These unitary operators in Hilbert space are all invertible, and it may be necessary to use enough auxiliary qubits to achieve the required goal. A single qubit has two quantum ground states |0〉, |1〉. If the quantum state |φ〉 can be linearly represented by |0〉, |1〉, then this state is called a superposition state |φ〉 = α|0〉 + β|1〉. Among them, the probability amplitudes α and β are complex numbers, and |α|² + |β|² = 1. When an n-qubit is given, the computational basis has 2ⁿ vectors. After applying a series of quantum gates to the initial state, the original superposition state changes. Finally, the system is measured and some n-qubit vectors are obtained on the computational basis to get the desired result.

Quantum computing takes advantage of parallel computing by utilizing quantum phenomena such as quantum superposition and entanglement, allowing multiple computable states to be processed simultaneously, thereby improving efficiency and speed. The unique capabilities of quantum computers enable them to surpass classical computers in certain computing tasks.

Simon’s algorithm [19] aims to solve the periodic problem of hidden subgroups, which can be described as follows:

Simon’s Problem with promise: suppose there is a quantum oracle to a function f: {0,1}ⁿ → {0,1}^m such that ∃ s ∈ {0,1}ⁿ, ∀ x ∈ {0,1}ⁿ, f(x) = f(x ⊕ s). The goal is to find the period s.

An individual Simon’s algorithm can be performed by the following steps, with the corresponding quantum circuit shown in Figure 1.

• Prepare the initial state |0〉I⊗n|0〉II⊗m|0\rangle _I^{ \otimes n}|0\rangle _{II}^{ \otimes m} and perform the Hadamard transform H^⊗n on the first register. The following quantum states can be obtained: 12n∑x∈{0,1}n|x〉I|0〉II.{1 \over {\sqrt {{2^n}} }}\sum\limits_{x \in {{\{ 0,1\} }^n}} | \;x{\rangle _I}|0{\rangle _{II}}.

• Perform a quantum query on the function f, mapping to the following quantum state: 12n∑x∈{0,1}n|x〉I|f(x)〉II.{1 \over {\sqrt {{2^n}} }}\sum\limits_{x \in {{\{ 0,1\} }^n}} | \;x{\rangle _I}|f(x){\rangle _{II}}.

• Perform the Hadamard transform H^⊗n on the first register, and the following quantum state can be obtained: 12n∑y∈{0,1}n∑x∈{0,1}n(−1)x·y|y〉I|f(x)〉II.{1 \over {{2^n}}}\sum\limits_{y \in {{\{ 0,1\} }^n}} {\sum\limits_{x \in {{\{ 0,1\} }^n}} {{{( - 1)}^{x\;\cdoty}}} } |y{\rangle _I}|f(x){\rangle _{II}}.

  Suppose there is some s ≠ 0, for each y, then |y, f(x)〉 = |y, f(x ⊕ s〉, and the amplitude of this configuration is: 1α(x,y)=12n[ (−1)x·y+(−1)(x⊕s)·y ]=12n(−1)x·y[ (1+(−1)s·y ].\alpha (x,y) = {1 \over {{2^n}}}\left[ {{{( - 1)}^{x\;\cdoty}} + {{( - 1)}^{(x \oplus s)\cdoty}}} \right] = {1 \over {{2^n}}}{( - 1)^{x\;\cdoty}}\left[ {\left( {1 + {{( - 1)}^{s\;\cdoty}}} \right].} \right.

  Let X₁ be an ((n – 1)-dimensional subspace of F2n_2^n, and divide F2n_2^n into coset X₁ and X₁ + s, s∈F2n\X1s \in _2^n\backslash {X_1}. In this setting, we assume x ∈ X₁.

• Measure the first register, and it will collapse to a value that satisfies y · s = 0.

Figure 1.

Quantum circuit of Simon’s algorithm.

When y · s = 1, the amplitude of α(x, y) is 0. Hence, we can only get the vector y orthogonal to period s. The parallel Simon’s algorithms under deferred measurement only need 𝒪(n) oracle queries, n – 1 linearly independent values of y are obtained with high probability, then s can be obtained by solving the following linear equations: 2{ y1·s=0y2·s=0⋮yn·s=0.\left\{ {\matrix{ {{y_1}\;\cdot\;s = 0} \hfill \cr {{y_2}\;\cdot\;s = 0} \hfill \cr {\;\;\; \vdots } \hfill \cr {{y_n}\;\cdot\;s = 0.} \hfill \cr } } \right.

Simon’s algorithm is a probabilistic algorithm, and the promise of Simon’s problem is not always fully satisfied in cryptanalysis. We introduce a theorem to quantify the relationship between the number of parallel instances of Simon’s algorithm and the success probability. The proof can be found in [23]:

Grover’s algorithm [8,9] aims to quickly search for r marked solution elements in an unstructured database of size N, which can achieve a quadratic speedup compared to the time complexity of classical exhaustive algorithms. It can be described as follows:

Grover’s problem: given a search space N whose elements are represented on n = log₂ N qubits, suppose there is a quantum oracle to a function f: {0,1}ⁿ → {0,1} such that x ∈ N, f(x) = 1. The goal is to find these r marked solution elements.

Amplitude amplification is a natural generalization of the original Grover’s algorithm. The result of amplitude amplification is described in the following theorem [13], with the corresponding quantum circuit shown in Figure 2.

Figure 2.

Quantum circuit of generalized Grover’s algorithm.

Here, 𝒜 is the Hadamard transform H^⊗n in the original Grover’s algorithm.

Given a quantum coefficient matrix |A〉m⊗n=∑iαi|Ai〉m⊗n|A{\rangle _{m \otimes n}} = \sum\nolimits_i {{\alpha _i}{{\left| {{A_i}} \right\rangle }_{m \otimes n}}} of linear systems of equations, there exists a unitary operator U_QGJE such that ∑iαi|Ai〉|0〉⊗num→UQGJE∑iαi|Ai′〉|εi〉\sum\nolimits_i {{\alpha _i}} \left| {{A_i}} \right\rangle |0{\rangle ^{ \otimes num}}\buildrel {{U_{{\rm{QGJE}}}}} \over \longrightarrow \sum\nolimits_i {{\alpha _i}} \left| {A_i^\prime } \right\rangle \left| {{\varepsilon _i}} \right\rangle , where |Ai′〉\left| {A_i^\prime } \right\rangle is the reduced row echelon form (RREF) matrix corresponding to different |A_i〉, and |ε_i〉 corresponding to each superposition component are auxiliary qubits after applying the generalized QGJE.

In formal description of the generalized QGJE, auxiliary qubits |0〉^⊗num are necessary to complete the generalized QGJE. Next, we provide a lemma to prove its necessity.

Assume for contradiction that there exists a unitary operator U without auxiliary qubits such that U|00〉 = |00〉,U|01〉 = |10〉,U|10〉 = |10〉,U|11〉 = |11〉. From this, we can find that { U|01〉=|10〉U|10〉=|10〉⇒{ U(0,0,1,0)T=(0,1,0,0)T(i)U(0,1,0,0)T=(0,1,0,0)T(ii).\left\{ {\matrix{ {U|01\rangle = \;|10\rangle } \hfill \cr {U|10\rangle = \;|10\rangle } \hfill \cr } \Rightarrow \left\{ {\matrix{ {U{{(0,0,1,0)}^T} = {{(0,1,0,0)}^T}\;(i)} \cr {U{{(0,1,0,0)}^T} = {{(0,1,0,0)}^T}\;(ii).} \cr } } \right.} \right.

If we do (i) – (ii), we get U(0, –1, 1, 0)^T = (0,0,0,0)^T, violating unitarity since U⁻¹ cannot recover the original state, contradicts! There is no inverse operator such that U⁻¹ (0,0,0,0)^T = (0, –1,1,0)^T. As a result, there exists no such unitary operator U. Thus, the assumption does not hold.

It can be seen that auxiliary qubits are necessary to store the values of data qubits to control the transformation.

Lemma 1 demonstrates the necessity of auxiliary qubits in the generalized QGJE. This naturally raises an important question: we need to consider whether the auxiliary qubits can be disentangled. Next, we provide a theorem to state the issue and show the form of the quantum state after the generalized QGJE.

Next, we use the method of contradiction. Suppose that there is an operator U such that ∑iαi|Ai〉|0〉⊗num→(∑jβj|Bj〉)⊗(∑kγk|ck〉)\sum\nolimits_i {{\alpha _i}} \left| {{A_i}} \right\rangle |0{\rangle ^{ \otimes num}} \to \;\left( {\sum\nolimits_j {{\beta _j}} \left| {{B_j}} \right\rangle } \right) \otimes \left( {\sum\nolimits_k {{\gamma _k}\left| {{c_k}} \right\rangle } } \right). We divide U into the product of two unitary operators U_QGJE and U′.

4UQGJE(∑iαi|Ai〉⊗|0〉⊗num)=∑iαi(|Ai′〉⊗|εi〉)U′→(∑jβj|Bj〉)⊗(∑kγk|ck〉)=∑j,kβjγk(|Bj〉⊗|ck〉).\matrix{ {{U_{{\rm{QGJE}}}}\left( {\sum\limits_i {{\alpha _i}} \left| {{A_i}} \right\rangle \otimes |0{\rangle ^{ \otimes num}}} \right)} \hfill & { = \sum\limits_i {{\alpha _i}} \left( {\left| {A_i^\prime } \right\rangle \otimes \left| {{\varepsilon _i}} \right\rangle } \right)} \hfill \cr {} \hfill & {\left( {\sum\limits_j {{\beta _j}} \left| {{B_j}} \right\rangle } \right) \otimes \left( {\sum\limits_k {{\gamma _k}} \left| {{c_k}} \right\rangle } \right)} \hfill \cr {} \hfill & { = \sum\limits_{j,k} {{\beta _j}} {\gamma _k}\left( {\left| {{B_j}} \right\rangle \otimes \left| {{c_k}} \right\rangle } \right).} \hfill \cr }

While the RREF of a matrix is unique, the reduction process may not be, which results in different auxiliary states. Multiple different A_i may correspond to the same RREF matrix B_j. Hence, j ≤ i always holds. The original problem can be reduced to whether the auxiliary states added during the operation can be disentangled through U′. If both Σj=1{\Sigma _j} = 1 and Σk=1{\Sigma _k} = 1, then the space containing ∑iαi(|Ai′〉⊗|εi〉)\sum\nolimits_i {{\alpha _i}} \left( {\left| {A_i^\prime } \right\rangle \otimes \left| {{\varepsilon _i}} \right\rangle } \right) has the same dimension as that of ∑j,kβjγk|Bj⊗ck〉\sum\nolimits_{j,k} {{\beta _j}} {\gamma _k}\left| {{B_j} \otimes {c_k}} \right\rangle since U′ is a unitary operator and they are both one-dimensional, which contradicts the fact that multiple |A_i〉 map to the same |B_j〉. Thus, it is evident that the case satisfying both Σj=1{\Sigma _j} = 1 and Σk=1{\Sigma _k} = 1 clearly cannot hold. There may exist the following cases:

• Case 1:

  Σj=1{\Sigma _j} = 1 and ∑k≠1\sum\nolimits_k \ne 1.

  Since auxiliary qubits record the information of |A_i〉, it is generally the case that |ε_i〉 ≠ |ε_i′〉 when i ≠ i′. However, due to Σj=1{\Sigma _j} = 1, all different |A_i〉 correspond to the same RREF matrix |B₁〉, which is clearly not the case.

• Case 2:

  Σj≠1{\Sigma _j} \ne 1 and Σk=1{\Sigma _k} = 1.

  According to Formula (4), when k = 1, that is, auxiliary qubits are disentangled and can return to all-zero states |0 〉^⊗num. Thus, we can get that ∑iαi|Ai〉U→∑jβj|Bj〉\sum\nolimits_i {{\alpha _i}} \left| {{A_i}} \right\rangle \sum\nolimits_j {{\beta _j}} \left| {{B_j}} \right\rangle . Different matrices may get the same RREF matrix after the generalized QGJE, that is |{A_i}| > |{B_j}|. Suppose that |B₁〉 is the RREF matrix corresponding to |A₁₁}, |A₁₂〉. And |B₂〉 is the RREF matrix corresponding to |A₂₁〉, |A₂₂〉. There are superposition states 12|A11〉+12|A21〉{1 \over {\sqrt 2 }}\left| {{A_{11}}} \right\rangle + {1 \over {\sqrt 2 }}\left| {{A_{21}}} \right\rangle and 12|A12〉+12|A22〉{1 \over {\sqrt 2 }}\left| {{A_{12}}} \right\rangle + {1 \over {\sqrt 2 }}\left| {{A_{22}}} \right\rangle . We get that 5U(12|A11〉+12|A21〉)=U(12|A12〉+12|A22〉)=12|B1〉+12|B2〉.U\left( {{1 \over {\sqrt 2 }}\left| {{A_{11}}} \right\rangle + {1 \over {\sqrt 2 }}\left| {{A_{21}}} \right\rangle } \right) = U\left( {{1 \over {\sqrt 2 }}\left| {{A_{12}}} \right\rangle + {1 \over {\sqrt 2 }}\left| {{A_{22}}} \right\rangle } \right) = {1 \over {\sqrt 2 }}\left| {{B_1}} \right\rangle + {1 \over {\sqrt 2 }}\left| {{B_2}} \right\rangle.

  Consider the invertibility of the unitary operator U, U−1(12|B1〉+12|B2〉){U^{ - 1}}\left( {{1 \over {\sqrt 2 }}\left| {{B_1}} \right\rangle + {1 \over {\sqrt 2 }}\left| {{B_2}} \right\rangle } \right) must have only unique preimage. Contradicting with the above Formula (5), this case does not hold.

• Case 3:

  ∑j≠1\sum\nolimits_j \ne \;1 and ∑k≠1\sum\nolimits_k \ne \;1.

  In this case, suppose that there are k₁ original matrices |A_i1〉 corresponding to the same RREF matrix |B₁〉 and there are k₂ original matrices |A_i2〉 corresponding to the same RREF matrix |B₂〉. Since the inputs are distinct and unitary operators are invertible, we have 6{ UQGJE(|Ai1⊗0num〉)=|B1⊗εi1〉,i1∈{ 1,2,⋯k1 }UQGJE(|Ai2⊗0num〉)=|B2⊗εi2〉,i2∈{ 1,2,⋯k2 }.\left\{ {\matrix{ {{U_{{\rm{QGJE}}}}\left( {\left| {{A_{{i_1}}} \otimes {0^{num}}} \right\rangle } \right) = \left| {{B_1} \otimes {\varepsilon _{{i_1}}}} \right\rangle,} \hfill & {{i_1} \in \left\{ {1,2, \cdots {k_1}} \right\}} \hfill \cr {{U_{{\rm{QGJE}}}}\left( {\left| {{A_{{i_2}}} \otimes {0^{num}}} \right\rangle } \right) = \left| {{B_2} \otimes {\varepsilon _{{i_2}}}} \right\rangle,} \hfill & {{i_2} \in \left\{ {1,2, \cdots {k_2}} \right\}.} \hfill \cr } } \right.

According to Formula (6), the number of original matrices corresponding to different RREF matrices may be different. Hence, there is no such unitary operation U’ that ∑iαi(|Ai′〉⊗|εi〉)U′→∑j,kβjγk(|Bj〉⊗|ck〉)\sum\nolimits_i {{\alpha _i}} \left( {\left| {A_i^\prime } \right\rangle \otimes \left| {{\varepsilon _i}} \right\rangle } \right)\sum\nolimits_{j,k} {{\beta _j}} {\gamma _k}\left( {\left| {{B_j}} \right\rangle \otimes \left| {{c_k}} \right\rangle } \right).

Besides, if ∑iαi|Ai〉|0〉⊗num→U(∑jβj|Bj〉)⊗(∑kγk|ck〉)\sum\limits_i {{\alpha _i}} \left| {{A_i}} \right\rangle |0{\rangle ^{ \otimes num}}\buildrel U \over \longrightarrow \left( {\sum\nolimits_j {{\beta _j}} \left| {{B_j}} \right\rangle } \right) \otimes \left( {\sum\nolimits_k {{\gamma _k}} \left| {{c_k}} \right\rangle } \right) holds, then there is always a unitary transformation that changes auxiliary qubits ∑kγk|ck〉\sum\nolimits_k {{\gamma _k}} \left| {{c_k}} \right\rangle into all-zero states. As in case 2, this case does not hold. In summary, there is no unitary transformation U’, equivalent to this theorem, which does not hold. Thus, the generalized QGJE can only realize ∑iαi|Ai〉|0〉⊗num→UQGJE∑iαi|Ai′〉|εi〉\sum\nolimits_i {{\alpha _i}} \left| {{A_i}} \right\rangle |0{\rangle ^{ \otimes num}}\buildrel {{U_{{\rm{QGJE}}}}} \over \longrightarrow \sum\nolimits_i {{\alpha _i}} \left| {A_i^\prime } \right\rangle \left| {{\varepsilon _i}} \right\rangle .

According to the above analysis, we provide a formal description and analysis of the generalized QGJE, demonstrating that it can serve as a subroutine for determining whether a matrix is of full rank or rank-(n – 1) in the quantum setting (see Remark 1).

In particular, since the registers of multiple instances of Simon’s algorithm form a tensor product, the resulting matrix is randomly generated. If Simon’s promise holds—i.e., there exists a hidden period, and then the rank of the resulting matrix is at most n – 1. In the following, we consider these cases and express them as a lemma.

However, this factorization is not unique because different pairs (U, V) can give rise to the same matrix A. Specifically, for any invertible matrix T ∈ GL_n–1 (𝔽₂), we have A = UV = (UT)(T⁻¹V), and both UT and T⁻¹V are still full-rank. Therefore, to avoid overcounting, we divide by the number of invertible (n – 1) × (n – 1) matrices over 𝔽₂. We proceed as follows:

• First, we count the number of full-rank (n – 1)-dimensional column spaces over F2l_2^l. This is the number of ordered sets of (n – 1) linearly independent column vectors over F2l_2^l, which is ∏i=0n−2(2l−2i)\prod\nolimits_{i = 0}^{n - 2} {\left( {{2^l} - {2^i}} \right)} .

• Next, we proceed to count the number of full-rank (n – 1)-dimensional row spaces over F2n_2^n, which is ∏i=0n−2(2n−2i)\prod\nolimits_{i = 0}^{n - 2} {\left( {{2^n} - {2^i}} \right)} .

• Finally, we divide by the number of invertible (n – 1) × (n – 1) matrices over 𝔽₂, which is | GLn−1(F2) |=∏i=0n−2(2n−1−2i)\left| {{\rm{G}}{{\rm{L}}_{n - 1}}\left( {{_2}} \right)} \right| = \prod\nolimits_{i = 0}^{n - 2} {\left( {{2^{n - 1}} - {2^i}} \right)} .

Combining all the above parts, we can obtain: NF2n(n−1)=∏i=0n−2(2l−2i)(2n−2i)2n−1−2i=(2n−1)∏i=0n−2(2l−2i){N_{_2^n}}(n - 1) = \prod\nolimits_{i = 0}^{n - 2} {{{\left( {{2^l} - {2^i}} \right)\left( {{2^n} - {2^i}} \right)} \over {{2^{n - 1}} - {2^i}}}} = \left( {{2^n} - 1} \right)\prod\nolimits_{i = 0}^{n - 2} {\left( {{2^l} - {2^i}} \right)} .

Consider the set of all l × n matrices over 𝔽₂ whose rank is exactly n – 1, and it is equivalent to a full-rank matrix associated with a homogeneous system of linear equations, i.e., the number of ordered sets of (n – 1) linearly independent column vectors over F2l_2^l, which is NF2n−1(n−1)=∏i=0n−2(2l−2i){N_{_2^{n - 1}}}(n - 1) = \prod\nolimits_{i = 0}^{n - 2} {\left( {{2^l} - {2^i}} \right)} .

For subsequent calculations, we provide the tight bound and approximation on this value of ∏i=0n−2(2l−2i)\prod\nolimits_{i = 0}^{n - 2} {\left( {{2^l} - {2^i}} \right)} , as summarized in Tight Bounds and Approximation.

Leander and May [30] proposed a key-recovery attack leveraging a combination of Grover’s algorithm and Simon’s algorithm. The method embeds Simon’s algorithm within the iterations of Grover’s search, using Simon’s algorithm as the internal decision function and Grover’s algorithm as the outer search procedure. They also provided a relatively loose success probability of 25{2 \over 5} by choosing a specific quantum input length, such as the number of parallel instances of Simon’s algorithm. In this subsection, we provide the generalized success probability and the optimal number of iterations of the Grover-meets-Simon algorithm, along with their proofs.

Indeed, the Grover-meets-Simon algorithm is the generalized Grover’s algorithm shown in Figure 2, where 𝒜 is l(≥ n) parallel Simon’s algorithms, U_f is used to determine whether the rank is n – 1 by applying the generalized QGJE, and U₀ changes the phase of the amplitude only for the zero state.

Let f : { 0,1 }^m × { 0,1 }ⁿ → { 0,1 }ⁿ be a function such that f(k′,x)=Enc(k′,x)+E(k′,x)f\left( {k',x} \right) = Enc\left( {k',x} \right) + E\left( {k',x} \right). It is evident that f (k′,x) has the period s = k₁ when k′ = k. Applying algorithm 𝒜 on |0〉^⊗m+2nl, the initial input state of Grover-meets-Simon algorithm is 9|φ〉=12m(12n)l∑k′∈F2mx1,⋯,x1∈F2ny1,⋯,yl∈F2n(−1)x1·y1⋯(−1)xl·yl|y1,y2⋯,yl〉|f(k′,x1),⋯,f(k′,xl)〉|k′〉.|\varphi \rangle = {1 \over {\sqrt {{2^m}} }}{\left( {{1 \over {{2^n}}}} \right)^l}\sum\limits_{\scriptstyle k' \in _2^m \atop {\scriptstyle {x_1}, \cdots,{x_1} \in _2^n \atop \scriptstyle {y_1}, \cdots,{y_l} \in _2^n}} {{{( - 1)}^{{x_1}\cdot{y_1}}}} \cdots {( - 1)^{{x_l}\cdot{y_l}}}\left| {{y_1},{y_2} \cdots,{y_l}} \right\rangle \left| {f\left( {k',{x_1}} \right), \cdots,f\left( {k',{x_l}} \right)} \right\rangle \left| {k'} \right\rangle.

Next, we analyze the initial state |φ〉 in detail. The key space ∑k′∈F2n|k′〉\sum\nolimits_{k' \in _2^n} {\left| {k'} \right\rangle } to be searched is entangled with the superposition state of the matrices ∑y1,⋯,yl∈F2n|y1,⋯,yl〉\sum\nolimits_{{y_1}, \cdots,{y_l} \in _2^n} {\left| {{y_1}, \cdots,{y_l}} \right\rangle } generated in parallel multiple Simon’s registers. Suppose that ϒ1={ (y1,y2,⋯,yl)∈F2nl∣yi⊥s,s≠0 }{Y_1} = \left\{ {\left( {{y_1},{y_2}, \cdots,{y_l}} \right) \in _2^{nl}\mid {y_i} \bot s,s \ne 0} \right\} and ϒ2={ (y1,y2,⋯,yl)∈F2nl∣yi∈F2n }{Y_2} = \left\{ {\left( {{y_1},{y_2}, \cdots,{y_l}} \right) \in _2^{nl}\mid {y_i} \in F_2^n} \right\}. When |k′〉 is the correct key |k〉, the row vector |y₁〉 (i ∈ 1,2 ⋯ l) of the corresponding matrix |y₁, y₂, ⋯, y₁ satisfies that y_i ∈ ϒ¹. Otherwise, the row vector |y_i〉 (i ∈ 1,2 ⋯ l) only satisfies y₁ ∈ ϒ₂. If we consider the intermediate measurement in the original Simon’s algorithm, the key space ∑k′∈F2n|k′〉\sum\nolimits_{k' \in _2^n} {\left| {k'} \right\rangle } will collapse so that we cannot search for the correct key |k〉. Therefore, we can measure only at the end of the algorithm according to the principle of deferred measurement.

In addition, when l = 𝒪(n), Simon’s algorithms are executed in parallel, the linear systems of equations generated are different from the linear systems of equations generated by a single Simon’s algorithm running 𝒪 (n) times. After O (n) Simon’s algorithms via measurement, we can obtain a determined classical matrix. Whereas as the number of parallel instances increases, the dimension of the span dim(span(( y₁, y₂, ⋯, y_l))) = n – 1 can be obtained with a high probability [23], enabling recovery of the period s. However, without intermediate measurement after 𝒪(n) Simon’s algorithms in parallel, the resulting superposition state of matrices ∑y1,y2,⋯,yl∈F2n|y1,y2,⋯,yl〉\sum\nolimits_{{y_1},{y_2}, \cdots,{y_l} \in _2^n} {\left| {{y_1},{y_2}, \cdots,{y_l}} \right\rangle } would contain all matrices generated by a row vector y that satisfies the promise. That is, the matrix components with rank less than n – 1 will inevitably be present in the superposition. For example, one of the components of the superposition state is |y₁, y₂, ⋯,y₁〉, that is, all row vectors are the same and dim((y₁, y₁ ⋯ y₁)) = 1. Therefore, under this deferred measurement setting, one must not only search for the correct key |k〉, but also identify and extract the appropriate components |y₁, y₂, ⋯,y_l〉 by applying the generalized QGJE.

Consider that if k is the correct key, then the function f (k, x) has a non-zero period s such that f (k, x) = f (k, x ⊕ s). To simplify the representation, we define a set X₁ that is the n – 1 dimensional subspace of F2n_2^n and divide F2n{\left( {{1 \over {{2^{n - 1}}}}} \right)^l}\sum\limits_{\scriptstyle x \in {X_1} \atop \scriptstyle {y_1}, \cdots,{y_l} \in _2^n,y \bot s} {{{( - 1)}^{{x_1}\cdot{y_1}}}} \cdots {( - 1)^{{x_l}\cdot{y_l}}}\left| {{y_1},{y_2}, \cdots,{y_l}} \right\rangle \left| {f\left( {k',{x_1}} \right), \cdots,f\left( {k',{x_l}} \right)} \right\rangle. into cosets X₁ and X₁ + s. We suppose that the ground states can be combined to obtain the following result by applying parallel Simon’s algorithms: 10(12n−1)l∑x∈X1y1,⋯,yl∈F2n,y⊥s(−1)x1·y1⋯(−1)xl·yl|y1,y2,⋯,yl〉|f(k′,x1),⋯,f(k′,xl)〉.{\left( {{1 \over {{2^{n - 1}}}}} \right)^l}\sum\limits_{\scriptstyle x \in {X_1} \atop \scriptstyle {y_1}, \cdots,{y_l} \in _2^n,y \bot s} {{{( - 1)}^{{x_1}\cdot{y_1}}}} \cdots {( - 1)^{{x_l}\cdot{y_l}}}\left| {{y_1},{y_2}, \cdots,{y_l}} \right\rangle \left| {f\left( {k',{x_1}} \right), \cdots,f\left( {k',{x_l}} \right)} \right\rangle.

Suppose that k is the correct key for the function f (k′, x).If k′ = k, the period s is not 0; if k′ ≠ k, the function f (k′, x) has no period. Then the initial state can be further written as 11|φ〉=12m(12n)l∑k′∈F2m,k′≠kx1,⋯,xl∈Fnny1,⋯,yl∈F2n(−1)x1·y1⋯(−1)xl·yl|y1,y2,⋯,yl〉|f(k′,x1),⋯,f(k′,xl)〉|k′〉+12m(12n−1)l∑x1,⋯,xl∈X1y1,⋯,yl⊥s,s≠0(−1)x1·y1⋯(−1)xl·yl|y1,y2⋯,yl〉|f(k,x1),⋯,f(k,xl)〉|k〉.\matrix{ {|\varphi \rangle = {1 \over {\sqrt {{2^m}} }}{{\left( {{1 \over {{2^n}}}} \right)}^l}\sum\limits_{\scriptstyle k' \in _2^m,k' \ne k \atop {\scriptstyle {x_1}, \cdots,{x_l} \in _n^n \atop \scriptstyle {y_1}, \cdots,{y_l} \in _2^n}} {{{( - 1)}^{{x_1}\cdot{y_1}}}} \cdots {{( - 1)}^{{x_l}\cdot{y_l}}}\left| {{y_1},{y_2}, \cdots,{y_l}} \right\rangle \left| {f\left( {k',{x_1}} \right), \cdots,f\left( {k',{x_l}} \right)} \right\rangle \left| {k'} \right\rangle } \hfill \cr { + {1 \over {\sqrt {{2^m}} }}{{\left( {{1 \over {{2^{n - 1}}}}} \right)}^l}\sum\limits_{\scriptstyle {x_1}, \cdots,{x_l} \in {X_1} \atop \scriptstyle {y_1}, \cdots,{y_l} \bot s,s \ne 0} {{{( - 1)}^{{x_1}\cdot{y_1}}}} \cdots {{( - 1)}^{{x_l}\cdot{y_l}}}\left| {{y_1},{y_2} \cdots,{y_l}} \right\rangle \left| {f\left( {k,{x_1}} \right), \cdots,f\left( {k,{x_l}} \right)} \right\rangle |k\rangle.} \hfill \cr }

In the Grover-meets-Simon algorithm, the above process is equivalent to moving all the measurements of the parallel Simon’s algorithms during the iteration process to the end of the entire algorithm, satisfying the principle of deferred measurement.

Here, the quantum classifier U_f is defined as follows: Uf:F2m×(F2n)l→{0,1}with(k′,y1,⋯,yl)→{0,1}.{U_f}:_2^m \times {\left( {_2^n} \right)^l} \to \{ 0,1\} {\rm{ }}with{\rm{ }}\left( {k',{y_1}, \cdots,{y_l}} \right) \to \{ 0,1\}.

• (1)

  If dim(y₁, y₂, ⋯, y_l) = n ≠ 1, the output will be 0. Otherwise compute a basis of |y₁, y₂, ⋯, y_l〉 by applying the generalized QGJE and the unique vector k1′∈F2n\{0}k_1^\prime \in _2^n\backslash \{ {\bf{0}}\} orthogonal to y.

• (2)

  Check (k′,k1′)=?(k,k1)\left( {{k^\prime },k_1^\prime } \right)\mathop = \limits^? \left( {k,{k_1}} \right) for arbitrary provided plaintext pairs (mi,mi′)∈RF2n\left( {{m_i},m_i^\prime } \right){ \in _R}_2^n. If all identities hold, the output will be 1, otherwise it will be 0.

Therefore, the operator U_f can be defined like: 12|φ′〉→{ −|φ′〉,ifUf|φ′〉=1|φ′〉,ifUf|φ′〉=0,\left| {\varphi '} \right\rangle \to \left\{ {\matrix{ { - \left| {\varphi '} \right\rangle,{\rm{ }}if{\rm{ }}{U_f}\left| {\varphi '} \right\rangle = 1} \cr {\left| {\varphi '} \right\rangle,{\rm{ }}if{\rm{ }}{U_f}\left| {\varphi '} \right\rangle = 0,} \cr } } \right. where |φ′〉 is the component of the superposition state |φ〉.

From Formula (11), we know that the initial state of the Grover-meets-Simon algorithm is not a uniform superposition and there is an amplitude of oscillation due to the entanglement between the key space |k′〉 and Simon’s registers |y₁, ⋯, y_l). Specifically, amplitudes for k′ = k (correct key) scale as 1/2^{(m+2(n–1)l)/2}, while others scale as 1/2^(m+2nl)/2, creating an oscillating imbalance.

In [39], Biron et al. discussed the maximum success probability and the optimal number of iterations of Grover’s algorithm in an arbitrary initial state. They depend only on the standard deviation of the initial amplitude distributions of the marked or unmarked states. Hence, we can provide a tight bound of the generalized success probability of the Grover-meets-Simon algorithm based on the initial amplitude from a novel perspective without considering quantum input length.

Biron et al. [39] obtained first-order linear difference equations for the time evolution of the amplitudes of r marked states and N – r unmarked states and solved them exactly. The results of the maximum success probability and the optimal number of iterations are summarized in the following theorem.

As shown in Formula (11), when k′ is the correct key k, the matrices generated by them contain cases with rank less than or equal to n – 1. We can calculate the number of marked correct solutions r (matrices with rank-(n – 1)) according to Lemma 2. For l parallel instances of Simon’s algorithm, the size of the overall state space is 2^2(n–1)l.

Then, we discuss the initial success probability based on the initial amplitudes. According to the calculation method of the maximum success probability in [39,40], we can get that the maximum success probability in the initial state is Pmax=1−(N−r)σl2,{P_{max}} = 1 - (N - r)\sigma _l^2,, where the variance σl2=1N−r∑i=1N−r| li(0)−l(0)¯ |2=1N−r∑i(li(0))2−(1N−r∑ili(0))2\sigma _l^2 = {1 \over {N - r}}\sum\nolimits_{i = 1}^{N - r} {{{\left| {{l_i}(0) - \overline {l(0)} } \right|}^2}} = {1 \over {N - r}}\sum\limits_i {{{\left( {{l_i}(0)} \right)}^2}} - {\left( {{1 \over {N - r}}\sum\limits_i {{l_i}} (0)} \right)^2}. From Formula (11), we can know that li(0)2={ 12m(122nl),k′≠k12m(122(n−1)l),k′=k.{l_i}{(0)^2} = \left\{ {\matrix{ {{1 \over {{2^m}}}\left( {{1 \over {{2^{2nl}}}}} \right),\quad k' \ne k} \hfill \cr {{1 \over {{2^m}}}\left( {{1 \over {{2^{2(n - 1)l}}}}} \right),\quad k' = k.} \hfill \cr } } \right.

Note that k′ = k but dim(span(y₁, y₂, ⋯, y_l)) < n – 1 are unmarked states. In unmarked states, when k′ ≠ k, the number is (2^m – 1)2^2nl and when k′ = k, the number is 2^2(n–1)l – r. Hence, we can get 13∑i(li(0))2=(2m−1)22nl2m22nl+22(n−1)l−r2m22(n−1)l)=1−r2m22(n−1)l).\sum\limits_i {{{\left( {{l_i}(0)} \right)}^2}} = {{\left( {{2^m} - 1} \right){2^{2nl}}} \over {{2^m}{2^{2nl}}}} + {{{2^{2(n - 1)l}} - r} \over {{2^m}{2^{2(n - 1)l)}}}} = 1 - {r \over {{2^m}{2^{2(n - 1)l)}}}}.

Then, we show ∑ili(0)=∑k′=k,dim(span(y1,⋯,yl))<n−1li(0)+∑k′≠kli(0)\sum\nolimits_i {{l_i}} (0) = {\sum _{k' = k}}, where ∑k′=kdim(span(y1,⋯,yl))<n−1li(0)=12m(12n−1)l∑x1,⋯,xl∈X1dim(span(y1,⋯,yl))<n−1(−1)x1·y1⋯(−1)xl·yl\left. {\left( {{y_1}, \cdots,{y_l}} \right)} \right) < n - {1^{{l_i}}}(0) + \sum\nolimits_{k' \ne k} {{l_i}} (0) and ∑k′≠kli(0)=12m(12n−1)l∑x1,…,xl∈Fnny1,⋯,yl∈F2n(−1)x1·y1⋯(−1)xl·yl.\sum\limits_{\scriptstyle k' = k \atop \scriptstyle \dim \left( {{\mathop{\rm span}\nolimits} \left( {{y_1}, \cdots,{y_l}} \right)} \right) < n - 1} {{l_i}} (0) = {1 \over {\sqrt {{2^m}} }}{\left( {{1 \over {{2^{n - 1}}}}} \right)^l}\sum\limits_{\scriptstyle {x_1}, \cdots,{x_l} \in {X_1} \atop \scriptstyle \dim \left( {{\mathop{\rm span}\nolimits} \left( {{y_1}, \cdots,{y_l}} \right)} \right) < n - 1} {{{( - 1)}^{{x_1}\cdot{y_1}}}} \cdots {( - 1)^{{x_l}\cdot{y_l}}}

When computing the value of ∑ili(0)\sum\limits_{\scriptstyle {x_1}, \cdots,{x_1} \in _2^n \atop \scriptstyle {y_1}, \cdots,{y_l} \in _2^n} {{{( - 1)}^{{x_1}\cdot{y_1}}}} \cdots {( - 1)^{{x_l}\cdot{y_l}}}, we need to get the value of ∑x1,⋯,x1∈F2ny1,⋯,yl∈F2n(−1)x1·y1⋯(−1)xl·yl\sum\limits_{x \in _2^n} {{{( - 1)}^{x\cdoty}}} = \sum\limits_{x \in {X_1}} {{{( - 1)}^{x\cdoty}}} + \sum\limits_{x \oplus s \in _2^n/{X_1}} {{{( - 1)}^{(x \oplus s)\cdoty}}} = \left\{ {\matrix{ {0,} \hfill & {y \ne 0} \hfill \cr {{2^n},} \hfill & {y = 0.} \hfill \cr } } \right.. According to theorem in [35], we know that ∑x∈F2n(−1)x·y=∑x∈X1(−1)x·y+∑x⊕s∈F2n/X1(−1)(x⊕s)·y={ 0,y≠02n,y=0.\sum\nolimits_{x \in _2^n} {{{( - 1)}^{x\cdoty}}} = 2\sum\nolimits_{x \in {X_1}} {{{( - 1)}^{x\cdoty}}}

Because of y ⊥ s, we can get ∑x∈F2n(−1)x·y=2∑x∈X1(−1)x·y\sum\nolimits_{x \in _2^n} {{{( - 1)}^{x\cdoty}}} = 2\sum\nolimits_{x \in {X_1}} {{{( - 1)}^{x\cdoty}}} . Thus, we can get 14∑x∈X1(−1)x·y={ 0,y≠02n−1,y=0.\sum\limits_{x \in {X_1}} {{{( - 1)}^{x\cdoty}}} = \left\{ {\matrix{ {0,y \ne 0} \hfill \cr {{2^{n - 1}},y = 0.} \hfill \cr } } \right.

According to the implementation of U_f, we know that x ∈ X₁, only when y₁, y₂, ⋯, y_l are all 0, the value of ∑k′=k,dim(span(y1,⋯,yl))<n−1li(0)≠0{\sum _{k' = k,\dim \left( {{\mathop{\rm span}\nolimits} \left( {{y_1}, \cdots,{y_l}} \right)} \right) < n - 1}}{l_i}(0) \ne 0; otherwise, it is 0. Likewise, ∑k′≠kli(0)\sum\nolimits_{k' \ne k} {{l_i}} (0) is the same. According to Formula (14), ∑k′=k,dim(span(y1,⋯,yl))<n−1li(0)=2(n−1)l2m2(n−1)l\sum\nolimits_{k' = k,\dim \left( {{\mathop{\rm span}\nolimits} \left( {{y_1}, \cdots,{y_l}} \right)} \right) < n - 1} {{l_i}(0) = {{{2^{(n - 1)l}}} \over {\sqrt {{2^m}} {2^{(n - 1)l}}}}} and ∑k′≠kli(0)=(2m−1)2nl2m2nl\sum\nolimits_{k' \ne k} {{l_i}} (0) = {{\left( {{2^m} - 1} \right){2^{nl}}} \over {\sqrt {{2^m}} {2^{nl}}}}. Hence, 15(1N−r∑ili(0))2=(1N−r((2m−1)2nl2m2nl+2(n−1)l2m2(n−1)l))2=2m(N−r)2.{\left( {{1 \over {N - r}}\sum\limits_i {{l_i}} (0)} \right)^2} = {\left( {{1 \over {N - r}}\left( {{{\left( {{2^m} - 1} \right){2^{nl}}} \over {\sqrt {{2^m}} {2^{nl}}}} + {{{2^{(n - 1)l}}} \over {\sqrt {{2^m}} {2^{(n - 1)l}}}}} \right)} \right)^2} = {{{2^m}} \over {{{(N - r)}^2}}}.

By calculation, we can get the time-independent quantity P_max and the initial success probability P(0) based on the initial amplitudes as follows: 16Pmax=1−(N−r)σl2=r2m22(n−1)l+2mN−r,{P_{max}} = 1 - (N - r)\sigma _l^2 = {r \over {{2^m}{2^{2(n - 1)l}}}} + {{{2^m}} \over {N - r}}, 17P(0)=Pmax−(N−r)|l(0)¯|2=r2m22(n−1)l.P(0) = {P_{max}} - (N - r)|\overline {l(0)} {|^2} = {r \over {{2^m}{2^{2(n - 1)l}}}}.

The size of the database searched is N = (2^m – 1)2^2nl + 2^2(n–1)l. The number of marked correct solutions is r = 2^(n–1)lP = Ω(2^{(n–1)(2l–1)}), where the scaling behavior of P is given in Formula (7). According to Theorem 4, we can compute the optimal number of iterations as follows: 18T=⌊ π4N/r ⌋~𝒪(N/r)=𝒪(2m+n+2l2).T = \left\lfloor {{\pi \over 4}\sqrt {N/r} } \right\rfloor \~{\cal O}(\sqrt {N/r} ) = {\cal O}\left( {{2^{{{m + n + 2l} \over 2}}}} \right).

The initial angle θ=arcsin(P(0))≈P(0)\theta = \arcsin (\sqrt {P(0)} ) \approx \sqrt {P(0)} for small values of P(0), where P(0)=r2m22(n−1)lP(0) = {r \over {{2^m}{2^{2(n - 1)l}}}}. Each iteration of Grover’s algorithm increases the angle by 2θ, reaching (2T + 1)θ after T iterations. Therefore, the generalized success probability is 19psuccess=sin2((2T+1)θ)≈Θ(1).{p_{success}} = {\sin ^2}((2T + 1)\theta ) \approx \Theta (1).

Therefore, we can obtain (k,y₁, ⋯, y_l) with the probability of Θ(1), where dim(span(y₁, ⋯, y_l)) = n – 1, thereby recovering the keys k, k₁.

When considering the amplitude of the initial state, the initial amplitude is not a uniform superposition state, and there is an oscillation in the amplitude. After analyzing the Grover-meets-Simon algorithm in detail, we know that the Grover-meets-Simon algorithm is an effective algorithm to obtain the correct key with the generalized success probability close to 1 under deferred measurement when moving the measurement of all parallel Simon’s algorithms during the iterative process to the end of the entire algorithm. Specifically, we provide a generalized success probability of the Grover-meets-Simon algorithm, which is independent of the length of the key of the block cipher and the number of parallel Simon’s algorithms. The advantage of the above analysis is that the generalized success probability in any different cases can be calculated without relying on assumptions about the number of plaintext pairs in the classifier or the number of parallel Simon’s algorithms.

Bonnetain et al. [34] proposed a new algorithm that also uses a combination of Grover’s algorithm and Simon’s algorithm for solving the asymmetric search problem of a period. This method can also be applied to the FX construction and can exponentially reduce query complexity. However, they do not provide a tight analysis of the generalized success probability of this algorithm.

Asymmetric Search of a Period. There are two functions F : {0,1}^m × {0,1}ⁿ → {0,1}ⁿ and g : {0,1}ⁿ → {0,1}ⁿ. F is a family of functions and can be written F(i, ·) = f_i(). There exists a unique i₀ ∈ {0,1}^m such that ∀x∈{ 0,1 }n,fi0(x)⊕g(x)=fi0(x⊕s)⊕g(x⊕s).\forall x \in {\{ 0,1\} ^n},{f_{{i_0}}}(x) \oplus g(x) = {f_{{i_0}}}(x \oplus s) \oplus g(x \oplus s)..

In the FX construction shown in Figure 3, g = Enc(i, x) is a secret key function that the adversary can query online to evaluate it, while f_i(x) = E(i, x) is a function that the adversary can evaluate it offline. Then, the function f_i ⊕ g has a period k₁ if i = k, whereas it does not have any period if i ≠ k. Therefore, we can guess whether i is equal to the key k by testing whether f_i ⊕ g has a period. The index i can be tested in superposition due to quantum queries to F and g. Thus, the uniform superposition over indices is created as follows: ∑i∈{0,1}m|i〉⊗|ψg〉\sum\limits_{i \in {{\{ 0,1\} }^m}} | \;i\rangle \otimes \left| {{\psi _g}} \right\rangle , where |ψg〉=⊗l(∑x∈{0,1}n|x〉|g(x)〉).\left| {{\psi _g}} \right\rangle = \mathop \otimes \limits^l \left( {\sum\limits_{x \in {{\{ 0,1\} }^n}} | \;x\rangle |g(x)\rangle } \right).

Similar to the Grover-meets-Simon algorithm, the Alg-PolyQ2 algorithm is also a generalized Grover’s algorithm shown in Figure 2, where 𝒜 is l(≥ n) parallel Simon’s algorithms for solving the asymmetric search of a period, U_f is used to determine whether the rank is n by applying the generalized QGJE, and U₀ changes the phase of the amplitude only for the zero state. Applying 𝒜 ⊗ I₁ on |0〉^⊗m+2nl+1, the initial input state of Alg-PolyQ2 algorithm is 20|φ〉=12m(12n)l∑i∈{0,1}mx1,…,xl∈Fnny1,…,yl∈F2n|i〉(−1)x1·y1⋯(−1)xl·yl|y1,…,yl〉⊗|(fi⊕g)(x1),…,(fi⊕g)(xl)〉|b〉.|\varphi \rangle = {1 \over {\sqrt {{2^m}} }}{\left( {{1 \over {{2^n}}}} \right)^l}\sum\limits_{\scriptstyle i \in {\{ 0,1\} ^m} \atop {\scriptstyle {x_1}, \ldots,{x_l} \in _n^n \atop \scriptstyle {y_1}, \ldots,{y_l} \in _2^n}} | \;i\rangle {( - 1)^{{x_1}\cdot{y_1}}} \cdots {( - 1)^{{x_l}\cdot{y_l}}}\left| {{y_1}, \ldots,{y_l}} \right\rangle \otimes \left| {\left( {{f_i} \oplus g} \right)\left( {{x_1}} \right), \ldots,\left( {{f_i} \oplus g} \right)\left( {{x_l}} \right)} \right\rangle |b\rangle.

Suppose that k is the correct key for the function (f_i ⊕ g)(x).If i = k, the period s is not 0; if i ≠ k, there may be values that are not actual non-zero periods t. For b ∈ {0,1}, compute |b ⊕ 1〉 if dim(span(y₁, ⋯, y_l)) < n; otherwise |b〉 if dim(span(y₁, ⋯, y_l)) = n. Then the initial state can be further written as 21|φ〉=α(∑i∈F2m,i≠kx1,⋯,xl∈F2ny1,⋯,yl∈F2n(−1)x1·y1⋯(−1)xl·yl|y1,⋯,yl〉|(fi⊕g)(x1),⋯,(fi⊕g)(xl)〉|i〉|b〉)+β(∑x1,⋯,xl∈X1y1,⋯,yl⊥s,s≠0(−1)x1·y1⋯(−1)xl·yl|y1,⋯,yl〉|(fi⊕g)(x1),⋯,(fi⊕g)(xl)〉|k〉|b⊕1〉),\matrix{ {|\varphi \rangle = \alpha \left( {\sum\limits_{\scriptstyle i \in _2^m,i \ne k \atop {\scriptstyle {x_1}, \cdots,{x_l} \in _2^n \atop \scriptstyle {y_1}, \cdots,{y_l} \in _2^n}} {{{( - 1)}^{{x_1}\cdot{y_1}}}} \cdots {{( - 1)}^{{x_l}\cdot{y_l}}}\left| {{y_1}, \cdots,{y_l}} \right\rangle \left| {\left( {{f_i} \oplus g} \right)\left( {{x_1}} \right), \cdots,\left( {{f_i} \oplus g} \right)\left( {{x_l}} \right)} \right\rangle |i\rangle |b\rangle } \right)} \hfill \cr { + \beta \left( {\sum\limits_{\scriptstyle {x_1}, \cdots,{x_l} \in {X_1} \atop \scriptstyle {y_1}, \cdots,{y_l} \bot s,s \ne 0} {{{( - 1)}^{{x_1}\cdot{y_1}}}} \cdots {{( - 1)}^{{x_l}\cdot{y_l}}}\left| {{y_1}, \cdots,{y_l}} \right\rangle \left| {\left( {{f_i} \oplus g} \right)\left( {{x_1}} \right), \cdots,\left( {{f_i} \oplus g} \right)\left( {{x_l}} \right)} \right\rangle |k\rangle |b \oplus 1\rangle } \right),} \hfill \cr } where α=12m(12n)l\alpha = {1 \over {\sqrt {{2^m}} }}{\left( {{1 \over {{2^n}}}} \right)^l} and β=12m(12n−1)l\beta = {1 \over {\sqrt {{2^m}} }}{\left( {{1 \over {{2^{n - 1}}}}} \right)^l}.

In the Alg-PolyQ2 algorithm, the above process also satisfies the principle of deferred measurement.

Here, the quantum oracle U_f is defined as follows: Uf:i∈F2m→{0,1}.{U_f}:i \in _2^m \to \{ 0,1\}.

Once we have the superposition |ψ_g〉 and given a quantum oracle access to U_f, we can know if f_i ⊕ g has a period or not without making new queries to g by the test oracle. This test oracle is a subroutine of the quantum oracle U_f. Next, the test oracle can be defined as follows:

|i〉ψg|b〉→test{ |i〉ψg〉|b〉, if (fi⊕g) has no period|i〉ψg〉|b⊕1〉, if (fi⊕g) has a period.\left\langle {|i\rangle {\psi _g}} \right.|b\rangle \buildrel {{\bf{test}}} \over \longrightarrow \left\{ {\matrix{ {\left\langle {|i\rangle {\psi _g}} \right.|b\rangle,\quad {\rm{ }}if{\rm{ }}\left( {{f_i} \oplus g} \right){\rm{ has no period}}} \hfill \cr {\left\langle {|i\rangle {\psi _g}} \right.|b \oplus 1\rangle,{\rm{ }}if{\rm{ }}\left( {{f_i} \oplus g} \right){\rm{ has a period}}{\rm{.}}} \hfill \cr } } \right.