The Longest Common Substring (LCS) poses classical challenges in computer science, pivotal for string processing. Classically, the problem is tackled with linear time algorithms leveraging sufix trees. Recent breakthroughs in the quantum domain have unveiled sublinear solutions for LCS, demanding ˜(2/3) quantum queries. Yet, these strides are tailored for the quantum query model, which treats input as a black box accessible via an oracle. In contrast, in this paper we delve into these challenges within the circuit model of computation. Here, circuit size gauges structural complexity, while depth identifies execution time on a quantum platform. As the query model complexity sets a baseline, any direct quantum circuit implementation yields a depth and size of at least Ω˜(2/3) for LCS. The main result of this paper is the introduction of a quantum algorithm for LCS in the circuit model, which, despite its ˜(3/2) size, achieves a groundbreaking ˜(√) depth, surpassing prior solutions. Notably, our algorithm is streamlined and readily translatable into quantum protocols. Furthermore, we demonstrate its practicality through a quantum circuit implementation operating in (√ log5()) time-steps.
Quantum computing is a rapidly developing field within computer science that utilizes the principles of quantum mechanics to create more powerful computing systems operating in a markedly difer ent way from classical computers. Unlike classical computers, which rely on bits (either 0 or 1) to process information, quantum computing leverages qubits, which can exist in multiple states simultaneously. Additionally, quantum entanglement, a physical phenomenon that allows two or more qubits to perform operations simultaneously, can be used to combine multiple qubits to perform faster and more eficient operations than classical bits. These unique features give quantum computers an advantage over classical ones, particularly in areas such as code-breaking and optimization, allowing them to perform certain calculations at an exceptional speed.
Quantum computing has had a significant impact on the development of algorithms, with some of
the most notable advancements being Shor’s algorithm [
Only recently, text processing and string problems have become a topic of interest within the realm
of quantum computation (see for instance [
In the realm of classical computation, the LCS problem admits a linear time solution [
More interestingly, in [
The eficiency of previous solutions [
The complexity of a quantum algorithm is de facto best expressed in the computational complexity model [18], where the input is encoded as a binary string and supplied to the algorithm, which computes an output string. In such a model, an algorithm is expressed using the quantum Turing machine model [19] or the quantum circuit model [20]. Perhaps, this latter is one of the most widespread among such models, considering that there are several programming languages featuring the circuit formalism, such as IBM’s Qiskit, Microsoft’s Q#, and Google’s Cirq, just to cite a few. The computational complexity of a quantum circuit can be measured by its size (the number of gates) or by its depth (the number of layers). We refer to Section 2.1 for details on the computational model based on quantum circuits and a discussion about the measures used to calculate its complexity.
Thus, given that any quantum oracle comprises at least one gate, and gates are applied sequentially
in an algorithm adhering to the query complexity model, the query complexity of solutions given
1We also mention an algorithm [
˜(5/6)
˜(2/3)
Ω ˜ (5/6)
Ω ˜ (2/3)
˜(3/2)
Ω ˜ (5/6)
Ω ˜ (2/3)
˜(√)
in [
In this paper we present the first quantum algorithm for the LCS problem in the circuit model of computation, providing an actual implementation of a quantum circuit that works in ˜(√) depth, despite its ˜(3/2) size. Specifically, our proposed approach leads to the definition of an efective circuit that requires (√ log4()) depth in the case of binary strings, and (√ log5()) depth in the general case.
At first glance, our result might seem contradictory to that of Le Gall and Seddighin; however, in fact, the comparison of the two results shows how in quantum computation space eficiency can be traded of for time eficiency. While Le Gall and Seddighin access the input by querying a quantum oracle, we have direct access to the input, which is encoded on a circuit register. Instead of claiming the preferability of one model over the other, we aim to draw the reader’s attention to the diferences between them. The query model allows one to study and analyse quantum algorithms without worrying about the technicalities around the construction of any specific oracle, and has been the framework of the first outstanding attempts to design algorithms that exhibit a theoretical advantage against classical ones.
Another significant diference lies in the ways in which the two algorithms access any input string
. In [
In contrast, our algorithm does not rely on a random access oracle, but we assume, as in [
Ultimately, our approach stands apart from the previous results due to its inherent simplicity, which enables us not only to provide a circuit-level blueprint, but also to assess the quantum resources required for its implementation.
The paper is organized as follows. In Section 2, we review some useful preliminaries. Next, in Section 3, we provide an abstract view of the algorithm for solving the LCS problem. Then, in Section 4, we describe an actual implementation of the same algorithm within the circuit-based model. Finally, in Section 5, we briefly draw our conclusions.
We represent a string of length ⩾ 1, over a finite alphabet Σ of size , as a finite array [0 .. − 1], and denote the empty string by . We also denote by [] the ( + 1)-st character of , for 0 ⩽ < , and by [ .. ] the substring of contained between the ( + 1)-st and the ( + 1)-st characters of , for 0 ⩽ ⩽ < . A -substring of a string is any substring of of length . For ease of notation, the ( + 1)-st character of the string will also be denoted by the symbol , so that = 01 . . . − 1. A substring of beginning at position 0 is a prefix of . We use the notation : to indicate the prefix of of length .
For any two strings and of length , we say that and have a common -substring if there exist two indices 0 ⩽ , < − such that [ .. + − 1] = [ .. + − 1]. In particular, when the indices and coincide, we say that and share a -substring at position . The expression · denotes the concatenation of and . Furthermore, given a string of length and a shift 0 ⩽ < , we denote by #» the cyclic rightward rotation of the characters of by positions. More formally, we have #» := [ − .. − 1] · [0 .. − − 1].
Due to space limitations, we assume the reader is familiar with essential concepts in quantum computation, including qubits, bra-ket notation, amplitudes, quantum entanglement, and measurement. Multiple qubits taken together are referred to as quantum registers. Specifically, a quantum register | ⟩ = |0, 1, . . . , − 1⟩ of qubits is the tensor product ⨂︀ =−01 |⟩ of its constituent qubits.
If is an integer value that can be represented as a binary string of length , we use the symbol |⟩ to denote the register ⨂︀
=−01 |⟩ of qubits, where |⟩ takes the value of the -th most significant binary digit of . Thus, the quantum register |8⟩ with 4 qubits is given by |8⟩ = |1000⟩.
Operators in quantum computing are mathematical entities used to represent functional processes that result in the change of the state of a quantum register. Although there is no problem in realizing any quantum operator capable of working in constant time on a quantum register of fixed size, operators of variable size can only be implemented through the composition of elementary gates.
Given a function : {0, 1} → {0, 1}, any quantum operator that maps a register containing the value of a given input ∈ {0, 1} into a register whose value depends on () is called a quantum oracle. A Boolean oracle maps a register |⟩ ⊗ | 0⟩, of size + 1, to the register |⟩ ⊗ | ()⟩. More formally, |, 0⟩ = |, ()⟩. A phase oracle for a function : {0, 1} → {0, 1} takes as input a quantum register |⟩, where ∈ {0, 1}, and leaves its value unchanged, while applying to it a negative global phase only when () = 1, that is, only if is a solution for the function. More formally, |⟩ = (− 1)()|⟩. Intuitively, a Boolean oracle is a black-box function that outputs a binary result (0 or 1) based on the input. A phase oracle, instead of giving a classical output, alters the phase of the quantum state if a certain condition is met, flipping its sign. Thus, while the Boolean oracle returns a bit, the phase oracle encodes the result directly into the quantum state’s phase, important for algorithms like Grover’s search.
In this paper we adopt the circuit model of computation [18]. David Deutsch was the first to formulate the idea of the quantum circuit model [26] to encapsulate quantum computations, although, in his original formalization, Deutsch uses the term quantum network.
In fact, quantum circuits are networks composed of wires that carry qubit values to gates that perform elementary operations on qubits. The qubits move through the circuit in a linear fashion, where the input values are written onto the wires entering the circuit from the left side, while the output values are read of the wires leaving the circuit on the right side. At every time step, each wire can enter at most one gate.
Formally, the quantum circuit model constitutes a broader framework than the classical circuit model. As in a classical circuit, the size, or number of gates involved in a quantum circuit, is a measure of its computational complexity, since it represents the number of elementary operations required to execute a given quantum algorithm: the more gates or operators are applied in a circuit, the more complex the operation the circuit is performing. This measure becomes even more meaningful within the quantum framework due to the inherent susceptibility of modern quantum computers to gate errors. As the number of gates increases, the reliability of the final outcome diminishes, necessitating the implementation of error correction methods.
On the other hand, it is imperative to acknowledge that, unlike classical computation, where only one gate can be executed at a time regardless of circuit structure, a quantum computer enjoys the remarkable advantage of concurrently executing two (or more) gates, provided they do not involve the same set of qubits [27, 28]. This characteristic of quantum computation, coupled with superposition and entanglement, underpins quantum supremacy.3
Hence, size does not consistently represent the most precise measure of complexity in quantum computation, often providing only a rough approximation of an algorithm’s intricacy. The complexity of a quantum algorithm depends on various factors, including the types of gates used, qubit connectivity within the quantum processor, and especially the circuit depth — defined as the number of layers required for parallel execution, where a qubit participates in at most one interaction per layer [29]. It is important to note that the depth of a circuit does not necessarily correspond to its size, as gates acting on disjoint sets of qubits can often be applied in parallel.
As quantum gates necessitate implementation time, the depth of a circuit in modern quantum computers approximately correlates with the duration required for the quantum computer to execute the circuit. Consequently, circuit depth serves as a crucial metric to assess the feasibility of running a quantum circuit on a device.4
In addition, enabling the realization of quantum algorithms in the near future with existing technology appears contingent upon the development of shallow-depth quantum circuits [29]. Qubits are susceptible to decoherence, rendering them prone to spontaneous state fluctuations, thereby limiting the duration of feasible operations. Maximizing the utilization of these delicate qubits necessitates the circuit depth reduction [27] and, therefore, the parallelization of circuits.5
In recent years, the complexity of quantum states has emerged as a pivotal quantity of interest spanning various domains, ranging from quantum computing [30] to black hole theory [31]. Reflecting this burgeoning interest, Haferkamp et al. [32] recently validated the Brown and Susskind conjecture [33], asserting that the complexity of quantum circuits typically experiences linear growth with circuit depth over an exponentially protracted period, ultimately reaching saturation when the number of applied gates surpasses a threshold that scales exponentially with the number of qubits.
For the reasons stated above, in this paper, our objective is to provide a solution to the LCS problem,
where the measure of complexity is more directed towards circuit depth rather than size.
3We observe that even in the absence of quantum entanglement, simultaneous operations on all qubits remain feasible.
Utilizing qubits permits concurrent operations per time step. Nevertheless, in theory, a quantum computer comprising
qubits could emulate the functionality of a classical computer outfitted with processors.
4The depth of a circuit is considered the measure of complexity in many quantum languages. See for example https:
//docs.quantum.ibm.com/api/qiskit/0.43/circuit
5It is noteworthy that achieving parallelism within the quantum circuit model mandates the capability to interact with
spatially distant qubits. Various implementations may impose physical constraints on the extent of such interaction.
Nonetheless, recent advancements in quantum computing [
Quantum-LCS(, , ): 1. ℓ ← 0; ← 2. while ℓ < do 3. ← ⌊ (ℓ + )/2⌋ 4. if ∃ , ∈ {0, . . . , − 1} : #» [ .. + − 1] = [ .. + − 1] 5. then ℓ ← 6. else ← − 1
← Quantum test
In this section, we first describe our quantum algorithm for computing the LCS within an abstract model, in order to better understand its design, by defining the quantum oracles involved in the computation, but without giving their actual implementation. Later, we will show that our abstract algorithm requires ˜(√) queries to oracles.6 Subsequently, we will present an actual implementation of our algorithm in the circuit-based computational model. Our algorithm, named Quantum-LCS, comprises a quantum computation-based and a classical computation-based components. Its simple underlying structure is summarized in the pseudocode shown in Figure 1.
The classical part of the computation involves a binary search to determine the length of the longest common substring of and (line 2). During each iteration, the algorithm checks for a common substring of length between and . Let [ℓ .. ] be the interval over which the binary search is restricted during an iteration of the algorithm, and let = ⌊(ℓ + )/2⌋ be its median. The values of ℓ and are initialized to 0 and , respectively. If the iterative test returns a positive answer, then the interval is narrowed to [ .. ], otherwise it is narrowed to [ℓ .. − 1]. The search identifies the length of the longest common substring in (log()) steps.
The quantum part of the algorithm implements the test of line 4. In what follows, we will focus exclusively on the implementation of such iterative test. Before describing the details of the quantum procedure for the iterative test, we formalize some assumptions we make along the description.
Since a quantum register of dimension log() can take on all values between 0 and − 1, like any binary sequence of the same dimension, for simplicity we will assume that both input strings and have length = 2, for some > 0. We also assume that and end with two diferent special characters, $ and %, respectively, not belonging to the alphabet Σ . These assumptions can be made without any loss of generality, since it would sufice to take the smallest value for which we have < 2 and concatenate the text with 2 − copies of the special character. For instance, if = abaacbcbbca is a text of length 11, we silently concatenate it with 5 copies of the character $, i.e., we assume that = abaacbcbbca$$$$$. This assumption does not afect on the asymptotic complexity, as the resulting string is at most twice as long as the original.
Despite any substring of length can begin at any position of the text, for 0 ⩽ ⩽ − , in this paper we also admit values of between 0 and − 1, thus assuming that a substring of the text can be obtained in a circular way. Even such an assumption can be made without loss of generality, since the last character of and are the special character $ and %, respectively, and therefore no substring obtained circularly can ever be returned as LCS. 6We would like to point out that in counting the number of queries requested by our algorithm, we do not intend to compute its query complexity, since we work within the circuit-based computational approach that does not conform to the constraints of the query-based model.
For the sake of simplicity and due to space constraints, we restrict to circuits algorithms designed for processing binary strings. This further simplification, however, does not lead to any substantial change in our results since, assuming that each character can be represented with (at most) log() bits, it is easy to show that the quantum operators used in the construction of the algorithm would undergo an increase in their complexity at most equal to a factor of log().
Given two strings and , both of length , and a bound ⩽ , the quantum test checks for the presence of a common substring of length between and .
The abstract procedure for the iterative test is outlined in Figure 2. It consists of three phases, each implemented by a quantum sub-procedure: (1) a search phase, (2) a verification phase, and (3) a final check. The output of the iterative test is the output of the final check. In this section we describe in detail the role, structure, and complexity of each of the phases and then discuss the overall complexity of the iterative test.
The search phase makes use of the Grover’s search algorithm [
0 otherwise.
When the values of and are clear from the context, for simplicity we will use the symbol instead of (,). Using this convention, the phase oracle operates so as to achieve the transformation |⟩ = (− 1) ()|⟩, for all ∈ {0, 1}log(). In Section 4.1, we show how the phase oracle can be efectively implemented by means of a circuit having depth (log3()).
After (√) iterations of Grover’s algorithm, the procedure returns a potential solution to the problem, such that #» and share a -substring. However, since such a solution may not exist (a case in which the search would return a random state 0 ⩽ < ), it is necessary to run the subsequent verification procedures to check whether the returned state is an actual solution of the function.
Assuming #» and share a -substring, the verification phase again makes use of Grover’s search #» algorithm in order to identify a position within the strings such that [ .. +− 1] = [ .. +− 1]. In this case, the input black box to the algorithm is a phase oracle implementing the function (,) : {0, . . . , − 1} × { 0, . . . , − 1} × { 0, . . . , − 1} →− { 0, 1}, where, for all strings and , and for all 0 ⩽ , , < , we have: (,)(, , ) = (2) Therefore, the oracle operates so as to achieve the phase transformation |⟩|⟩|⟩ = (− 1) (,,)|⟩|⟩, for all , , ∈ {0, 1}log(). In Section 4.1, we provide an implementation of the phase oracle that operates in (log3()) time.
Even in this case, after (√) iterations of Grover’s algorithm, the procedure returns a potential position , such that #» [ .. + − 1] = [ .. + − 1].
Quantum test: 1. ← get a random such that #» and (possibly) share a -substring 2. ← get a random such that #» [ .. + − 1] is (possibly) equal to [ .. + − 1] 3. check if #» [ .. + − 1] is equal to [ .. + − 1]
Ultimately, the quantum test ends by checking whether the two substrings of length beginning at position of the strings #» and are indeed equal. Such a final check can be exactly computed through a single execution of the quantum oracle implementing the function defined in (2).
The whole structure of the quantum test is depicted in Figure 2. The first two phases require both (√) queries to the oracles and , respectively, while the last check requires a single query to the Boolean oracle . Therefore, the quantum iterative test requires (√) queries.
We point out that, when a solution exists, both the search and verification phases may fail with a probability (1/), due to the internal randomness of Grover’s algorithm. When the search phase or the verification phase returns a value that is not a solution of the respective function, the final check fails by returning the value 0. In such a case, we can simply repeat the whole test an arbitrary constant number of times in order to suppress the probability of failure. The test terminates when a common substring is found, or when such an attempt fails an arbitrary number of times.
The overall number of queries needed to solve the problem is (√ log()), since the execution of the quantum iterative test requires (√) queries and the binary search for the length of the LCS requires (log()) iterations.
In this section we provide an actual implementation of the iterative test shown in Figure 2 within the circuit-based computational model. The purpose of this translation is to provide a direct implementation of the algorithm in a quantum computer and evaluate the actual resources required.
The three steps of the iterative test are implemented by the three circuits reported in Figure 5. Only three operators are used as building-blocks in the three circuits: the circular shift (ROT) operator, the shared fixed substring checking (SFC) operator, and the fixed prefix matching (FPM) operator (see Table 2). We observe that the oracles used in the actual circuits of Fig.5 are implemented as Boolean oracles rather than as phase oracles. These are denoted as and instead of and , respectively. However, we recall that initializing the output register of a Boolean oracle to the value |−⟩ allows it to behave like a phase oracle.
For lack of space, in this section we only provide a brief overview of how these operators are structured, referring the reader to the appropriate references.
A circular shift operator (or rotation operator) ROT applies a rightward shift of positions to a
register of qubits for a fixed parameter 0 ⩽ < . Thus, the element at position is moved to
position ( + ) mod . Such an operator has been efectively used in other quantum text searching
algorithms [
In our implementation we make use of the controlled version of the circular shift operator, which applies a circular rotation of a number of positions, depending on an input value such that 0 ⩽ < .
( log()) ( log()) ( log())
(log2()) (log3()) (log3())
(log2()) (log4()) (log4()) [34] [35, 25] [35, 25]
More formally, for all ∈ {0, 1} and all ∈ {0, 1}log(), the controlled circular shift operator performs the mapping ROT|⟩|⟩ = |⟩| #» ⟩.
The controlled variant of the circular shift operator can be implemented by means of a well-known
technique [
The shared fixed substring checking (SFC) operator addresses the following simple string matching problem, in which, given two strings and , both of length , and a bound ⩾ 0, one wants to check whether and share a common -substring, i.e., if there exists a position , with 0 ⩽ < − , such that [ .. + − 1] = [ .. + − 1]. In other words, the SFC operator computes the function (,)(, ) for the special case where = 0, that is, does not undergo any cyclic rotation. More formally, given a bound ⩽ , the SFC operator, for all , ∈ {0, 1} and ∈ {0, 1}log(), is defined by SFC|⟩|⟩|⟩|0⟩ = |⟩|⟩|⟩| (,)(0, )⟩.
The construction of a quantum circuit implementing the SFC operator has been recently proposed in [35], where the authors provide a circuit with a (log3()) depth in the case of binary input strings and a circuit with a (log4()) depth in the general case. The size of the circuit is ( log()) in both cases. We do not provide here further details on the construction of the operator but refer to [35] for any structural aspects of the corresponding circuit.
Given two strings and , both of length , and a bound ⩽ , the fixed prefix matching (FPM) operator performs a simple check to determine whether the first characters of the string match their counterparts in the string . Roughly speaking, the FPM operator checks if : = :. More formally, for all , ∈ {0, 1}, and all ∈ {0, 1}log(), the FPM operator is defined by
FPM|⟩|⟩|⟩|0⟩ = |⟩|⟩|⟩| (,)(0, 0, )⟩.
The construction of a quantum circuit implementing the FPM operator has also been recently proposed in [35], where the authors give a circuit with a depth of (log3()) for the case of binary input strings and a circuit with a depth of (log4()) for the general case. The size of the corresponding circuit is ( log()) in both cases.
We are now ready to describe the quantum circuits that implement the three phases of the quantum iterative test. All circuits make use of two registers |⟩ and |⟩, both of size , which we assume to contain the characters of the two input strings and , respectively. We also assume that these registers are already stored in a quantum memory and do not need initialization. All circuits involve the presence of an input register |⟩, of size ⌈log()⌉ ⩽ log(), containing the binary representation of the bound ⩽ . The initialization of such input register requires (log()) time. The output of the computation, for all circuits, is stored in the |⟩ register consisting of a single qubit. |⟩ |⟩ |⟩ |⟩ |⟩
|⟩ ||⟩⟩ ||||###»»»⟩⟩⟩⟩ ||⟩⟩ ||⟩⟩ ||0⟩( #»,)(0, )⟩ ||00⟩⟩ |⟩ |⟩ |⟩ |0⟩ |0⟩ |⟩ |⟩ |⟩ | ( #»,)(0, )⟩ | ( #»,)(0, )⟩ |⟩ | #» ⟩ |⟩ |⟩ |0⟩ | ( #»,)(0, )⟩ |⟩ |⟩ |⟩ |⟩ |0⟩ | ( #»,)(0, )⟩ ← initialization ← application of ROT|⟩|⟩ ← application of SFC|⟩|⟩|⟩|⟩ ← application of CX|⟩|⟩ ← application of SFC†|⟩|⟩|⟩|⟩ ← application of ROT†|⟩|⟩ |||||⟩⟩⟩⟩⟩ |||||⟩⟩⟩⟩⟩ ||||||#####»»»»»⟩++++⟩⟩⟩⟩ ||||||###»»»⟩⟩⟩⟩⟩⟩ |||||⟩⟩⟩⟩⟩ |||||0000⟩⟩⟩⟩( #»+, #»)(0, 0, )⟩ |||||00000⟩⟩⟩⟩⟩ |||⟩⟩⟩ |||⟩⟩⟩ || ##»» ++⟩⟩⟩ ||#»⟩⟩ |||⟩⟩⟩ |||00⟩⟩( #»+, #»)(0, 0, )⟩ ||| ((( ###»»»+++,,, ###»»»)))(((000,,, 000,,, )))⟩⟩⟩ |⟩ |⟩ | #» ⟩ |⟩ |⟩ |0⟩ | ( #»+, #»)(0, 0, )⟩ |⟩ |⟩ |⟩ |⟩ |⟩ |0⟩ | ( #»+, #»)(0, 0, )⟩ initialization application of ROT|⟩|⟩ application of ROT|⟩|⟩ application of ROT|⟩|⟩ application of FPM|⟩|⟩|⟩|⟩ application of CX|⟩|⟩ application of FPM†|⟩|⟩|⟩|⟩ application of ROT†|⟩|⟩ application of ROT†|⟩|⟩ application of ROT†|⟩|⟩
The circuit for the search phase is depicted on the top of Figure 5. It makes use of the additional |⟩ register, of size log(), which holds the rotation values of the string . It is initialized to |+⟩log(), in order to maintain, at the initial stage, the superposition of all possible rotation values between 0 and − 1. The |⟩ register, of a single qubit initialized to |0⟩, stores the output of the SFC operator.
The core of the quantum procedure involves applying Grover’s search algorithm on the phase oracle, , of the (,) function, as defined in (1). The Boolean oracle takes the two registers |⟩ and |⟩ as input, and is implemented through the ROT and SFC operators. The output of the SFC operator is stored in the qubit |⟩, while the output of is stored on the |⟩ register, which is initialized to |−⟩ to make to behave as a phase oracle.
In Figure 3, we show the evolution of the 6 registers involved in the computation of the Boolean oracle , namely |⟩|⟩|⟩|⟩|⟩ and |⟩ (see also Figure 5).
Specifically, the application on the register |⟩ of the ROT operator, controlled by the register |⟩, allows |⟩ to be modified so that it contains the superposition of all its possible cyclic rotations. Next, the application of the SFC operator on the registers |⟩, |⟩, and |⟩ allows the procedure to identify a possible position (if any) for which #» [ .. + − 1] = [ .. + − 1]. Note that the application of the SFC operator is done in parallel, for all possible rotations of the register |⟩. The oracle completes its computation by saving the output of the SFC operator into the |⟩ register and uncomputing the entire process by applying the inverse operators in their reverse order.
Regarding the depth of the circuit for the search phase, we can observe that the ROT and the ||⟩⟩ lloogg(()) k ||⟩⟩ ec |⟩ h C |⟩ l ian |⟩ F ⏞ rot rot rot
SFC operators have a depth equal to (log2()) and (log3()), respectively. The same is true for their inverse, while the Grover’s difuser is executed in (log(log())) time. Since Grover’s search requires iterating the phase oracle and difuser a number of times equal to (√), we state that the depth of circuit implementing the search phase is (√ log3()).
Once the value has been returned by the search phase, the circuit for the verification phase again #» uses Grover’s search algorithm to identify the position , with 0 ⩽ < , for which [ .. + − 1] = [ .. + − 1] holds. The circuit, depicted in the middle of Figure 5, uses the |⟩ register containing the output of the search phase, and the |⟩ register, holding the position values of the two strings, initialized to |+⟩log(), in order to maintain, at the initial stage, the superposition of all possible position values between 0 and − 1. The qubit |⟩, initialized to |0⟩, stores the output of the operator.
At the heart of the quantum circuit lies the application of Grover’s search algorithm to the function (,,), as outlined in equation (2). The quantum phase oracle, , for the function (,,) operates on the input register |⟩, and is executed using the ROT and the FPM operators. The output from the FPM operator is stored in the register |⟩, while the output from the oracle gets stored in the |⟩ register, a single qubit that is initially set to |−⟩ in order to make to behave as a phase oracle rot rot rot
rot rot rot
Diff within the Grover’s search procedure.
In Figure 4, we outline the evolution of the seven registers (|⟩, |⟩, |⟩, |⟩, |⟩, |⟩, and |⟩) involved in the computation of the Boolean oracle , as depicted in Figure 5.
Specifically, we apply the ROT operator on the register |⟩, controlled by the register |⟩, allowing |⟩ to be modified in order to contain the cyclic rotation of positions. Next, an application of the rotation operator controlled by register |⟩ to both registers |⟩ and |⟩ allows the two strings to be rotated by a shift of the same value. Note that, after the application of these operators, the register |⟩ contains the superposition of all possible rotations of #» , while |⟩ contains the superposition of all its possible rotations. Formally, the application of the FP1M], fooprearlaltpoorsosniblteherorteagtiisotnesrso|f#⟩» anadnd|⟩. allows the procedure to check if #» [0 .. − 1] = [0 .. − The oracle completes its computation by saving the output into the |⟩ register and uncomputing the entire process by applying the inverse operators in reverse order.
Regarding the depth of the circuit for the verification phase, we observe that three ROT operators have a depth equal to (log2()), as well as their inverse. The FPM operator is executed in (log3()) time-steps, while the Grover’s difuser on the register |⟩ requires (log(log())) time-steps. Since Grover’s search requires (√) iteration, we can conclude that the depth of the circuit implementing the verification phase is equal to (√ log3()).
The circuit for the final check takes as input two registers, |⟩ and |⟩, containing the output of the search phase and the verification phase, respectively, and checks whether #» [ .. + − 1] = [ .. + − 1]. Such a circuit is obtained by means of the Boolean oracle . Thus, the resulting circuit implementing the final check has a depth equal to (log3()).
Ultimately, the three phases achieve (√ log3()), (√ log3()), and (log3()) time-steps, respectively. This allows us to state that the quantum iterative test has a (√ log3()) overall depth and that, therefore, the Quantum-LCS algorithm admits an efective implementation that achieves a (√ log4()) depth in the case of binary strings. This complexity grows by a logarithmic factor, reaching (√ log5()) in the general case.
In this paper we provided a concrete implementation of the first quantum algorithm for the LCS problem within the circuit model, achieving a significant milestone in the development of practical quantum algorithms. While previous works in the query model ofer valuable theoretical insights, our approach emphasizes the importance of circuit-based implementations for real-world applications, where practical considerations such as quantum resource requirements and hardware constraints play a crucial role. By directly encoding the input into the circuit register, we achieve a time complexity of (√ log4()), highlighting the trade-ofs between time and space eficiency in quantum computation. Our results not only advance the state of quantum algorithms for LCS but also highlight the broader implications for circuit-based quantum computing, where optimizing resources is essential. Future work will continue to explore these trade-ofs further and aim to refine quantum algorithms for practical deployment on quantum hardware.
We are confident that a similar approach could be used to develop a quantum solution for the Longest Palindromic Substring (LPS) problem with comparable computational complexity. In future work, we will focus on this goal, aiming to extend our findings to address the LPS problem with equivalent eficiency. [15] S. Burkhardt, J. Kärkkäinen, Fast lightweight sufix array construction and checking, in: R. A.
Baeza-Yates, E. Chávez, M. Crochemore (Eds.), Combinatorial Pattern Matching, 14th Annual Symposium, CPM 2003, Morelia, Michocán, Mexico, June 25-27, 2003, Proceedings, volume 2676 of Lecture Notes in Computer Science, Springer, 2003, pp. 55–69. URL: https://doi.org/10.1007/ 3-540-44888-8_5. doi:10.1007/3-540-44888-8\_5. [16] A. Montanaro, Quantum pattern matching fast on average, Algorithmica 77 (2017) 16–39. URL: https://doi.org/10.1007/s00453-015-0060-4. doi:10.1007/s00453-015-0060-4. [17] A. S. Arora, A. Coladangelo, M. Coudron, A. Gheorghiu, U. Singh, H. Waldner, Quantum depth in the random oracle model, in: Proceedings of the 55th Annual ACM Symposium on Theory of Computing, ACM, 2023. URL: https://doi.org/10.1145%2F3564246.3585153. doi:10. 1145/3564246.3585153. [18] R. Cleve, An introduction to quantum complexity theory, in: Quantum Computation and Quantum Information Theory, WORLD SCIENTIFIC, 2001, pp. 103–127. URL: https://doi.org/10. 1142%2F9789810248185_0004. doi:10.1142/9789810248185_0004. [19] E. Bernstein, U. V. Vazirani, Quantum complexity theory, SIAM J. Comput. 26 (1997) 1411–1473.
URL: https://doi.org/10.1137/S0097539796300921. doi:10.1137/S0097539796300921. [20] A. C. Yao, Quantum circuit complexity, in: 34th Annual Symposium on Foundations of Computer Science, Palo Alto, California, USA, 3-5 November 1993, IEEE Computer Society, 1993, pp. 352– 361. URL: https://doi.org/10.1109/SFCS.1993.366852. doi:10.1109/SFCS.1993.366852. [21] K. Phalak, A. Chatterjee, S. Ghosh, Quantum random access memory for dummies, 2023.
arXiv:2305.01178. [22] V. Giovannetti, S. Lloyd, L. Maccone, Quantum random access memory, Physical Review Letters 100 (2008). URL: https://doi.org/10.1103%2Fphysrevlett.100.160501. doi:10.1103/ physrevlett.100.160501. [23] V. Giovannetti, S. Lloyd, L. Maccone, Architectures for a quantum random access memory, Physical Review A 78 (2008). URL: https://doi.org/10.1103%2Fphysreva.78.052310. doi:10.1103/ physreva.78.052310. [24] D. K. Park, F. Petruccione, J.-K. K. Rhee, Circuit-based quantum random access memory for classical data, Scientific Reports 9 (2019). URL: https://doi.org/10.1038%2Fs41598-019-40439-3. doi:10.1038/s41598-019-40439-3. [25] D. Cantone, S. Faro, A. Pavone, C. Viola, Quantum circuits for fixed substring matching problems, in: To appear in Proceedings of the 12th Computing Conference, London, United Kingdom, 11-12 July 2024, 2024. To appear. [26] D. Deutsch, Quantum computational networks, Proceedings of the Royal Society of London. A.
Mathematical and Physical Sciences 425 (1989) 73 – 90. URL: https://api.semanticscholar.org/ CorpusID:123073680. [27] C. Moore, M. Nilsson, Parallel quantum computation and quantum codes, SIAM J.
Comput. 31 (2001) 799–815. URL: https://doi.org/10.1137/S0097539799355053. doi:10.1137/ S0097539799355053. [28] F. Green, S. Homer, C. Moore, C. Pollett, Counting, fanout and the complexity of quantum ACC, Quantum Inf. Comput. 2 (2002) 35–65. URL: https://doi.org/10.26421/QIC2.1-3. doi:10.26421/ QIC2.1-3. [29] A. Broadbent, E. Kashefi, Parallelizing quantum circuits, Theor. Comput. Sci. 410 (2009) 2489– 2510. URL: https://doi.org/10.1016/j.tcs.2008.12.046. doi:10.1016/J.TCS.2008.12.046. [30] F. G. Brandão, W. Chemissany, N. Hunter-Jones, R. Kueng, J. Preskill, Models of quantum complexity growth, PRX Quantum 2 (2021) 030316. URL: https://link.aps.org/doi/10.1103/ PRXQuantum.2.030316. doi:10.1103/PRXQuantum.2.030316. [31] L. Susskind, Computational Complexity and Black Hole Horizons, Fortsch. Phys. 64 (2016) 24–43. doi:10.1002/prop.201500092. arXiv:1403.5695, [Addendum: Fortsch.Phys. 64, 44–48 (2016)]. [32] J. Haferkamp, P. Faist, N. B. T. Kothakonda, J. Eisert, N. Yunger Halpern, Linear growth of quantum circuit complexity, Nature Physics 18 (2022) 528–532. doi:10.1038/ s41567-022-01539-6. arXiv:2106.05305. [33] A. R. Brown, L. Susskind, Second law of quantum complexity, Phys. Rev. D 97 (2018) 086015. URL: https://link.aps.org/doi/10.1103/PhysRevD.97.086015. doi:10.1103/PhysRevD.97.086015. [34] A. Pavone, C. Viola, The quantum cyclic rotation gate, in: G. Castiglione, M. Sciortino (Eds.), Proceedings of the 24th Italian Conference on Theoretical Computer Science, Palermo, Italy, September 13-15, 2023, volume 3587 of CEUR Workshop Proceedings, CEUR-WS.org, 2023, pp. 206–218. URL: https://ceur-ws.org/Vol-3587/4071.pdf. [35] D. Cantone, S. Faro, A. Pavone, C. Viola, Quantum circuits for fixed substring matching problems, 2023. arXiv:2308.11758, arXiv: 2308.11758.