# Estimating the Effect of Crosstalk Error on Circuit Fidelity Using Noisy
Intermediate-Scale Quantum Devices

Sovanmonynuth Heng  Pukyong National University, Department of AI Convergence,
Busan, South Korea  Myeongseong Go  Pukyong National University, Department of
AI Convergence, Busan, South Korea  Youngsun Han<EMAIL_ADDRESS>Pukyong
National University, Department of AI Convergence, Busan, South Korea

###### Abstract

Current advancements in technology have focused the attention of the quantum
computing community toward exploring the potential of near-term devices whose
computing power surpasses that of classical computers in practical
applications. An unresolved central question revolves around whether the
inherent noise in these devices can be overcome or whether any potential
quantum advantage would be limited. There is no doubt that crosstalk is one of
the main sources of noise in noisy intermediate-scale quantum (NISQ) systems,
and it poses a fundamental challenge to hardware designs. Crosstalk between
parallel instructions can corrupt quantum states and cause incorrect program
execution. In this study, we present a comprehensive analysis of the crosstalk
error effect on NISQ computers. Our approach is extremely straightforward and
practical for characterizing the crosstalk error of various multi-qubit
devices. In particular, we combine the randomized benchmarking (RB) and
simultaneous randomized benchmarking (SRB) protocol to characterize the
crosstalk error from the correlation controlled-NOT (CNOT) gate. We
demonstrate this protocol experimentally on 5- & 7-qubit devices. Our results
demonstrate the crosstalk error model of two different IBM quantum devices
over the experimental week and compare the error variation against the
machine, number of qubits, quantum volume, processor, and topology of the IBM
quantum devices. We then confirm the improvement in the circuit fidelity on
different benchmarks by up to 3.06x via inserting an instruction barrier, as
compared with an IBM quantum noisy device which offers near-optimal crosstalk
mitigation in practice. Most importantly, we provide insight to ensure that
the quantum operation can perform its quantum magic undisturbed. This is
expected to help many quantum fields move closer to the dream of quantum
supremacy and unlock new possibilities in computation.

Keywords

crosstalk error, noisy intermediate-scale quantum (NISQ), quantum device

††preprint: APS/123-QED

##  I  Introduction

(a) IBM Nairobi 7 connectivity

(b) Asynchronous CNOT execution

(c) Simultaneous CNOT execution

Figure 1: Example of the crosstalk effects characterization on IBM Nairobi
7-qubits connectivity on qubit (1,3) (marked by gray lightning) with crosstalk
correlation pairing between qubit (0,1) and qubit (3,5).

Quantum computing may be able to solve certain intractable classical problems.
Companies like IBM, Google, and Rigetti have released their quantum chips with
many qubits such as 433, 53, and 79 qubits, respectively [1, 2, 3]. However,
these chips are classified as noisy intermediate-scale quantum (NISQ)
hardware, which has less than one thousand qubits and suffers from inevitable
noise. IBM Cloud now offers could-based services with 5-133 qubits, and
services with more than a thousand qubits may appear in the next few years
according to the IBM roadmap [4, 5, 6]. Moreover, quantum information
processors (QIPs) have demonstrated 1 and 2-qubit quantum operations with
error rates below the threshold required for fault-tolerant quantum
computation (FTQC) [7, 8, 9]. A major obstacle to achieving similar low error
rates in large and integrated quantum processors is the ability to maintain
the crosstalk error [10, 11, 12].

Crosstalk can increase error rates both for individual qubits and across
different qubits, in which case errors are correlated [10, 13, 14]. Such
correlations make error correction difficult. Optimizing the power of quantum
error correction (QEC) requires an understanding of and strict control of
crosstalk errors. In addition, it is one of the major sources of noise in
superconducting and also trapped-ion devices [14]. It can corrupt the qubit
state when multiple quantum operations are executed simultaneously. It also
has a significant impact on the quantum gate error. For instance, an increase
of CNOT errors up to 3 times caused by crosstalk on IBMQ Casablanca [15],
while the CNOT errors increase up to 11 times caused by crosstalk on IBMQ 20
Poughkeepsie [13]. Different protocols were proposed in [16, 17, 18, 19, 20,
21] to detect and characterize crosstalk in quantum devices. After we assess
crosstalk, we can introduce different mitigation techniques such as modifying
simultaneous CNOT operations with high crosstalk error rate to execute
sequentially while trading off an increase in depth and decoherence time [22,
23, 20, 24].

Through an analysis of real quantum computer historical calibration data from
different IBM devices, we observe how device crosstalk error rates correlate
between different devices and how they correlate with the ordering of the
qubit connectivity. We discover some correlations in which the same
correlation pair in the same device offers different crosstalk error rates
than the revised of those correlation pairs, which indicates that they may
share the same qubit, control, or other infrastructure. Shared infrastructure
by devices could be a potential failure point for users looking for reliable
execution of their programs on NISQ quantum devices. For this reason, we may
prefer to avoid using devices that may share all or some of the same
infrastructure. We also note that many of the calibration changes do not
correlate to periods when the devices might have been offline, which
represents unknown reasons for the calibration changes. However, changes to
the control hardware or software have an important impact on the dependability
of NISQ quantum computers.

In this work, we first introduce ways to characterize a crosstalk error using
simultaneous randomized benchmarking (SRB) protocol [25]. We then model the
crosstalk error model variation on each device during an experimental week.
Second, we evaluate the crosstalk error model on different devices in terms of
machine, number of qubits, quantum volume, processor, and topology. Finally,
we insert crosstalk error pairs on different devices to show their impact on
output circuit fidelity. We also demonstrate the fidelity improvement on
various quantum circuit benchmarks and compare it with the results when an
instruction barrier is inserted between the simultaneous crosstalk error pair.
To this end, the following contributions are made in this paper.

  * •

We validate the presence of crosstalk on two different IBM quantum devices by
applying randomized benchmarking (RB) and simultaneous randomized benchmarking
(SRB) protocols on several experimental simulations.

  * •

We model and evaluate the dynamic of the crosstalk error models by comparing
the error variations against the machine, number of qubits, quantum volume,
processor, and topology of the IBM quantum devices.

  * •

We demonstrate its impact on the output fidelity and the improvement of the
circuit fidelity on various quantum benchmarks with up to 3.06x with the
insertion of an instruction barrier.

This paper is organized as follows. Section II briefly discusses the
background noise in the NISQ computers, especially crosstalk errors. Section
III introduces related works on crosstalk error characterization using
different techniques that motivate our study. Section IV explains our
methodology for addressing crosstalk on different devices. Section V presents
a detailed evaluation of the crosstalk error rate results. Section VI
discusses the limitations and issues beyond current NISQ devices. We conclude
our study in Section VII.

##  II  Background

This section explains the primer concept of quantum bits (qubits) and quantum
gates, various kinds of noise in NISQ computers, quantum device topologies,
and the crosstalk error in NISQ computers.

###  II.1  Primer on Qubits and Quantum Gates

Quantum bits, or qubits $|\psi\rangle$, represent the fundamental units of
quantum information in quantum computing paradigms. In stark contrast to
classical bits, qubits exhibit the phenomenon of superposition, which enables
them to concurrently exist in states of $|0\rangle$, or $|1\rangle$, and/or
both, until they are subjected to a measurement operation [26, 27, 28].
Quantum gates, which are pivotal components in quantum computing frameworks,
diverge significantly from their classical counterparts. While classical logic
gates operate deterministically based on input states, quantum gates leverage
the unique attributes of quantum mechanics. Quantum gates employ the
principles of superposition and entanglement to execute operations on qubits,
thereby enabling transformations that transcend classical logical constraints
[29, 30, 31]. Prominent among quantum gates are the Hadamard gate, which is a
catalyst for the generation of superposition
$|\psi\rangle=\alpha|0\rangle+\beta|1\rangle$, and the CNOT gate, which
facilitates qubit entanglement $|\psi\rangle=|\psi 1\rangle\otimes|\psi
2\rangle$ as shown in Figure 1(b) and 1(c). These gates serve as quantum
analogs to the classical logic gates, and they manipulate the quantum states
of qubits to affect computational processes.

###  II.2  Noise in the NISQ Computer

The intricacies of noise in NISQ computers unfold across various dimensions,
each contributing to the formidable challenges inherent in quantum
computation. The coherence error [32] reflects the susceptibility of the qubit
to environmental factors and captures the gradual loss of quantum coherence
over time. Measurement errors [33] stem from detector imperfections and signal
noise to compound the challenges of obtaining precise quantum outcomes.
Concurrently, two-qubit gate errors [33] arise from imperfections in the
execution of quantum gates which introduce inaccuracies in state
transformations. Single-qubit gate errors [33] result from imperfections in
the implementation of operations on individual qubits. While decoherence noise
poses a formidable threat, resulting from interactions between qubits and
their external environment. Among the above types, a significant source of
noise is two-qubit gates that face challenges stemming from imperfect
entanglement operations namely crosstalk noise [10, 13, 14]. It exacerbates
errors through unwanted interactions between neighboring qubits during quantum
operations. Effectively addressing these multifaceted noise sources is crucial
to improving the reliability and efficacy of NISQ computers for practical
applications.

###  II.3  Quantum Device Topology

The quantum device topologies of IBM’s Lima 5 [34, 35] and Nairobi 7 [36, 37]
in Figure 2 represent noteworthy advancements in quantum computing
architecture, specifically delineating connectivity patterns within these
quantum processors. These two topologies are popular in research to address
many emerging problems in practical application. Figure 2(a) shows IBM Lima 5
exhibiting a topological configuration characterized by five qubits and their
corresponding interconnections, which reflects the intricacies of quantum
entanglement and gate operations. Similarly, Figure 2(b) shows the IBM Nairobi
7-qubit topology, which manifests an expanded quantum processor with an
intricate connectivity matrix. The connectivity within these devices is
established through two-qubit gates, enabling entanglement operations between
adjacent qubit pairs. The topologies, which are guided by the principles of
QEC and qubit coupling, help to orchestrate quantum computations within the
constraints of physical qubit relations. By elucidating these patterns of
connectivity, these types of quantum device topologies contribute
significantly to our understanding and optimization of quantum algorithms and
error mitigation strategies in the context of emerging quantum information
processing (QIP) technologies [38, 39, 40, 41].

(a) IBM Lima 5

(b) IBM Nairobi 7

Figure 2: IBM quantum devices with its connectivity.

###  II.4  Crosstalk Error in the NISQ

Crosstalk error in quantum computing refers to unwanted interaction or
interference between qubits, during quantum operations [10, 13, 14]. It arises
from the imperfect isolation of quantum components, and it leads to unintended
effects on neighboring qubits, thereby compromising the fidelity of quantum
computations. Characterizing crosstalk errors is paramount to the
comprehensive assessment and improvement of quantum processors.

One prevalent technique for quantifying crosstalk errors is quantum state
tomography (QST) [19], which is employed for crosstalk error characterization
that involves the reconstruction of the full quantum state through a series of
measurements. This technique allows for a detailed examination of the density
matrix, revealing crosstalk-induced deviations from the ideal quantum states.
Positive operator-valued measure (POVM) techniques [19] also contribute to
crosstalk error analysis by characterizing the measurement processes. POVM
enables a more nuanced understanding of measurement-induced errors and
crosstalk effects, enhancing the overall comprehension of the quantum
information processing landscape. Among others, the randomized benchmarking
(RB) protocol [17] is the most straightforward technique as an estimated
protocol in QIP. The RB protocol evaluates the average fidelity of quantum
gates by subjecting them to random sequences of Clifford group gates and
provides a robust measure of the global error rate. The simultaneous
randomized benchmarking (SRB) protocol [18] extends this methodology to
concurrently assess multiple gates of $\mathcal{E}\left(g_{i}\right)$ or
$\mathcal{E}\left(g_{j}\right)$, offering insights into the collective impact
of crosstalk errors on the diverse gate operations of
$\mathcal{E}\left(g_{i}\mid g_{j}\right)$. If the crosstalk error exists
between them, the relation between independent and correlated errors should
comply with $\mathcal{E}\left(g_{i}\mid
g_{j}\right)>\mathcal{E}\left(g_{i}\right)$ or $\mathcal{E}\left(g_{j}\mid
g_{i}\right)>\mathcal{E}\left(g_{j}\right)$.

To calculate the rate of the correlated error to independent error as an
indicator of the crosstalk effect on CNOT pairs, we used the following
equation 1.

$r\left(g_{i}\mid g_{j}\right)=\mathcal{E}\left(g_{i}\mid
g_{j}\right)/\mathcal{E}\left(g_{i}\right)$ (1)

These RB and SRB protocols can be used in as many iterations as possible to
address the most scalable and accurate CNOT error rate because CNOT errors
vary with each calibration on different devices[42, 43, 44].

Figure 3: Schematic implementation of the crosstalk error characterization
using randomized benchmarking (RB) and simultaneous randomized benchmarking
(SRB) protocol. These protocols can be subdivided into three parts, depicted
within the different curly brackets for input, CNOT error detection, and
output. The crosstalk error model can be addressed by detecting each CNOT
error pair with a randomly generated RB and SRB protocol from the crosstalk
error patterns to obtain each Error Per Clifford (EPC) and Error Per Gate
(EPG).

##  III  Related Work and Motivation

Crosstalk error has been studied extensively in recent years with its
opportunity in terms of mitigation [16, 17, 18, 45]. Some studies have
characterized, modeled, and analyzed crosstalk errors by applying the benefit
of the simultaneous randomized benchmarking (SRB) protocol [17, 21, 37, 46].
Moreover, the techniques used in studies [16, 11, 47, 48] to detect or
characterize crosstalk error involve quantum tomography methods such as gate
set tomography, idle tomography, process tensor tomography, and parallel
tomography. However, some methods based on process tomography involve a
process matrix having significant computational complexity to measure
crosstalk errors, and it is difficult to distinguish between crosstalk errors
reliably [18]. However, [19] employed the quantum mechanics physiology of the
positive operator-valued measure (POVM) to quantify crosstalk error and define
the nature of the error. Similarly, [10] was measured and characterized
crosstalk by focusing on its impact on the gate performance in quantum
systems, particularly in the context of simultaneous gate operations on
superconducting qubits.

However, most of the aforementioned studies [16, 17, 18, 20, 21, 19, 46, 45]
were conducted ultimately to apply their proposed mitigation technique. As a
result of this simplicity, these methods may not comprehensively address the
intricate dynamics of crosstalk errors and their impact on different devices.
In addition, [16, 17, 18, 20, 21, 19] are out-of-date data since crosstalk
error is a very emerging type of error that requires up-to-date data to
address its effect from real machines with detailed analysis. In light of this
study [19], it becomes evident that a single qubit crosstalk error is too
small to address or interfere with the quantum computation. The trade-off
between the number of qubits, resource consumption, the difficulty of
characterization, and the crosstalk effect. The problem we want to address in
our study is not about the mitigation technique; the most challenging first
task is to realize how much error rate on each pair and how much error rate we
will face if we do not mitigate it. Moreover, we believe that not all
crosstalk error rates on different devices of multiple qubits are created
equal and there are many different factors to take into account which we will
demonstrate in this study.

##  IV  Methodology

In this section, we will discuss the overall protocol we used to characterize
the crosstalk error for different devices and the detailed technique used for
crosstalk detection and implementation with the RB & SRB protocols.

###  IV.1  Overall Protocol

To characterize the effect of the crosstalk error model on quantum devices, we
follow the RB and SRB protocols which we segment into three distinct phases
namely input, CNOT error detection, and output. These components are
delineated for discussion within the protocol, as illustrated in Figure 3.

To address the crosstalk error, we first select the qubit topology of the
quantum device such as IBM Lima or IBM Nairobi, as shown in Figure 2 or
another quantum device as needed. We also analyze the pattern based on the
selected topology to address the crosstalk error correlation pairs as input to
another step in the protocol. To analyze the pattern of crosstalk error for
each topology, Khadirsharbiyani et al. [49] stated that if two qubits do not
have simultaneously running CNOTs, no crosstalk occurs. Hence, we use these
crosstalk rules of no duplicate qubits in our experiment. For instance, Figure
2(b) shows IBM Nairobi with a 7-qubit topology. The pattern of the crosstalk
error pairing with [0, 1] would be [0, 1] and [3, 5], [0, 1] and [4, 5], [0,
1] and [5, 6], and so on. The pattern that does not have a crosstalk error
would be [0, 1] and [0, 1] or [0, 1] and [1, 2], since these pairs are
redundant for qubit (0 and 1), and qubit (1), respectively. By following this
rule for all crosstalk error correlation pairs, we derive the crosstalk error
pattern of IBM Nairobi.

Then, the quantum circuit layer for the RB and SRB protocols is generated
using the input as a crosstalk error pattern. Each iteration of CNOT error
detection involves the use of two RB and one SRB quantum circuit layer. When
two RB quantum circuit layers are employed, one layer corresponds to the first
pair of qubits and the other layer corresponds to the second pair of qubits.
The simulation randomly selects two qubits from several available qubits for
the Clifford group gates, which results in only two qubits being used.
Similarly, the SRB quantum circuit layer requires the random selection of four
qubits for the Clifford group gates. Subsequently, the Error Per Gate (EPG)
for the CNOT gate errors per iteration is calculated. The experimental setup
can accommodate as many iterations as are feasible to enhance accuracy. Upon
the completion of each iteration, both the RB and SRB circuit layers yield
their respective EPG values. To calculate the EPG, the initial step involves
computing the average Error Per Clifford (EPC) for either the RB or SRB
circuit layers. In the RB experiment, the Clifford group gates and their
inverse gate sequences are randomly sampled, and the average EPC is then
derived using the $pref$ parameter (where $pref$corresponds to a reference
parameter with d = 2 for a single qubit) [50]. Subsequently, the EPG for the
CNOT gate in each iteration is calculated. Previous studies [51, 52] have
indicated that each circuit layer decomposition has on average 1.5 CNOT gates
per Clifford group gate and reported as an upper bound on the EPG as roughly
equivalent to EPC/1.5.

Using the EPG results from each iteration, we can finally calculate the
average output of the EPG of the CNOT errors for the two RB and the single SRB
quantum circuit layers, denoted as $Avg(EPG_{RB1})$, $Avg(EPG_{RB2})$, and
$Avg(EPG_{SRB})$, respectively. The $Avg(EPG_{RB1})$ and $Avg(EPG_{SRB})$
values are used to determine the crosstalk error rate $r(SRB)$ and assess the
dynamic occurrence of crosstalk error on specific error correlation pairs
within the topology. If the summation of $Avg(EPG_{RB1})$ and $Avg(EPG_{RB2})$
over $Avg(EPG_{RB1})$ is found to be less than $Avg(EPG_{SRB})$ alone, then it
can be inferred that there is no presence of crosstalk. Otherwise, a crosstalk
error occurs and its rate is $r(SRB)$ which is equivalent to $Avg(EPG_{SRB})$
over $Avg(EPG_{RB1})$.

Data:

$bg$: basic gates,

$nQ$: number of qubits,

$nS$: number of seeds,

$nC$: number of Clifford group gates,

$P1$: crosstalk correlation pair 1,

$P2$: crosstalk correlation pair 2

Result:

$EPG_{RB1}$: Randomized Benchmarking Pair 1,

$EPG_{RB2}$: Randomized Benchmarking Pair 2,

$EPG_{SRB}$: Simultaneous RB between Pair 1 & 2

for  _$pair1$ $\in$ $P1$_ do

for  _$pair2$ $\in$ $P2$_ do

for  _$r$ $\in$ 3_ do

if  _$r$ == 0_ then

$nQ$ = 2;

$pattern$ = [pair1];

$EPC_{RB1}$ = ($bg$, $nQ$, $nS$, $nC$, $pattern$);

$EPG_{RB1}$ = $EPC_{RB1}$ / 1.5;

else if  _$r$ == 1_ then

$nQ$ = 2;

$pattern$ = [pair2];

$EPC_{RB2}$ = ($bg$, $nQ$, $nS$, $nC$, $pattern$);

$EPG_{RB2}$ = $EPC_{RB2}$ / 1.5;

else

$nQ$ = 4;

$pattern$ = [pair1, pair2];

$EPC_{SRB}$ = ($bg$, $nQ$, $nS$, $nC$, $pattern$);

$EPG_{SRB}$ = $EPC_{SRB}$ / 1.5;

end if

end for

end for

end for

ALGORITHM 1 CNOT Error Detection

###  IV.2  Crosstalk Error Characterization

To characterize the crosstalk error in IBM quantum devices, we first must
address each CNOT error correlation pair for the crosstalk error pair.
Algorithm 1 describes the operation of the RB and SRB protocols to detect each
CNOT error on different IBM quantum devices. The algorithm begins by deciding
the necessary input components such as basic gates (bs), number of qubits
(nQ), number of seeds (nS), number of Clifford group gates (nC), crosstalk
correlation pair 1 (P1), and crosstalk correlation pair 2 (P2), which are
generated according to the connectivity of the selected quantum device or
topology. After completing this process, we use an experimental quantum
circuit layer of RB and SRB to calibrate the EPC and EPG. Then, we are able to
analyze whether or not the crosstalk error occurs on that specific correlated
pair of qubits. For the first iteration of the CNOT error detection, we first
address the two RB circuit layers in two separate 2-qubit crosstalk
correlation pairs ([P1] and [P2]) and one SRB circuit layer between the
4-qubit crosstalk correlation pairs ([P1] with [P2]) simultaneously. If we
want to address the RB circuit layer of $q_{i}$ and $q_{j}$, we use only two
qubits ($nQ$ = 2) that are randomly generated for the circuit layer based on
the pattern of pair1 or pair2 to find the $EPG_{RB1}$ or $EPG_{RB2}$.
Otherwise, we will use four randomly generated qubits ($nQ$ = 4) to find the
$EPG_{SRB}$ between the pattern of pair1 and pair2 simultaneously. Finally,
the algorithm returns the output components of $EPG_{RB1}$ and $EPG_{RB2}$ for
the RB circuit layer and of the $EPG_{SRB}$ for the SRB circuit layer,
depending on the input components of the topology. These outputs are used to
observe whether or not there is a crosstalk error occurs and how severe it is
for that specific pair of crosstalk correlation pairs. For example, if the
$EPG_{SRB}$ is greater than the summation of $EPG_{RB1}$ and $EPG_{RB2}$ over
$EPG_{RB1}$, then there is a crosstalk error rate on top of the CNOT error.

##  V  Evaluation

In this section, we discuss our experimental setup and evaluate the RB and SRB
protocols by presenting our crosstalk error model, daily variation in the
crosstalk error, comparing the dynamic of the crosstalk error model, and
illustrating the impact of crosstalk error on several benchmark circuits using
two IBM quantum devices.

###  V.1  Experimental Setup

To facilitate our evaluation, we present an experimental setup for addressing
the crosstalk error simulation.

Backend: We select two different IBM quantum devices namely IBM Fake LimaV2
with 5 qubits and IBM Fake NairobiV2 with 7 qubits as the backend for the
entire experiment depends on the type of machine, number of qubits, quantum
volume, processor, and topology of the IBM quantum devices.

Experimental Circuit: We use random circuits for randomized benchmarking (RB)
with a default of 1024 shots and $n$ number of qubits based on the device’s
basic gates. In each experimental circuit layer, we randomly combined 150
Clifford group gates in the circuit layer together and ran them for 5
iterations (5 seeds). Each iteration includes 8 subcircuits, so we have 40
subcircuits to execute and calculate the average number of errors per gate
(EPG). Many qubit errors, particularly crosstalk errors, are not apparent in
low-width circuit layers; thus, studying low-width circuit layers is
insufficient. Hence, our goal is to scale the RB and SRB to quantify the
average error in high-width circuit layer sets.

Baselines: A circuit with no simultaneous CNOT is used as the baseline for
comparison with the number of CNOT insertions simultaneously into the circuit.

Benchmark: We select a small-scale circuit as a benchmark that fits in with
our two IBM quantum devices to validate the fidelity, namely grover_n2,
toffoli_n3, cat_state_n4, and Ipn_n5.

(a) Average crosstalk error rate for IBM Lima

(b) Average crosstalk error rate for IBM Nairobi

Figure 4: Average crosstalk error rate model for different IBM quantum
devices. The x-axis and y-axis represent the pairwise correlation between
qubit pair 1 and qubit pair 2, respectively. A lighter purple color indicates
a higher crosstalk error rate on both devices.

###  V.2  Crosstalk Error Models

To illustrate the presence of crosstalk error, we conducted an experiment
using two different IBM quantum devices. For a fair result, Figure 4 presents
the average crosstalk error characterization on each of the IBM quantum
devices over 5 consecutive days. A correlation pair with no color is a
correlation pair with no crosstalk because it contains duplicate qubits, such
as [0, 1] and [0, 1] or [1, 2] and [0, 1], whereas the color purple indicates
a correlation pair with crosstalk error based on its variation mode.

Figure 4(a) shows the average crosstalk error rate for IBM Lima 5. From these
results, we can see that the crosstalk correlation pair with the minor error
pair is [3, 4] and [1, 2] because it is darker in color and the most severe is
[1, 2], and [3, 4] because it is lighter in color. In addition, Figure 4(b)
shows the average crosstalk error rate for IBM Nairobi 7. It shows more
crosstalk correlation pairs because it uses 7 qubits in this topology. The
minor error pairs are [3, 5] and [1, 2] and [4, 5] and [1, 2], whereas the
most severe is the pair [1, 2] and [3, 5].

This result shows that the crosstalk correlation pair varies depending on the
pair selected for the operation. Even the same pair with the reverse of the
qubit pair can also create a very different crosstalk error rate. Notably, the
ascending number of qubit orders usually got a higher crosstalk effect on the
operation. For example, [1, 2] and [3, 4] are more severe than [3, 4] and [1,
2] on IBM Lima 5, and [1, 2] and [3, 5] are more severe than [3, 5] and [1, 2]
on IBM Nairobi 7. Hence, both figures show that the upper-right correlation
pair is lighter in purple, which indicates the severity of the crosstalk error
pair. In contrast, the bottom left is a darker purple, which indicates a minor
crosstalk error pair.

###  V.3  Daily Variation in Crosstalk Error

To illustrate the daily variation in the crosstalk error, we present the daily
variation in the crosstalk error rate for 5 consecutive days starting from
December 4, 2023 to December 8, 2023 using two different IBM quantum devices.
Figure 5 shows the daily variation in the crosstalk error rate on IBM Lima 5
and IBM Nairobi 7. This variation indicates the consistency for the same
device even though we performed experiments on different days. The consistency
refers to the level of the crosstalk correlation pairs behaved among other
pairs. The line on all pairs (both devices) seems to go up and down; this
variation corresponds to the updated calibration data provided by the IBM
cloud services.

Figure 5(a) shows the daily variation in the crosstalk error rate for IBM
Lima. The severe crosstalk correlation pair of [1, 2] and [3, 4] is colored in
the black solid line with the circle markers. The minor crosstalk correlation
pair of [0, 1] and [3, 4] is colored in the black dotted line with the star
markers. The daily variation in the crosstalk error rate varies up to 4.66x on
average (1.2 to 5.6) for IBM Lima.

Figure 5(b) shows the daily variation in the crosstalk error rate for IBM
Nairobi. The severe crosstalk correlation pair of [1, 2] and [3, 5] is a black
solid line with circle markers. The minor crosstalk correlation pair of [1, 3]
and [4, 5]] is colored in the black solid line with square markers. Among
others, we observe that the crosstalk correlation pairs of [0, 1] and [5, 6],
which are shown as the black solid line with the triangle markers are the most
consistent from December 4, 2023 to December 7, 2023. The daily variation in
the crosstalk error rate varies up to 1.68x on average (1.6 to 2.7) for IBM
Nairobi.

This daily variation indicates that not all crosstalk correlation pairs behave
quite the same way on every single day of the experiment. However, it does
indicate that the severe pairs are still severe and the minor pairs are still
minor pairs. We note that the variation for IBM Nairobi 7 is extremely low
compared with the IBM Lima 5. The reason for this is that the IBM Nairobi 7
has greater quantum volume (QV) than the IBM Lima 5 in which the QV is the
metric that measures the capabilities and error rates of quantum devices.

(a) Daily variation of crosstalk error rate for IBM Lima

(b) Daily variation of crosstalk error rate for IBM Nairobi

Figure 5: Daily variation in crosstalk error rate for two different IBM
quantum devices. The x-axis represents the five consecutive days of
experimentation, and the y-axis represents the crosstalk error rate. Each line
with a marker represents a distinguished individual crosstalk correlation pair
on the devices.

###  V.4  Crosstalk Error Model Comparison

Table 1 shows the detailed crosstalk error model for two different IBM quantum
devices in terms of machine, number of qubits (#Qubit), quantum volume (QV),
processor, crosstalk mode, and topology.

Within the IBM Lima architecture, a Falcon r4T configuration contains five
qubits carefully arranged in a T topology connectivity. Contrary to
expectations, the crosstalk error model exhibited by these arrangements
surpasses that observed for the IBM Nairobi device. It is noteworthy that
despite the modest number of qubits (just five) and a quantum volume of eight,
the Falcon r4T configuration on IBM Lima experiences a significantly more
pronounced crosstalk error. The severity of the crosstalk error on this
machine is approximately 2.5x greater than that encountered on the IBM
Nairobi.

Although the new Falcon r5.1H IBM Nairobi processor boasts a configuration of
seven qubits, a standout attribute is its remarkable reduction in crosstalk
errors. Adding to its technical capability, this processor is ingeniously
arranged as an H processor type with higher levels of connectivity. The
driving force behind this notable achievement lies in the quantum volume,
which reaches an impressive 32. This substantial increase in quantum volume
translates into a significant enhancement of error rates, particularly for
crosstalk errors.

After we analyze the comparison between the IBM Lima 5 and IBM Nairobi 7
devices, it is evident that the selection of a specific device holds
significant importance in the execution of various operations, notably in
terms of quantum error mitigation (QEM) and quantum error correction (QEC).
This comparison emphasizes the critical role that the choice of a quantum
device plays in ensuring the efficacy and success of operations that involve
error mitigation and correction within the quantum computing paradigm.

Machine | #Qubits | QV | Processors | Crosstalk Mode | $EPG_{RB1}$ | $EPG_{RB2}$ | $EPG_{SRB}$ | Topology
---|---|---|---|---|---|---|---|---
IBM Lima | 5 | 8 | Falcon r4T | Minor | 0.004 | 0.026 | 1.2 |
Medium | 0.007 | 0.023 | 3.4
Severe | 0.010 | 0.037 | 5.6
IBM Nairobi | 7 | 32 | Falcon r5.11H | Minor | 0.006 | 0.006 | 1.6 |
Medium | 0.0075 | 0.009 | 2.15
Severe | 0.009 | 0.012 | 2.7
Table 1: Characteristics of IBM quantum devices used in our study, IBM Lima
and IBM Nairobi. Each device has a different number of qubits (#Qubit),
quantum volume (QV), processor, crosstalk mode, Error Per Gate of RB and SRB
($EPG_{RB1}$, $EPG_{RB2}$, and $EPG_{SRB}$), and topology.

###  V.5  Impact of Crosstalk Error on Circuit Fidelity

Finally, we evaluate the crosstalk error for the most severe IBM Nairobi to
determine its effect on the circuit fidelity. We choose four benchmarks from
[53] like grover_n2, toffoli_n3, cat_state_n4, and Ipn_n5 with the different
numbers of qubits and gates per benchmark. We prepare all experimental
benchmarks at optimization level 0, which is no optimization for the
simulation to determine the real effect of crosstalk error. The baseline is no
simultaneous CNOTs (no crosstalk) with the experimental benchmarks.

Figure 6 shows the impact of the crosstalk error of the Probability of Success
Trails (PST) on the small-scale benchmarks of 2-5 qubits on the IBM Nairobi
7-qubits device. PST is the real system success probability of the number of
trails with the correct measurement result divided by the total number of
trails when executing on the real simulation. The probability of obtaining the
right output state decreases with an increase in simultaneous CNOTs due to the
inserted crosstalk error. Inserting the crosstalk error decreases the PST by
1.85x on average (up to 3.06x) based on the noise model of the tested pair.
This experimental result is based on the highest crosstalk error pair in the
crosstalk error model for the IBM Nairobi.

In the case of grover_n1, the fidelity decreases by 44.05% compared with the
non-crosstalk case. When we compare the presence of a barrier with no barrier
in terms of output fidelity, the fidelity is improved by 2.06x. In the best
case of toffoli_n3, the fidelity decreases by 30.54% and improves by 3.06x
when a barrier is inserted. In the worst case, such as for cat_state_n4, the
fidelity decreases by 48.35% compared with the non-crosstalk case. In our
comparison in terms of output fidelity and circuit depth with and without a
barrier, the fidelity improves by 1.87x. With Ipn_n5, the fidelity decreases
by 40.21% with an improvement of 2.3x after the barrier is inserted.

As we can see from the figure above, the insertion of a barrier results in an
improvement in output fidelity up to almost the same level as that of no
crosstalk errors. Consequently, this work may lead to a greater interest in
QEM techniques in the future.

Figure 6: Probability of Success Trails (PST) for four benchmarks under
different conditions with only CNOT gate, with simultaneous CNOT gates, and
with barriers along with simultaneous CNOT gates.

##  VI  Discussion and Limitations

A recent trend in QEM techniques [54] is to exploit greater potential from the
crosstalk error with a greater number of mitigation opportunities. Unlike
innovations that are mostly driven by the underlying technologies, our study
takes the first profound direction which is to enable a deeper understanding
of the crosstalk error model for different devices by leveraging the RB and
SRB protocols. Relatively little attention has been paid to this approach for
two main reasons: 1) it is exceedingly difficult to extract useful information
from a large number of circuit and gate sequences, which is the accurate level
at which most operations today operate, and 2) the scalability of the protocol
on all different devices, which is an effective static analysis of a protocol,
becomes quite difficult as the size of the operation matrix grows
exponentially with the number of qubits. We believe that these are two
critical yet difficult problems in the understanding of crosstalk error
characteristics because they prevent the quantum operation from performing
correctly.

Limited Value on a Realistic System: As the data are limited on realistic
systems, specific details about the current state of IBM’s quantum devices and
their performance with real-world data may not be available to all
researchers. The progress made by and specifications for quantum devices is
continuously evolving as research and development in quantum computing
advance. To obtain the most accurate and up-to-date information about IBM’s
quantum devices, including any limited crosstalk error from real systems, we
used a fake device that mimics a real system. Additionally, due to the
expensive runtime cost and the limits of crosstalk metric within the RB and
SRB protocols on a real system, a fake device is preferable for this study.

Noise Beyond the NISQ Systems: In systems other than NISQ systems, the noise
problem in quantum computing becomes more severe as researchers develop
quantum components that are more fault-tolerant. QEC is paramount, and it
demands additional qubits and computational resources. The challenges include
mitigating decoherence and environmental interactions, reducing error rates,
ensuring scalability while managing noise, improving quantum hardware, and
refining noise models for accurate characterization. Strategies such as hybrid
quantum-classical approaches may serve to address these challenges, as the
field focuses on building robust, scalable quantum computers that are capable
of handling errors effectively and enabling practical quantum information
processing. However, our study experiments with the current NISQ devices,
which have a different way of handling errors to explore more in the practical
QIP.

Trade-off between Fidelity and Depth: Although the fidelity is enhanced
because of the insertion barrier, the increase in circuit depth is not
negligible. Fidelity is crucial to reliable quantum computation, and it
represents the accuracy of quantum operations. However, the depth of the
quantum circuit and the number of sequential quantum operations may be
compromised to reduce the crosstalk error. This trade-off arises because
mitigation techniques to counter crosstalk can lead to increased computational
overhead and decreased depth. Striking the right balance is essential, as
sacrificing too much depth may undermine the computational advantage offered
by quantum systems. Researchers are exploring innovative techniques and error-
mitigation strategies that maintain an equilibrium between fidelity and depth
to ensure the efficient functioning of quantum circuits while effectively
suppressing the disruptive effects of crosstalk.

Mitigation Opportunity: Mitigating crosstalk errors provides a valuable
opportunity to enhance the robustness and reliability of quantum information
processing. By identifying and implementing effective mitigation strategies,
researchers can significantly minimize the impact of crosstalk, thereby
improving the overall performance of quantum circuits. Opportunities for
mitigation crosstalk include the development of error correction codes,
optimized control mechanisms, and advanced calibration techniques. Moreover,
leveraging QEC methods can help counteract the undesirable effects of
crosstalk by preserving the integrity of quantum states during computation. As
quantum computing technologies advance, exploring novel mitigation
opportunities will be crucial to unlocking the full potential of quantum
systems and ensuring their viability in practical applications in the future
to bridge between NISQ and FTQC.

##  VII  Conclusion and Outlook

In this work, we leverage the RB and SRB protocols to quantify the effect of
crosstalk errors on the NISQ computers. The RB and SRB protocols enable the
accurate estimation of crosstalk errors by measuring average gate performance
by running sequences of random Clifford group gates that should return the
qubits to their initial state simultaneously. This provides an estimation of
the error for the two-qubit crosstalk correlation error pair on different
quantum devices in a systematic manner. We provide comprehensive error
information for each device as a crosstalk error model, its daily variation,
and a comparison between the two devices. Additionally, we evaluate the impact
of crosstalk error on several small-scale benchmarks to determine the
improvements in circuit fidelity brought about by the insertion of an
instruction barrier. Our use of RB and SRB protocols could be extended to
different backends and devices by configuring the topology correlation of the
crosstalk error pairs. Our work confirms that these protocols can address the
crosstalk error model on different devices and a straightforward estimation
protocol in a more effective, scalable, and better reconfigurable method.
Future work on analytically bounding the number of iterations could
demonstrate the performance of this method against well-known characterization
techniques. We believe that the results explored in this study would promote
future work in the direction of exploring the crosstalk error model in the
context of producing a better quantum algorithm.

###### Acknowledgements.

This research was partly supported by Quantum Computing based on Quantum
Advantage challenge research (RS-2023-00257994) through the National Research
Foundation of Korea (NRF) funded by the Korean government (MSIT) and Institute
for Information & communications Technology Planning & Evaluation (IITP) grant
funded by the Korea government (MSIT) (No. 2020-0-00014, A Technology
Development of Quantum OS for Fault-tolerant Logical Qubit Computing
Environment).

## References

  * Choi [2023] C. Q. Choi, Ibm’s quantum leap: The company will take quantum tech past the 1,000-qubit mark in 2023, IEEE Spectrum 60, 46 (2023).
  * Arute  _et al._ [2019] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. Brandao, D. A. Buell, _et al._ , Quantum supremacy using a programmable superconducting processor, Nature 574, 505 (2019).
  * Gustafson  _et al._ [2023] E. J. Gustafson, A. C. Li, A. Khan, A. Kahn, J. Kim, D. M. Kurkcuoglu, M. S. Alam, P. P. Orth, A. Rahmani, and T. Iadecola,  _Preparing quantum many-body scar states on quantum computers_ , Tech. Rep. (Fermi National Accelerator Lab.(FNAL), Batavia, IL (United States), 2023).
  * Riel [2021] H. Riel, Quantum computing technology, in  _2021 IEEE International Electron Devices Meeting (IEDM)_ (IEEE, 2021) pp. 1–3.
  * Xu and Szefer [2023] C. Xu and J. Szefer, Long-term analysis of the dependability of cloud-based nisq quantum computers, in  _Proceedings of the 18th International Conference on Availability, Reliability and Security_ (2023) pp. 1–6.
  * Alvarado-Valiente  _et al._ [2023] J. Alvarado-Valiente, J. Romero-Álvarez, E. Moguel, J. García-Alonso, and J. M. Murillo, Technological diversity of quantum computing providers: a comparative study and a proposal for api gateway integration, Software Quality Journal , 1 (2023).
  * Noiri  _et al._ [2022] A. Noiri, K. Takeda, T. Nakajima, T. Kobayashi, A. Sammak, G. Scappucci, and S. Tarucha, Fast universal quantum gate above the fault-tolerance threshold in silicon, Nature 601, 338 (2022).
  * Hashim  _et al._ [2023] A. Hashim, S. Seritan, T. Proctor, K. Rudinger, N. Goss, R. K. Naik, J. M. Kreikebaum, D. I. Santiago, and I. Siddiqi, Benchmarking quantum logic operations relative to thresholds for fault tolerance, npj Quantum Information 9, 109 (2023).
  * Postler  _et al._ [2022] L. Postler, S. Heu$\beta$en, I. Pogorelov, M. Rispler, T. Feldker, M. Meth, C. D. Marciniak, R. Stricker, M. Ringbauer, R. Blatt, _et al._ , Demonstration of fault-tolerant universal quantum gate operations, Nature 605, 675 (2022).
  * Zhao  _et al._ [2022] P. Zhao, K. Linghu, Z. Li, P. Xu, R. Wang, G. Xue, Y. Jin, and H. Yu, Quantum crosstalk analysis for simultaneous gate operations on superconducting qubits, PRX quantum 3, 020301 (2022).
  * Ash-Saki  _et al._ [2020a] A. Ash-Saki, M. Alam, and S. Ghosh, Analysis of crosstalk in nisq devices and security implications in multi-programming regime, in  _Proceedings of the ACM/IEEE International Symposium on Low Power Electronics and Design_ (2020) pp. 25–30.
  * Niu and Todri-Sanial [2023a] S. Niu and A. Todri-Sanial, Multi-programming mechanism on near-term quantum computing, in  _Quantum Computing: Circuits, Systems, Automation and Applications_ (Springer, 2023) pp. 19–54.
  * Murali  _et al._ [2020] P. Murali, D. C. McKay, M. Martonosi, and A. Javadi-Abhari, Software mitigation of crosstalk on noisy intermediate-scale quantum computers, in  _Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems_ (2020) pp. 1001–1016.
  * Gaebler  _et al._ [2021] J. Gaebler, C. Baldwin, S. Moses, J. Dreiling, C. Figgatt, M. Foss-Feig, D. Hayes, and J. Pino, Suppression of midcircuit measurement crosstalk errors with micromotion, Physical Review A 104, 062440 (2021).
  * McKay  _et al._ [2020] D. C. McKay, A. W. Cross, C. J. Wood, and J. M. Gambetta, Correlated randomized benchmarking, arXiv preprint arXiv:2003.02354 (2020).
  * Sarovar  _et al._ [2020] M. Sarovar, T. Proctor, K. Rudinger, K. Young, E. Nielsen, and R. Blume-Kohout, Detecting crosstalk errors in quantum information processors, Quantum 4, 321 (2020).
  * Niu and Todri-Sanial [2021] S. Niu and A. Todri-Sanial, Analyzing crosstalk error in the nisq era, in  _2021 IEEE Computer Society Annual Symposium on VLSI (ISVLSI)_ (IEEE, 2021) pp. 428–430.
  * Rudinger  _et al._ [2021] K. Rudinger, C. W. Hogle, R. K. Naik, A. Hashim, D. Lobser, D. I. Santiago, M. D. Grace, E. Nielsen, T. Proctor, S. Seritan, _et al._ , Experimental characterization of crosstalk errors with simultaneous gate set tomography, PRX Quantum 2, 040338 (2021).
  * Seo and Bae [2021] S. Seo and J. Bae, Measurement crosstalk errors in cloud-based quantum computing, IEEE Internet Computing 26, 26 (2021).
  * Ding  _et al._ [2020] Y. Ding, P. Gokhale, S. F. Lin, R. Rines, T. Propson, and F. T. Chong, Systematic crosstalk mitigation for superconducting qubits via frequency-aware compilation, in  _2020 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_ (IEEE, 2020) pp. 201–214.
  * Ash-Saki  _et al._ [2020b] A. Ash-Saki, M. Alam, and S. Ghosh, Experimental characterization, modeling, and analysis of crosstalk in a quantum computer, IEEE Transactions on Quantum Engineering 1, 1 (2020b).
  * Razif  _et al._ [2019] R. A. M. Razif, S. M. M. Maharum, A. H. Hasani, and Z. Mansor, Mitigation techniques for crosstalk in ics, in  _IOP Conference Series: Materials Science and Engineering_ , Vol. 701 (IOP Publishing, 2019) p. 012037.
  * Winick  _et al._ [2021] A. Winick, J. J. Wallman, and J. Emerson, Simulating and mitigating crosstalk, Physical review letters 126, 230502 (2021).
  * Xie  _et al._ [2021] L. Xie, J. Zhai, and W. Zheng, Mitigating crosstalk in quantum computers through commutativity-based instruction reordering, in  _2021 58th ACM/IEEE Design Automation Conference (DAC)_ (IEEE, 2021) pp. 445–450.
  * Gambetta  _et al._ [2012] J. M. Gambetta, A. D. Córcoles, S. T. Merkel, B. R. Johnson, J. A. Smolin, J. M. Chow, C. A. Ryan, C. Rigetti, S. Poletto, T. A. Ohki, M. B. Ketchen, and M. Steffen, Characterization of addressability by simultaneous randomized benchmarking, Phys. Rev. Lett. 109, 240504 (2012).
  * Marella and Parisa [2020] S. T. Marella and H. S. K. Parisa, Introduction to quantum computing, Quantum Computing and Communications (2020).
  * de Lima Marquezino  _et al._ [2019] F. de Lima Marquezino, R. Portugal, and C. Lavor,  _A primer on quantum computing_ (Springer, 2019).
  * Hidary and Hidary [2019] J. D. Hidary and J. D. Hidary,  _Quantum computing: an applied approach_ , Vol. 1 (Springer, 2019).
  * Renner and Brukner [2022] M. J. Renner and Č. Brukner, Computational advantage from a quantum superposition of qubit gate orders, Physical Review Letters 128, 230503 (2022).
  * Ivanov and Vitanov [2020] P. A. Ivanov and N. V. Vitanov, Two-qubit quantum gate and entanglement protected by circulant symmetry, Scientific Reports 10, 5030 (2020).
  * Mummadi and Rudra [2023] S. Mummadi and B. Rudra, Fundamentals of quantum computation and basic quantum gates, in  _Handbook of Research on Quantum Computing for Smart Environments_ (IGI Global, 2023) pp. 1–24.
  * Krasnok  _et al._ [2024] A. Krasnok, P. Dhakal, A. Fedorov, P. Frigola, M. Kelly, and S. Kutsaev, Superconducting microwave cavities and qubits for quantum information systems, Appl Phys Rev 11 (2024).
  * Zheng  _et al._ [2023] M. Zheng, A. Li, T. Terlaky, and X. Yang, A bayesian approach for characterizing and mitigating gate and measurement errors, ACM Transactions on Quantum Computing 4, 1 (2023).
  * Selvarajan  _et al._ [2021] R. Selvarajan, V. Dixit, X. Cui, T. S. Humble, and S. Kais, Prime factorization using quantum variational imaginary time evolution, Scientific reports 11, 20835 (2021).
  * Russo  _et al._ [2023] V. Russo, A. Mari, N. Shammah, R. LaRose, and W. J. Zeng, Testing platform-independent quantum error mitigation on noisy quantum computers, IEEE Transactions on Quantum Engineering (2023).
  * Konar  _et al._ [2022] D. Konar, E. Gelenbe, S. Bhandary, A. D. Sarma, and A. Cangi, Random quantum neural networks (rqnn) for noisy image recognition, arXiv preprint arXiv:2203.01764 (2022).
  * Niu and Todri-Sanial [2023b] S. Niu and A. Todri-Sanial, Enabling multi-programming mechanism for quantum computing in the nisq era, Quantum 7, 925 (2023b).
  * Singh  _et al._ [2022] D. Singh, S. Jakhodia, and B. Jajodia, Experimental evaluation of adder circuits on ibm qx hardware, in  _Inventive Computation and Information Technologies: Proceedings of ICICIT 2021_ (Springer, 2022) pp. 333–347.
  * Baheri  _et al._ [2021] B. Baheri, D. Chen, B. Fang, S. A. Stein, V. Chaudhary, Y. Mao, S. Xu, A. Li, and Q. Guan, Tqea: Temporal quantum error analysis, in  _2021 51st Annual IEEE/IFIP International Conference on Dependable Systems and Networks-Supplemental Volume (DSN-S)_ (IEEE, 2021) pp. 65–67.
  * Yetis and Karakoes [2021] H. Yetis and M. Karakoes, Investigation of noise effects for different quantum computing architectures in ibm-q at nisq level, in  _2021 25th International Conference on Information Technology (IT)_ (IEEE, 2021) pp. 1–4.
  * Martina  _et al._ [2022] S. Martina, L. Buffoni, S. Gherardini, and F. Caruso, Learning the noise fingerprint of quantum devices, Quantum Machine Intelligence 4, 8 (2022).
  * Helsen  _et al._ [2022] J. Helsen, I. Roth, E. Onorati, A. H. Werner, and J. Eisert, General framework for randomized benchmarking, PRX Quantum 3, 020357 (2022).
  * Hines  _et al._ [2023] J. Hines, M. Lu, R. K. Naik, A. Hashim, J.-L. Ville, B. Mitchell, J. M. Kriekebaum, D. I. Santiago, S. Seritan, E. Nielsen, _et al._ , Demonstrating scalable randomized benchmarking of universal gate sets, Physical Review X 13, 041030 (2023).
  * Mills  _et al._ [2022] A. R. Mills, C. R. Guinn, M. J. Gullans, A. J. Sigillito, M. M. Feldman, E. Nielsen, and J. R. Petta, Two-qubit silicon quantum processor with operation fidelity exceeding 99%, Science Advances 8, eabn5130 (2022).
  * Liu  _et al._ [2023] R. Liu, Z. Guan, X. Cheng, P. Zhu, and S. Feng, Suppression of crosstalk in quantum computers based on instruction exchange rules and duration, in  _Journal of Physics: Conference Series_ , Vol. 2524 (IOP Publishing, 2023) p. 012026.
  * Ibrahim  _et al._ [2023] M. Ibrahim, N. T. Bronn, and G. T. Byrd, Crosstalk-based parameterized quantum circuit approximation, arXiv preprint arXiv:2305.04172 (2023).
  * White  _et al._ [2022] G. A. White, F. A. Pollock, L. C. Hollenberg, K. Modi, and C. D. Hill, Non-markovian quantum process tomography, PRX Quantum 3, 020344 (2022).
  * Pereira  _et al._ [2023] L. Pereira, J. J. García-Ripoll, and T. Ramos, Parallel tomography of quantum non-demolition measurements in multi-qubit devices, npj Quantum Information 9, 22 (2023).
  * Khadirsharbiyani  _et al._ [2023] S. Khadirsharbiyani, M. Sadeghi, M. E. Zarch, J. Kotra, and M. T. Kandemir, Trim: crosstalk-aware qubit mapping for multiprogrammed quantum systems, in  _2023 IEEE International Conference on Quantum Software (QSW)_ (IEEE, 2023) pp. 138–148.
  * Li  _et al._ [2023a] Z. Li, P. Liu, P. Zhao, Z. Mi, H. Xu, X. Liang, T. Su, W. Sun, G. Xue, J.-N. Zhang, _et al._ , Error per single-qubit gate below $10^{-4}$ in a superconducting qubit, arXiv preprint arXiv:2302.08690 (2023a).
  * Wei  _et al._ [2022] K. Wei, E. Magesan, I. Lauer, S. Srinivasan, D. Bogorin, S. Carnevale, G. Keefe, Y. Kim, D. Klaus, W. Landers, _et al._ , Hamiltonian engineering with multicolor drives for fast entangling gates and quantum crosstalk cancellation, Physical Review Letters 129, 060501 (2022).
  * Finck  _et al._ [2021] A. Finck, S. Carnevale, D. Klaus, C. Scerbo, J. Blair, T. McConkey, C. Kurter, A. Carniol, G. Keefe, M. Kumph, _et al._ , Suppressed crosstalk between two-junction superconducting qubits with mode-selective exchange coupling, Physical Review Applied 16, 054041 (2021).
  * Li  _et al._ [2023b] A. Li, S. Stein, S. Krishnamoorthy, and J. Ang, Qasmbench: A low-level quantum benchmark suite for nisq evaluation and simulation, ACM Transactions on Quantum Computing 4, 10.1145/3550488 (2023b).
  * Sun  _et al._ [2021] J. Sun, X. Yuan, T. Tsunoda, V. Vedral, S. C. Benjamin, and S. Endo, Mitigating realistic noise in practical noisy intermediate-scale quantum devices, Phys. Rev. Appl. 15, 034026 (2021).


#  $S$-parts of sums of terms of linear recurrence sequences

S. S. Rout  Sudhansu Sekhar Rout, Institute of Mathematics and Applications
Andharua, Bhubaneswar, Odisha - 751029
India<EMAIL_ADDRESS><EMAIL_ADDRESS>and  N. K. Meher
Nabin Kumar Meher, National Institute of Science Education and Research,
Bhubaneswar, HBNI, P.O. Jatni, Khurda, Odisha -752050, India.
<EMAIL_ADDRESS>
###### Abstract.

Let $S=\\{p_{1},\ldots,p_{s}\\}$ be a finite, non-empty set of distinct prime
numbers and $(U_{n})_{n\geq 0}$ be a linear recurrence sequence of integers of
order $r$. For any positive integer $k,$ we define $(U_{j}^{(k)})_{j\geq 1}$
an increasing sequence composed of integers of the form
$U_{n_{k}}+\cdots+U_{n_{1}},\ n_{k}>\cdots>n_{1}$. Under certain assumptions,
we prove that for any $\epsilon>0,$ there exists an integer $n_{0}$ such that
$[U_{j}^{(k)}]_{S}<\left(U_{j}^{(k)}\right)^{\epsilon},$ for $j>n_{0},$ where
$[m]_{S}$ denote the $S$-part of the positive integer $m$. On further
assumptions on $(U_{n})_{n\geq 0},$ we also compute an effective bound for
$[U_{j}^{(k)}]_{S}$ of the form $\left(U_{j}^{(k)}\right)^{1-c}$, where $c$ is
a positive constant depends only on $(U_{n})_{n\geq 0}$ and $S.$

2010 Mathematics Subject Classification: Primary 11B37, Secondary 11D61,
11J86.
Keywords: Linear recurrence sequence, exponential Diophantine equations,
linear forms in logarithms, Baker’s method

##  1\. Introduction

Let $S=\\{p_{1},\ldots,p_{s}\\}$ be a finite, non-empty set of distinct prime
numbers. For a positive integer $n$, we write $n=p_{1}^{e_{1}}\cdots
p_{s}^{e_{s}}\cdot M$, where $e_{1},\ldots,e_{s}$ are non-negative integers
and $M$ is relatively prime to $p_{1},\ldots,p_{s}$. The $S$-part $[n]_{S}$ of
$n$ is defined as

$[n]_{S}=p_{1}^{e_{1}}\cdots p_{s}^{e_{s}}.$

Recently, there have been many advances in the study of $S$-parts of integer
polynomials, decomposable forms evaluated at integer points and linear
recurrence sequences. For example, Stewart [20] proved a non-trivial,
computationally effective upper bounds for $[n(n+1)\cdots(n+k)]_{S}$ for any
integer $k>0$ and this result has been extended by Gross and Vincent [11] to
$[f(n)]_{S}$ for an arbitrary $f(x)\in\mathbb{Z}[x]$ having at least two
distinct roots. Motivated by the work in [11], Bugeaud, Evertse and Györy [6]
proved that if $f(x)\in\mathbb{Z}[x]$ is a polynomial of degree $n\geq 1$
without multiple roots, then for any $\delta>0$ and any $x\in\mathbb{Z}$ with
$f(x)\neq 0$ one has

$[f(x)]_{S}\ll_{f,S,\delta}(f(x))^{\frac{1}{n}+\delta}.$

Further, Bugeaud [4] proved that for any base $b$, there are only finitely
many integers not divisible by $b$ which have a given number of non-zero
$b$-ary digits and whose prime divisors belong to a given finite set.

In [12], Mahler obtained a non-trivial upper bound for the $S$-parts of a
special family of binary recurrence sequences $(u_{n})_{n\geq 0}$. In fact,
using Ridout Theorem [18] (which is a $p$-adic extension of Roth theorem),
Mahler showed that, if $n$ is large enough, then
$[u_{n}]_{S}<|u_{n}|^{\epsilon}$. Mahler also observed that, his result
implies that $P[u_{n}]$ tends to infinity as $n$ tends to infinity, where
$P[m]$ denotes the largest prime factor of the integer $m$ with $P[0]=P[\pm
1]=1$. Later in [3], Bugeaud and Evertse, extends Mahler’s result to every
non-degenerate recurrence sequence $(U_{n})_{n\geq 0}$ of integers. In
particular, using $p$-adic Schmidt Subspace Theorem they proved that for every
sufficiently large $n$ and for any $\epsilon>0$

$[U_{n}]_{S}\leq|U_{n}|^{\epsilon}.$

Let $(F_{n})_{n\geq 0}$ denote the Fibonacci sequence defined by

$F_{0}=0\,F_{1}=1\quad\mbox{and}\quad F_{n+1}=F_{n}+F_{n-1}$

for $n\geq 0$. Every positive integer $N$ can be written uniquely as a sum

$N=\epsilon_{\ell}F_{\ell}+\cdots+\epsilon_{1}F_{1},$

with $\epsilon_{\ell}=1,\epsilon_{j}\in\\{0,1\\}$ and
$\epsilon_{j}\epsilon_{j+1}=0$ for $j=1,\ldots,\ell-1$. This representation is
called its Zekendorf representation. In [5], Bugeaud proved that there are
only finitely many integers which have a given number of digits in their
Zekendorf representation and whose prime divisors belong to a given set. Like
Zekendorf representation, there is a well defined representation of any
positive integer $N$ in the form

$N=\sum_{j=0}^{L(N)}\epsilon_{j}\cdot U_{j},$ (1.1)

where $U=(U_{n})_{n\geq 0}$ is linear recurrence sequence of order $r$, the so
called $U$-ary representation of $N$ with digits $\epsilon_{j}$. For detail
study about such expansion one may refer [16, 10].

In this paper, we extend the results of Bugeaud and Evertse [3] and Bugeaud
[5]. Here we consider a linear recurrence sequences of integers
$(U_{n})_{n\geq 0}$ of arbitrary order. Let $k\geq 1$ be a positive integer.
We denote by $(U_{j}^{(k)})_{j\geq 1}$ the sequence, arranged in increasing
order, of all positive integers which have at most $k$-digits in their
expansions as in equation (1.1). That is, $(U_{j}^{(k)})_{j\geq 1}$ an
increasing sequence composed of the integers of the form

$U_{n_{k}}+\cdots+U_{n_{1}},\quad n_{k}>\cdots>n_{1}.$

We provide an upper bound for $S$-parts of the sequence $(U_{j}^{(k)})_{j\geq
1}$. First we give a general ineffective result. Then, under some technical
assumptions, we provide an effective upper bound for $S$-parts of the sequence
$(U_{j}^{(k)})_{j\geq 1}$.

##  2\. Notation and main results

For a positive integer $r$, we define the linear recurrence sequence
$(U_{n})_{n\geq 0}$ of order $r$ as follows:

$U_{n}=a_{1}U_{n-1}+\dots+a_{r}U_{n-r}$ (2.1)

where $a_{1},\dots,a_{r}\in\mbox{$\mathbb{Z}$}$ with $a_{r}\neq 0$ and
$U_{0},\dots,U_{r-1}$ are integers not all zero. The characteristic polynomial
of $U_{n}$ is defined by

$f(x):=x^{r}-a_{1}x^{r-1}-\dots-
a_{r}=\prod_{i=1}^{t}(x-\alpha_{i})^{m_{i}}\in\mbox{$\mathbb{Z}$}[X]$ (2.2)

where $\alpha_{1},\dots,\alpha_{t}$ are distinct algebraic numbers and
$m_{1},\dots,m_{t}$ are positive integers. Then $U_{n}$ (see e.g. Theorem C1
in part C of [19]) has a nice representation of the form

$U_{n}=\sum_{i=1}^{t}f_{i}(n)\alpha_{i}^{n}\ \ \ \text{for all}\ n\geq 0.$
(2.3)

Here $f_{i}(x)$ is a polynomial of degree $m_{i}-1$ $(i=1,\dots,t)$ and this
representation is uniquely determined. We call the sequence $(U_{n})_{n\geq
0}$ simple if $t=r$. The sequence $(U_{n})_{n\geq 0}$ is called degenerate if
there are integers $i,j$ with $1\leq i<j\leq t$ such that
$\alpha_{i}/\alpha_{j}$ is a root of unity; otherwise it is called non-
degenerate. Here, we assume that $t\geq 2,$ the polynomials
$f_{1}(x),\ldots,f_{t}(x)$ are non-zero and $(U_{n})_{n\geq 0}$ is non-
degenerate.

If $|\alpha_{1}|>|\alpha_{j}|$ for all $j$ with $2\leq j\leq t$, then we say
that $\alpha_{1}$ is a dominant root of the sequence $(U_{n})_{n\geq 0}$. The
zero multiplicity of the sequence $U_{n}$ is the number of
$n\in\mbox{$\mathbb{Z}$}$ for which $U_{n}=0$. A classical theorem of Skolem-
Mahler-Lech says that a non-degenerate linear recurrence sequence has finite
zero multiplicity.

In our first result, we compute a non-trivial upper bound for the integer
sequence $(U_{j}^{(k)})_{j\geq 1}.$

######  Theorem 1.

Let $(U_{n})_{n\geq 0}$ be a non-degenerate recurrence sequence of integers
defined in (2.1) and assume that

$|\alpha_{1}|>1>|\alpha_{j}|,\quad\mbox{for}\quad j=2,\ldots,t.$ (2.4)

Let $k$ be a positive integer, $\epsilon$ a positive real number and
$S:=\\{p_{1},\ldots,p_{s}\\}$ be a finite, non-empty set of distinct prime
numbers. If $\gcd(p_{1}\cdots p_{s},a_{1},\cdots,a_{r})=1$ then, we have

$[U_{j}^{(k)}]_{S}<\left(U_{j}^{(k)}\right)^{\epsilon},$ (2.5)

for every sufficiently large integer $j$.

The assumption in equation $\eqref{eq6d}$ can be achieved from the relation
(2.1) with $a_{1}>a_{2}>\cdots>a_{r}>0$ (see [2]). However, Theorem 1 is
ineffective as the proof of this depends on a general result on $S$-unit
equations and which further rely on the $p$-adic Schmidt Subspace Theorem.
Therefore, we can not compute the set of $(n_{1},\ldots,n_{k})$ for which
(2.5) does not hold.

Our next theorem gives, under certain conditions, an effective finiteness
result and the main tool for this is Baker’s theory and we use an argument
from [14].

######  Theorem 2.

Let $(U_{n})_{n\geq 0}$ be a non-degenerate recurrence sequence of integers of
order $r\geq 2$ and has a dominant root $\alpha_{1}$ with
$1<\alpha_{1}\notin\mathbb{Z}$. Let $k\geq 1$ be a positive integer and
$S:=\\{p_{1},\ldots,p_{s}\\}$ be a finite, non-empty set of distinct prime
numbers. Then there exist effectively computable positive numbers $c_{1}$ and
$c_{2}$ depending $(U_{n})_{n\geq 0}$ and $S$, such that

$[U_{j}^{(k)}]_{S}<\left(U_{j}^{(k)}\right)^{1-c_{1}},$ (2.6)

for every $j\geq c_{2}$.

By proceeding in a similar line of argument as in [7], we obtain the following
result. Hence we omit the details.

######  Theorem 3.

Let $\epsilon>0$ and $k\geq 1$ be an integer. Then there exist an effectively
computable positive number $N$, depending on $k$ and $\epsilon$ such that

$\displaystyle P[U_{j}^{(k)}]>\left(\frac{1}{k}-\epsilon\right)\log\log
U_{j}^{(k)}\frac{\log\log\log U_{j}^{(k)}}{\log\log\log\log
U_{j}^{(k)}}\quad\text{for}\ j>N.$ (2.7)

##  3\. Preliminaries

Let $K:=\mathbb{Q}(\alpha_{1},\ldots,\alpha_{t})$ be an algebraic number field
and $\mathcal{O}_{K}$ be its ring of integers. Let $V_{K}$ be the set of
places of $K$. For $v\in V_{K}$, if $v$ is an infinite place, then

$|x|_{v}:=|x|^{[K_{v}:\mathbb{R}]/[K:\mathbb{Q}]}\quad\hbox{for}\
x\in\mathbb{Q},$ (3.1)

where as if $v$ is a finite place lying above the prime $p$, then

$|x|_{v}:=|x|^{[K_{v}:\mathbb{Q}_{p}]/[K:\mathbb{Q}]}\quad\hbox{for}\
x\in\mathbb{Q}.$ (3.2)

For $p\in V_{\mathbb{Q}}$, we choose a normalized absolute value $|\cdot|_{p}$
in the following way. If $p=\infty$, then $|\cdot|_{p}$ is the ordinary
absolute value on $\mathbb{Q}$, and if $p$ is prime, then the absolute value
is the $p$-adic absolute value on $\mathbb{Q}$, with $|p|_{p}=1/p$. In either
case, we have

$|x|_{v}:=|N_{K_{v}/\mathbb{Q}_{p}}(x)|_{p}^{1/[K:\mathbb{Q}]},$ (3.3)

for $x\in K$ and $v\mid p$. These absolute values satisfy the product formula

$\prod_{v\in V_{K}}|x|_{v}=1,$

for any $x\in K\setminus\\{0\\}$. Moreover, if $x\in\mathbb{Q}$, then
$\prod_{v\mid\infty}|x|_{v}=|x|$ and $\prod_{v\mid p}|x|_{v}=|x|_{p}$ where
the product is taken over all infinite places of $K$ and all places of $K$
lying above the prime number $p$, respectively. We then define height $h(x)$
of a non-zero $x$ in $K$ by

$h(x)=\sum_{v\in V_{K}}\log\max\\{1,|x|_{v}\\}.$ (3.4)

Let $T$ be a finite set of places of $K$, containing all infinite places.
Define the ring of $T$-integers and $T$-units of $K$ by

$O_{T}:=\\{x\in K:|x|_{v}\leq 1\quad\mbox{for}\quad v\in V_{K}\setminus T\\}$
(3.5)

and

$O_{T}^{*}:=\\{x\in K:|x|_{v}=1\quad\mbox{for}\quad v\in V_{K}\setminus T\\},$
(3.6)

respectively. Further, we define

$H_{T}(x_{1},\ldots,x_{n}):=\prod_{v\in
T}\max\\{|x_{1}|_{v},\ldots,|x_{n}|_{v}\\}$ (3.7)

for $x_{1},\ldots,x_{n}\in O_{T}$.

###  3.1. Auxiliary results

In the proof of Theorem 1, we use the following result on $S$-unit equations
of Pethő and Tichy [16].

######  Proposition 4.

[16, Theorem 1] Let $K$ be an algebraic number field of degree $d$ over
$\mathbb{Q}$. Let $\alpha_{1},\ldots,\alpha_{k}\in K$ be multiplicatively
independent of degrees $m_{1},\ldots,m_{k}$ respectively, $\beta_{i,j}\in
K\setminus\\{0\\}$ for $i=1,\ldots,k,j=1,\ldots,m_{i}$. Set
$M=m_{1}+\cdots+m_{k}$. Let $S_{1}$ be the set of places of $K$ (including the
infinite places) having $s$ elements such that $|\alpha_{i}|_{v}=1$ for all
$i=1,\ldots,k$ and $v\notin S_{1}$. Then the Diophantine equation

$\sum_{\ell=1}^{k}\sum_{i=1}^{m_{\ell}}\beta_{\ell,i}\alpha_{\ell}^{\lambda_{\ell,i}}=0$
(3.8)

has at most $(4sd!)^{2^{36Md!}}s^{6}$ solutions in
$(\lambda_{1,1},\ldots,\lambda_{1,m_{1}},\ldots,\lambda_{k,1},\ldots,\lambda_{k,m_{k}})$
such that

$\sum_{i\in J}\beta_{\ell,i}\alpha_{\ell}^{\lambda_{\ell,i}}\neq 0$

holds for every $J\subseteq\\{1,\ldots,m_{\ell}\\},\ell=1,\ldots,k$.

To proof Theorem 1, we use the following proposition (see [8, Theorem 2] and
[9, Proposition 6.2.1].

######  Proposition 5.

Let $T_{1}$ be a subset of $T$ and $t\geq 2$. Then for every $\epsilon>0$,
there exists a constant C, depending only on $K,T,t$ and $\epsilon$ such that
for all $x_{1},\ldots,x_{t}\in O_{T}$ with every non-empty subsum of
$x_{1}+\cdots+x_{t}$ is non-zero, we have

$\prod_{i=1}^{t}\prod_{v\in T}|x_{i}|_{v}\cdot\prod_{v\in
T_{1}}\left|\sum_{\ell=1}^{t}x_{\ell}\right|_{v}\geq C\left(\prod_{v\in
T_{1}}\max\\{|x_{1}|_{v},\ldots,|x_{t}|_{v}\\}\right)H_{T}(x_{1},\ldots,x_{t})^{-\epsilon}.$

######  Lemma 3.2.

Suppose $\alpha$ is an algebraic number of degree $t$ and
$\alpha=\alpha_{1},\cdots,\alpha_{t}$ denotes its conjugates. Assume
$|\alpha_{1}|>1>|\alpha_{2}|\geq\cdots\geq|\alpha_{t}|$. If $t>2$ then the
conjugates of $\alpha$ are pairwise multiplicatively independent. If $t=2$ and
$\alpha_{1}$ and $\alpha_{2}$ are multiplicatively dependent then
$|\alpha_{1}\alpha_{2}|=1$.

###### Proof.

See proof of Lemma 2 in [16]. ∎

In the proof of Theorem 1, we also need the following result which gives
information on the characteristic roots and its coefficients appearing in the
explicit forms of recurrence sequences.

######  Lemma 3.3.

[1] Let $(U_{n})_{n\geq 0}$ be a non-degenerate recurrence sequence of order
$r\geq 2$ and set

$\gamma:=\max\left\\{\max_{1\leq i\leq r}|a_{i}|,\max_{0\leq
j\leq{r-1}}|U_{j}|\right\\}.$

  1. (i)

With the notation in (2.3), write

$f_{i}(n)=\beta_{i,0}+\beta_{i,1}n+\dots+\beta_{i,m_{i}-1}n^{m_{i}-1}\
(i=1,\dots,t).$

Then we have

$\max\limits_{1\leq i\leq t,\ 0\leq\ell\leq
m_{i}-1}\left\\{h(\alpha_{i}),h(\beta_{i,\ell})\right\\}\leq c_{3}.$

Here $c_{3}$ is an effectively computable constant depending only on $\gamma$
and $r$.

  2. (ii)

If $n\geq 1$ and $f_{i}(n)\neq 0$ then

$c_{4}\leq|f_{i}(n)|\leq c_{5}n^{m_{i}-1}\ \ \ (1\leq i\leq t),$

where $c_{4}$ and $c_{5}$ are effectively computable constants depending only
on $\gamma$ and $r$.

  3. (iii)

Suppose that $\alpha_{1}$ is dominant root of the sequence $(U_{n})_{n\geq
0}$. Then we have

$|U_{n}|\leq c_{6}n^{r-1}|\alpha_{1}|^{n}\ \ \ (n\geq 1),$

where $c_{6}$ is an effectively computable constant depending only on $\gamma$
and $r$.

##  4\. Proof of Theorem 1

To proof Theorem 1, we need the following lemma.

######  Lemma 4.1.

Let $(U_{n})_{n\geq 0}$ be a non-degenerate recurrence sequence of integers
defined in (2.1) and assume that $|\alpha_{1}|>1>|\alpha_{j}|$ for
$j=2,\ldots,t$. Then, there are finitely many tuples $(n_{1},\ldots,n_{k})$
such that either

$U_{n_{k}}+\cdots+U_{n_{1}}=0$

or

$\sum_{h\in J_{k}}U_{n_{h}}=0\;\quad\mbox{for}\quad
J_{k}\subseteq\\{1,\ldots,k\\}.$

###### Proof.

Suppose that $U_{n_{k}}+\cdots+U_{n_{1}}=0$. That is

$\sum_{i=1}^{k}\sum_{j=1}^{t}f_{j}(n_{i})\alpha_{j}^{n_{i}}=\sum_{j=1}^{t}\sum_{i=1}^{k}f_{j}(n_{i})\alpha_{j}^{n_{i}}=0.$
(4.1)

Since $|\alpha_{1}|>1>|\alpha_{j}|$ for $j=2,\ldots,t$, by Lemma 3.2 the
algebraic numbers $\alpha_{1},\cdots,\alpha_{t}$ are multiplicatively
independent. To apply Proposition 4, we need to show that $\alpha_{\ell}$ are
$S_{1}$-units for $\ell=1,\ldots,t$.

From (2.2), the constant term of characteristic polynomial is $a_{r}$. Let
$S_{1}$ be the minimal set of places of $K$ such that $\prod_{v\in
S_{1}}|a_{r}|_{v}=1$. Then $s_{1}:=|S_{1}|\leq d(\omega(a_{r})+1)$, where
$\omega(a_{r})$ is the number of distinct prime divisors of $a_{r}$ and $d$ is
the degree of the number field. Also, $\alpha_{\ell}$ divides $a_{r}$ in
$\mathcal{O}_{K}$ for all $1\leq\ell\leq t$. Thus, $\prod_{v\in
S_{1}}|\alpha_{\ell}|_{v}=1$, i.e., $\alpha_{\ell}$ are $S_{1}$-units.

By Proposition 4 equation (4.1) has at most $(4s_{1}d!)^{2^{36ktd!}}s_{1}^{6}$
solutions in

$(n_{1},\ldots,n_{k},\ldots,n_{1},\ldots,n_{k})\in\mathbb{Z}^{kt}$

such that

$\sum_{h\in J_{k}}f_{j}(n_{h})\alpha_{j}^{n_{h}}\neq 0$ (4.2)

holds for all $J_{k}\subseteq\\{1,\ldots,k\\}$.

Assume that for $J_{k}\subseteq\\{1,\ldots,k\\}$, equation (4.2) does not
hold, i.e.,

$\sum_{h\in J_{k}}f_{j}(n_{h})\alpha_{j}^{n_{h}}=0.$ (4.3)

Let $\sigma_{j}$ be an automorphism of $K$ which sends $\alpha_{j}$ to
$\alpha_{i}$. Applying $\sigma_{j}$ to (4.3), we get

$\sum_{h\in J_{k}}f_{i}(n_{h})\alpha_{i}^{n_{h}}=0.$

Therefore, (4.3) holds for all $j=1,\ldots,t$. Thus, we get

$\sum_{h\in J_{k}}U_{n_{h}}=\sum_{h\in
J_{k}}\left(f_{1}(n_{h})\alpha_{1}^{n_{h}}+\cdots+f_{t}(n_{h})\alpha_{t}^{n_{h}}\right)=0.$
(4.4)

From the above arguments, we conclude that either there are finitely many
$(n_{1},\ldots,n_{k})$ such that $U_{n_{k}}+\cdots+U_{n_{1}}=0$ or $\sum_{h\in
J_{k}}U_{n_{h}}=0$ for $J_{k}\subseteq\\{1,\ldots,k\\}$. ∎

###  4.2. Proof of Theorem 1

Let $S_{1}$ be the set of places of $K$ as in the proof of Lemma 4.1 and
$S_{2}$ be any subset of $S_{1}$. Choose a real number $\epsilon^{\prime}>0$
which will be later taken sufficiently small in terms of $\epsilon$. In the
proof $c_{7},\ldots,c_{16}$ denote positive effective constants depending on
$\epsilon,K,S_{1},(U_{n})_{n\geq 0},S$. Further, we introduce the following
notation. Put

$A:=\max\\{|\alpha_{1}|,\ldots,|\alpha_{t}|\\},\quad
A_{p}:=\max\\{|\alpha_{1}|_{p},\ldots,|\alpha_{t}|_{p}\\}$

for $p\in S$ and

$A_{v}:=\max\\{|\alpha_{1}|_{v},\ldots,|\alpha_{t}|_{v}\\}$

for $v\in V_{K}$. Then by our choice of the absolute values on $K$, we have

$\prod_{v\mid\infty}A_{v}=A,\quad\prod_{v\mid
p}A_{v}=A_{p},\quad\mbox{for}\;\;p\in S.$

Our first claim is each subsum of

$U_{n_{k}}+\cdots+U_{n_{1}}=\sum_{j=1}^{t}f_{j}(n_{k})\alpha_{j}^{n_{k}}+\cdots+\sum_{j=1}^{t}f_{j}(n_{1})\alpha_{j}^{n_{1}}$
(4.5)

is non-zero except for finitely many choices of $(n_{1},\ldots,n_{k})$.
Suppose that each $U_{n_{\ell}}=0$ for $\ell=1,\ldots,k$. Since
$(U_{n})_{n\geq 0}$ is a non-degenerate linear recurrence sequence, by Skolem-
Mahler-Lech Theorem, there are only finitely many non-negative integers
$n_{\ell}$ for which at least one of the subsums of $U_{n_{\ell}}$ vanishes.

For a given partition $P$ of the set $\\{1,\ldots,k\\}$, suppose we have the
following system of equations

$\sum\limits_{i\in\lambda}U_{n_{i}}=0\ \ \ (\lambda\in P),$ (4.6)

with cardinality of $\lambda\geq 2$. Consider those solutions of (4.6) which
do not satisfy any further refinement of the partition $P$. Then by Lemma 4.1
we conclude that each equation in (4.6) has finitely many solutions. Since
number of partitions $P$ of $\\{1,\ldots,k\\}$ is bounded in terms of $k$, the
claim is valid. For the remaining positive integer tuples
$(n_{1},\ldots,n_{k})$ by applying Proposition 5, we have,

$\prod_{i=1}^{k}\prod_{v\in S_{1}}|U_{n_{i}}|_{v}\cdot\prod_{v\in
S_{2}}|U_{n_{k}}+\cdots+U_{n_{1}}|_{v}\geq c_{7}\left(\prod_{v\in
S_{2}}\max_{\begin{subarray}{c}1\leq i\leq k\\\ 1\leq j\leq
t\end{subarray}}|f_{j}(n_{i})\alpha_{j}^{n_{i}}|_{v}\right)\left(\prod_{v\in
S_{1}}\max_{\begin{subarray}{c}1\leq i\leq k\\\ 1\leq j\leq
t\end{subarray}}|f_{j}(n_{i})\alpha_{j}^{n_{i}}|_{v}\right)^{-\epsilon^{\prime}/2}.$
(4.7)

Since $\alpha_{1}$ is dominant root of the sequence $(U_{n})$, by Lemma
3.3(iii) the left hand side of the inequality (4.7) is

$\displaystyle\leq c_{8}\prod_{i=1}^{k}\prod_{v\in
S_{1}}\left|n_{i}^{r-1}\right|_{v}\left|\alpha_{1}\right|^{n_{i}}_{v}\cdot\prod_{v\in
S_{2}}|U_{n_{k}}+\cdots+U_{n_{1}}|_{v}$ $\displaystyle\leq
c_{9}n_{k}^{k(r-1)}\cdot\prod_{v\in S_{2}}|U_{n_{k}}+\cdots+U_{n_{1}}|_{v},$

where we have used $\prod_{v\in S_{1}}|\alpha_{i}|_{v}=1$ for $i=1,\ldots,k$
and $n_{k}>\cdots>n_{1}$. By Lemma 3.3(ii) the right hand side of the
inequality (4.7) is

$\displaystyle\geq c_{10}\left(\prod_{v\in
S_{2}}\max_{\begin{subarray}{c}1\leq i\leq k\\\ 1\leq j\leq
t\end{subarray}}|\alpha_{j}^{n_{i}}|_{v}\right)\left(\prod_{v\in
S_{1}}\max_{\begin{subarray}{c}1\leq i\leq k\\\ 1\leq j\leq
t\end{subarray}}|\alpha_{j}^{n_{i}}|_{v}\right)^{-\epsilon^{\prime}/2}$
$\displaystyle\geq c_{11}\left(\prod_{v\in
S_{2}}A_{v}\right)^{n_{k}}\left(\prod_{v\in
S_{1}}A_{v}\right)^{-n_{k}\epsilon^{\prime}/2}\geq c_{12}\left(\prod_{v\in
S_{2}}A_{v}\right)^{n_{k}}\cdot A^{-n_{k}\epsilon^{\prime}/2}.$

Hence, we conclude

$\prod_{v\in S_{2}}|U_{n_{k}}+\cdots+U_{n_{1}}|_{v}\geq
c_{13}n_{k}^{-k(r-1)}\cdot\left(\prod_{v\in S_{2}}A_{v}\right)^{n_{k}}\cdot
A^{-n_{k}\epsilon^{\prime}/2}.$ (4.8)

Further, we estimate an trivial upper bound

$\prod_{v\in S_{2}}|U_{n_{k}}+\cdots+U_{n_{1}}|_{v}\leq\prod_{v\in
S_{2}}\max_{1\leq i\leq k}|U_{n_{i}}|_{v}\leq
c_{14}n_{k}^{k(r-1)}\cdot\left(\prod_{v\in S_{2}}A_{v}\right)^{n_{k}}.$ (4.9)

Thus from (4.8) and (4.9)

$c_{15}\left(\prod_{v\in S_{2}}A_{v}\right)^{n_{k}}\cdot
A^{-n_{k}\epsilon^{\prime}/2}\leq\prod_{v\in
S_{2}}|U_{n_{k}}+\cdots+U_{n_{1}}|_{v}\leq
c_{16}n_{k}^{k(r-1)}\cdot\left(\prod_{v\in S_{2}}A_{v}\right)^{n_{k}}.$

Since $A>1$, for sufficiently large $n_{k}$ we have

$\left(\prod_{v\in S_{2}}A_{v}\right)^{n_{k}}\cdot
A^{-n_{k}\epsilon^{\prime}}\leq\prod_{v\in
S_{2}}|U_{n_{k}}+\cdots+U_{n_{1}}|_{v}\leq\left(\prod_{v\in
S_{2}}A_{v}\right)^{n_{k}}\cdot A^{n_{k}\epsilon^{\prime}}$ (4.10)

Now we consider two cases. In the first case, suppose that $S_{2}$ has only
infinite places of $K$, then for sufficiently large $n_{k}$, we have

$A^{n_{k}(1-\epsilon^{\prime})}\leq|U_{n_{k}}+\cdots+U_{n_{1}}|\leq
A^{n_{k}(1+\epsilon^{\prime})}.$ (4.11)

In the other case, if $S_{2}$ consists the places of $K$ lying above the
primes in $S$, then

$\prod_{v\in S_{2}}|U_{n_{k}}+\cdots+U_{n_{1}}|_{v}=\prod_{p\in
S}[U_{n_{k}}+\cdots+U_{n_{1}}]_{S}^{-1},\quad\mbox{and}\;\;\prod_{v\in
S_{2}}A_{v}=\prod_{p\in S}A_{p}=A^{-\delta}$

where $\delta:=-\frac{\sum_{p\in
S}\log\max\\{|\alpha_{1}|_{p},\ldots,|\alpha_{t}|_{p}\\}}{\log\max\\{|\alpha_{1}|,\ldots,|\alpha_{t}|\\}}$.
Hence,

$A^{n_{k}(\delta-\epsilon^{\prime})}\leq[U_{n_{k}}+\cdots+U_{n_{1}}]_{S}\leq
A^{n_{k}(\delta+\epsilon^{\prime})},$

and by taking $\epsilon^{\prime}$ sufficiently small interms of $\epsilon$, we
have

$[U_{j}^{(k)}]_{S}\leq(U_{j}^{(k)})^{(\delta+\epsilon)}.$ (4.12)

Suppose that $\delta>0$. Then there is a prime number $p\in S$ such that
$\max_{i}|\alpha_{i}|_{p}<1$. Again since $a_{1},\ldots,a_{k}$ are the
elementary symmetric functions in $\alpha_{i}$ up to sign, we have
$|a_{i}|_{p}<1$ for $i=1,\ldots,k$. This is not true as $\gcd(p_{1}\cdots
p_{s},a_{1},\cdots,a_{r})=1$. Thus, $\delta=0$. This completes the proof of
Theorem 1. ∎

##  5\. Proof of Theorem 2

To prove Theorem 2, we need the following results. First one is a Baker-type
result of Matveev [13, Theorem 2.2]. Further, in the proof of Lemma 5.2 and
Theorem 2, $c_{20},c_{21},\ldots,c_{41}$ denote effectively computable
positive constants and depending on $\epsilon,(U_{n})_{n\geq 0},S,K$ and the
constants $C_{1},C_{2},\ldots,C_{8}$ are absolute, positive and effectively
computable, .

######  Proposition 6 ([13]).

For any integer $m\geq 2,$ let $\gamma_{1},\ldots,\gamma_{m}$ be non-zero
algebraic numbers and let $b_{1},\ldots,b_{m}$ be rational integers. Let $D$
be the degree of the number field $\mathbb{Q}(\gamma_{1},\ldots,\gamma_{m})$
over $\mathbb{Q}$. Let $A_{1},\ldots,A_{m}$ be real numbers with

$\log
A_{j}\geq\max\left\\{h(\gamma_{j}),\frac{|\log\gamma_{j}|}{D},\frac{0.16}{D}\right\\},\quad(j=1,\ldots,m)$
(5.1)

where $h(\gamma)$ denotes the absolute logarithmic height of $\gamma$ and set

$B=\max\left\\{1,\left\\{|b_{j}|\frac{\log A_{j}}{\log A_{m}}:1\leq j\leq
m\right\\}\right\\}.$

Consider the linear form

$\Lambda:=\gamma_{1}^{b_{1}}\cdots\gamma_{m}^{b_{m}}-1$

and assume that $\Lambda\neq 0$. Then,

$\log|\Lambda|\geq-4\times 30^{m+4}\times{(m+1)}^{5.5}\times
D^{m+2}\log(eD)\log(eB)\log A_{1}\cdots\log A_{m}.$

######  Lemma 5.1.

Suppose $\alpha$ is an algebraic number of degree $t$ and
$\alpha=\alpha_{1},\cdots,\alpha_{t}$ denotes its conjugates and $f_{i}(x)$’s
are defined as in (2.3). Suppose

$\Lambda_{i}:=M\left(\prod_{j=1}^{s}p_{j}^{r_{j}}\right)(f_{1}(n_{k}))^{-1}\alpha_{1}^{-n_{k}}\left(1+\frac{f_{1}(n_{k-1})}{f_{1}(n_{k})}\alpha_{1}^{n_{k-1}-n_{k}}+\cdots+\frac{f_{1}(n_{i})}{f_{1}(n_{k})}\alpha_{1}^{n_{i}-n_{k}}\right)^{-1}-1$

for all $1\leq i\leq k-1$ and $1<\alpha_{1}\notin\mathbb{Z}$. If
$\Lambda_{i}=0$, then

$n_{k}<\begin{cases}\frac{c_{18}\log
n_{k}}{\log\alpha_{1}}&\quad\text{if}\;\;|\alpha_{m}|\leq 1\\\
\frac{c_{19}\log
n_{k}}{\log(\alpha_{1}/|\alpha_{m}|)}&\quad\text{if}\;\;|\alpha_{m}|>1,\end{cases}$
(5.2)

where $c_{18}$ and $c_{19}$ are effectively computable constants depending on
$\alpha$.

###### Proof.

Now $\Lambda_{i}=0$ imply

$M\left(\prod_{j=1}^{s}p_{j}^{r_{j}}\right)=f_{1}(n_{k})\alpha_{1}^{n_{k}}+\cdots+f_{1}(n_{i})\alpha_{1}^{n_{i}}.$
(5.3)

Since $\alpha_{1}\notin\mathbb{Z}$, then there exists a conjugate $\alpha_{m}$
of $\alpha_{1}$ in the field $\mathbb{Q}(\alpha_{1},\ldots,\alpha_{t})$ such
that $\alpha_{1}\neq\alpha_{m}$. Therefore, on taking the $m$-th conjugate of
both sides of (5.3), we get

$M\left(\prod_{j=1}^{s}p_{j}^{r_{j}}\right)=f_{m}(n_{k})\alpha_{m}^{n_{k}}+\cdots+f_{m}(n_{i})\alpha_{m}^{n_{i}}.$
(5.4)

Since $\alpha_{1}>1$ and by comparing (5.3) and (5.4),

$\displaystyle|f_{1}(n_{k})|\alpha_{1}^{n_{k}}$
$\displaystyle<|f_{1}(n_{k})\alpha_{1}^{n_{k}}+\cdots+f_{1}(n_{i})\alpha_{1}^{n_{i}}|=|f_{m}(n_{k})\alpha_{m}^{n_{k}}+\cdots+f_{m}(n_{i})\alpha_{m}^{n_{i}}|.$

By Lemma 3.3(ii) we obtain,

$\alpha_{1}^{n_{k}}<c_{17}\sum_{j=i}^{k}n_{j}^{m_{j}-1}|\alpha_{m}|^{n_{k}}.$
(5.5)

Then from (5.5), we have

$n_{k}<\begin{cases}\frac{c_{18}\log
n_{k}}{\log\alpha_{1}}&\quad\text{if}\;\;|\alpha_{m}|\leq 1\\\
\frac{c_{19}\log
n_{k}}{\log(\alpha_{1}/|\alpha_{m}|)}&\quad\text{if}\;\;|\alpha_{m}|>1,\end{cases}$

where $c_{18}$ and $c_{19}$ are effectively computable constants depending on
$\alpha$. ∎

######  Lemma 5.2.

Let $(U_{n})_{n\geq 0}$ be a non-degenerate recurrence sequence of integers of
order $r\geq 2$. Suppose that $(U_{n})_{n\geq 0}$ has a dominant root (say)
$\alpha_{1}$ and $1<\alpha_{1}\notin\mathbb{Z}$. Let $k\geq 1$ be a positive
integer and $p_{1},\ldots,p_{s}$ be prime numbers such that $p_{i}\nmid M$. If

$U_{n_{k}}+\cdots+U_{n_{1}}=p_{1}^{r_{1}}\cdots q_{s}^{r_{s}}\cdot M$ (5.6)

with $n_{k}>\cdots>n_{1}$, then

$n_{k}<\left(c_{35}C_{7}^{s}Qk\log(kQ)\right)^{k}(\log A).$

###### Proof.

From Lemma 5.1, we may assume $n_{k}>\ell$. Rewrite (5.6) as

$M\cdot p_{1}^{r_{1}}\cdots
p_{s}^{r_{s}}-f_{1}(n_{k})\alpha_{1}^{n_{k}}=\sum_{i=2}^{t}f_{i}(n_{k})\alpha_{i}^{n_{k}}+\sum_{j=1}^{k-1}U_{n_{j}}.$

Without loss of generality, we assume
$|\alpha_{2}|\geq\cdots\geq|\alpha_{t}|$. By Lemma 3.3, the above equation
becomes

$|M\cdot p_{1}^{r_{1}}\cdots
p_{s}^{r_{s}}-f_{1}(n_{k})\alpha_{1}^{n_{k}}|<c_{20}n_{k}^{r-1}|\alpha_{2}|^{n_{k}}+c_{21}(k-1)n_{k}^{r-1}\alpha_{1}^{n_{k-1}}.$
(5.7)

Dividing both sides of (5.7) by $|f_{1}(n_{k})\alpha_{1}^{n_{k}}|$, we have

$|M\cdot p_{1}^{r_{1}}\cdots
p_{s}^{r_{s}}f_{1}(n_{k})^{-1}\alpha_{1}^{-n_{k}}-1|\leq
c_{22}n_{k}^{r}\alpha_{1}^{n_{k-1}-n_{k}}.$ (5.8)

Thus, from (5.8), we have

$\log|\Lambda_{1}|<-c_{23}(n_{k}-n_{k-1})\log{n_{k}},$ (5.9)

where

$\Lambda_{1}:=\left(\prod_{j=1}^{s}p_{j}^{r_{j}}\right)\alpha_{1}^{-n_{k}}\left(Mf_{1}(n_{k})^{-1}\right)-1,$

is our first linear form. By Lemma 5.1, $\Lambda_{1}$ is non-zero as
$n_{k}>\ell$. Hence, we can apply Proposition 6 to $\Lambda_{1}$ with $D\leq
r^{t},m=s+2,\gamma_{j}=p_{j},(1\leq j\leq s),\gamma_{s+1}=\alpha_{1}$ and
$\gamma_{s+2}=\left(Mf_{1}(n_{k})^{-1}\right)$. Set

$Q:=\prod_{i=1}^{s}\log p_{i},\quad\log A:=\max\\{h(Mf_{1}(n_{k})^{-1}),2\\}.$
(5.10)

Using equation (5.6) and Lemma 3.3, one can show that $r_{j}\log
p_{j}\leq(n_{k}+1)\log\alpha_{1}$. Thus, we may choose $B=c_{24}n_{k}/\log A$.
By applying Proposition 6 with the above parameters we obtain that

$\log|\Lambda_{1}|>-c_{25}C_{1}^{s}Q(\log A)\log\left(\frac{n_{k}}{\log
A}\right).$ (5.11)

Thus, from (5.9) and (5.11), we get

$n_{k}-n_{k-1}\leq c_{26}C_{2}^{s}Q(\log A)\log\left(\frac{n_{k}}{\log
A}\right).$ (5.12)

Proceeding in this similar way, for $i=2,\ldots,k-1$, we have

$\displaystyle M\cdot$ $\displaystyle p_{1}^{r_{1}}\cdots
p_{s}^{r_{s}}-\left(\sum_{j=i}^{k}f_{1}(n_{j})\alpha_{1}^{n_{j}}\right)=\sum_{j=i}^{k}\sum_{\ell=2}^{t}f_{\ell}(n_{j})\alpha_{\ell}^{n_{j}}+\sum_{j=1}^{i-1}U_{n_{j}}.$

This implies that

$\displaystyle\Lambda_{i}:=$
$\displaystyle\left|M\left(\prod_{j=1}^{s}p_{j}^{r_{j}}\right)f_{1}(n_{k})^{-1}\alpha_{1}^{-n_{k}}\left(1+\frac{f_{1}(n_{k-1})}{f_{1}(n_{k})}\alpha_{1}^{n_{k-1}-n_{k}}+\cdots+\frac{f_{1}(n_{i})}{f_{1}(n_{k})}\alpha_{1}^{n_{i}-n_{k}}\right)^{-1}-1\right|$
$\displaystyle=\left|\left(\prod_{j=1}^{s}p_{j}^{r_{j}}\right)\frac{Mf_{1}(n_{k})^{-1}}{\left(1+\frac{f_{1}(n_{k-1})}{f_{1}(n_{k})}\alpha_{1}^{n_{k-1}-n_{k}}+\cdots+\frac{f_{1}(n_{i})}{f_{1}(n_{k})}\alpha_{1}^{n_{i}-n_{k}}\right)}\alpha_{1}^{-n_{k}}-1\right|$
$\displaystyle\leq c_{27}(k-i)n_{k}^{r}\alpha_{1}^{n_{i-1}-n_{k}}$

and hence

$\log|\Lambda_{i}|\leq-c_{28}(n_{k}-n_{i-1})\log n_{k}.$ (5.13)

By Lemma 5.1, $\Lambda_{i}$ is non-zero. By Proposition 6, we get

$\log|\Lambda_{i}|\geq-c_{29}C_{3}^{s}Q(\log
A+|n_{k}-n_{i}|)\log\frac{n_{k}}{\log A+n_{k}-n_{i}}.$ (5.14)

From, (5.13) and (5.14), we have

$n_{k}-n_{i-1}+\log A\leq c_{30}C_{3}^{s}Q(\log
A+|n_{k}-n_{i}|)\log\frac{n_{k}}{\log A+n_{k}-n_{i}}.$

As a consequence, we have

$n_{k}-n_{1}\leq n_{k}-n_{1}+\log A\leq c_{30}C_{3}^{s}Q(\log
A+|n_{k}-n_{2}|)\log\frac{n_{k}}{\log A}.$ (5.15)

and for $i=3,\ldots,k-1$, we get

$n_{k}-n_{i-1}+\log A\leq c_{30}C_{3}^{s}Q(\log
A+|n_{k}-n_{i}|)\log\frac{n_{k}}{\log A}.$ (5.16)

Thus from (5.12), (5.15) and (5.16), we get,

$\displaystyle n_{k}-n_{1}\leq\left(c_{31}C_{4}^{s}Q\right)^{k-1}(\log
A)\left(\log\frac{n_{k}}{\log A}\right)^{k-1}.$ (5.17)

Finally, we want to compute the upper bound of $n_{k}$. Note that

$\displaystyle M\cdot$ $\displaystyle p_{1}^{r_{1}}\cdots
p_{s}^{r_{s}}-\left(\sum_{j=1}^{k}f_{1}(n_{j})\alpha_{1}^{n_{j}}\right)=\sum_{j=1}^{k}\sum_{\ell=2}^{t}f_{\ell}(n_{j})\alpha_{\ell}^{n_{j}}.$

We consider the following linear form

$\displaystyle\Lambda_{k}:=$
$\displaystyle\left|M\left(\prod_{j=1}^{s}p_{j}^{r_{j}}\right)f_{1}(n_{k})^{-1}\alpha_{1}^{-n_{k}}\left(1+\frac{f_{1}(n_{k-1})}{f_{1}(n_{k})}\alpha_{1}^{n_{k-1}-n_{k}}+\cdots+\frac{f_{1}(n_{1})}{f_{1}(n_{k})}\alpha_{1}^{n_{1}-n_{k}}\right)^{-1}-1\right|$
$\displaystyle\leq c_{32}n_{k}^{r}(|\alpha_{2}|/\alpha_{1})^{n_{k}}.$

By Lemma 5.1, $\Lambda_{k}$ is non-zero. By Proposition 6, we get

$\log|\Lambda_{k}|\geq-
c_{33}C_{5}^{s}Q\left(n_{k}-n_{1}\right)\left(\log\frac{n_{k}}{\log
A}\right).$ (5.18)

Comparing the lower and upper bound of $\log|\Lambda_{k}|$ and using the upper
bound for $n_{k}-n_{1}$, we obtain

$n_{k}\leq\left(c_{34}C_{6}^{s}Q\right)^{k}(\log A)\left(\log\frac{n_{k}}{\log
A}\right)^{k}.$

Since $X\leq Y\log X$ implies $X\leq 2Y\log Y$ for all real number $X,Y\geq
3$, we have

$n_{k}<\left(c_{35}C_{7}^{s}Qk\log(kQ)\right)^{k}(\log A).$ (5.19)

This completes the proof of lemma. ∎

###  5.3. Proof of Theorem 2.

From equation (5.10),

$\log A\leq\log|M|+c_{36}\log n_{k}.$

If $|M|<n_{k}^{c_{36}}$, then $\log A\leq 2c_{36}\log n_{k}$. By Lemma 5.2

$n_{k}<\left(c_{37}C_{7}^{s}Qk\log(kQ)\right)^{k}(\log n_{k})$

and this implies

$n_{k}\leq\left(c_{38}C_{8}^{s}Qk\log(kQ)^{2}\right).$

Now assume that $|M|>n_{k}^{c_{36}}$, then $A\leq M^{2}$. From Lemma 5.2 we
get

$n_{k}<\left(c_{39}C_{7}^{s}Qk\log(kQ)\right)^{k}(\log|M|).$

Further,

$\frac{U_{j}^{(k)}}{[U_{j}^{(k)}]_{S}}=M\geq
2^{c_{40}n_{k}(C_{8}^{s}Qk\log(kQ))^{-k}}\geq(U_{j}^{(k)})^{c_{41}(C_{8}^{s}Qk\log(kQ))^{-k}},$

and this implies

$[U_{j}^{(k)}]_{S}<\left(U_{j}^{(k)}\right)^{1-c_{41}(C_{8}^{s}Qk\log(kQ))^{-k}}.$

This completes the proof of Theorem 2.

## References

  * [1] A. Bérczes, L. Hajdu, I. Pink and S. S. Rout, _Sums of $S$-units in recurrence sequences_ J. Number Theory 196 (2019), 353-363.
  * [2] A. Brauer, _On algebraic equations with all but one root in the interior of the unit circle_ , Math. Nachr. 39 (1991), 108-116.
  * [3] Y. Bugeaud and J.-H. Evertse, _$S$ -parts of terms of integer linear recurrence sequences_, Mathematika 63 (2017), 840-851.
  * [4] Y. Bugeaud, _On the digital representation of integers with bounded prime factors_ , Osaka J. Math. 55 (2018), 315-324.
  * [5] Y. Bugeaud, _On the Zeckendorf representation of smooth numbers_ , arXiv:1909.03863v1.
  * [6] Y. Bugeaud, J.-H. Evertse and K. Györy, _$S$ -parts of values of univariate polynomials, binary forms and decomposable forms at integral points_, Acta Arith. 184 (2018), 151-185.
  * [7] Y. Bugeaud and H. Kaneko, _On the digital representation of smooth numbers_ , Math. Proc. Cambridge Philos. Soc. 165 (2018), 533-540.
  * [8] J.-H. Evertse, _On sums of $S$-units and linear recurrences_, Compos. Math. 53 (1984), 225–244.
  * [9] J.-H. Evertse and K. Győry, _Unit Equations in Diophantine Number Theory_ , Cambridge University Press, 2015, pp. 378.
  * [10] P. Grabner and R. F. Tichy, _Contributions to digit expansions with respect to linear recurrences,_ J. Number Theory 36 (1990), 160-169.
  * [11] S. S. Gross and A. F. Vincent, _On the factorization of $f(n)$ for $f(x)$ in $\mathbb{Z}[X]$_, Int. J. Number Theory 9 (2013), 1225–1236.
  * [12] K. Mahler, _A remark on recursive sequences_ , J. Math. Sci. Delhi 1 (1966), 12–17.
  * [13] E. M. Matveev, An explicit lower bound for a homogeneous rational linear form in the logarithms of algebraic numbers II, Izv. Math. 64 (2000), 1217–1269.
  * [14] E. Mazumdar and S. S. Rout, _Prime powers in sums of terms of binary recurrence sequences_ , Monatsh. Math. 189 (2019), 695–714.
  * [15] A. Pethö and R. F. Tichy, _On digit expansions with respect to linear recurrences,_ J. Number Theory 35 (1989), 243 - 256.
  * [16] A. Pethő and R. F. Tichy, _$S$ -unit equations, linear recurrences and digit expansions_, Publ. Math. Debrecen 42 (1993) 145–154.
  * [17] A. J. van der Poorten and H. P. Schlickewei, _The growth condition for recurrence sequences_ , Macquarie University Math. Rep. (1982), 82–0041.
  * [18] D. Ridout, _The $p$-adic generalization of the Thue-Siegel-Roth theorem_, Mathematika 5 (1958) 40–48.
  * [19] T. N. Shorey and R. Tijdeman, _Exponential Diophantine Equations_ , Cambridge University Press, Cambridge, 1986.
  * [20] C. L. Stewart, _A note on the product of consecutive integers_ , in Topics in Classical Number Theory, Vols. I, II, Colloq. Math. Soc. János Bolyai, Vol. 34 (North-Holland, Amsterdam, 1984), pp. 1523-1537.