# Increasing Interference Detection in Quantum Cryptography using the Quantum
Fourier Transform

Nicholas J.C. Papadopoulos, Kirby Linvill  Department of Computer Science
University of Colorado Boulder
{Nicholas.Papadopoulos<EMAIL_ADDRESS>
###### Abstract

Quantum key distribution (QKD) and quantum message encryption protocols
promise a secure way to distribute information while detecting eavesdropping.
However, current protocols may suffer from significantly reduced eavesdropping
protection when only a subset of qubits are observed by an attacker. In this
paper, we present two quantum cryptographic protocols leveraging the quantum
Fourier transform (QFT) and show their higher effectiveness even when an
attacker measures only a subset of the transmitted qubits. The foremost of
these protocols is a novel QKD method that leverages this effectiveness of the
QFT while being more practical than previously proposed QFT-based protocols,
most notably by not relying on quantum memory. We additionally show how
existing quantum encryption methods can be augmented with a QFT-based approach
to improve eavesdropping detection. Finally, we provide equations to analyze
different QFT-based detection schemes within these protocols so that protocol
designers can make custom schemes for their purpose.

###### Keywords:

Quantum cryptography, key distribution, quantum Fourier transform.

##  I Introduction

Quantum key distribution (QKD) is a paradigm that employs quantum principles
to exchange a secret key which can then be used to establish secure
communication channels. Unlike classical key agreement algorithms, QKD schemes
allow participants to detect when an eavesdropper listens in on the exchanged
key information. Importantly, this eavesdropping detection relies on well-
established properties of quantum mechanics, namely the no-cloning theorem [1]
and state collapse upon measurement, instead of on the assumed hardness of
problems such as the discrete log problem used in the classical Diffie-Hellman
key exchange algorithm [2] or the semiprime factoring problem used in the
Rivest–Shamir–Adleman (RSA) [3] public encryption algorithm. This reliance on
quantum mechanical properties is especially advantageous given that Shor [4]
devised a way to efficiently break these classical cryptographic schemes using
a sufficiently large quantum computer.

The BB84 protocol, introduced by Bennett and Brassard in 1984 [5], was the
first such QKD protocol. Several other QKD schemes have been developed that
rely on the same underlying principles. Unfortunately, in many QKD schemes,
including BB84, subsequently transmitted qubits are independent of previous
qubits. This independence leaves these schemes susceptible to partial
information leakage and the concept of a “many-copies” attack introduced in
Sec. III-B, which is solely an issue in quantum-based protocols. Partial
information leakage allows an eavesdropper to significantly reduce the search
space without needing to extract the whole message, while the “many-copies
attack” allows an adversary to exploit vulnerabilities in conventional QKD
methods by flooding the system with replicated quantum states. Through the
“many-copies attack” attack, an eavesdropper could potentially extract the
entire message with certainty and without being detected.

Our work introduces a novel two-pass QKD approach employing the quantum
Fourier transform (QFT) [6] to better resist these attacks. Additionally, we
extend the application of the QFT to direct message encryption, presenting a
three-pass protocol that combines the benefits of confidential communication
with an increase in eavesdropping detection. As part of our contributions, we
explore various eavesdropping detection schemes within QFT-based cryptographic
protocols and discuss the implications of different encoding strategies,
considering scenarios where carefully chosen qubits are measured by an
eavesdropper. This analysis offers insights into the design of robust
eavesdropping detection schemes tailored to specific application requirements.

#### Contributions

Our contributions are summarized as follows:

  * •

We introduce a novel QKD protocol that uses the QFT to improve eavesdropping
detection (Sec. IV-A). This scheme also provides an entirely quantum QKD
protocol, allowing for eavesdropping detection without the need for an
authenticated classical channel that other schemes require to protect against
intercept-resend attacks.

  * •

We show how Kak’s well-known quantum message encryption scheme [7] can be
augmented with the QFT, thereby improving its eavesdropping detection (Sec.
IV-C).

  * •

We introduce the many-copies attack, in which an attacker is able to use
partial observations to reconstruct a whole shared key (Sec. III-B).

  * •

We provide equations to analyze the probability of detecting an eavesdropper
when using QFT-based eavesdropping detection schemes, which we call
verification schemes (Sec. V).

  * •

We compare different key examples of QFT-based verification schemes to show
that our protocol is more effective in detecting eavesdroppers than other
protocols, and we show how one might want to cater such a scheme to their
specific case. (Sec. VI).

##  II Related Work

QKD has been a booming field since the foundational BB84 [5] protocol was
developed. Ekert subsequently proposed a protocol based on entanglement rather
than the impossibility of perfectly discriminating non-orthogonal states [8].
However, this entanglement is only between qubits that represent the same bit
of information. Ekert’s protocol lacks entanglement between subsequent qubits
representing different bits of information. As a result, Ekert’s protocol is
just as susceptible to the partial information leakage and “many-copies”
attack as BB84. Other, more recent QKD approaches derived from these works are
reviewed in more depth by [9]. The theoretical development of these protocols
has been accompanied by implementations on real hardware [10, 11, 12].

Unfortunately, real implementations have inspired attacks against the
necessarily imperfect implementations of these schemes [13]. For example, the
photon number splitting (PNS) attack [14] takes advantage of the fact that
physical implementations of QKD devices can emit more than one photon per
pulse. Mitigations against these PNS attacks include the use of decoy states
to verify that photon loss is within expected parameters [15, 16, 17]. Since
these mitigations against physical imperfections and side-channels are
typically orthogonal to the underlying scheme, we do not focus on such
mitigations for the scheme we introduce.

A few QKD schemes that entangle subsequent qubits have been proposed. Similar
to the QKD scheme we propose in this paper, Nagy, Akl, and Kershaw introduced
a QKD method utilizing the quantum Fourier transform (QFT) that improved upon
BB84-like protocols by causing entanglement if there is interference or a 3rd-
party observation [18]. However, the proposed method of Nagy et al. relies on
quantum memory, which may be seen as infeasible or unreliable with present
technology. In this paper, we propose a method that also uses the QFT, and
therefore leverages its benefits such as a high sensitivity to 3rd-party
observations, without relying on quantum memory to store qubits for some
indeterminate amount of time.

Other methods using the QFT for QKD have also been proposed. Xing-Yu Yan et
al. [19] proposed a QFT-based scheme to encode high-dimensional data using
qudits. They achieve higher information-density rates than other QKD schemes
but rely on a pre-shared $d$-dimensional quantum state, which is not a
standard assumption in QKD schemes as this would require trusted or
authenticated quantum channels. Xiaoqing Tan et al. [20] proposed another
scheme that distributes EPR pairs to two parties and applies the QFT to the
qubits of one of the parties. However, this protocol requires quantum memory,
similar to Nagy et al., both while Bob waits for Alice to communicate the
positions of the decoy photons and while Alice waits for Bob to communicate
his measurement bases.

In addition to providing a QKD scheme based on the QFT, we provide a scheme in
this paper to directly send encrypted messages. Kak [7] proposed a three-stage
protocol that allows Alice to send an encrypted message directly to Bob. This
eliminates the need for classical messaging while simultaneously protecting
the confidentiality of the sent data and allowing for the detection of Eve’s
presence. We propose a modified instance of Kak’s protocol using the QFT,
allowing for a higher sensitivity of detection under certain attacks while
still directly sending encrypted messages.

##  III Background: Notable Attacks on QKD Protocols

###  III-A Partial Information Leakage

QKD protocols aim to detect eavesdroppers on a quantum channel and therefore
must be analyzed with respect to a quantum adversary, typically called Eve.
One of the simplest attacks Eve can carry out is the intercept-resend attack,
in which Eve measures photons in transit in a chosen basis and then passes on
any prepared state of her choosing, often the measured state. The BB84
protocol protects against this attack by having its participants, typically
called Alice and Bob, choose a random subset of exchanged qubits to verify
that they indeed match the expected measurement values. This verification step
is conducted over an authenticated classical channel after the qubits have all
been exchanged. In the case of BB84, an attacker is expected to be detected
with probablity $1-(.75)^{|V|}$ where $V$ is the set of verification qubits,
meaning qubits used solely for detecting Eve’s presence, and $|V|$ is the
number of verification qubits. However, this protection assumes the quantum
adversary measures all the transmitted qubits.

An attacker could alternatively choose to only measure a subset of the qubits
transmitted over the wire, resulting in only partial information leakage in
exchange for a reduced chance of detection. For the BB84 protocol, the
expected chance of detection is $1-(.75)^{Pr[q\in V]*|V|}$ where $Pr[q\in V]$
is the probability that a qubit $q$ Eve measures is a verification qubit. In
the average case, this results in a decreased chance of detection in exchange
for partial information. However, in the worst case Eve will not measure any
verification qubits resulting in a probability of detection of $0$.
Furthermore, if the qubits that will be used as verification bits are
predictable, perhaps by relying on a weak pseudo-random number generator [21,
22] or perhaps by relying on a deterministic verification scheme, Eve can
ensure she always only measures non-verification qubits and therefore always
avoid detection.

Figure 1 shows an example of such an attack on the BB84 protocol. Alice first
generates a random message and encodes each qubit in a random choice of basis.
She then sends the qubits to Bob. Eve chooses to measure half of the qubits.
Alice and Bob then announce the bases they transmitted/measured in and discard
the bits for which they used different bases. Alice and Bob then publicly
choose the verification bits out of the remaining bits. In this case Eve was
lucky, and none of the bits she measured were verification bits, so she is not
detected.

Alice and Bob can optionally go through a privacy amplification process [23]
to reduce the information Eve learns about the exchanged key. However, if Eve
measured all of the exchanged key bits, she would on average learn half of the
bits that she measured. This is because she has a 50% of randomly choosing the
same basis in which Alice transmitted a qubit. Since she knows about half of
the exchanged key bits, Eve will then be able to significantly cut down the
possible keys after privacy amplification from $2^{|k|}$ to $2^{|k|/2}$, where
$|k|$ is the length of the derived key $k$ in bits, all while avoiding
detection.

Figure 1: Example partial leakage from the BB84 protocol. Eve only measures
some of the qubits Alice sends to Bob. She measures none of the verification
qubits and therefore has no chance of detection.

###  III-B The Many-Copies Attack

We introduce the concept of an attack where many copies of some state may be
sent by Alice or Bob. This could be done by any number of means, including
maliciously by Eve planting a bug in their computers to create and send many
copies of a transmission, or it could be an honest user-error or
misconfiguration in either hardware or software. We call this the many-copies
attack, and it can allow Eve to obtain information about bits in BB84 and
similar protocols without detection. By measuring some non-verification qubit
in many different bases over many copies of the quantum state, she would be
able to extract the intended value with certainty without detection. Eve could
do this for, in the worst case, each non-verification qubit sequentially
across many copies of the state to retrieve the whole message undetected. This
is similarly a problem in Kak’s three-stage protocol [7], where Eve could
potentially retrieve $U_{A}^{\dagger}$ using similar techniques and apply it
to the initial state to retrieve the original message.

| Original Copy | Copy 2 | Copy 3 | Copy 4
---|---|---|---|---
| Secret | Verification | Secret | Verification | Secret | Verification | Secret | Verification
Alice’s bits | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0
Alice’s sending basis | + | $\times$ | + | $\times$ | + | $\times$ | + | $\times$
Eve’s measuring basis | + |  | + |  | $\times$ |  | $\times$ |
Eve’s measurement | 1 |  | 1 |  | 1 |  | 0 |
Bob’s measuring basis | + | $\times$ | $\times$ | + | + | + | $\times$ | $\times$
Bob’s measurement | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0
Measurement bases match | ✓ | ✓ | ✗ | ✗ | ✓ | ✗ | ✗ | ✓
Verification passes |  | ✓ |  |  |  |  |  | ✓
TABLE I: An example of the many-copies attack on the BB84 protocol. Eve
remains undetected while finding the value of the secret bit.

Table I shows an example of this attack. Alice and Bob try to generate a 1-bit
secret key and use a single verification bit to try to detect Eve. Four total
copies of the message from Alice to Bob are sent, and Eve measures only the
secret key bit. One can see that this has no effect on the verification bit,
and so Eve will remain undetected. Eve, on the other hand, measures each basis
twice. She sees that one basis is consistent while the other has multiple
outputs. She can then conclude that Alice measured in the basis that was
consistent, and the intended bit value was the value that was measured from
that basis.

##  IV Memory-free Quantum Cryptographic Protocols using the QFT

We now present a two-pass quantum key distribution protocol using the quantum
Fourier transform for the purpose of quantum key distribution. The protocol
allows Alice to share a secret key of $|k|$ random bits with Bob such that
they have a higher probability of detecting an eavesdropper Eve compared to
BB84, regardless of which qubits Eve measures. Unlike the scheme presented in
[18], our method does not require quantum memory, i.e., holding the quantum
state until a later time, such as when further classical communication is
received. Instead, all state modifications and measurements in this protocol
are done upon reception of the state. This scheme is therefore much more
feasible to realize using current and near-future technology than schemes that
require qubit storage.

###  IV-A Quantum Key Distribution Protocol

The protocol consists of four steps: phase scrambling, key encoding, key
decoding, and key extraction. The first three of these steps can be carried
out using the circuit shown in Fig. 2.

@C=1em @R=1em & Bob Alice Bob

Scrambling Encoding Decoding

H Z^θ_0 U_p(2^p-1m) Z^-θ_0 5QFT^†
H Z^θ_1 U_p(2^p-2 m) Z^-θ_1 QFT^†
QFT^†
⋮ QFT^† ⋮
QFT^†
H Z^θ_p-1 U_p(m) Z^-θ_p-1 QFT^†

212160em. 161160em. 431150em– 471190em– 11011100em. 41111150em–
5101.0em5.0em—ψ⟩ = —0⟩^⊗p

Figure 2: The circuit for the quantum portion of the QFT-based QKD protocol
presented in this paper.

#### Scrambling

First, Alice and Bob determine the verification bit string $v$ along with the
positions the bits will occupy in the transmitted messages. This scheme,
unlike BB84, does not require any secrecy regarding the verification bits, so
we assume this is public information to which Eve has access. Therefore, this
scheme allows for an entirely quantum key distribution protocol since no
classical communication is needed for verification. Alternatively, Alice may
randomly create a verification bit string in secret, similar to in BB84, but
this requires classical communication between the two parties afterwards to
verify it. Possible schemes for verification are discussed in Sec. VI.

Bob creates a state with the quantum register $\ket{\psi}=\ket{+}^{\otimes
p}$, where $p=|k|+|v|$, $|k|$ is the number of bits in the key to be shared,
and $|v|$ is the number of verification bits. Here,
$\ket{+}=H\ket{0}=\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$, where
$H=\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\\ 1&-1\end{bmatrix}$. Next, he
applies $p$ random phase shifts,

$\text{Scr}(\theta)=\bigotimes_{j=0}^{p-1}Z^{\theta_{p-1-j}},$ (1)

where $\theta_{j}$ is the random phase applied to the $j$-th qubit and
$Z^{\theta_{j}}=\begin{bmatrix}1&0\\\ 0&e^{i\theta_{j}}\end{bmatrix}$. This
results in the register
$\ket{\psi}=\frac{1}{\sqrt{2^{p}}}(\ket{0}+e^{i\theta_{p-1}}\ket{1})(\ket{0}+e^{i\theta_{p-2}}\ket{1})...(\ket{0}+e^{i\theta_{0}}\ket{1})$.
Bob sends this state to Alice.

Preparing these bits with random phases that only Bob knows ensures that, upon
interference by Eve, Eve will destroy and cannot replicate these phases. In
that case, when Bob reverses the random phases in the decoding step, the state
needed to keep the $QFT^{\dagger}$ from causing entanglement will be
destroyed, thereby causing entanglement and exposing the interference. In some
sense, these random phases may be considered a secret key, known only to Bob,
that Alice can use without knowledge of it.

#### Encoding

Alice generates a bit string $k$, which is the key she will share with Bob.
Alice then inserts the verification bits into either predetermined or randomly
generated positions, resulting in the bit string $m$, which may also be
interpreted as an integer value. She then encodes $m$ by applying

$\text{Enc}(m)=\bigotimes_{j=0}^{p-1}U_{p}(2^{j}m),$ (2)

where $U_{p}(x)=Z^{\pi x/2^{p-1}}$. Alice sends this state to Bob.

#### Decoding

Bob undoes his rotations, followed by $QFT^{\dagger}$, to retrieve
$m^{\prime}$

$\text{Dec}(\theta)=QFT^{\dagger}\bigotimes_{j=0}^{p-1}Z^{-\theta_{p-1-j}}.$
(3)

The circuit for the steps up until this point is shown in Fig. 2.

#### Extraction

Bob can then extract the verification bit positions, either predetermined or
classically communicated after measurement, from $m^{\prime}$ resulting in
$v^{\prime}$. The remaining bits in $m^{\prime}$ then form $k^{\prime}$. If
$v^{\prime}=v$, or if $v^{\prime}$ differs from $v$ by less than some agreed-
upon limit, Bob may assume that Eve did not interfere with the state and that
$k^{\prime}=k$, meaning that Alice and Bob now share a key $k$. Otherwise,
they throw the key out and try again.

Note that this circuit resembles the Quantum Phase Estimation circuit [6] once
Bob’s secret phases are undone, ensuring that Bob can reliably recover the key
$k$ when there is no eavesdropper.

###  IV-B Interference Resistance

In order to always evade detection, Eve must measure in the basis dependent on
Bob’s (secret) random phases. It is extremely unlikely that Eve guesses the
basis of the random phases that Bob initially encoded. In fact, the
probability that Eve guesses correctly is 0 if Bob chooses rotations from a
continuous distribution. Therefore, any measurement Eve makes will collapse to
a different state than Bob’s initial state with probability 1. When he undoes
his state in the decoding stage, the measured qubits will have random phases,
causing the $QFT^{\dagger}$ to apply random rotations to subsequent qubits,
increasing the chance of mismatched verification qubits. This is explored in
[18] and Sec. V. Thus, it is difficult for Eve to avoid detection by Bob in
any intercept-resend attack. An optional authenticated classical channel can
be used once Bob obtains the key to verify that the key was from Alice instead
of Eve, thereby preventing an impersonation attack as well.

###  IV-C Direct Message Encryption

@C=1em @R=1em & Alice Bob Alice Bob

H U_p(2^p-1m) Z^θ_0 Z^ϕ_0 Z^-θ_0 Z^-ϕ_0 5QFT^†
H U_p(2^p-2 m) Z^θ_1 Z^ϕ_1 Z^-θ_1 Z^-ϕ_1 QFT^†
QFT^†
⋮ QFT^† ⋮
QFT^†
H U_p(m) Z^θ_p-1 Z^ϕ_p-1 Z^-θ_p-1 Z^-ϕ_p-1 QFT^†

212170em. 17970em. 19990em. 1119110em. 381em5em—0⟩^⊗p

Figure 3: The circuit for direct message encryption using the QFT.

The QKD method introduced in Sec. IV-A should not, however, be used to
directly send sensitive information since Eve can measure Bob’s initial
transmission and know the state of the system when Alice receives it. Eve can
then measure Alice’s transmission in the QFT basis minus the measured state to
retrieve Alice’s string. Since the verification bit positions may be public
information, Eve could then know $k$ herself. Instead, we introduce a QFT-
based three-pass protocol here that can be used to directly send an encrypted
message while preventing partial leakage.

Specifically, the protocol proceeds according to Kak’s protocol [7], except
the secret state to transfer is encoded by inserting the verification bits in
their respective positions. This results in the string $m$ to which the
$\text{Enc}(m)$ transformation (Eq. 2) is applied and retrieved at the end
with $QFT^{\dagger}$. Since Eve cannot measure before the message was
concealed with Alice’s secret phases and released, Eve is unlikely to recover
any meaningful phase information unless she knows the secret phases.

The analyses of verification bit schemes discussed in Secs. V and VI apply to
this three-pass scheme when $U_{A}=Scr(\theta)$ and $U_{B}=Scr(\phi)$, where
$\theta_{i}$ is Alice’s random phase on the $i$-th qubit and $\phi_{i}$ is
Bob’s. The three-pass circuit with these unitary operations is shown in Fig.
3.

##  V Probability of Interference Detection

We may analyze the effectiveness of different verification layouts and schemes
by calculating the likelihood of detecting interference from Eve. A
verification qubit contributes to this detection by the likelihood that it
measures incorrectly, i.e., it measures as zero when intended to be one or
vice versa. This probability is determined by the error in phase rotation
before the final Hadamard gate, $H$, on that qubit in the $QFT^{\dagger}$
gate.

In the below analysis we assume no transmission noise as well as no errors in
gates, qubits, or circuit implementation. In practice, one issue with the QFT
encoding is the propagation of errors. Especially during the Noisy
Intermediate Scale Quantum (NISQ) computing era, errors may propagate and be
misinterpreted as Eve interference with a higher probability than BB84. The
downside of this proposed scheme, then, is more often having to restart the
protocol unnecessarily. We leave such a noise-sensitive protocol analysis for
future work.

###  V-A Probability of measuring correctly due to a phase error

To always measure a qubit as zero in the Hadamard basis, the relative phase
rotation of that qubit needs to be exactly zero. So, the state before the
final Hadamard in the $QFT^{\dagger}$ gate should be
$\frac{1}{\sqrt{2}}(\ket{0}+\ket{1})$. With an error in the phase rotation,
say $\theta_{e}$, we have the state after the Hadamard gate, $H$, application
as

$\frac{1}{\sqrt{2}}H(\ket{0}+e^{i\theta_{e}}\ket{1})=\frac{1}{2}((1+e^{i\theta_{e}})\ket{0}+(1-e^{i\theta_{e}})\ket{1}).$
(4)

Hence, the probability that the qubit measures correctly as zero given some
rotation error is

$\Pr_{r,0}(\theta_{e})=\left|\frac{1}{2}(1+e^{i\theta_{e}})\right|^{2}.$ (5)

In the case where the intended measurement is one, the state before the final
Hadamard should be $\frac{1}{\sqrt{2}}(\ket{0}+e^{i\pi}\ket{1})$. With an
error in the phase rotation, say $\theta_{e}$, we have the state after the
Hadamard gate application as
$\frac{1}{2}((1+e^{i(\pi+\theta_{e})})\ket{0}+(1-e^{i(\pi+\theta_{e})})\ket{1})$.
Hence, the probability that the qubit measures correctly as one given some
rotation error is

$\displaystyle\Pr_{r,1}(\theta_{e})$
$\displaystyle=\left|\frac{1}{2}(1-e^{i(\pi+\theta_{e})})\right|^{2}$ (6)
$\displaystyle=\left|\frac{1}{2}(1-e^{i\pi}e^{i\theta_{e}})\right|^{2}$
$\displaystyle=\left|\frac{1}{2}(1+e^{i\theta_{e}})\right|^{2}$
$\displaystyle=\Pr_{r,0}(\theta_{e}).$

Therefore, the probability that the qubit measures correctly is the same,
given some phase error, whether the intended measurement is supposed to be
zero or one. So, we use the simpler expression as the equation to determine
the probability of measuring correctly given some rotation error,
$\Pr_{r}(\theta_{e})$, as

$\displaystyle\Pr_{r}(\theta_{e})$ $\displaystyle=\Pr_{r,0}(\theta_{e})$ (7)
$\displaystyle=\left|\frac{1}{2}(1+e^{i\theta_{e}})\right|^{2}.$

###  V-B Rotation effect from previous qubits

Since $QFT^{\dagger}$ can be considered as each previous qubit having been
measured before applying the controlled phase rotation [24], the phase error
that will be applied to a particular qubit, which we refer to as the target
qubit, depends on the previous qubits that measured incorrectly. If there are
no errors in previous qubits, then the target qubit will have no additional
phase error and hence measure correctly if not touched by the attacker. If
there is an error in a previous qubit, then the rotation effect depends on how
far away the incorrect qubit is from the target qubit as well as whether the
incorrect qubit was intended to be one or zero.

If the intention was zero, then it will have incorrectly measured one,
triggering the controlled phase rotation in $QFT^{\dagger}$ and adding a
negative phase error to the target. If the intention was one, then it was
supposed to trigger the controlled phase rotation but instead did not,
effectively adding a positive phase error to the target.

The magnitude of the rotation is directly due to the phase rotation applied in
the $QFT^{\dagger}$ gate. Denote the actual measured outcome $A$ of $n$
previous qubits as a binary array where $a_{i}=1$ means that the qubit $i$ was
measured as one, and $a_{i}=0$ means that it was measured as zero. We also
denote the intended outcome of the qubit measurements as a binary array $B$,
where $b_{i}\in\\{0,1\\}$ denotes the intended outcome of qubit $q_{j}$. We
say that the rotation effect applied to a qubit $q_{t}$ due to a previous
qubit $q_{j}$, where $j<t$, is

$\displaystyle R(t,j,A,B)$ $\displaystyle=(b_{j}-a_{j})\frac{\pi}{2^{t-j}}.$
(8)

Finding the probability of a target qubit measuring correctly due to the
rotation effect from previous qubits depends, then, on the intended and actual
measurement outcomes of the previous qubits. More precisely, the cumulative
rotation error $\theta_{e}$ on a qubit $q_{t}$ given intended measurements $B$
and actual measurements $A$ is computed as

$\theta_{e}(t,A,B)=\sum_{j=0}^{t-1}R(t,j,B,A).$ (9)

###  V-C Probablity of measuring a qubit correctly

The probability that the previous qubits to the target qubit $q_{t}$ lie in
the outcome $A$ is

$\displaystyle\Pr_{p}(t,A,B)$
$\displaystyle=\prod_{j=0}^{t-1}\begin{cases}\Pr_{c}(j,B)&a_{j}=b_{j}\\\
1-\Pr_{c}(j,B)&\text{otherwise},\end{cases}$ (10)

where $\Pr_{c}(j,B)$ is the probability of qubit at index $j$ measuring
correctly. This probability is determined by summing, for each possible
measurement outcome of previous qubits, the product of the probability of
obtaining that measurement outcome and the probability of measuring the target
qubit correctly given the resulting rotation effect,

$\displaystyle\Pr_{c}(t,B)$
$\displaystyle=\sum_{A\in\\{0,1\\}^{t}}\Pr_{p}(t,A,B)\Pr_{r}(\theta_{e}(t,A,B)).$
(11)

There are two special cases to this equation. (1) If the target qubit has been
measured by Eve, then we simply say that $\Pr_{c}(t,B)=.5$. This is because
since Eve’s best option is to “undo” some random rotation and measure in the
X-basis, by expectation there will be an equal chance of measuring correctly
or incorrectly after the subsequent $QFT^{\dagger}$ gate regardless of phase
errors induced by previous measurements. This is also explored in [18]. (2) If
the target bit is zero and Eve did not measure it, then $\Pr_{c}(t,B)=1$.

One can then determine the total probability of detecting Eve, here defined as
the probability that at least one verification bit is measured incorrectly.
This probability, given some $B$ and the bit indices of the verification bits,
$V$, is

$\Pr_{e}(V,B)=1-\prod_{t\in V}\Pr_{c}(t,B).$ (12)

Note that a consequence of our protocol is that phase error contributions from
different qubits can have different signs, and can therefore diminish the
collective phase error. For example, suppose $q_{1}$ incorrectly measured as
1, leading to a negative phase error contribution on future qubits, and
suppose $q_{3}$ incorrectly measured as 0, leading to a positive phase error
contribution on future qubits. Then the collective phase error on $q_{4}$ is
$-\frac{\pi}{2^{3}}+\frac{\pi}{2^{1}}$, a diminished phase error due to the
opposing signs of $q_{1}$ and $q_{3}$. As a consequence, the probability of
detecting an attacker depends on the intended measurement outcome $B$.

Since the probability of detection is dependent on the specific $B$, it can
then be computed by ranging over a set of possible intended measurement
outcomes. One way this overall chance may be computed is by averaging the
obtained probabilities. However, it is safer to consider the case that phase
errors introduced by the eavesdropper interfere with each other leading to the
worst likelihood of detection. This worst-case analysis can be accomplished by
instead taking the minimum probability of detection, where the qubits are most
likely to measure correctly despite any phase errors.

Note that this formula takes exponential time to compute. We opt to
analytically compute probabilities of detection for small numbers of qubits in
Fig. 5. However, when comparing verification schemes for implementations it
may be preferable to instead simulate the probability of detection using the
parameters of the physical implementation and scheme.

##  VI Analysis of Verification Schemes

Figure 4: Example verification schemes. Each square represents a transmitted
qubit. Qubits marked with $v$ are used for verification, and qubits marked
with $E$ are qubits that Eve measured. Qubits marked with $QFT$ denote
compartments of QFT encoding. (a) BB84 with random verification qubit
placement and Eve measuring all qubits. (b) Two-pass, QFT-based QKD with
random verification qubit placement and Eve measuring all qubits. (c)
Compartmentalized two-pass, QFT-based QKD with one verification qubit per key
qubit. (d) Uncompartmentalized two-pass, QFT-based QKD with one verification
qubit per key qubit. (e) Compartmentalized two-pass, QFT-based QKD with two
verification qubits per key qubit. (f) Uncompartmentalized two-pass, QFT-based
QKD with two verification qubits per key qubit. Eve is assumed to only measure
key qubits in (c)-(f).

The probability of detecting interference from an eavesdropper is dependent on
the verification scheme used. We first discuss an analogous verification
scheme to the one used in BB84 [5]. Notably our protocol with this scheme
provides improvements against both complete and partial attacks. We then
present a collection of public verification schemes and analyze their
detection performance. Notably the probability of detecting an eavesdropper
using public verification schemes in protocols like BB84 is 0, while our
protocol still allows for detecting the eavesdropper in these cases.

###  VI-A Analogous Verification Scheme to BB84

The verification scheme in BB84 involves random post-selection of verification
qubits. Specifically, Alice and Bob agree on a random subset of qubits to
verify. One such choice of random qubits is shown in Fig. 4(a). We can
therefore describe an analogous verification scheme for the protocol
introduced in Sec. IV-A where the same verification qubits are chosen as shown
in Fig. 4(b). To present a fair comparison, we assume the attacker does not
know which bits are verification bits a priori. This can be achieved by Alice
secretly choosing the verification qubit positions when constructing her
message and then later conveying those positions to Bob after his
measurements.

We may begin analyzing the chance of detection in the simple case that Eve
measures all transmitted qubits, the typical attacker model when analyzing QKD
schemes. BB84, shown in Fig. 4(a), has a $1-(.75)^{|v|}$ chance of detecting
Eve when all the verification qubits are measured. This is because Eve is only
detectable if she both picks the incorrect basis for a qubit (probability
$0.5$) and Bob measures the wrong outcome for that qubit (probability $0.5$),
resulting in only a probability of detection of $0.25$ for each individual
verification qubit. However, in our proposed protocol with an analogous
verification scheme, shown in Fig. 4(b), each verification qubit will have a
$.5$ chance of measuring correctly (Eq. 11). This results in an overall
probability of $1-(.5)^{|v|}$ of Eve being detected. In this case, QDK using
QFT outperforms BB84 significantly.

It is also the case that our proposed QKD protocol outperforms BB84 in
detecting an eavesdropper when Eve measures only a subset of the transmitted
qubits. This scenario corresponds to the partial information leakage attack
mentioned in Sec. III-A. Let the chance of detecting an eavesdropper be
defined by Eq. 12, except where $\Pr_{c}(t,B)$, as defined in the QFT case by
Eq. 11, can be differently defined for different protocols. For clarity we use
$\Pr_{e,BB84}(V,B)$ to denote probabilities for the BB84 protocol, and
$\Pr_{e,QFT}(V,B)$ to denote probabilities for our protocol.

######  Lemma VI.1.

The probability of detection for our protocol is at least as great as that for
BB84: $\Pr_{e,BB84}(V,B)\leq\Pr_{e,QFT}(V,B)$

###### Proof sketch.

For each qubit, assume Eve measures a qubit from our protocol if and only if
Eve measures the corresponding qubit in the BB84 protocol (proof by coupling).

By the definition of $\Pr_{e}(V,B)$, ${\prod_{t\in
V}\Pr_{c,BB84}(t,B)\geq\prod_{t\in
V}\Pr_{c,QFT}(t,B)}\implies{\Pr_{e,BB84}(V,B)\leq\Pr_{e,QFT}}(V,B)$.

We then consider each qubit by ascending index $i$. Since we assume noiseless
protocols, let $\Pr_{c}(i,B)=1$ unless otherwise specified.

######  Case 1 (Eve does not measure $q_{i}$, $q_{i}$ is not a verification
qubit).

No effect in this case.

######  Case 2 (Eve measures $q_{i}$, $q_{i}$ is not a verification qubit).

In BB84, non-verification qubits are independent from verification qubits. As
a result, measuring non-verification qubits does not effect verification
qubits.

In our protocol, this could potentially cause a phase rotation on subsequent
verification qubits, so $\forall j.\;j>i\implies\Pr_{c,QFT}(j,B)\leq 1$. In
other words, measuring a non-verification qubit may introduce a probability of
error in later verification qubits.

######  Case 3 (Eve does not measure $q_{i}$, $q_{i}$ is a verification
qubit).

For BB84, verification qubits are independent from non-verification qubits. As
a result, there is no effect on verification qubits if it is untouched by Eve.

For our protocol, if no previous qubit was measured by Eve, then there is no
potential measurable effect. In this case $\Pr_{c,QFT}(i,B)=1$, equal to the
probability of evasion in BB84. However, if a previous qubit was measured by
Eve, then by Case 2 $\Pr_{c,QFT}(i,B)\leq 1$, meaning the probability of
evasion for this qubit under our protocol is less than the probability of
evasion for this qubit under BB84.

Overall for this case, it is clear that
$\Pr_{c,QFT}(i,B)\leq\Pr_{c,BB84}(i,B)$

######  Case 4 (Eve measures $q_{i}$, $q_{i}$ is a verification qubit).

For BB84, $\Pr_{c,BB84}(i,B)=.75$ as previously discussed. For our protocol,
$\Pr_{c,QFT}(i,B)=.5$ as previously discussed. It is therefore clear that
$\Pr_{c,QFT}(i,B)<\Pr_{c,BB84}(i,B)$ for this case.

Since ${\forall t\in V.\;{0\leq\Pr_{c}(t,B)\leq 1}}$ and by Cases 3 and 4
${\forall t\in V.\;{\Pr_{c,QFT}(t,B)\leq\Pr_{c,BB84}(t,B)}}$, then
$\prod_{t\in V}\Pr_{c,BB84}(t,B)\geq\prod_{t\in V}\Pr_{c,QFT}(t,B)$.

Finally, by the definition of $\Pr_{e}$,
$\Pr_{e,BB84}(V,B)\leq\Pr_{e,QFT}(V,B)$. ∎

Figure 5: The probabilities of detecting an eavesdropper over an increasing
number of key qubits with (a) one and (b) two verification qubits per key
qubit.

###  VI-B Public Verification Schemes

Unlike BB84 and other QKD protocols with independent key and verification
qubits, our protocol is resilient against an attacker even if they know the
locations and intended values of the verification qubits. In this section we
will therefore examine public verification schemes. Specifically we analyze
representative schemes in which all verification qubits are intended to
measure zero.

We analytically compute the probabilities of detection for four different
public verification schemes in which key qubits are uniformly interleaved with
verification qubits. In two schemes, shown in Figs. 4(c) and (d), each key
qubit is followed by one verification qubit. An eavesdropper’s optimal
strategy then is to measure only the key qubits and leave the verification
qubits untouched as indicated by the E over each key qubit in the figure. This
knowledge would break most QKD schemes, including BB84. However, our protocol,
based on the QFT transform, can still detect an eavesdropper in this scenario.
Alternative schemes include one where each key qubit is followed by two
verification qubits (Figs. 4(e) and (f)).

These schemes can be further modified by what we call compartmentalization.
That is, instead of encoding and decoding all the bits with a single QFT, the
message would be split into smaller groups that are independently encoded and
decoded with the QFT. These groups are denoted by several QFTs in Fig. 4.

For example, Fig. 4(c) shows a scheme where each group consists of a key and
verification qubit pair. Notably, this public verification scheme matches the
chance of detection from BB84 when all qubits are measured, $1-(.75)^{|v|}$ as
per Eq. 11. This is quite interesting because the worst case for Alice and Bob
in this public scheme, where Eve deliberately chooses her measured qubits with
knowledge, is equal to the best case for Alice and Bob in BB84, where Eve
measures all qubits. This emphasises the benefit of using a QFT-based protocol
to increase eavesdropping detection.

As mentioned in Sec. V, we can compute the average or pessimistic probability
of detection using the mean or min statistic functions, respectively. When
comparing schemes that use compartmentalization versus ones that do not, one
can see that the statistics function used makes a difference. In Fig. 5(a),
for example, we compare the compartmentalized scheme from Fig. 4(c) against
the non-compartmentalized scheme from Fig. 4(d). One can see that the non-
compartmentalized version is better in the average case, using the mean
function, but worse in the worst-case, using the min function.

Looking at Fig. 5(b), which compares the compartmentalized scheme from Fig.
4(e) against the non-compartmentalized scheme from Fig. 4(f), we again see
that the non-compartmentalized scheme outperforms the compartmentalized one on
average. However, in the worst-case the compartmentalized and non-
compartmentalized schemes have similar detection rates.

One can see that different verification schemes can be better for different
use cases, and Eq. (11) allows one to analyze different schemes to try to pick
one that is best-suited for their specific case. If two parties were sending
many messages, where each message in particular didn’t need high security, but
they wanted to detect Eve with high likelihood over the course of many
messages, then they might consider using QFT encoding on all the qubits
together in a non-compartmentalized way. If they wanted high security on each
message, on the other hand, they may want to use a compartmentalized version
of the scheme.

In all these schemes, the chance of detecting an attacker is below
$1-(.5)^{|v|}$, which is the chance of detecting an attacker who measures all
qubits, as is generally assumed in the case without knowledge of the
verification scheme. However, unlike BB84 where the chance of detecting an
attacker given a public verification scheme is 0, with our protocol the chance
of detecting an attacker grows with each qubit they measure.

##  VII Conclusion

We have shown a novel two-pass approach to QKD using the QFT as well as a QFT-
based approach to sending encrypted messages directly. These protocols allow
for a greater chance of detecting an eavesdropper against certain attacks,
including partial information leakage and many-copies attacks, than
independent qubit measurement based approaches such as BB84. This paper then
provides a formula to determine the probability of detecting an eavesdropper’s
presence under any verification scheme. As we showed through key examples,
this formula allows for analyzing verification schemes of one’s own to help
determine the best scheme for each situation. Notably, our analysis shows that
our QFT-based approach allows for detecting an eavesdropper even when the
verification scheme is known to the attacker. Altogether our protocols provide
for robust eavesdropping detection against more powerful eavesdroppers than
other schemes can handle.

## Acknowledgments

The authors thank John Drew Wilson for useful discussions.

## References

  * [1] W. K. Wootters and W. H. Zurek, “A single quantum cannot be cloned,” _Nature_ , vol. 299, no. 5886, pp. 802–803, Oct. 1982. [Online]. Available: https://doi.org/10.1038/299802a0
  * [2] W. Diffie and M. Hellman, “New directions in cryptography,” _IEEE Transactions on Information Theory_ , vol. 22, no. 6, pp. 644–654, 1976.
  * [3] R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” _Commun. ACM_ , vol. 21, no. 2, p. 120–126, feb 1978. [Online]. Available: https://doi.org/10.1145/359340.359342
  * [4] P. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in _Proceedings 35th Annual Symposium on Foundations of Computer Science_ , 1994, pp. 124–134.
  * [5] C. H. Bennett and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing,” _Theoretical Computer Science_ , vol. 560, pp. 7–11, 2014.
  * [6] M. A. Nielsen and I. L. Chuang, _Phase Estimation_. Cambridge University Press, 2010, p. 221–226.
  * [7] S. Kak, “A three-stage quantum cryptography protocol,” _Foundations of Physics Letters_ , vol. 19, no. 3, pp. 293–296, 2006.
  * [8] A. K. Ekert, “Quantum cryptography based on bell’s theorem,” _Phys. Rev. Lett._ , vol. 67, pp. 661–663, Aug 1991. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.67.661
  * [9] Z. Yang, M. Zolanvari, and R. Jain, “A survey of important issues in quantum computing and communications,” _IEEE Communications Surveys & Tutorials_, vol. 25, no. 2, pp. 1059–1094, 2023.
  * [10] M. Lucamarini, K. A. Patel, J. F. Dynes, B. Fröhlich, A. W. Sharpe, A. R. Dixon, Z. L. Yuan, R. V. Penty, and A. J. Shields, “Efficient decoy-state quantum key distribution with quantified security,” _Opt. Express_ , vol. 21, no. 21, pp. 24 550–24 565, Oct 2013.
  * [11] Y. Zhang, Z. Li, Z. Chen, C. Weedbrook, Y. Zhao, X. Wang, Y. Huang, C. Xu, X. Zhang, Z. Wang, M. Li, X. Zhang, Z. Zheng, B. Chu, X. Gao, N. Meng, W. Cai, Z. Wang, G. Wang, S. Yu, and H. Guo, “Continuous-variable qkd over 50 km commercial fiber,” _Quantum Science and Technology_ , vol. 4, no. 3, p. 035006, May 2019. [Online]. Available: http://dx.doi.org/10.1088/2058-9565/ab19d1
  * [12] B. Korzh, C. C. W. Lim, R. Houlmann, N. Gisin, M. J. Li, D. Nolan, B. Sanguinetti, R. Thew, and H. Zbinden, “Provably secure and practical quantum key distribution over 307 km of optical fibre,” _Nature Photonics_ , vol. 9, no. 3, p. 163–168, Feb. 2015. [Online]. Available: http://dx.doi.org/10.1038/nphoton.2014.327
  * [13] V. Scarani, H. Bechmann-Pasquinucci, N. J. Cerf, M. Dušek, N. Lütkenhaus, and M. Peev, “The security of practical quantum key distribution,” _Reviews of modern physics_ , vol. 81, no. 3, p. 1301, 2009.
  * [14] G. Brassard, N. Lütkenhaus, T. Mor, and B. C. Sanders, “Limitations on practical quantum cryptography,” _Physical review letters_ , vol. 85, no. 6, p. 1330, 2000.
  * [15] W.-Y. Hwang, “Quantum key distribution with high loss: toward global secure communication,” _Physical review letters_ , vol. 91, no. 5, p. 057901, 2003.
  * [16] H.-K. Lo, X. Ma, and K. Chen, “Decoy state quantum key distribution,” _Physical review letters_ , vol. 94, no. 23, p. 230504, 2005.
  * [17] X.-B. Wang, “Beating the photon-number-splitting attack in practical quantum cryptography,” _Physical review letters_ , vol. 94, no. 23, p. 230503, 2005.
  * [18] M. Nagy, S. G. Akl, and S. Kershaw, “Key distribution based on quantum fourier transform,” in _International Conference on Security and Cryptography_ , vol. 2. SCITEPRESS, 2008, pp. 263–269.
  * [19] X.-Y. Yan, N.-R. Zhou, L.-H. Gong, Y.-Q. Wang, and X.-J. Wen, “High-dimensional quantum key distribution based on qudits transmission with quantum fourier transform,” _Quantum Information Processing_ , vol. 18, no. 9, p. 271, 2019.
  * [20] X. Tan, S. Cheng, J. Li, and Z. Feng, “Quantum key distribution protocol using quantum fourier transform,” in _2015 IEEE 29th International Conference on Advanced Information Networking and Applications Workshops_ , 2015, pp. 96–101.
  * [21] “Cwe-330: Use of insufficiently random values,” online; accessed 7-February-2024. [Online]. Available: https://cwe.mitre.org/data/definitions/330.html
  * [22] “Cwe-338: Use of cryptographically weak pseudo-random number generator (prng),” online; accessed 7-February-2024. [Online]. Available: https://cwe.mitre.org/data/definitions/338.html
  * [23] C. H. Bennett, G. Brassard, and J.-M. Robert, “Privacy amplification by public discussion,” _SIAM journal on Computing_ , vol. 17, no. 2, pp. 210–229, 1988.
  * [24] M. Mosca and A. Ekert, “The hidden subgroup problem and eigenvalue estimation on a quantum computer,” in _Quantum Computing and Quantum Communications_ , C. P. Williams, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999, pp. 174–188.


# This is the title

FUNCTIONAL GHOBBER-JAMING UNCERTAINTY PRINCIPLE
K. MAHESH KRISHNA
Post Doctoral Fellow

Statistics and Mathematics Unit

Indian Statistical Institute, Bangalore Centre

Karnataka 560 059, India

Email<EMAIL_ADDRESS>
Date:

Abstract: Let $(\\{f_{j}\\}_{j=1}^{n},\\{\tau_{j}\\}_{j=1}^{n})$ and
$(\\{g_{k}\\}_{k=1}^{n},\\{\omega_{k}\\}_{k=1}^{n})$ be two p-orthonormal
bases for a finite dimensional Banach space $\mathcal{X}$. Let
$M,N\subseteq\\{1,\dots,n\\}$ be such that

$\displaystyle
o(M)^{\frac{1}{q}}o(N)^{\frac{1}{p}}<\frac{1}{\displaystyle\max_{1\leq j,k\leq
n}|g_{k}(\tau_{j})|},$

where $q$ is the conjugate index of $p$. Then for all $x\in\mathcal{X}$, we
show that

(1)
$\displaystyle\|x\|\leq\left(1+\frac{1}{1-o(M)^{\frac{1}{q}}o(N)^{\frac{1}{p}}\displaystyle\max_{1\leq
j,k\leq n}|g_{k}(\tau_{j})|}\right)\left[\left(\sum_{j\in
M^{c}}|f_{j}(x)|^{p}\right)^{\frac{1}{p}}+\left(\sum_{k\in
N^{c}}|g_{k}(x)|^{p}\right)^{\frac{1}{p}}\right].$

We call Inequality (1) as Functional Ghobber-Jaming Uncertainty Principle.
Inequality (1) improves the uncertainty principle obtained by Ghobber and
Jaming [Linear Algebra Appl., 2011].

Keywords: Uncertainty Principle, Orthonormal Basis, Hilbert space, Banach
space.

Mathematics Subject Classification (2020): 42C15, 46B03, 46B04.

###### Contents

  1. 1 Introduction
  2. 2 Functional Ghobber-Jaming Uncertainty Principle

##  1\. Introduction

Let $d\in\mathbb{N}$ and
$~{}\widehat{}:\mathcal{L}^{2}(\mathbb{R}^{d})\to\mathcal{L}^{2}(\mathbb{R}^{d})$
be the unitary Fourier transform obtained by extending uniquely the bounded
linear operator

$\displaystyle\widehat{}:\mathcal{L}^{1}(\mathbb{R}^{d})\cap\mathcal{L}^{2}(\mathbb{R}^{d})\ni
f\mapsto\widehat{f}\in
C_{0}(\mathbb{R}^{d});\quad\widehat{f}:\mathbb{R}^{d}\ni\xi\mapsto\widehat{f}(\xi)\coloneqq\int_{\mathbb{R}^{d}}f(x)e^{-2\pi
i\langle x,\xi\rangle}\,dx\ \in\mathbb{C}.$

In 2007, Jaming [4] extended the uncertainty principle obtained by Nazarov for
$\mathbb{R}$ in 1993 [8] (cf. [3]). In the following theorem, Lebesgue measure
on $\mathbb{R}^{d}$ is denoted by $m$. Mean width of a measurable subset $E$
of $\mathbb{R}^{d}$ having finite measure is denoted by $w(E)$.

######  Theorem 1.1.

[4, 8] (Nazarov-Jaming Uncertainty Principle) For each $d\in\mathbb{N}$, there
exists a universal constant $C_{d}$ (depends upon $d$) satisfying the
following: If $E,F\subseteq\mathbb{R}^{d}$ are measurable subsets having
finite measure, then for all $f\in\mathcal{L}^{2}(\mathbb{R}^{d})$,

(2) $\displaystyle\int_{\mathbb{R}^{d}}|f(x)|^{2}\,dx$ $\displaystyle\leq
C_{d}e^{C_{d}\min\\{m(E)m(F),m(E)^{\frac{1}{d}}w(F),m(F)^{\frac{1}{d}}w(E)\\}}$
$\displaystyle\left[\int_{E^{c}}|f(x)|^{2}\,dx+\int_{F^{c}}|\widehat{f}(\xi)|^{2}\,d\xi\right].$

In particular, if $f$ is supported on $E$ and $\widehat{f}$ is supported on
$F$, then $f=0$.

Theorem 1.1 and the milestone paper [1] of Donoho and Stark which derived
finite dimensional uncertainty principles, motivated Ghobber and Jaming [2] to
ask what is the exact finite dimensional analogue of Theorem 1.1? Ghobber and
Jaming were able to derive the following beautiful theorem. Given a subset
$M\subseteq\\{1,\dots,n\\}$, the number of elements in $M$ is denoted by
$o(M)$.

######  Theorem 1.2.

[2] (Ghobber-Jaming Uncertainty Principle) Let $\\{\tau_{j}\\}_{j=1}^{n}$ and
$\\{\omega_{j}\\}_{j=1}^{n}$ be orthonormal bases for the Hilbert space
$\mathbb{C}^{n}$. If $M,N\subseteq\\{1,\dots,n\\}$ are such that

(3) $\displaystyle o(M)o(N)<\frac{1}{\displaystyle\max_{1\leq j,k\leq
n}|\langle\tau_{j},\omega_{k}\rangle|^{2}},$

then for all $h\in\mathbb{C}^{n}$,

$\displaystyle\|h\|\leq\left(1+\frac{1}{1-\sqrt{o(M)o(N)}\displaystyle\max_{1\leq
j,k\leq n}|\langle\tau_{j},\omega_{k}\rangle|}\right)\left[\left(\sum_{j\in
M^{c}}|\langle h,\tau_{j}\rangle|^{2}\right)^{\frac{1}{2}}+\left(\sum_{k\in
N^{c}}|\langle h,\omega_{k}\rangle|^{2}\right)^{\frac{1}{2}}\right].$

In particular, if $h$ is supported on $M$ in the expansion using basis
$\\{\tau_{j}\\}_{j=1}^{n}$ and $h$ is supported on $N$ in the expansion using
basis $\\{\omega_{j}\\}_{j=1}^{n}$, then $h=0$.

It is reasonable to ask whether there is a Banach space version of Ghobber-
Jaming Uncertainty Principle, which when restricted to Hilbert space, reduces
to Theorem 1.2? We are going to answer this question in the paper.

##  2\. Functional Ghobber-Jaming Uncertainty Principle

In the paper, $\mathbb{K}$ denotes $\mathbb{C}$ or $\mathbb{R}$ and
$\mathcal{X}$ denotes a finite dimensional Banach space over $\mathbb{K}$.
Identity operator on $\mathcal{X}$ is denoted by $I_{\mathcal{X}}$. Dual of
$\mathcal{X}$ is denoted by $\mathcal{X}^{*}$. Whenever $1<p<\infty$, $q$
denotes conjugate index of $p$. For $d\in\mathbb{N}$, the standard finite
dimensional Banach space $\mathbb{K}^{d}$ over $\mathbb{K}$ equipped with
standard $\|\cdot\|_{p}$ norm is denoted by $\ell^{p}([d])$. Canonical basis
for $\mathbb{K}^{d}$ is denoted by $\\{\delta_{j}\\}_{j=1}^{d}$ and
$\\{\zeta_{j}\\}_{j=1}^{d}$ be the coordinate functionals associated with
$\\{\delta_{j}\\}_{j=1}^{d}$. Motivated from the properties of orthonormal
bases for Hilbert spaces, we set the following notion of p-orthonormal bases
which is also motivated from the notion of p-approximate Schauder frames [7]
and p-unconditional Schauder frames [6].

######  Definition 2.1.

Let $\mathcal{X}$ be a finite dimensional Banach space over $\mathbb{K}$. Let
$\\{\tau_{j}\\}_{j=1}^{n}$ be a basis for $\mathcal{X}$ and let
$\\{f_{j}\\}_{j=1}^{n}$ be the coordinate functionals associated with
$\\{\tau_{j}\\}_{j=1}^{n}$. The pair
$(\\{f_{j}\\}_{j=1}^{n},\\{\tau_{j}\\}_{j=1}^{n})$ is said to be a
p-orthonormal basis ($1<p<\infty$) for $\mathcal{X}$ if the following
conditions hold.

  1. (i)

$\|f_{j}\|=\|\tau_{j}\|=1$ for all $1\leq j\leq n$.

  2. (ii)

For every $(a_{j})_{j=1}^{n}\in\mathbb{K}^{n}$,

$\displaystyle\left\|\sum_{j=1}^{n}a_{j}\tau_{j}\right\|=\left(\sum_{j=1}^{n}|a_{j}|^{p}\right)^{\frac{1}{p}}.$

Given a p-orthonormal basis
$(\\{f_{j}\\}_{j=1}^{n},\\{\tau_{j}\\}_{j=1}^{n})$, we easily see from
Definition 2.1 that

$\displaystyle\|x\|=\left\|\sum_{j=1}^{n}f_{j}(x)\tau_{j}\right\|=\left(\sum_{j=1}^{n}|f_{j}(x)|^{p}\right)^{\frac{1}{p}},\quad\forall
x\in\mathcal{X}.$

######  Example 2.2.

The pair $(\\{\zeta_{j}\\}_{j=1}^{d},\\{\delta_{j}\\}_{j=1}^{d})$ is a
p-orthonormal basis for $\ell^{p}([d])$.

Like orthonormal bases for Hilbert spaces, the following theorem characterizes
all p-orthonormal bases.

######  Theorem 2.3.

Let $(\\{f_{j}\\}_{j=1}^{n},\\{\tau_{j}\\}_{j=1}^{n})$ be a p-orthonormal
basis for $\mathcal{X}$. Then a pair
$(\\{g_{j}\\}_{j=1}^{n},\\{\omega_{j}\\}_{j=1}^{n})$ is a p-orthonormal basis
for $\mathcal{X}$ if and only if there is an invertible linear isometry
$V:\mathcal{X}\to\mathcal{X}$ such that

$\displaystyle g_{j}=f_{j}V^{-1},~{}\omega_{j}=V\tau_{j},\quad\forall 1\leq
j\leq n.$

###### Proof.

$(\Rightarrow)$ Define $V:\mathcal{X}\ni
x\mapsto\sum_{j=1}^{n}f_{j}(x)\omega_{j}\in\mathcal{X}$. Since
$\\{\omega_{j}\\}_{j=1}^{n}$ is a basis for $\mathcal{X}$, $V$ is invertible
with inverse $V^{-1}:\mathcal{X}\ni
x\mapsto\sum_{j=1}^{n}g_{j}(x)\tau_{j}\in\mathcal{X}$. For $x\in\mathcal{X}$,

$\displaystyle\|Vx\|=\left\|\sum_{j=1}^{n}f_{j}(x)\omega_{j}\right\|=\left(\sum_{j=1}^{n}|f_{j}(x)|^{p}\right)^{\frac{1}{p}}=\left\|\sum_{j=1}^{n}f_{j}(x)\tau_{j}\right\|=\|x\|.$

Therefore $V$ is isometry. Note that we clearly have
$\omega_{j}=V\tau_{j},\forall 1\leq j\leq n.$ Now let $1\leq j\leq n$. Then

$\displaystyle
f_{j}(V^{-1}x)=f_{j}\left(\sum_{k=1}^{n}g_{k}(x)\tau_{k}\right)=\sum_{k=1}^{n}g_{k}(x)f_{j}(\tau_{k})=g_{j}(x),\quad\forall
x\in\mathcal{X}.$

$(\Leftarrow)$ Since $V$ is invertible, $\\{\omega_{j}\\}_{j=1}^{n}$ is a
basis for $\mathcal{X}$. Now we see that
$g_{j}(\omega_{k})=f_{j}(V^{-1}V\tau_{k})=f_{j}(\tau_{k})=\delta_{j,k}$ for
all $1\leq j,k\leq n$. Therefore $\\{g_{j}\\}_{j=1}^{n}$ is the coordinate
functionals associated with $\\{\omega_{j}\\}_{j=1}^{n}$. Since $V$ is an
isometry, we have $\|\omega_{j}\|=1$ for all $1\leq j\leq n$. Since $V$ is
also invertible, we have

$\displaystyle\|g_{j}\|$
$\displaystyle=\displaystyle\sup_{x\in\mathcal{X},\|x\|\leq
1}|g_{j}(x)|=\displaystyle\sup_{x\in\mathcal{X},\|x\|\leq
1}|f_{j}(V^{-1}x)|=\displaystyle\sup_{Vy\in\mathcal{X},\|Vy\|\leq
1}|f_{j}(y)|$ $\displaystyle=\displaystyle\sup_{Vy\in\mathcal{X},\|y\|\leq
1}|f_{j}(y)|=\|f_{j}\|=1,\quad\forall 1\leq j\leq n.$

Finally, for every $(a_{j})_{j=1}^{n}\in\mathbb{K}^{n}$,

$\displaystyle\left\|\sum_{j=1}^{n}a_{j}\omega_{j}\right\|=\left\|\sum_{j=1}^{n}a_{j}V\tau_{j}\right\|=\left\|V\left(\sum_{j=1}^{n}a_{j}\tau_{j}\right)\right\|=\left\|\sum_{j=1}^{n}a_{j}\tau_{j}\right\|=\left(\sum_{j=1}^{n}|a_{j}|^{p}\right)^{\frac{1}{p}}.$

∎

In the next result we show that Example 2.2 is prototypical as long as we
consider p-orthonormal bases.

######  Theorem 2.4.

If $\mathcal{X}$ has a p-orthonormal basis
$(\\{f_{j}\\}_{j=1}^{n},\\{\tau_{j}\\}_{j=1}^{n})$, then $\mathcal{X}$ is
isometrically isomorphic to $\ell^{p}([n])$.

###### Proof.

Define $V:\mathcal{X}\ni
x\mapsto\sum_{j=1}^{n}f_{j}(x)\delta_{j}\in\ell^{p}([n])$. By doing a similar
calculation as in the direct part in the proof of Theorem 2.3, we see that $V$
is an invertible isometry. ∎

Now we derive main result of this paper.

######  Theorem 2.5.

(Functional Ghobber-Jaming Uncertainty Principle) Let
$(\\{f_{j}\\}_{j=1}^{n},\\{\tau_{j}\\}_{j=1}^{n})$ and
$(\\{g_{k}\\}_{k=1}^{n},\\{\omega_{k}\\}_{k=1}^{n})$ be p-orthonormal bases
for $\mathcal{X}$. If $M,N\subseteq\\{1,\dots,n\\}$ are such that

$\displaystyle
o(M)^{\frac{1}{q}}o(N)^{\frac{1}{p}}<\frac{1}{\displaystyle\max_{1\leq j,k\leq
n}|g_{k}(\tau_{j})|},$

then for all $x\in\mathcal{X}$,

(4)
$\displaystyle\|x\|\leq\left(1+\frac{1}{1-o(M)^{\frac{1}{q}}o(N)^{\frac{1}{p}}\displaystyle\max_{1\leq
j,k\leq n}|g_{k}(\tau_{j})|}\right)\left[\left(\sum_{j\in
M^{c}}|f_{j}(x)|^{p}\right)^{\frac{1}{p}}+\left(\sum_{k\in
N^{c}}|g_{k}(x)|^{p}\right)^{\frac{1}{p}}\right].$

In particular, if $x$ is supported on $M$ in the expansion using basis
$\\{\tau_{j}\\}_{j=1}^{n}$ and $x$ is supported on $N$ in the expansion using
basis $\\{\omega_{k}\\}_{k=1}^{n}$, then $x=0$.

###### Proof.

Given $S\subseteq\\{1,\dots,n\\}$, define

$\displaystyle P_{S}x\coloneqq\sum_{j\in S}f_{j}(x)\tau_{j},\quad\forall
x\in\mathcal{X},\quad\|x\|_{S,f}\coloneqq\left(\sum_{j\in
S}|f_{j}(x)|^{p}\right)^{\frac{1}{p}},\quad\|x\|_{S,g}\coloneqq\left(\sum_{j\in
S}|g_{j}(x)|^{p}\right)^{\frac{1}{p}}.$

Also define $V:\mathcal{X}\ni
x\mapsto\sum_{k=1}^{n}g_{k}(x)\tau_{k}\in\mathcal{X}$. Then $V$ is an
invertible isometry. Using $V$ we make following important calculations:

$\displaystyle\|P_{S}x\|=\left\|\sum_{j\in
S}f_{j}(x)\tau_{j}\right\|=\left(\sum_{j\in
S}|f_{j}(x)|^{p}\right)^{\frac{1}{p}}=\|x\|_{S,f},\quad\forall
x\in\mathcal{X}$

and

$\displaystyle\|P_{S}Vx\|$ $\displaystyle=\left\|\sum_{j\in
S}f_{j}(Vx)\tau_{j}\right\|=\left\|\sum_{j\in
S}f_{j}\left(\sum_{k=1}^{n}g_{k}(x)\tau_{k}\right)\tau_{j}\right\|=\left\|\sum_{j\in
S}\sum_{k=1}^{n}g_{k}(x)f_{j}(\tau_{k})\tau_{j}\right\|$
$\displaystyle=\left\|\sum_{j\in S}g_{j}(x)\tau_{j}\right\|=\left(\sum_{j\in
S}|g_{j}(x)|^{p}\right)^{\frac{1}{p}}=\|x\|_{S,g},\quad\forall
x\in\mathcal{X}.$

Now let $y\in\mathcal{X}$ be such that $\\{j\in\\{1,\dots,n\\}:f_{j}(y)\neq
0\\}\subseteq M.$ Then $\|P_{N}Vy\|=\|P_{N}VP_{M}y\|\leq\|P_{N}VP_{M}\|\|y\|$
and

$\displaystyle\|y\|_{N^{c},g}=\|P_{N^{c}}Vy\|=\|Vy-
P_{N}Vy\|\geq\|Vy\|-\|P_{N}Vy\|=\|y\|-\|P_{N}Vy\|\geq\|y\|-\|P_{N}VP_{M}\|\|y\|.$

Therefore

(5) $\displaystyle\|y\|_{N^{c},g}\geq(1-\|P_{N}VP_{M}\|)\|y\|.$

Let $x\in\mathcal{X}$. Note that $P_{M}x$ satisfies
$\\{j\in\\{1,\dots,n\\}:f_{j}(P_{M}x)\neq 0\\}\subseteq M.$ Now using (5) we
get

$\displaystyle\|x\|$
$\displaystyle=\|P_{M}x+P_{M^{c}}x\|\leq\|P_{M}x\|+\|P_{M^{c}}x\|\leq\frac{1}{1-\|P_{N}VP_{M}\|}\|P_{M}x\|_{N^{c},g}+\|P_{M^{c}}x\|$
$\displaystyle=\frac{1}{1-\|P_{N}VP_{M}\|}\|P_{N^{c}}VP_{M}x\|+\|P_{M^{c}}x\|=\frac{1}{1-\|P_{N}VP_{M}\|}\|P_{N^{c}}V(x-P_{M^{c}}x)\|+\|P_{M^{c}}x\|$
$\displaystyle\leq\frac{1}{1-\|P_{N}VP_{M}\|}\|P_{N^{c}}Vx\|+\frac{1}{1-\|P_{N}VP_{M}\|}\|P_{N^{c}}VP_{M^{c}}x\|+\|P_{M^{c}}x\|$
$\displaystyle\leq\frac{1}{1-\|P_{N}VP_{M}\|}\|P_{N^{c}}Vx\|+\frac{1}{1-\|P_{N}VP_{M}\|}\|P_{M^{c}}x\|+\|P_{M^{c}}x\|$
$\displaystyle=\frac{1}{1-\|P_{N}VP_{M}\|}\|P_{N^{c}}Vx\|+\left(1+\frac{1}{1-\|P_{N}VP_{M}\|}\right)\|P_{M^{c}}x\|$
$\displaystyle\leq\|P_{N^{c}}Vx\|+\frac{1}{1-\|P_{N}VP_{M}\|}\|P_{N^{c}}Vx\|+\left(1+\frac{1}{1-\|P_{N}VP_{M}\|}\right)\|P_{M^{c}}x\|$
$\displaystyle=\left(1+\frac{1}{1-\|P_{N}VP_{M}\|}\right)[\|P_{N^{c}}Vx\|+\|P_{M^{c}}x\|]=\left(1+\frac{1}{1-\|P_{N}VP_{M}\|}\right)[\|x\|_{N^{c},g}+\|P_{M^{c}}x\|]$
$\displaystyle=\left(1+\frac{1}{1-\|P_{N}VP_{M}\|}\right)\left[\left(\sum_{j\in
M^{c}}|f_{j}(x)|^{p}\right)^{\frac{1}{p}}+\left(\sum_{k\in
N^{c}}|g_{k}(x)|^{p}\right)^{\frac{1}{p}}\right].$

For $x\in\mathcal{X}$, we now find

$\displaystyle\|P_{N}VP_{M}x\|^{p}=\left\|\sum_{k\in
N}f_{k}(VP_{M}x)\tau_{k}\right\|^{p}=\left(\sum_{k\in
N}|f_{k}(VP_{M}x)|^{p}\right)^{\frac{1}{p}}=\sum_{k\in
N}\left|(f_{k}V)\left(\sum_{j\in M}f_{j}(x)\tau_{j}\right)\right|^{p}$
$\displaystyle=\sum_{k\in N}\left|\sum_{j\in
M}f_{j}(x)f_{k}(V\tau_{j})\right|^{p}=\sum_{k\in N}\left|\sum_{j\in
M}f_{j}(x)f_{k}\left(\sum_{r=1}^{n}g_{r}(\tau_{j})\tau_{r}\right)\right|^{p}=\sum_{k\in
N}\left|\sum_{j\in
M}f_{j}(x)\sum_{r=1}^{n}g_{r}(\tau_{j})f_{k}(\tau_{r})\right|^{p}$
$\displaystyle=\sum_{k\in N}\left|\sum_{j\in
M}f_{j}(x)g_{k}(\tau_{j})\right|^{p}\leq\sum_{k\in N}\left(\sum_{j\in
M}|f_{j}(x)g_{k}(\tau_{j})|\right)^{p}\leq\left(\displaystyle\max_{1\leq
j,k\leq n}|g_{k}(\tau_{j})|\right)^{p}\sum_{k\in N}\left(\sum_{j\in
M}|f_{j}(x)|\right)^{p}$ $\displaystyle=\left(\displaystyle\max_{1\leq j,k\leq
n}|g_{k}(\tau_{j})|\right)^{p}o(N)\left(\sum_{j\in
M}|f_{j}(x)|\right)^{p}\leq\left(\displaystyle\max_{1\leq j,k\leq
n}|g_{k}(\tau_{j})|\right)^{p}o(N)\left(\sum_{j\in
M}|f_{j}(x)|^{p}\right)^{\frac{p}{p}}\left(\sum_{j\in
M}1^{q}\right)^{\frac{p}{q}}$ $\displaystyle\leq\left(\displaystyle\max_{1\leq
j,k\leq
n}|g_{k}(\tau_{j})|\right)^{p}o(N)\left(\sum_{j=1}^{n}|f_{j}(x)|^{p}\right)^{\frac{p}{p}}\left(\sum_{j\in
M}1^{q}\right)^{\frac{p}{q}}=\left(\displaystyle\max_{1\leq j,k\leq
n}|g_{k}(\tau_{j})|\right)^{p}o(N)\|x\|^{p}o(M)^{\frac{p}{q}}.$

Therefore

$\displaystyle\|P_{N}VP_{M}\|\leq\displaystyle\max_{1\leq j,k\leq
n}|g_{k}(\tau_{j})|o(N)^{\frac{1}{p}}o(M)^{\frac{1}{q}}$

which gives the theorem. ∎

######  Corollary 2.6.

Theorem 1.2 follows from Theorem 2.5.

###### Proof.

Let $\\{\tau_{j}\\}_{j=1}^{n}$, $\\{\omega_{j}\\}_{j=1}^{n}$ be two
orthonormal bases for a finite dimensional Hilbert space $\mathcal{H}$. Define

$\displaystyle f_{j}:\mathcal{H}\ni h\mapsto\langle
h,\tau_{j}\rangle\in\mathbb{K};\quad g_{j}:\mathcal{H}\ni h\mapsto\langle
h,\omega_{j}\rangle\in\mathbb{K},\quad\forall 1\leq j\leq n.$

Then $p=q=2$ and $|f_{j}(\omega_{k})|=|\langle\omega_{k},\tau_{j}\rangle|$ for
all $1\leq j,k\leq n.$ ∎

By interchanging p-orthonormal bases in Theorem 2.5 we get the following
theorem.

######  Theorem 2.7.

(Functional Ghobber-Jaming Uncertainty Principle) Let
$(\\{f_{j}\\}_{j=1}^{n},\\{\tau_{j}\\}_{j=1}^{n})$ and
$(\\{g_{k}\\}_{k=1}^{n},\\{\omega_{k}\\}_{k=1}^{n})$ be p-orthonormal bases
for $\mathcal{X}$. If $M,N\subseteq\\{1,\dots,n\\}$ are such that

$\displaystyle
o(M)^{\frac{1}{q}}o(N)^{\frac{1}{p}}<\frac{1}{\displaystyle\max_{1\leq j,k\leq
n}|f_{j}(\omega_{k})|},$

then for all $x\in\mathcal{X}$,

$\displaystyle\|x\|\leq\left(1+\frac{1}{1-o(M)^{\frac{1}{q}}o(N)^{\frac{1}{p}}\displaystyle\max_{1\leq
j,k\leq n}|f_{j}(\omega_{k})|}\right)\left[\left(\sum_{k\in
M^{c}}|g_{k}(x)|^{p}\right)^{\frac{1}{p}}+\left(\sum_{j\in
N^{c}}|f_{j}(x)|^{p}\right)^{\frac{1}{p}}\right].$

In particular, if $x$ is supported on $M$ in the expansion using basis
$\\{\omega_{k}\\}_{k=1}^{n}$ and $x$ is supported on $N$ in the expansion
using basis $\\{\tau_{j}\\}_{j=1}^{n}$, then $x=0$.

Observe that the constant

$\displaystyle
C_{d}e^{C_{d}\min\\{m(E)m(F),m(E)^{\frac{1}{d}}w(F),m(F)^{\frac{1}{d}}w(E)\\}}$

in Inequality (2) is depending upon subsets $E$, $F$ and not on the entire
domain $\mathbb{R}$ of functions $f$, $\widehat{f}$. Thus it is natural to ask
whether there is a constant sharper in Inequality (4) depending upon subsets
$M$, $N$ and not on $\\{1,\dots,n\\}$. A careful observation in the proof of
Theorem 2.5 gives following result.

######  Theorem 2.8.

Let $(\\{f_{j}\\}_{j=1}^{n},\\{\tau_{j}\\}_{j=1}^{n})$ and
$(\\{g_{k}\\}_{k=1}^{n},\\{\omega_{k}\\}_{k=1}^{n})$ be p-orthonormal bases
for $\mathcal{X}$. If $M,N\subseteq\\{1,\dots,n\\}$ are such that

$\displaystyle
o(M)^{\frac{1}{q}}o(N)^{\frac{1}{p}}<\frac{1}{\displaystyle\max_{j\in M,k\in
N}|g_{k}(\tau_{j})|},$

then for all $x\in\mathcal{X}$,

$\displaystyle\|x\|\leq\left(1+\frac{1}{1-o(M)^{\frac{1}{q}}o(N)^{\frac{1}{p}}\displaystyle\max_{j\in
M,k\in N}|g_{k}(\tau_{j})|}\right)\left[\left(\sum_{j\in
M^{c}}|f_{j}(x)|^{p}\right)^{\frac{1}{p}}+\left(\sum_{k\in
N^{c}}|g_{k}(x)|^{p}\right)^{\frac{1}{p}}\right].$

Similarly we have the following result from Theorem 2.7.

######  Theorem 2.9.

Let $(\\{f_{j}\\}_{j=1}^{n},\\{\tau_{j}\\}_{j=1}^{n})$ and
$(\\{g_{k}\\}_{k=1}^{n},\\{\omega_{k}\\}_{k=1}^{n})$ be p-orthonormal bases
for $\mathcal{X}$. If $M,N\subseteq\\{1,\dots,n\\}$ are such that

$\displaystyle
o(M)^{\frac{1}{q}}o(N)^{\frac{1}{p}}<\frac{1}{\displaystyle\max_{j\in N,k\in
M}|f_{j}(\omega_{k})|},$

then for all $x\in\mathcal{X}$,

$\displaystyle\|x\|\leq\left(1+\frac{1}{1-o(M)^{\frac{1}{q}}o(N)^{\frac{1}{p}}\displaystyle\max_{j\in
N,k\in M}|f_{j}(\omega_{k})|}\right)\left[\left(\sum_{k\in
M^{c}}|g_{k}(x)|^{p}\right)^{\frac{1}{p}}+\left(\sum_{j\in
N^{c}}|f_{j}(x)|^{p}\right)^{\frac{1}{p}}\right].$

Theorem 2.5 brings the following question.

######  Question 2.10.

Given $p$ and a Banach space $\mathcal{X}$ of dimension $n$, for which subsets
$M,N\subseteq\\{1,\dots,n\\}$ and pairs of p-orthonormal bases
$(\\{f_{j}\\}_{j=1}^{n},\\{\tau_{j}\\}_{j=1}^{n})$,
$(\\{g_{k}\\}_{k=1}^{n},\\{\omega_{k}\\}_{k=1}^{n})$ for $\mathcal{X}$, we
have equality in Inequality (4)?

It is clear that we used $1<p<\infty$ in the proof of Theorem 2.5. However,
Definition 2.1 can easily be extended to include cases $p=1$ and $p=\infty$.
This therefore leads to the following question.

######  Question 2.11.

Whether there are Functional Ghobber-Jaming Uncertainty Principle (versions of
Theorem 2.5) for 1-orthonormal bases and $\infty$-orthonormal bases?

We end by mentioning that Donoho-Stark-Elad-Bruckstein-Ricaud-Torrésani
Uncertainty Principle for finite dimensional Banach spaces is derived in [5]
(actually, in [5] the functional uncertainty principle was derived for
p-Schauder frames which is general than p-orthonormal bases. Thus it is worth
to derive Theorem 2.5 or a variation of it for p-Schauder frames, which we are
unable).

## References

  * [1] David L. Donoho and Philip B. Stark.  Uncertainty principles and signal recovery.  SIAM J. Appl. Math., 49(3):906–931, 1989.
  * [2] Saifallah Ghobber and Philippe Jaming.  On uncertainty principles in the finite dimensional setting.  Linear Algebra Appl., 435(4):751–768, 2011.
  * [3] Victor Havin and Burglind Jöricke.  The uncertainty principle in harmonic analysis, volume 28 of A Series of Modern Surveys in Mathematics.  Springer-Verlag, Berlin, 1994.
  * [4] Philippe Jaming.  Nazarov’s uncertainty principles in higher dimension.  J. Approx. Theory, 149(1):30–41, 2007.
  * [5] K. Mahesh Krishna.  Functional Donoho-Stark-Elad-Bruckstein-Ricaud-Torrésani uncertainty principle.  arXiv: 2304.03324v1 [math.FA] 5 April, 2023.
  * [6] K. Mahesh Krishna.  Group-frames for Banach spaces.  arXiv: 2305.01499v1 [math.FA] 5 May, 2023.
  * [7] K. Mahesh Krishna and P. Sam Johnson.  Towards characterizations of approximate Schauder frame and its duals for Banach spaces.  J. Pseudo-Differ. Oper. Appl., 12(1):Paper No. 9, 13, 2021.
  * [8] F. L. Nazarov.  Local estimates for exponential polynomials and their applications to inequalities of the uncertainty principle type.  Algebra i Analiz, 5(4):3–66, 1993.


# Writing summary for the state-of-the-art methods for big data clustering in
distributed environment
††thanks: Identify applicable funding agency here. If none, delete this.

Dipesh Gyawali  Department of Computer Science and Engineering
Louisiana State University
Baton Rouge, United States
<EMAIL_ADDRESS>
###### Abstract

Big Data processing systems handle huge unstructured and structured data to
store, process, and analyze through cluster analysis which helps in
identifying unseen patterns to find the relationships between them. Clustering
analysis over the shared machines in big data technologies helps in deriving
the relations and making decisions using data in context. It can handle every
form of raw, tabular data along with structured, semi-structured, and
unstructured data. The data doesn’t have to possess linearity property. It can
reflect associative and correlative patterns and groupings. The main
contribution and findings of this paper are to gather and summarize the recent
big data clustering techniques, and their strengths, and weaknesses in any
distributed environment.

###### Index Terms:

Clustering, Big data technologies, Distributed environment, Scalability

##  I Introduction

Big Data technologies process huge data to derive meaningful results from
them. Data in the real world could be of different formats like text, images,
graphs, audio, etc. These data are present in unstructured, semi-structured,
and structured forms. Real-world data is in raw form and doesn’t contain
meaningful information. When processed and analyzed, meaningful information
can be extracted. Cluster analysis helps in identifying the hidden patterns
and relationships in data that leverage a lot of power to experiment and
discover new results. This paper discusses the primary ideas of five research
papers in the area of shared cluster architecture in a distributed
environment. Most of these papers elaborate upon how the performance of shared
clustering in big data can be enhanced by introducing new methodologies and
approaches within shared clusters. These papers also talk about how scaling
can be done in this architecture without facing any interruptions. The
strengths and weaknesses of each clustering technique are also discussed
briefly.

##  II Summary

###  II-A Multi-objective Fuzzy-Swarm Optimizer for Data Partitioning

Data partitioning is extremely useful in today’s context when we try to use
big data applications in distributed environments. While handling huge
datasets, it is significant to make data partition scalable and elastic.
Multi-objective fuzzy swarm optimizer is based on clustering for data
partitioning, data reduction, and processing. In traditional technologies like
Apache Hadoop and Spark, shared-nothing architecture is used as every node
inside them is free and independent of other frameworks within both data and
resources. In the Hadoop framework, if we want to combine several machines
into a computing cluster, it will be more expensive in terms of investment and
resources and it is sometimes infeasible because of its unavailability. This
method helps to reduce the expense of computing clusters and uplift the
performance of big data processing in computing by acquiring high throughput
and low latency.

In this paper, the optimization using multi-objective functions is introduced
with the application of swarm optimization and fuzzy-logic. Complex datasets
require multi-objective optimization which contains multiple constraints for
the best possible solutions. The stopping criteria are extremely important to
get an optimized solution which is chosen as a total number of maximum
iterations for fuzzy-swarm optimization. This algorithm is used to optimize
parameters for maximizing the given objective function and reducing the time
complexity at the same time. After the whole iteration is completed, the
optimized algorithm helps in identifying the best search space in the clusters
in addition with good fitness. As compared to previous traditional approaches
which solely focus on designing only a single objective and multi-objective
clustering algorithms to partition data, this experiment integrates some
solutions with the pre-existed designs to improve the efficacy.

With the increase in data and users, various types of data are collected and
analyzed with different data mining tools. Categorization of data into various
clusters that are collected from multiple sources are done. This paper has
proven the effectiveness of swarm optimization for partitioning the data into
various clusters for analyzing and other operations. It improves the global
search ability for the best solution by using a multi-objective optimization
approach and gains higher accuracy compared to single-objective swarm
optimization algorithms in the context of complex data.

###  II-B CHIME: A checkpoint-based approach in order to improve the
performance of the shared clusters

Tasks can come up with higher and lower priorities according to their need in
huge commercial cloud platforms utilizing big data technologies. For handling
the task, a preemptive algorithm should be adopted in that case. It is obvious
that higher priority tasks are executed immediately as compared to lower
priority tasks in big data cloud platforms like Microsoft Azure, GCP, and
Amazon Web Services. This is helpful when there are not enough resources to
perform cloud operations at a certain period of time. And, when the resources
are available later, the task is re-executed. However, these low-priority
tasks could be restarted many times during peak times because of the lack of
resources which will induce memory-related problems across hard disk drives
and CPU cores. To handle this, checkpoint technology is introduced and adopted
which generally checkpoints the low-priority tasks that have been restarted
periodically. This paper talks about the checkpoint technology to improve the
performance on clouds by handling low-priority tasks.

This paper has proposed a method called ’CHIME’ to handle task handling with
different priorities that utilize checkpoint technology and introduce a
waiting list approach. Generally, low-priority tasks are sacrificed in order
to perform high-priority tasks when the system is under a heavy workload and
there is a lack of resources. Microsoft once reported that 21% of its tasks
were killed due to preemptive scheduling in its Dyrad cluster. For this, CHIME
has been one of the successful implementations in handling task scheduling on
the shared clusters.

When the priority of one task is greater than the priority of tasks that is
already being executed with optimum machine performance, those tasks will be
kept on a combined waiting list and the previous task will be executed. The
number of checkpoints performed is also decreased by setting a checkpoint
checking condition. Performing unnecessary overhead will add redundant
overhead to the cluster. Checkpointing is only done when the occupancy of the
entire system decreases more than the threshold C. When occupancy becomes
greater than C, checkpointing will be started for low-priority tasks. This
approach starts the task in the combined waiting list as soon as the resource
starts becoming free. This combined waiting list can hold all the tasks
including tasks never checkpointed, previously checkpointed, and were killed
without any checkpoint.

The introduction of CHIME has improved the scheduling techniques of tasks
being executed on big data platforms which ultimately improves cloud
performance, and helps in proper resource utilization for data operations and
handling.

###  II-C CoBell: Runtime Prediction for Distributed Dataflow Jobs in Shared
Clusters

When developing big data applications, users/programmers don’t know much about
the distributed part that big data frameworks generally handle. Users can
easily develop huge applications in a parallel computing environment using big
data technologies. They can assign resources for the workloads. They don’t
fully understand resource utilization and system dynamics. Some technologies
are developed to select the amount of resources required for fulling the
tasks. This paper discusses ’CoBell’ which is a resource allocation system
that aims to enhance the runtime prediction of multiple jobs in shared
clusters. It reserves the required resources for the users based on runtime
prediction.

CoBell has been implemented as a job submission tool for YARN. Its main goal
is to enhance the runtime prediction’s accuracy for interfered workloads by
storing knowledge for the co-located jobs. Users submit jobs along with their
constraints (scale-out) and runtime to CoBell which is later converted into
resource reservation. It is achieved from the record of already executed jobs.
After the submission of a new job, it queries its database to find out the
runs of the previous job. These old runs are utilized to build the prediction
model. Its runtime model helps in accumulating the knowledge about the co-
located jobs to improve runtime performance. Two types of models are provided
- a strong model which performs extrapolation, and another non-parametric
model that provides an alternative to interpolation. After building the model,
it is then used for predicting the runtime resources.

###  II-D Enabling Elastic Stream Processing in Shared Clusters

Various big data frameworks like Hadoop MapReduce helps in handling large data
sets, process, storing, and analyzing them, Recently, there has been
increasing in the number of applications that require computing real-time data
being generated like dynamic content delivery, intrusion detection systems,
graph processing, etc. Nowadays, other big data frameworks like Spark
Streaming and Storm support live data processing that runs on shared clusters.
Here, low cost needs to be achieved to maintain the proper cluster performance
which is one of the challenges in stream data processing.

Due to workloads and requirements of system resources, the velocity of inputs
in data stream processing systems is not constant. It’s not possible for
current system to scale up the resources dynamically without any service
interruptions. For scaling up, the application first needs to be shut down,
reconfigured, and restarted. This is extremely unreliable where real-time data
processing is required due to network interruptions. In addition to this,
there arises a problem with the application state that results in work lost
and ambiguous results. Elastic data streaming helps to add up resources
dynamically without the requirement of system shutdown. This is achieved by
the adoption of the stateful scaling mechanism and cost-dependent scaling. The
researchers added a Hadoop YARN cluster resource manager to coordinate
resources between batch and stream processing.

The elastic data processing also helps in saving the system’s state which is
sent to the global state manager component. The global manager component helps
to coordinate the transfer of the operations at the place of scaling
operations. Congestion Detection Monitor (CDM) is used to detect congestion.
It keeps track of the CPU performance, and memory and analyzes congestion when
the threshold of machines is crossed. If any of the resources in the system is
bottle-necked, CDM will increase the number of workers in the topology.
Likewise, the workers are decreased if no system metrics are overloaded.

###  II-E Building Strongly Reliable and High-Performance Storage Cluster with
Network and Attached Storage Disks Using PCs

The authors of this paper has discussed a prototype implementation of a
storage cluster where every node is equipped with network-attached storage
disks forming a Network Attached Cluster (NAS). Memory is shared between nodes
inside the clusters to implement a strong cache to disk policy. Nowadays, the
users can create a storage cluster using off-the-shelf commodity parts in the
presence of tremendous power. Every PC node is attached to local storage
devices. These devices form the Storage Area Network.

Users/Clients can use distributed system protocols like Common Internet File
System (CIFS) and Network File System (NFS). Basic file operations command
like create, read, write and NAS clusters can also be used. The system is
server-less where nodes are responsible for storing the file data and managing
metadata. The files received are divided across the nodes for parallel
processing. Global Unified Content Cache (GUCC) utilizes high-level
abstraction for dealing with global caching, and remote resources. When the
user requests are missed by local caches in each node, they are handled by the
global cache. The daemon in the cluster includes functions like managing the
global cache and providing files for nodes across the clusters.

Daemon checks the usage of the global cache periodically to provide a
reasonable cache policy. The daemon will move the data blocks from the remote
to balance the node load when a particular node’s capacity goes below a
threshold value. In a nutshell, this paper is based on the notion of GUCC
which is different than the traditional caching that lets the cache miss of
one node be handled by a different remote node. This increases the overall
memory of the shared cluster to go beyond the local working limit.

##  III Pros and Cons

###  III-A Multi-objective Fuzzy-Swarm Optimizer for Data Partitioning

There is an improvement in efficiency for data partitioning as compared to the
previous approach as it uses the solution from other sources to integrate in
their design. Using a multi-objective optimizer, the data partitioning process
is more reliable and accurate comparitively to a single objective optimizer.

When trying to use a multi-objective optimization function, it’s sometimes
difficult to converge them simultaneously. The optimization directly depends
upon the type of optimizer used to determine how quickly and efficiently the
data partition process takes place.

###  III-B CHIME: A checkpoint-based approach in order to improve the
performance of the shared clusters

The choice of preemption policy is only applied when absolutely necessary in
CHIME. During the peak time of clusters, restoring and preemptive operations
take place. This helps in preventing the loss of low-priority tasks by
developing a proper mechanism for handling all the tasks in order using a
combined waiting list. This is most effective in real-time environment when
the decision should be made instantaneously. Regarding the cons, sometimes the
execution of high-priority tasks could be delayed due to the adoption of the
FIFO method for a combined waiting list. In FIFO, the task is not executed
based on priorities. Rather they are treated equally.

###  III-C CoBell: Runtime Prediction for Distributed Dataflow Jobs in Shared
Clusters

CoBell depends on the job submissions and the scale-out constraints with the
job history from database to detect the runtime environment that is easily
accessible in the system. Hence, it doesn’t require many inputs or parameters
to detect the environment. Dynamic scaling in or out is not required since the
resources are already reserved before. It also utilizes the knowledge of
concurrently running jobs to predict the required resources in the shared
clusters. Sometimes, there is a greater number of jobs in real-world
applications. When there are big applications with a random number of job
interference, this approach of runtime predictions could be an issue.

###  III-D Enabling Elastic Stream Processing in Shared Clusters

The main contribution of this approach is to remove the requirement of system
shutdown and reconfiguration like that of traditional scaling approaches which
is one of the main advantages. The absence of frequent shutdowns helps to
prevent data loss that directly impacts network interruptions. The automatic
congestion detection system enables limited user monitoring and manual
intervention. The elastic stream processing helps to identify CPU bottlenecks.
The dynamic load-aware scheduling mechanism can elastically scale out or scale
down components according to the different requirements. This scaling
mechanism helps to save application state to prevent the loss of work and
prevent performance deterioration. The model is based on rule-based
assumptions which make it less flexible. It generally checks the threshold
levels of the CPU. Instead of a rule-based model, the predictive model could
be better. Elastic stream processing generally doesn’t handle the processing
of a single machine with multiple clusters which are common among various
applications.

###  III-E Building Strongly Reliable and High-Performance Storage Cluster
With Network Attached Storage Disks Using PCs

There are no limits on the number of nodes present inside the cluster which
makes this approach scalable. Two types of caching make the data transfer
faster. The global cache mechanism helps to access data when the local cache
is unable to access it. One node’s memory can be utilized by others during
data transfer which reduces memory overhead. There is an easy switching
mechanism between RAID1 and RAID5 schemes to achieve the highest performance.
GUCC solves the disk latency issues. This approach is also suitable for small
and large writes. This system sometimes doesn’t support multiple operating
systems as it is specifically designed for Linux. The overall system’s
performance is achieved from the hardware’s optimum performance and speed
which is not always the case. This introduces the biasness in the performance
from this context. Moreover, Network Attached Storage is highly dependent on
commodity machines and chips.

##  IV Conclusion

Different state-of-the-art approaches for shared clustering architecture have
been studied in the paper that is prevailing in the distributed environment.
Cluster architecture helps to make systems more scalable and reliable that
could handle big data operations smoothly. Still, there are many approaches
that are not defined in this paper that work well in distributed clusters. The
summary, strengths and, weaknesses of the five approaches are well defined in
the paper.

## References

  * [1] Goyal, S.B., Bedi, P., Rajawat, A.S., Shaw, R.N., Ghosh, A. (2022). Multi-objective Fuzzy-Swarm Optimizer for Data Partitioning. In: Bianchini, M., Piuri, V., Das, S., Shaw, R.N. (eds) Advanced Computing and Intelligent Technologies. Lecture Notes in Networks and Systems, vol 218. Springer, Singapore. https://doi.org/10.1007/978-981-16-2164-2
  * [2] Y. Shao, X. Zhu, W. Bao, W. Zhou and W. Xiao, ”CHIME: A Checkpoint-Based Approach to Improving the Performance of Shared Clusters,” 2016 IEEE 22nd International Conference on Parallel and Distributed Systems (ICPADS), 2016, pp. 1007-1014, doi: 10.1109/ICPADS.2016.0134.
  * [3] I. Verbitskiy, L. Thamsen, T. Renner and O. Kao, ”CoBell: Runtime Prediction for Distributed Dataflow Jobs in Shared Clusters,” 2018 IEEE International Conference on Cloud Computing Technology and Science (CloudCom), 2018, pp. 81-88, doi: 10.1109/CloudCom2018.2018.00029.
  * [4] J. Li, C. Pu, Y. Chen, D. Gmach and D. Milojicic, ”Enabling Elastic Stream Processing in Shared Clusters,” 2016 IEEE 9th International Conference on Cloud Computing (CLOUD), 2016, pp. 108-115, doi: 10.1109/CLOUD.2016.0024.
  * [5] Cai Bin, Changsheng Xie and Huaiyang Li, ”Building Strongly-Reliable and High-Performance Storage Cluster with Network Attached Storage Disks Using PCs,” The Fifth International Conference on Computer and Information Technology (CIT’05), 2005, pp. 315-321, doi: 10.1109/CIT.2005.82.