id

11institutetext:  Institute of Software, Chinese Academy of Sciences, Beijing
100190, China
<EMAIL_ADDRESS>
# Optimal Mechanisms for Quantum Local Differential Privacy

Ji Guan

###### Abstract

In recent years, centralized differential privacy has been successfully
extended to quantum computing and information processing to safeguard privacy
and prevent leaks in neighboring relationships of quantum states. This paper
introduces a framework known as quantum local differential privacy (QLDP) and
initializes the algorithmic study of QLDP. QLDP utilizes a parameter
$\varepsilon$ to manage privacy leaks and ensure the privacy of individual
quantum states. The optimization of the QLDP value $\varepsilon$, denoted as
$\varepsilon^{*}$, for any quantum mechanism is addressed as an optimization
problem. The introduction of quantum noise is shown to provide privacy
protections similar to classical scenarios, with quantum depolarizing noise
identified as the optimal unital privatization mechanism within the QLDP
framework. Unital mechanisms represent a diverse set of quantum mechanisms
that encompass frequently employed quantum noise types. Quantum depolarizing
noise optimizes both fidelity and trace distance utilities, which are crucial
metrics in the field of quantum computation and information, and can be viewed
as a quantum counterpart to classical randomized response methods.
Additionally, a composition theorem is presented for the application of QLDP
framework in distributed (spatially separated) quantum systems, ensuring the
validity (additivity of QLDP value) irrespective of the states’ independence,
classical correlation, or entanglement (quantum correlation). The study
further explores the trade-off between utility and privacy across different
quantum noise mechanisms, including unital and non-unital quantum noise
mechanisms, through both analytical and numerically experimental approaches.
Meanwhile, this highlights the optimization of quantum depolarizing noise in
QLDP framework.

##  1 introduction

Quantum computers have the potential to solve specific problems significantly
faster than classical computers through the utilization of quantum parallelism
in the development of quantum algorithms [1]. Examples include Grover’s
algorithm [2] for searching unstructured databases, Shor’s algorithm [3] for
identifying prime factors of integers, and the HHL algorithm [4] by Aram
Harrow, Avinatan Hassidim, and Seth Lloyd for solving linear equations
systems. This advancement could bring about revolutionary changes in various
fields such as financial analysis [5], drug discovery [6], and machine
learning [7]. On another note, principles of quantum mechanics like the no-
cloning theorem and the observer effect establish inherently secure
communication channels [1]. Any unauthorized attempt to intercept quantum
signals would inevitably disrupt them, thereby alerting the legitimate
parties. This feature allows for the secure distribution of encryption keys,
exemplified by the BB84 quantum key distribution (QKD) protocol [8]. As
quantum hardware techniques rapidly advance, quantum computers have been
developed to exhibit quantum supremacy (outperforming classical computation),
as seen in Google’s Sycamore [9], USTC’s Jiuzhang [10], and Zhucongzhi [11].
Additionally, various quantum communication channels and networks have been
demonstrated or deployed mainly for research and experimental purposes.
Notable examples include the Chicago Quantum Exchange in the United States,
China’s Micius Satellite, Japan’s Tokyo QKD Network, and the Netherlands’
Quantum City Internet.

However, just like their classical counterparts, quantum computers and
channels are susceptible to data privacy leakage. This is due to the various
threats they encounter, including internal and external attacks like coherent
attacks [12], entangling attacks [13], higher-energy state attacks [14], and
quantum-side-channel attacks [15]. Some of these attacks are unique to quantum
systems and necessitate new methods to safeguard against them, surpassing the
capabilities of traditional classical defense mechanisms. Consequently,
safeguarding the privacy of information stored in quantum states for computing
and communication purposes presents significant challenges.

In the realm of classical computing, differential privacy stands out as a key
method for safeguarding individual data [16]. It is commonly divided into two
categories: centralized differential privacy, where institutions publish
databases containing information about multiple individuals or respond to
queries based on such databases (e.g., the US Government releasing census data
or companies like Netflix sharing proprietary data for testing advanced
machine learning techniques), and local differential privacy, where
individuals reveal personal details, such as voluntarily on social networking
platforms. The former aims to safeguard data privacy against the interrelation
between datasets, while the latter seeks to protect all information pertaining
to an individual. Previous studies have endeavored to expand centralized
differential privacy into the realm of quantum computing by establishing
various meaningful relationships between neighboring quantum data sources [17,
18, 19, 20]. A more adaptable framework has recently been put forth [21] by
building upon the classical concept of pufferfish privacy [22]. Nevertheless,
practical implementation of quantum databases remains challenging in the
current era of Noisy Intermediate-Scale Quantum (NISQ) computing. Presently,
quantum systems are predominantly utilized in a distributed fashion. In the
realm of quantum computing, users typically access quantum computers via cloud
platforms (e.g. IBM’s Qiskit and Amazon’s Braket), enabling them to remotely
submit their data for computational t‘asks on these quantum machines. On the
other hand, in quantum communication, the transfer and sharing of quantum
states occur between remote user nodes within a communication network.
Consequently, the deployment of quantum computing has predominantly focused on
the local model where quantum systems gather quantum states directly from
users as computational and communication resources, thereby emphasizing the
critical need to protect users’ information comprehensively. Therefore,
integrating privacy measures into the quantum state at the client end before
collection is essential to preserve individual data. Local differential
privacy emerges as one of the most effective privacy measures in the context
of local models; however, its application in quantum systems remains
relatively unexplored.

In this paper, we initialize the algorithmic study of _quantum local
differential privacy (QLDP)_ and establish a framework for safeguarding
quantum state privacy. The key inquiries addressed are:

  1. 1.

How can we evaluate and manage the local differential privacy of quantum
mechanisms?

  2. 2.

How can we maintain a balance between preserving utility and safeguarding
privacy in quantum systems?

  3. 3.

How can privacy be safeguarded against unique quantum attacks facilitated by
quantum entanglement?

To tackle these issues, we commence by defining local differential privacy for
quantum computers and communication systems. Similar to the classical
scenario, QLDP incorporates a parameter denoted as $\varepsilon$ that governs
the formal evaluation of privacy loss. We present a method for quantifying the
optimization (minimum) of $\varepsilon$, denoted as $\varepsilon^{*}$, for any
given quantum mechanism by solving an optimization problem. In order to ensure
privacy, a post-processing theorem is demonstrated to ensure that clients’
quantum state privacy is preserved through quantum noise mechanisms before
aggregation, akin to the classical setting. Subsequently, we present the
$\varepsilon^{*}$ value of various standard quantum noise mechanisms for
practical implementation. It is noteworthy that all quantum mechanisms involve
trade-offs between utility and privacy, and a primary objective of algorithmic
research in differential privacy is to optimize this balance. By considering
two key quantum utility measures — fidelity and trace distance, we establish
that the (quantum) depolarizing noise mechanism is the optimal choice,
enhancing both utility measures, for all $\varepsilon$-QLDP unital quantum
mechanisms. The collection of unital quantum mechanisms encompasses a diverse
range of quantum processes, such as the frequently employed quantum noises —
bit flip and phase flip, which will be elaborated on later. The depolarizing
noise mechanism can be seen as a quantum adaptation of the classical
differential privatization mechanism known as randomized response [23].
Furthermore, in the classical case, the correlation between data has been
found to disclose more information than expected [24]. In the context of the
current distributed quantum computers and communication systems over long
distances, we present a composition theorem to ensure QLDP protection among
multiple parties irrespective of the quantum states’ independence, classical
correlation, or entanglement (quantum correlation). Entanglement is a unique
and anti-intuitive relationship over quantum states, and the attacker can use
it to engage in an entangling attack and may gain privacy leakage [13]. Last
but not least, to validate the optimization of depolarizing noise mechanisms
in terms of $\varepsilon$-QLDP, we conduct both analytical and numerical
analysis illustrating the trade-offs between utility and QLDP privacy across a
range of standard quantum noise mechanisms, including unital noises (bit flip,
phase flip, bit-phase flip, and depolarizing noises) as well as non-unital
noises like (generalized) amplitude damping and phase damping [1].

In summary, our main contributions in QLDP framework are:

  1. 1.

Offering a practical approach to quantifying the optimal parameter
$\varepsilon^{*}$ of QLDP for any quantum mechanism by addressing an
optimization problem. [Theorem 5.2]

  2. 2.

Introducing a post-processing theorem that ensures the preservation of
clients’ quantum state privacy during aggregation using quantum noise
mechanisms, similar to classical methods. [Theorem 5.3]

  3. 3.

Proving that the depolarizing quantum noise mechanism is the most effective
privatization mechanism, optimizing both fidelity and trace distance utilities
overall $\varepsilon$-QLDP unital quantum mechanisms. [Theorem 6.3]

  4. 4.

_Establishing_ a composition theorem to defend against entangling attacks and
protect QLDP in the current scenario of quantum systems distributed over a
distance and sharing entangled quantum states. [Theorem 7.1]

  5. 5.

_Conducting_ both analytical and numerical analyses to evaluate the balance
between utility and privacy across different standard quantum noise
mechanisms, emphasizing the superiority of the depolarizing noise mechanism.
[Examples 5.4 and 6.1]

##  2 Related Works

Quantum Centralized versus Local Differential Privacy. In recent years, there
has been successful progress in extending centralized differential privacy to
quantum computing and information processing to enhance privacy and prevent
leaks in neighboring relationships of quantum states. These neighboring
relationships are defined qualitatively and quantitatively using informatic
measures — local operation [18] and trace distance [25], respectively. The
former involves monic classical neighboring through a local operation to
transfer a state to another, while the latter measures the distance between
quantum states on a scale from 0 to 1. Moreover, the evaluation and formal
verification of quantum centralized differential privacy have been established
[25], along with the establishment of a connection to quantum gentle
measurements [18].

On the other hand, quantum local differential privacy (QLDP), a generalization
of LDP, was introduced to ensure that two distinct quantum states passed
through a quantum mechanism are indistinguishable by any measurement [19] to
maintain quantum state privacy. While previous studies have delved into the
applications of the QLDP framework in quantum statistical query models [26]
and quantum hypothesis testing [27], there has been limited direct research on
implementing the QLDP approach to safeguard quantum state privacy. This paper
marks the beginning of an algorithmic investigation into QLDP, aiming to
measure and describe the balance between the utility and privacy of unital
quantum privacy mechanisms. Our findings indicate that the depolarizing noise
mechanism, a quantum generalization of the classical randomized response
mechanism, emerges as the optimal solution for managing this balance
effectively.

Classical versus Quantum Local Differential Privacy. The concept of classical
local differential privacy (LDP) has been extensively researched and
implemented in real-world applications like Google’s Chrome and Apple’s iOS
keyboard to safeguard user privacy. However, the methods used in classical LDP
cannot be directly translated to the quantum realm, where QLDP emerges as an
extension of LDP. Verifying that a quantum mechanism adheres to QLDP is
equivalent to confirming that an infinite number of classical randomized
mechanisms comply with LDP (refer to Lemma 1). Therefore, novel techniques,
such as eigenvalue analysis of quantum mechanisms, are being developed to
explore the fundamental properties of QLDP and ensure its practical efficacy
in preserving the privacy of quantum states. Moreover, quantum systems
encounter distinctive vulnerabilities, like entangling attacks, in current
distributed environments. To demonstrate the effectiveness of the QLDP
framework in multi-party scenarios, a composition theorem is established to
counteract entangling attacks in this paper.

##  3 Preliminaries

In this section, we aim to present the fundamental concepts of quantum
computing in a more accessible manner for the reader by using mathematical
explanations.

Quantum computing, in essence, represents a novel circuit model that departs
from traditional classical circuits. It offers computational advantages and
employs quantum communication protocols that utilize quantum channels as
opposed to classical ones for transmitting quantum states. Both quantum
circuits and channels operate based on quantum states as inputs, enabling them
to carry classical information essential for executing classical computational
tasks and transmitting classical messages. The information encoded within
these quantum states can be decoded through quantum measurement processes.
Therefore, the execution of comprehensive quantum computational or
communication tasks involves three key components: _quantum states, quantum
mechanisms (quantum circuits or channels)_ , and _quantum measurements_. In
the subsequent sections, we will delve into each of these components
individually.

###  3.1 Quantum State

Quantum Bit. In the classical realm, a bit represents the fundamental unit of
data characterized by two distinct states, $0$ and $1$. In quantum computing,
a _quantum bit (qubit)_ is a 2-dimensional unit vector $\vec{q}$ existing
within a linear complex vector space spanned by the computational basis
$\\{\vec{0},\vec{1}\\}$, defined as:

$\vec{q}:=\left(\matrix{a}\\\ b\right)=a\left(\matrix{1}\\\
0\right)+b\left(\matrix{0}\\\ 1\right)=a\vec{0}+b\vec{1}.$

Here, $\vec{0}=\left(\matrix{1}\\\ 0\right)$ and $\vec{1}=\left(\matrix{0}\\\
1\right)$, and $a$ and $b$ are complex numbers satisfying the normalization
condition $|\vec{q}|:=\sqrt{aa^{*}+bb^{*}}=1$. A qubit can be interpreted as a
probabilistic distribution over $\\{\vec{0},\vec{1}\\}$, corresponding to the
classical states $\\{0,1\\}$. However, this distribution is not unique and is
contingent upon the method of observation (specifically, the choice of basis).
Further elucidation on this matter will be provided subsequently.

Bra–ket Representation. In quantum computation and information, the bra-ket
representation, also known as Dirac notation, is commonly employed to depict
quantum states. This notation, utilizing angle brackets $\langle$ and
$\rangle$ along with a vertical bar $|$, is utilized to describe linear
algebra and linear operators on complex vector spaces and their dual spaces.
It is specifically tailored to simplify calculations frequently encountered in
quantum mechanics, hence its widespread application in this field.

In this notation, "bras" and "kets" are constructed using angle brackets and a
vertical bar to represent a column vector and a row vector, respectively. For
instance, in the case of a qubit, the representation is as follows:

$\ket{x}:=\vec{x}=\left(\matrix{a}\\\
b\right)\quad\bra{x}:=\vec{x}^{\dagger}=\left(\matrix{a}^{*},b^{*}\right)$

Here, $\vec{x}^{\dagger}$ denotes the complex conjugate and transpose of
$\vec{x}$, and $a^{*}$ represents the conjugate of the complex number $a$.

For a concrete example, the computational basis of a qubit consists of
$\ket{0}$ and $\ket{1}$ corresponding to the classical bit:

$\ket{0}=\left(\matrix{1}\\\ 0\right)\quad\ket{1}=\left(\matrix{0}\\\
1\right).$

These states, $\ket{0}$ and $\ket{1}$, can be combined to create larger
quantum systems through their tensor product:
$\ket{k,l}=\ket{k}\otimes\ket{l}$ for $k,l\in\\{0,1\\}$.

$\ket{0,0}=\left(\matrix{1}\\\ 0\\\ 0\\\
0\right),\ket{0,1}=\left(\matrix{0}\\\ 1\\\ 0\\\
0\right),\ket{1,0}=\left(\matrix{0}\\\ 0\\\ 1\\\
0\right),\ket{1,1}=\left(\matrix{0}\\\ 0\\\ 0\\\ 1\right).$

The tensor product of the computational basis $\ket{0}$ and $\ket{1}$
corresponds to the bit string of the classical bits $0$ and $1$.

Pure Quantum State. In accordance with the bra-ket notation, a state
$\ket{\psi}$ comprising $n$ qubits can be constructed by combining individual
qubits as shown below:

$\ket{\psi}:=\left(\matrix{a}_{0}\\\ a_{1}\\\ \vdots\\\
a_{2^{n}-1}\right)\text{andensuringnormalization}|\psi|=1,$

where $|\psi|:=\sqrt{\braket{\psi}{\psi}}=\sqrt{\sum_{0\leq k\leq
2^{n}-1}a_{k}a_{k}^{*}}.$ Generally, $\ket{\psi}$ is referred to as a _pure
state_ , distinct from _mixed states_ discussed later. Essentially, a pure
state $\ket{\psi}$ consisting of $n$ qubits can be represented as a normalized
column vector in a Hilbert space (a finite-dimensional linear space)
$\mathcal{H}$ with a dimension of $2^{n}$.

Moreover, $\ket{\psi}$ can be expressed as a sum over binary strings of length
$n$ as follows:

$a_{0}\ket{0,0,\ldots,0}+a_{1}\ket{1,0,\ldots,0}+\cdots+a_{2^{n}-1}\ket{1,1,\ldots,1}.$

Here, $a_{k}^{\prime}s$ represents the _amplitudes_ of $\ket{\psi}$.

To facilitate the understanding of the reader, we summarize the linear algebra
concepts pertaining to the pure state $\ket{\psi}$ utilized in this paper
using the bra-ket notation as described below:

  1. 1.

$\ket{\psi}$ denotes an $n$-qubit unit complex column vector (quantum pure
state) labeled as $\psi$;

  2. 2.

$\bra{\psi}:=\ket{\psi}^{\dagger}$ represents the complex conjugate and
transpose of $\ket{\psi}$;

  3. 3.

$\braket{\psi_{1}}{\psi_{2}}:=\bra{\psi_{1}}\ket{\psi_{2}}$ signifies the
inner product of $\ket{\psi_{1}}$ and $\ket{\psi_{2}}$;

  4. 4.

$|\psi_{1}\rangle\langle\psi_{2}|:=\ket{\psi_{1}}\cdot\bra{\psi_{2}}$ denotes
the outer product of $\ket{\psi_{1}}$ and $\ket{\psi_{2}}$; specifically,
$\psi:=|\psi\rangle\langle\psi|$ represents the outer product of $\ket{\psi}$
with itself.

Quantum State Encoding. In order to apply quantum circuits to solve practical
classical problems and transfer classical information through channel
mechanisms, the initial step involves encoding classical data into quantum
states. Specifically, a classical unit vector
$\vec{x}=(a_{0},a_{1},\cdots,a_{2^{n}-1})$ can be represented by the
amplitudes of a quantum state $\ket{\psi}$, known as _amplitude encoding_. For
more general cases, including non-unit vectors, various encoding methods such
as _angle encoding_ and _bit encoding_ can be employed [25]. These encoding
techniques can be physically realized through quantum circuits, a process
referred to as quantum state preparation.

Mixed Quantum State. In quantum mechanics, uncertainty is a common feature of
quantum systems due to quantum noise and measurements. The concept of a
_quantum mixed state_ $\rho$ is introduced to describe the uncertainty of
possible pure quantum states. It can be expressed as

$\aligned\rho=\sum_{k}p_{k}\ket{\psi_{k}}\bra{\psi_{k}}.$ (1)

Here, $\\{(p_{k},\ket{\psi_{k}})\\}_{k}$ denotes an ensemble, signifying that
the quantum state is $\ket{\psi_{k}}$ with probability $p_{k}$. Moreover, if
$\ket{\psi_{k}}$ are mutually orthogonal (i.e.,
$\braket{\psi_{i}}{\psi_{j}}=0$ for all $i\not=j$), then the decomposition of
$\rho$ above represents the eigendecomposition with $\ket{\psi_{k}}$ as the
eigenvector of $\rho$ corresponding to eigenvalue $p_{k}$. In the context of
mixed quantum states, a pure quantum state $\psi$ can be seen as a mixed state
$\psi=|\psi\rangle\langle\psi|$. To ensure clarity, in the subsequent
discussion, the term "quantum states" will specifically denote mixed quantum
states, given the broader context.

From a mathematical viewpoint, a mixed quantum state $\rho$ is a
$2^{n}$-by-$2^{n}$ matrix on a $n$-qubit system $\mathcal{H}$ that satisfies
three conditions:

  1. 1.

_Hermitian_ $\rho^{\dagger}=\rho$. Here ${\dagger}$ denotes the complex
conjugate and transpose of matrices;

  2. 2.

_positive semi-definite_ $\bra{\psi}\rho\ket{\psi}\geq 0$ for all pure quantum
state $\ket{\psi}\in\mathcal{H}$;

  3. 3.

_unit trace_ ${\rm tr}(\rho)=\sum_{k}\bra{\psi_{k}}\rho\ket{\psi_{k}}=1$
defines the trace of $\rho$ as the total of the diagonal elements of $\rho$.
Here, ${\rm tr}(\rho)$ signifies the trace of $\rho$, which is the sum of the
diagonal elements of $\rho$, and $\\{\ket{\psi_{k}}\\}$ represents a unit
basis of $\mathcal{H}$ that extracts the diagonal element of $\rho$.

###  3.2 Quantum Mechanism

Quantum mechanisms governed by quantum mechanics can be broadly categorized
into two types: quantum circuits for computation and quantum channels for
information transmission. Both quantum circuits and channels on a Hilbert
space $\mathcal{H}$ are mathematically described by a _super-operator_ denoted
as $\mathcal{E}$, which transforms an input quantum state $\rho$ into an
output state $\rho^{\prime}$ according to the equation:

$\rho^{\prime}=\mathcal{E}(\rho).$ (2)

The super-operator $\mathcal{E}(\,\mathord{\cdot}\,)$ mathematically
represents a linear mapping from $\mathcal{D(H)}$ to $\mathcal{D(H)}$, where
$\mathcal{D(H)}$ is the set of all quantum states on $\mathcal{H}$. According
to the _Kraus representation theorem_ [28], $\mathcal{E}$ can be represented
by a finite set of matrices $\\{E_{k}\\}$ on $\mathcal{H}$ with the expression

$\mathcal{E}(\rho)=\sum_{k}E_{k}\rho
E_{k}^{{\dagger}}\qquad\forall\rho\in\mathcal{D(H)}.$

This representation also satisfies the trace-preserving condition, which is
expressed as $\sum_{k}E_{k}^{{\dagger}}E_{k}=I$, where $I$ is the identity
matrix on $\mathcal{H}$. Furthermore, if
$\mathcal{E}(I)=\sum_{k}E_{k}E_{k}^{\dagger}=I$, then $\mathcal{E}$ is a
_unital_ quantum mechanism.

In classical differential privacy, the introduction of noise mechanisms is a
primary method to safeguard privacy. Similarly, in the realm of quantum
privacy, we can employ analogous techniques, which will be elaborated upon
later. Below, we outline some typical and standard quantum noise mechanisms
represented by super-operators. In contrast to the standard quantum mechanism
denoted by $\mathcal{E}$, we specifically highlight the quantum noise
mechanism represented by the symbol $\mathcal{N}$.

######  Example 1 (Quantum Noise Mechanisms)

Quantum computation and information fields commonly involve quantum noises on
a single qubit [1]. General quantum noise with multiple qubits can be
constructed based on these individual noises. One type of 1-qubit noise
involves Pauli matrices ($X,Y,$ and $Z$), which give rise to four types of
errors in quantum systems similar to classical errors. These matrices consist
of three 2-by-2 complex Hermitian matrices and together with the identity
matrix $I$, they form a basis for 2-by-2 matrices.

$X=\bmatrix 0&1\\\ 10,\quad Y=\bmatrix 0&-i\\\ i0,\quad Z=\bmatrix 1&0\\\
0-1.$

By manipulating these matrices with a probability $0\leq p\leq 1$, four Pauli-
type noise mechanisms can be created to control the introduction of errors,
where errors occur with a probability of $1-p$ (quantum states are staying
unchanged with a _noiseless probability_ $p$).

  1. 1.

X flip (Bit flip) noise mechanism:

$\mathcal{N}_{\text{XF}}(\rho)={p}\rho+(1-p)X\rho X$

using Kraus matrices $\\{\sqrt{p}I,\sqrt{1-p}X\\}$;

  2. 2.

Z flip (Phase flip) noise mechanism:

$\mathcal{N}_{\text{ZF}}(\rho)={p}\rho+(1-p)Z\rho Z$

using Kraus matrices $\\{\sqrt{p}I,\sqrt{1-p}Z\\}$;

  3. 3.

Y flip (Bit–phase flip) noise mechanism:

$\mathcal{N}_{\text{YF}}(\rho)={p}\rho+(1-p)Y\rho Y$

using Kraus matrices $\\{\sqrt{p}I,\sqrt{1-p}Y\\}$;

  4. 4.

Depolarizing noise mechanism:

$\mathcal{N}_{\text{Dep}}(\rho)=\frac{1+3p}{4}\rho+\frac{1-p}{4}(X\rho X+Y\rho
Y+Z\rho Z)$

using Kraus matrices
$\\{\frac{\sqrt{1+3p}}{2}I,\frac{\sqrt{1-p}}{2}X,\frac{\sqrt{1-p}}{2}Y,\frac{\sqrt{1-p}}{2}Z\\}$.

Alternative form of $\mathcal{N}_{\text{Dep}}$ is

$\mathcal{N}_{\text{Dep}}(\rho)=p\rho+(1-p)\frac{I}{2}.$

Furthermore, a parameter denoted as $\gamma$ can be introduced to regulate the
energy damping within a quantum system, with $\gamma$ representing the
probability associated with energy loss. Subsequently, three distinct types of
damping noise mechanisms are derived:

  1. 1.

Phase damping noise mechanism:

$\mathcal{N}_{\text{PD}}(\rho)=N_{0}\rho N_{0}^{\dagger}+N_{1}\rho
N_{1}^{\dagger}$

where the corresponding Kraus matrices are given by:

$N_{0}=\bmatrix 1&0\\\ 0\sqrt{1-\gamma},\quad N_{1}=\bmatrix 0&0\\\
0\sqrt{\gamma}.$

  2. 2.

Amplitude damping noise mechanism:

$\mathcal{N}_{\text{AD}}(\rho)=N_{0}\rho N_{0}^{\dagger}+N_{1}\rho
N_{1}^{\dagger}$

where the corresponding Kraus matrices are given by:

$N_{0}=\bmatrix 1&0\\\ 0\sqrt{1-\gamma},\quad N_{1}=\bmatrix
0&\sqrt{\gamma}\\\ 00.$

  3. 3.

Generalized amplitude damping noise mechanism:

$\mathcal{N}_{GAD}(\rho)=N_{0}\rho N_{0}^{\dagger}+N_{1}\rho
N_{1}^{\dagger}+N_{2}\rho N_{2}^{\dagger}+N_{3}\rho N_{3}^{\dagger}$

where the Kraus matrices are defined as follows:

$N_{0}=\sqrt{q}\bmatrix 1&0\\\ 0\sqrt{1-\gamma},\quad N_{2}=\sqrt{1-q}\bmatrix
0&0\\\ \sqrt{\gamma}0$ $N_{1}=\sqrt{q}\bmatrix 0&\sqrt{\gamma}\\\ 00,\quad
N_{3}=\sqrt{1-q}\bmatrix\sqrt{1-\gamma}&0\\\ 01.$

Here, a probability $0\leq q\leq 1$ represents the likelihood of Kraus
matrices $\\{N_{0},N_{1}\\}$ contributing to $\mathcal{N}_{\text{AD}}$.
Specifically, when $q=1$, the generalized amplitude damping noise
$\mathcal{N}_{\text{GAD}}$ is simplified to the standard noise model
$\mathcal{N}_{\text{AD}}$.

Through basic calculations, it is evident that amplitude damping and
generalized amplitude damping noises are non-unital, whereas all other noises
are unital.

###  3.3 Quantum Measurement

To extract classical information from a quantum state $\rho$, the only method
is to conduct a quantum measurement on $\rho$. In mathematical terms, a
quantum measurement $\mathcal{M}$ is a stochastic mechanism defined over a
finite set $\mathcal{O}_{\mathcal{M}}$ of measurement outcomes:
$\mathcal{M}:\mathcal{D(H)}\rightarrow\mathcal{D(O)}$.

$\aligned\text{Pr}[\mathcal{M}(\rho)=k]={\rm
tr}(M_{k}\rho)\quad\forall\rho\in\mathcal{D(H)}.$ (3)

In this context, $\mathcal{D(O)}$ represents the set of probability
distributions over the measurement outcomes set $\mathcal{O}$,
$\\{M_{k}\\}_{k\in\mathcal{O}}$ denotes a collection of positive semi-definite
matrices on the state (Hilbert) space $\mathcal{H}$, and
$\text{Pr}[\mathcal{M}(\rho)=k]$ signifies the probability of observing the
outcome $k$ through the measurement $\mathcal{M}$. It is essential to note
that the set of measurements $\\{M_{k}\\}_{k\in\mathcal{O}}$ adheres to the
_unity condition_ $\sum_{k}M_{k}=I$, ensuring that the sum of probabilities of
all outcomes equals 1. In simpler terms, $\sum_{k}{\rm tr}(M_{k}\rho)={\rm
tr}(\sum_{k}M_{k}\rho)={\rm tr}(\rho)=1$.

These types of measurements are commonly referred to as _Positive Operator-
Valued Measures_ and are extensively utilized for determining outcome
probabilities without involving the post-measurement quantum states. It is
important to note that following the measurement, the state undergoes collapse
or alteration based on the measurement outcome $k$, demonstrating a
fundamental distinction from classical computation.

##  4 Quantum Threat Model

Creating a threat model for local differential privacy in quantum systems
requires defining possible adversaries and outlining their abilities. This
section aims to establish a comprehensive threat model for our QLDP framework,
highlighting the distinctive characteristics of adversaries in quantum
environments. These adversaries can access quantum states directly and execute
various quantum measurements in single-part scenarios, while also being
capable of conducting entangling attacks through quantum entanglement in
distributed multi-part settings.

Single-part Setting. In order to enhance the resilience of our defense
strategies, we are addressing _the (quantum) adversary with the ability to
directly manipulate the quantum states published by quantum computers and
communication channels and conduct diverse quantum measurements on them_ , as
illustrated in the right side of Fig. 1. This is a departure from conventional
attacks, where adversaries are limited to observing the outcomes of a specific
quantum measurement only [25]. As discussed in the previous section, classical
defense mechanisms can effectively thwart such attacks due to the stochastic
nature of the measurement process. However, in our more stringent scenario,
the adversary can execute any quantum measurement on the state acquired from
the quantum system and infer the state’s confidentiality. Consequently, there
is a necessity to introduce quantum defense measures to uphold local
differential privacy in quantum systems, given the infinite potential quantum
measurements for a quantum system. In this paper, we propose the utilization
of quantum noise to protect QLDP and advocate for depolarizing noise as the
optimal choice to strike a balance between utility and privacy.

Figure 1: The framework of quantum local differential privacy

Multi-party Distributed Setting. Traditional studies in the classical domain
often assume independence among dataset records when implementing differential
privacy. However, real-world datasets typically show correlations among
records, which may result in unintended data disclosures [24]. In the quantum
realm, entanglement, a unique feature in quantum state correlation beyond
classical correlation, poses new challenges in ensuring privacy. In the
current distributed setting of quantum systems and communication channels,
quantum states are stored in remote locations. Users can perform local
measurements on a part of the system and communicate the results via classical
channels for further processing. This process, known as Local Operations and
Classical Communication (LOCC), has led to significant advancements in quantum
information science [29], benefiting applications such as state preparation,
state discrimination, and entanglement transformations. Shared entangled
states among multiple parties play a vital role in enhancing these
applications within the LOCC framework.

To enhance the practicality of our QLDP framework, we consider _the
adversary’s access to any quantum state shared among spatially separated
systems, which can be independent, classically correlated, or entangled._ In
our defense strategy, we introduce a composition theorem to show that the QLDP
loss across multiple parties can be controlled by combining the privacy loss
across all parties, even when dealing with entangled quantum states. This
framework validates the effectiveness of our defense approach in real-world
scenarios for protecting the privacy of distributed quantum states.

##  5 Quantum Local Differential Privacy

In this section, we start by defining local differential privacy for quantum
systems and exploring its relationship with classical local differential
privacy via quantum measurements. Following that, we demonstrate the
assessment of the local differential privacy in quantum mechanisms and
introduce a post-processing theorem for leveraging quantum noise to safeguard
the privacy of the quantum state. For the convenience of the reader, we put
all proofs of theoretical results in the appendix.

In accordance with the threat model we face in Section 4, the attacker has the
ability to access the quantum state and conduct any quantum measurement on it.
To safeguard the quantum state privacy under such conditions, quantum local
differential privacy is introduced as follows.

###### Definition 1

A quantum mechanism $\mathcal{E}$ operating on a Hilbert space $\mathcal{H}$
is $\varepsilon$-_quantum locally differentially private (
$\varepsilon$-QLDP)_ if, for any quantum measurement
$\mathcal{M}=\\{M_{k}:k\in\mathcal{O}_{\mathcal{M}}\\}$ and any quantum states
$\rho,\sigma\in\mathcal{D(H)}$, the following inequality holds:

$\text{Pr}[\mathcal{M}(\mathcal{E}(\rho))\in\mathcal{S}]\leq
e^{\varepsilon}\text{Pr}[\mathcal{M}(\mathcal{E}(\sigma))\in\mathcal{S}]\quad\forall\mathcal{S}\subseteq\mathcal{O}_{M}$

where
$\text{Pr}[\mathcal{M}(\mathcal{E}(\rho))\in\mathcal{S}]=\sum_{k\in\mathcal{S}}{\rm
tr}(M_{k}\mathcal{E}(\rho))$.

The provided definition elaborates on classical local differential privacy for
randomized mechanisms (see Fig. 1). It builds upon the same idea as local
differential privacy, asserting that despite an adversary having access to an
individual’s personal responses, they should not be able to discern
significant personal data due to the consistent behavior of the randomized
mechanism across any pair of input states. This concept is extended to the
quantum realm by introducing a parameter $\varepsilon$ that ensures the
similarity between the outcome probabilities $\sum_{k\in\mathcal{S}}{\rm
tr}(M_{k}\mathcal{E}(\rho))\text{and}\sum_{k\in\mathcal{S}}{\rm
tr}(M_{k}\mathcal{E}(\sigma))$ of quantum measurement $\mathcal{M}$ for any
outcome subset $\mathcal{S}\subseteq\mathcal{O}_{\mathcal{M}}$ to manage the
leakage of quantum state privacy under quantum mechanism $\mathcal{E}$.

To draw a comparison between quantum and classical local differential privacy,
we can utilize quantum measurement $\mathcal{M}$ as a (classical) randomized
mechanism, as explained in Section 3.3. Let us first revisit classical local
differential privacy (LDP).

###### Definition 2

A randomized mechanism (mapping) $f$ is $\varepsilon$-_locally differentially
private (LDP)_ if, for any states $x,y\in\text{domain}(f)$, the following
condition is met:

$\text{Pr}[f(x)\in\mathcal{S}]\leq
e^{\varepsilon}\text{Pr}[f(x)\in\mathcal{S}]\quad\forall\mathcal{S}\subseteq\text{image}(f)$

where $\text{domain}(f)$ and $\text{image}(f)$ denote the domain and image of
the mapping $f(\cdot)$, respectively.

For any quantum mechanism $\mathcal{E}$, we can derive a randomized mechanism
$\mathcal{M}\circ\mathcal{E}$, which represents the function composition of
$\mathcal{E}$ and $\mathcal{M}$. Subsequently, we can redefine QLDP of
$\mathcal{E}$ by considering the LDP of $\mathcal{M}\circ\mathcal{E}$.

###### Lemma 1

A quantum mechanism $\mathcal{E}$ is said to be $\varepsilon$-QLDP if and only
if the randomized mechanism $\mathcal{M}\circ\mathcal{E}$ exhibits
$\varepsilon$-LDP for any quantum measurement $\mathcal{M}$.

Based on the aforementioned outcome, it is evident that in order to ensure an
$\varepsilon$-QLDP assurance for a quantum system, a quantum mechanism must
ensure $\varepsilon$-LDP for all quantum measurements conducted on the system
simultaneously. This presents a significant challenge in safeguarding privacy
against potential attackers, given the infinite number of quantum measurements
possible within the system’s Hilbert space $\mathcal{H}$. To overcome this
difficulty, we apply eigenvalue analysis on the matrices describing the
evolution of quantum mechanisms to study the essential quantitative properties
of QLDP in the following.

###  5.1 Evaluating QLDP

In this section, we discuss the evaluation of the parameter $\varepsilon$ for
QLDP. Initially, we outline a method to calculate the classical LDP value of a
randomized mechanism $f=\mathcal{M}\circ\mathcal{E}$ involving a quantum
mechanism $\mathcal{E}$ and measurement $\mathcal{M}$. By utilizing this
approach, we can determine the parameter $\varepsilon$ of QLDP using Lemma 1.

Before proceeding, it is necessary to introduce the Heisenberg picture, which
tracks the evolution of quantum measurements, as opposed to the Schrödinger
picture that monitors the evolution of quantum states as shown previously in
Eq.(2). To illustrate this, when considering a quantum measurement
$\mathcal{M}$ with matrices $\\{M_{k}\\}_{k\in\mathcal{O}}$ and a quantum
mechanism denoted by $\mathcal{E}$ with Kraus matrices $\\{E_{j}\\}$, given a
quantum state $\rho$, the following calculations of the probability
$\text{Pr}[\mathcal{M}(\mathcal{E}(\rho))=k]={\rm tr}(M_{k}\mathcal{E}(\rho))$
of observing measurement outcome $k$ can be made:

$\aligned{\rm tr}(M_{k}\sum_{j}E_{j}\rho E_{j}^{\dagger})={\rm
tr}(\sum_{j}E_{j}^{\dagger}M_{j}E_{k}\rho)={\rm
tr}(\mathcal{E}^{\dagger}(M_{k})\rho).$

In this context, the second equation is derived from the commutative nature of
the trace operation, specifically, ${\rm tr}(AB)={\rm tr}(BA)$, where
$\mathcal{E}^{\dagger}(\cdot)=\sum_{j}E_{j}^{\dagger}\cdot E_{j}$ represents
the dual (adjoint) mapping of $\mathcal{E}$ aimed at describing the evolution
of quantum measurement $\mathcal{M}$.

With the Heisenberg picture and the dual mapping $\mathcal{E}$, we are able to
analyze the LDP of randomized mechanism $\mathcal{M}\circ\mathcal{E}$.

###### Theorem 5.1

Suppose $\mathcal{E}$ represents a quantum mechanism and $\mathcal{M}$
represents a quantum measurement with matrices
$\\{M_{k}\\}_{k\in\mathcal{O}_{\mathcal{M}}}$. The randomized mechanism
$\mathcal{M}\circ\mathcal{E}$ is $\varepsilon$-LDP if and only if

$0\geq\max_{\mathcal{S}\subseteq\mathcal{O}_{\mathcal{M}}}\lambda_{\max}[\mathcal{E}^{\dagger}(M_{\mathcal{S}})]-e^{\varepsilon}\lambda_{\min}[\mathcal{E}^{\dagger}(M_{\mathcal{S}})].$

Here, $M_{\mathcal{S}}=\sum_{k\in\mathcal{S}}M_{k}$, and $\lambda_{\max}(M)$
and $\lambda_{\min}(M)$ refer to the maximum and minimum eigenvalues of the
positive semi-definite matrix $M$, respectively.

Therefore, the (optimal) LDP value $\varepsilon^{*}$ (minimizing
$\varepsilon$) provided by the randomized mechanism
$\mathcal{M}\circ\mathcal{E}$ can be determined as follows:

$\varepsilon^{*}(\mathcal{M}\circ\mathcal{E})=\max_{\mathcal{S}\subseteq\mathcal{O}_{\mathcal{M}}}\ln\frac{\lambda_{\max}[\mathcal{E}^{\dagger}(\sum_{k\in\mathcal{S}}M_{k})]}{\lambda_{\min}[\mathcal{E}^{\dagger}(\sum_{k\in\mathcal{S}}M_{k})]}.$
(4)

In cases where
$\lambda_{\min}[\mathcal{E}^{\dagger}(\sum_{k\in\mathcal{S}}M_{k})]=0$ for
certain $\mathcal{S}\subseteq\mathcal{O}_{\mathcal{M}}$, the mechanism
$\mathcal{M}\circ\mathcal{E}$ is considered to be $\infty$-LDP, indicating
that the LDP leakage is unbounded.

Here, $\varepsilon^{*}(\cdot)$ is considered a function determining the
(optimal) LDP value for randomized mechanisms, which can also be extended to
QLDP for quantum mechanisms. By utilizing Lemma 1, we can express

$\varepsilon^{*}(\mathcal{E})=\max_{\mathcal{M}}\varepsilon^{*}(\mathcal{M}\circ\mathcal{E}).$

Calculation of $\varepsilon^{*}(\mathcal{M}\circ\mathcal{E})$ is essential for
all quantum measurements $\mathcal{M}$ as indicated by the equation provided.
It is worth noting that a quantum measurement can be defined by approximately
$\mathcal{O}(N^{4})$ parameters, where $N=2^{n}$ denotes the size of the state
space in an $n$-qubit quantum system $\mathcal{H}$. This arises from a quantum
measurement consisting of $N^{2}$ $N$-by-$N$ matrices at most [30, Theorem
2.1] and each matrix containing $N^{2}$ parameters. In the following, the
objective is to gradually decrease the parameter count from
$\mathcal{O}(N^{4})$ to $\mathcal{O}(N)$ to enhance the efficiency of QLDP
evaluation in quantum mechanisms.

In order to accomplish this, it can be observed that when $S^{*}$ denotes the
optimal subset where $\varepsilon^{*}(\mathcal{M}\circ\mathcal{E})$ is
achieved in Eq. (4), we can establish a binary (outcome) quantum measurement
$\mathcal{M}_{\mathcal{S}^{*}}=\\{M_{\mathcal{S}^{*}},I-M_{\mathcal{S}^{*}}\\}$.
Thus, $\mathcal{M}\circ\mathcal{E}$ obeys $\varepsilon$-LDP if and only if
$\mathcal{M}_{\mathcal{S}^{*}}\circ\mathcal{E}$ complies with
$\varepsilon$-LDP. It is essential to recognize that $M_{\mathcal{S}^{*}}$ is
a matrix falling within the set $\\{M:0\leq M\leq I\\}$. For any positive
semi-definite matrices $M_{1}$ and $M_{2}$, $M_{1}\leq M_{2}$ if and only if
$\bra{\psi}M_{1}\ket{\psi}\leq\bra{\psi}M_{2}\ket{\psi}$ holds for all pure
quantum state $\ket{\psi}$. Moreover, any $0\leq M\leq I$ can function as a
matrix contributing to a quantum measurement (for instance, a binary one
$\mathcal{M}_{M}$ with matrices $\\{M,I-M\\}$). Such a matrix $0\leq M\leq I$
is referred to as a _measurement matrix_. Consequently, we obtain

$\varepsilon^{*}(\mathcal{E})=\max_{0\leq M\leq
I}\varepsilon^{*}(\mathcal{M}_{M}\circ\mathcal{E}).$

By combining these insights with Theorem 5.1, we can derive the following
description of QLDP for the quantum mechanism $\mathcal{E}$.

###### Lemma 2

A quantum mechanism $\mathcal{E}$ is $\varepsilon$-QLDP if and only if, for
any measurement matrix $0\leq M\leq I$, the following inequality holds:

$0\geq\max_{0\leq M\leq
I}\lambda_{\max}[\mathcal{E}^{\dagger}(M)]-e^{\varepsilon}\lambda_{\min}[\mathcal{E}^{\dagger}(M)].$

Following the above result, our attention turns to managing an $N$-by-$N$
matrix $M$, which can be expressed through $N^{2}$ parameters based on the
aforementioned outcome. To decrease the number of parameters even further, we
can utilize the eigendecomposition of the measurement matrix
$M=\sum_{k}\lambda_{k}|\psi_{k}\rangle\langle\psi_{k}|$ with eigenvalue
$\lambda_{k}\geq 0$, as illustrated in Eq.(1) by noting that the normalized
$\frac{M}{{\rm tr}(M)}$ is a quantum state.

###### Theorem 5.2

A quantum mechanism $\mathcal{E}$ acting on a Hilbert space $\mathcal{H}$ is
$\varepsilon$-QLDP if and only if
$\varepsilon\geq\varepsilon^{*}(\mathcal{E})$, where the optimal QLDP value
$\varepsilon^{*}(\mathcal{E})$ of $\mathcal{E}$ is determined by the formula:

$\varepsilon^{*}(\mathcal{E})=\max_{\ket{\psi}\in\mathcal{H}}\ln\frac{\lambda_{\max}[\mathcal{E}^{\dagger}(\psi)]}{\lambda_{\min}[\mathcal{E}^{\dagger}(\psi)]}.$

If $\lambda_{\min}[\mathcal{E}^{\dagger}(\psi)]=0$ for some $\psi$, then we
say $\mathcal{E}$ is $\infty$-QLDP, denoted as
$\varepsilon^{*}(\mathcal{E})=\infty$, indicating unbounded QLDP leakage.

Here, it is worth recalling that $\psi=|\psi\rangle\langle\psi|$ represents
the mixed state form corresponding to the pure state $\ket{\psi}$. Based on
the outcome mentioned above, we can calculate the QLDP value by addressing an
optimization problem involving the variables represented by $\ket{\psi}$,
which encompass around $N$ parameters for $(N=2^{n})$-dimensional quantum
system $\mathcal{H}$. This approach aims to minimize the parameter count to
$\mathcal{O}(N)$ as previously discussed for enhancing efficiency.

For the 1-qubit quantum system, calculating QLDP value
$\varepsilon^{*}(\mathcal{E})$ of quantum mechanism $\mathcal{E}$ can be
simplified by recognizing that there are a maximum of 2 eigenvalues for 2-by-2
positive semi-definite matrices.

###### Corollary 1

If $\mathcal{E}$ is a 1-qubit quantum mechanism, then

$\varepsilon^{*}(\mathcal{E})=\ln\left(\frac{1}{1-\max_{\psi}\lambda_{\max}[\mathcal{E}^{\dagger}(\psi)]}-1)\right).$

By utilizing Theorems 5.1 and 5.2, we can calculate the LDP and QLDP values
for randomized mechanisms and quantum mechanisms, correspondingly. Examining
examples of quantum noise mechanisms can help illustrate the distinction
between these two quantities.

###### Example 2

Consider two measurements $\mathcal{M}_{0}$ and $\mathcal{M}_{1}$ denoted by
measurement matrices $\\{|0\rangle\langle 0|,|1\rangle\langle 1|\\}$ and
$\\{\frac{1}{2}I,\frac{1}{2}I\\}$, respectively. When subjected to
depolarizing noise mechanism $\mathcal{N}_{\text{Dep}}$ with probability $p$
as defined in Example 1, the QLDP value is given as
$\varepsilon^{*}(\mathcal{N}_{\text{Dep}})=\ln\frac{1+p}{1-p}$, while the LDP
value is expressed as

$\varepsilon^{*}(\mathcal{M}_{0}\circ\mathcal{N}_{\text{Dep}})=\ln\frac{1+p}{1-p}\text{and}\varepsilon^{*}(\mathcal{M}_{1}\circ\mathcal{N}_{\text{Dep}})=0.$

It is evident that the QLDP value $\varepsilon^{*}(\mathcal{N}_{\text{Dep}})$
can be reached using the LDP value
$\varepsilon^{*}(\mathcal{M}_{0}\circ\mathcal{N}_{\text{Dep}})$. This suggests
that by employing quantum measurement $\mathcal{M}_{0}$, an attacker can
attain the maximum QLDP leakage offered by the quantum noise mechanism
$\mathcal{N}_{\text{Dep}}$. On the other hand, utilizing quantum measurement
$\mathcal{M}_{1}$ alone does not provide any information on quantum state
privacy, as the corresponding LDP value is 0.

In the simplest scenario of quantum algorithms and channels, a quantum
mechanism $\mathcal{E}=\mathcal{U}$ can be represented by a single Kraus
(unitary) matrix U ($UU^{\dagger}=I$), where $\mathcal{U}(\rho)=U\rho
U^{\dagger}$ for all $\rho\in\mathcal{D(H)}$. In such instances, the QLDP of
$\mathcal{U}$ can be directly obtained from Theorem 5.2 in the worst-case
scenario.

###### Corollary 2

Any unitary quantum mechanism $\mathcal{U}$ is $\infty$-QLDP.

As stated in Corollary 2, unitary quantum systems are highly vulnerable to
attacks in the QLDP scenario. Therefore, it is imperative to establish a
defense mechanism to safeguard the privacy of quantum states. In classical
local differential privacy, one can provide privacy guarantee by incorporating
noise into the classical data before collecting. Similarly, in the realm of
quantum systems, this can be achieved through the application of a quantum
post-processing theorem, as elaborated in the subsequent section.

###  5.2 Post-processing Guarantee and Effective Noise Mechanisms

In this section, we introduce a post-processing theorem for QLDP to
demonstrate that incorporating quantum noise mechanisms is an effective
strategy for safeguarding the privacy of quantum states. Additionally, we
outline a method to pinpoint efficient quantum noise mechanisms that yield a
measurable QLDP value.

###### Theorem 5.3

If a quantum mechanism $\mathcal{E}$ is $\varepsilon$-QLDP, then the
(functionally) composed quantum mechanism $\mathcal{N}\circ\mathcal{E}$ is
still $\varepsilon$-QLDP for any quantum mechanism $\mathcal{N}$.

According to this post-processing theorem, we can utilize a quantum noise
mechanism to avoid privacy breaches. The challenge now lies in selecting the
appropriate mechanism, which should offer a finite QLDP value at the very
least. To address this, it is essential to initially assess whether
$\varepsilon^{*}(\mathcal{E})<\infty$ for a specified quantum mechanism
$\mathcal{E}$.

###### Lemma 3

Consider a quantum mechanism $\mathcal{E}$ with Kraus matrices
$\\{E_{k}\\}_{k=0}^{K-1}$ on a Hilbert space $\mathcal{H}$. The QLDP value
$\varepsilon^{*}(\mathcal{E})<\infty$ holds if and only if one of the
following equivalent conditions is met:

  1. 1.

$\mathcal{E}^{\dagger}\otimes\mathcal{I}(|\Omega\rangle\langle\Omega|)>0$,
where $\ket{\Omega}=\sum_{j}|j,j\rangle\langle j,j|$ is the unnormalized
maximal entangled state over composed quantum system
$\mathcal{H}\otimes\mathcal{H}$ and $\\{\ket{j}\\}_{j}$ is a mutually
orthogonal basis of $\mathcal{H}$;

  2. 2.

The linear span of $\\{E_{k}^{\dagger}\\}$ encompasses the entire matrix space
on $\mathcal{H}$, indicating that any matrix on $\mathcal{H}$ can be linearly
represented by $\\{E_{k}^{\dagger}\\}$.

Checking either of the two conditions mentioned above has a time complexity of
$\mathcal{O}(N^{4}K^{2})$, where $N$ represents the dimension of $\mathcal{H}$
and $K$ stands for the number of Kraus matrices of $\mathcal{E}$.

Based on the second condition, we can infer from linear algebra principles
that a minimum of $N^{2}$ Kraus matrices is required to cover the entire
matrix space on a Hilbert space $\mathcal{H}$ of dimension $N$. Consequently,
the number $K$ of Kraus matrices $\\{E_{k}\\}_{k=0}^{K-1}$ in a quantum system
$\mathcal{E}$ effectively indicates that
$\varepsilon^{*}(\mathcal{E})=\infty$.

###### Corollary 3

Consider a quantum mechanism $\mathcal{E}$ with Kraus matrices
$\\{E_{k}\\}_{k=1}^{K}$ on a Hilbert space $\mathcal{H}$ with dimension $N$.
If $K<N^{2}$, then $\varepsilon^{*}(\mathcal{E})=\infty$.

By the corollary, it is evident that some quantum noise mechanisms outlined in
Example 1 do not yield a quantifiable QLDP value. In contrast, for the rest
quantum noises, we can determine the QLDP value $\varepsilon^{*}$ by solving
the optimization problem shown in Theorem 5.2 along with its corresponding
corollary (Corollary 1).

######  Theorem 5.4 (QLDP Values)

For the standard 1-qubit noises presented in Example 1, the (optimal) QLDP
values provided by them are as follows.

  1. 1.

For the Pauli-type noises with probability $0\leq p\leq 1$, we have

$\varepsilon^{*}(\mathcal{N}_{\text}{XF})=\varepsilon^{*}(\mathcal{N}_{\text}{YF})=\varepsilon^{*}(\mathcal{N}_{\text}{ZF})=\infty$

and

$\varepsilon^{*}(\mathcal{N}_{\text{Dep}})=\left\\{\aligned&\ln\frac{1+p}{1-p}\textrm{
if }0\leq p<1\\\ \infty\textrm{ if }p=1\right..$

  2. 2.

For the damping-type noises with parameters $0\leq r,q\leq 1$, we have

$\varepsilon^{*}(\mathcal{N}_{\text}{PD})=\varepsilon^{*}(\mathcal{N}_{\text}{AD})=\infty$

and furthermore, for $q=0,1$ or $r=0$,
$\varepsilon^{*}(\mathcal{N}_{\text{GAD}})=\infty.$ Otherwise,

$\varepsilon^{*}(\mathcal{N}_{\text{GAD}})=\ln(\frac{1+\sqrt{1-4rq+4rq^{2}}}{1-\sqrt{1-4rq+4rq^{2}}}).$

Moreover, when considering these efficient quantum noise mechanisms such as
$\mathcal{N}_{\text{Dep}}$ and $\mathcal{N}_{\text{GAD}}$, the key issue is
determining their relative effectiveness. In addressing this concern, utility
serves as a crucial criterion for selecting the most suitable noise mechanism
within the classical realm. Therefore, the subsequent section will focus on
identifying the most optimal mechanism in terms of utility to effectively
manage the trade-off between QLDP and utility.

Remark. By Theorem 5.4, many quantum noise mechanisms do not yield a finite
QLDP value necessary for safeguarding the privacy of quantum states. This
limitation may result from the stringent confinement of QLDP as defined in
Definition 1, which relies solely on the parameter $\varepsilon$. To address
this issue, we may consider loosening the requirement of achieving
$\varepsilon$-QLDP by introducing an additional parameter $\delta$ to manage
privacy breaches. This approach follows the same idea as the classical case.
Consequently, we introduce the following revised definition:

###### Definition 3

A quantum mechanism $\mathcal{E}$ acting on a Hilbert space $\mathcal{H}$ is
$(\varepsilon,\delta)$-_quantum locally differentially private (QLDP)_ if, for
any quantum measurement
$\mathcal{M}=\\{M_{k}:k\in\mathcal{O}_{\mathcal{M}}\\}$ and any quantum states
$\rho,\sigma\in\mathcal{D(H)}$, the following condition holds:

$\sum_{k\in\mathcal{S}}{\rm tr}(M_{k}\mathcal{E}(\rho))\leq
e^{\varepsilon}\sum_{k\in\mathcal{S}}{\rm
tr}(M_{k}\mathcal{E}(\sigma))+\delta\quad\forall\mathcal{S}\subseteq\mathcal{O}_{M}.$

Despite the relaxation in the QLDP definition, it is observed that
$\mathcal{N}_{\text}{XF},\mathcal{N}_{\text}{ZF},\mathcal{N}_{\text}{PD}$, and
$\mathcal{N}_{\text}{AD}$ in Example 1 can only ensure $(\varepsilon,1)$-QLDP
for any $\varepsilon$, which is unsurprising given that $\delta\leq 1$.
Consequently, this relaxed version of QLDP may not be the most suitable for
quantum computing, necessitating the exploration of alternative methods to
incorporate these noises effectively as a defensive mechanism. We left this as
a future work.

##  6 Optimal Mechanisms for Utilities

In this section, we demonstrate that the depolarizing noise mechanism is the
best choice for ensuring an $\varepsilon$-QLDP guarantee while maximizing
fidelity and trace distance utilities across all dimensions of quantum state
space compared to other unital quantum mechanisms.

###  6.1 Choices of Utilities

Within our threat model framework in Section 4, the key emphasis lies in
protecting quantum states. The incorporation of quantum noise mechanisms is
crucial to achieving this objective but can potentially compromise the
integrity of these quantum states. Consequently, this compromises the
precision and utility of quantum states for specific analytical purposes.
Therefore, it becomes essential to assess the effectiveness of a quantum noise
mechanism in retaining information pertaining to quantum states.
Traditionally, the evaluation of such utilities is often conducted through
fidelity and anti-trace distance within the quantum realm.

The two utilities of quantum noise mechanisms are based on fidelity and trace
distance of a pair of quantum states. The fidelity $F(\rho,\sigma)$ and trace
distance $T(\rho,\sigma)$ for two quantum states $\rho$ and $\sigma$ are
defined as follows:

$F(\rho,\sigma):=[\text{tr}(\sqrt{\sqrt{\rho}\sigma\sqrt{\rho}})]^{2}\quad\text{and}\quad
T(\rho,\sigma):=\frac{1}{2}\text{tr}(|\rho-\sigma|).$

For any Hermitian matrix $H$111A matrix $H$ is considered Hermitian when
$H^{\dagger}=H$. Consequently, all eigenvalues of $H$ are real numbers. (e.g.,
$\rho$ and $\rho-\sigma$) with eigendecomposition
$\sum_{k}\lambda_{k}|\psi_{k}\rangle\langle\psi_{k}|$, the square root of $H$
is defined as
$\sqrt{H}=\sum_{k}\sqrt{\lambda_{k}}|\psi_{k}\rangle\langle\psi_{k}|$ and the
absolute value of $H$ is denoted as
$|H|=\sum_{k}|\lambda_{k}||\psi_{k}\rangle\langle\psi_{k}|$. The fidelity of
two states quantifies their similarity, while trace distance measures their
dissimilarity. To see this, for example, $F(\rho,\sigma)=1$
($T(\rho,\sigma)=0$) if and only if $\rho=\sigma$, indicating that $\rho$ and
$\sigma$ are indistinguishable. On the other hand, $F(\rho,\sigma)=0$
($T(\rho,\sigma)=1$) if and only if $\rho$ is orthogonal to $\sigma$, implying
that $\rho$ and $\sigma$ are entirely distinguishable [1].

We can now establish the concepts of fidelity and anti-trace distance
utilities for quantum mechanisms with respect to all quantum states in the
worst-case scenario [1, Section 9.3].

###### Definition 4

The fidelity utility of a quantum mechanism $\mathcal{N}$ on a Hilbert space
$\mathcal{H}$ is defined as

$F(\mathcal{N}):=\min_{\rho\in\mathcal{D(H)}}F(\mathcal{N}(\rho),\rho).$

By definition, the fidelity utility $F(\mathcal{N})$ is determined by the
minimal information (utility) preserved by $\mathcal{N}$ on all quantum states
based on the fidelity measure.

###### Definition 5

The anti-trace distance utility of a quantum mechanism $\mathcal{N}$ on a
Hilbert space $\mathcal{H}$ is defined as:

$\hat{T}(\mathcal{N}):=1-T(\mathcal{N})$

where

$T(\mathcal{N}):=\max_{\rho\in\mathcal{D(H)}}\|\mathcal{N}(\rho)-\rho\|.$

Defined as $T(\mathcal{N})$, this metric quantifies the maximal noisy effects
caused by $\mathcal{N}$ on all quantum states using the trace distance.
Consequently, $\hat{T}(\mathcal{N})$ evaluates the minimal information
(utility) preserved by $\mathcal{N}$ on all quantum states.

To estimate the two utilities, by the joint concavity of fidelity and trace
distance [1, Section 9.3], we only need to focus on pure quantum states as
follows.

$\aligned&F(\mathcal{N})=\min_{\ket{\psi}\in\mathcal{H}}F(\mathcal{N}(\psi),\psi)=\min_{\ket{\psi}\in\mathcal{H}}\bra{\psi}\mathcal{N}(\psi)\ket{\psi}\\\
\hat{T}(\mathcal{N})=1-\max_{\ket{\psi}\in\mathcal{H}}T(\mathcal{N}(\psi),\psi).$

With the above equations, we can analytically compute the fidelity and anti-
trace distance utilities for the quantum noise mechanisms introduced in
Example 1.

######  Theorem 6.1 (Utilities for Quantum Noise Mechanisms)

For the standard 1-qubit noises presented in Example 1, the (optimal) QLDP
values provided by them are as follows.

  1. 1.

For the Pauli-type noises with noiseless probability $0\leq p\leq 1$, we have

$\aligned&F(\mathcal{N}_{\text}{UF})=\hat{T}(\mathcal{N}_{\text}{UF})=p\quad\text{for}\quad
U\in\\{X,Y,Z\\}\\\
F(\mathcal{N}_{\text{Dep}})=\hat{T}(\mathcal{N}_{\text}{Dep})=\frac{1+p}{2}\\\
$

  2. 2.

For the damping-type noises with parameters $0\leq r,q\leq 1$, we have

$\aligned&F(\mathcal{N}_{\text}{PD})=\hat{T}(\mathcal{N}_{\text}{PD})=\frac{1+\sqrt{1-r}}{2}\\\
F(\mathcal{N}_{AD})=\hat{T}(\mathcal{N}_{AD})=1-r\\\
F(\mathcal{N}_{\text{GAD}})=\hat{T}(\mathcal{N}_{\text{GAD}})=\left\\{\aligned
1-qr\text{if}q\geq\frac{1}{2}\\\ 1-(1-q)r\text{if}q<\frac{1}{2}\right..$

As we can see, parameters $p,q,$ and $r$ can be utilized to regulate the
utilities offered by quantum noise mechanisms. When considering the QLDP value
illustrated in Theorem 5.4, determining the most suitable option becomes an
intriguing challenge.

By utilizing Theorems 5.4 and 6.1, we can establish the quantitative
connection between utility and privacy concerning 1-qubit depolarizing and
generalized amplitude damping noise mechanisms with $0\leq p<1$, $0<q<1$ and
$0<r\leq 1$. It is important to note that other noise mechanisms in Example 1
do not yield significant QLDP values in this context, as shown in Theorem 5.4.

$\aligned&F(\mathcal{N}_{\text{Dep}})=\hat{T}(\mathcal{N}_{\text{Dep}})=\frac{e^{\varepsilon}}{e^{\varepsilon}+1}\quad\text{for}\quad\varepsilon=\varepsilon^{*}(\mathcal{N}_{\text{Dep}})$
(5)
$F(\mathcal{N}_{\text}{GAD})=\hat{T}(\mathcal{N}_{\text}{GAD})=\left\\{\aligned&1-\frac{e^{\varepsilon}}{(1-q)(e^{\varepsilon}+1)^{2}}\text{if}q\geq\frac{1}{2}\\\
1-\frac{e^{\varepsilon}}{q(e^{\varepsilon}+1)^{2}}\text{if}0<q<\frac{1}{2}\\\
1\text{if}q=0\right.$ (6)

Here, $\varepsilon=\varepsilon^{*}(\mathcal{N}_{\text{GAD}})$.

The forms above illustrate the balance between the utilities and QLDP value of
the two quantum noises. Additionally, we can compare these quantum noises
within the QLDP framework. Further elaboration on this comparison will be
presented in the subsequent analytical analysis and numerical experiments in
Section 8.

Remark. Although Theorem 6.1 demonstrates that for any standard 1-qubit
quantum noise mechanism introduced in Example 1, the fidelity utility is equal
to the anti-trace distance utility, it remains uncertain whether this equality
holds true for all quantum mechanisms. Instead, a general inequality holds for
any quantum mechanism $\mathcal{N}$:

$\hat{T}(\mathcal{N})\leq F(\mathcal{N}).$

To elaborate, the relationship between trace distance and fidelity states that
for any quantum states $\rho$ and $\sigma$, the trace distance provides upper
and lower bounds on the fidelity, as indicated by the Fuchs–van de Graaf
inequalities [31]:

${\displaystyle 1-{\sqrt{F(\rho,\sigma)}}\leq
T(\rho,\sigma)\leq{\sqrt{1-F(\rho,\sigma)}}.\,}$ (7)

When at least one of the states is a pure state $\psi$, the lower bound can be
further refined to:

$1-F(\rho,\psi)\leq T(\rho,\psi).$

Consequently, through the arbitrariness of $\rho$, we deduce

$1-T(\mathcal{N}(\psi),\psi)\leq F(\mathcal{N}(\psi),\psi).$

By optimizing all pure states independently on both sides, we derive

$\min_{\psi}[1-T(\mathcal{N}(\psi),\psi)]\leq\min_{\psi}F(\mathcal{N}(\psi),\psi).$

This leads to the conclusion $\hat{T}(\mathcal{N})\leq F(\mathcal{N}).$ It is
important to note that the trace distance is often more computationally
feasible to evaluate or constrain compared to fidelity, making these
relationships particularly valuable.

In this paper, we examine the balance between the utility and privacy concerns
of quantum noise mechanisms. We do not currently address the equivalence of
these benefits and consider it a topic for future research.

###  6.2 Optimal Mechanisms

This section is dedicated to the identification of optimal unital quantum
mechanisms that maximize information theoretic utilities while upholding a
constant QLDP value. Specifically, we focus on fidelity and trace distance
utilities within an $n$-qubit quantum system $\mathcal{H}$ for practical
implementation.

We address two main problems formally:

######  Problem 1 (Fidelity utility optimization)

In the case of fidelity utility, the objective is to maximize fidelity utility
among all $\varepsilon$-QLDP quantum mechanisms, given by: max_$\mathcal{N}$ &
F($\mathcal{N}$)
subject to $\mathcal{N}$∈$\mathbb{N}$_ε. Here,
$\mathbb{N}_{\varepsilon}=\\{\mathcal{N}:\varepsilon^{*}(\mathcal{N})=\varepsilon\text{and}\mathcal{N}(I)=I\\}$
represents the set of unital quantum mechanisms with a QLDP value of
$\varepsilon$.

######  Problem 2 (Anti-trace distance utility optimization)

In the case of trace distance utility, the goal is to maximize the anti-trace
distance utility $\hat{T}$ among all $\varepsilon$-QLDP quantum mechanisms,
given by: max_$\mathcal{N}$ & ^T($\mathcal{N}$)
subject to $\mathcal{N}$∈$\mathbb{N}$_ε.

To address the two optimization issues mentioned above, we initially establish
the optimal bounds for both utilities by utilizing the QLDP value as depicted
below.

###### Theorem 6.2

For any unital quantum mechanism $\mathcal{N}$ with
$\varepsilon^{*}(\mathcal{N})<\infty$, we have

$\aligned
F(\mathcal{N})\leq\frac{e^{\varepsilon}}{e^{\varepsilon}+2^{n}-1}\qquad\hat{T}(\mathcal{N})\leq\frac{e^{\varepsilon}}{e^{\varepsilon}+2^{n}-1}.$

Here $\varepsilon=\varepsilon^{*}(\mathcal{N})$ and either of these equalities
is obtained if and only if $\mathcal{N}\in\mathbb{N}^{*}$, where the set of
optimal quantum mechanisms $\mathbb{N}^{*}$ is defined as

$\\{\mathcal{N}_{\eta}:\mathcal{N}^{\dagger}_{\eta}(\rho)=\eta\rho+\frac{1-\eta}{2^{n}-1}(I-{\rho})\text{and}1>\eta\geq\frac{1}{2^{n}}\\}.$

Hence, based on the aforementioned outcome, our primary focus should be on the
set $\mathbb{N}^{*}$ to maximize utilities. Let’s examine the scenario of a
1-qubit system, where $n=1$. In this instance, $\mathbb{N}^{*}$ is represented
by the set

$\\{\mathcal{N}_{\eta}:\mathcal{N}^{\dagger}_{\eta}(\rho)=(2\eta-1)\rho+(1-\eta)I\text{and}1>\eta\geq\frac{1}{2}\\}.$

If we let $p=2\eta-1$, we can express $\mathbb{N}^{*}$ as

$\\{\mathcal{N}:\mathcal{N}^{\dagger}(\rho)=p\rho+\frac{1-p}{2}I\text{and}1>p\geq
0\\}.$

Therefore, in a 1-qubit system, $\mathbb{N}^{*}$ is comprised of depolarizing
quantum noise processes with a probability $p<1$, where depolarizing noise
$\mathcal{N}_{\text{Dep}}$ is its own adjoint. Extending this concept to a
general $n$-qubit quantum system, the parameter $p$ defined as
$p=\eta-\frac{1-\eta}{2^{n}-1}$ results in:

$\mathbb{N}^{*}=\\{\mathcal{N}:\mathcal{N}^{\dagger}(\rho)=p\rho+(1-p)\frac{I}{2^{n}}\text{and}0\leq
p<1\\}.$

Under this definition, all quantum processes within $\mathbb{N}^{*}$ are
essentially $n$-qubit depolarizing noises with a probability less than 1. The
formal representation of a depolarizing noise, denoted as
$\mathcal{N}_{\text{Dep}}^{n}$, acting with a probability of $p$ on an
$n$-qubit quantum state space $\mathcal{H}$ [1], is given by

$\mathcal{N}_{\text{Dep}}^{n}(\rho)=p\rho+(1-p)\frac{I}{2^{n}}\qquad\forall\rho\in\mathcal{D(H)}.$

Furthermore, the adjoint of $\mathcal{N}_{\text{Dep}}^{n}$ is itself.
Specifically, the depolarizing noise for a 1-qubit system is labeled as
$\mathcal{N}_{\text{Dep}}^{1}$. Therefore, the optimal set $\mathbb{N}^{*}$ in
Theorem 6.2 encompasses all depolarizing noises with a probability $p<1$. It
is worth noting that the adjustment of utilities and QLDP values of
depolarizing noise can be achieved by manipulating the probability $p$.

###### Lemma 4

For a depolarizing quantum noise $\mathcal{N}_{\text{Dep}}^{n}$ with
probability $0\leq p<1$ on a $n$-qubit system, we have

  * •

QLDP value is

$\varepsilon^{*}(\mathcal{N}_{\text{Dep}}^{n})=\ln[1+2^{n}(\frac{1}{1-p}-1)].$

  * •

Fidelity and anti-trace distance utilities both are

$F(\mathcal{N}_{\text{Dep}}^{n})=\hat{T}(\mathcal{N}_{\text{Dep}}^{n})=\frac{(2^{n}-1)p+1}{2^{n}}.$

This result indicates that as the increment of $p$ occurs, the QLDP value and
utilities also increase. This demonstrates a clear quantitative trade-off
between the utilities and privacy of depolarizing noise mechanisms. By
combining these values based on $p$, we can address the optimization problems
related to fidelity and trace distance utility (Problems 1 and 2) as follows.

###### Theorem 6.3

The optimal solutions for the fidelity and anti-trace distance utility
optimization problems (Problems 1 and 2) in an $n$-qubit system are given by

$F(\mathcal{N}^{*})=\hat{T}(\mathcal{N}^{*})=\frac{e^{\varepsilon}}{e^{\varepsilon}+2^{n}-1},$

where $\mathcal{N}^{*}$ represents the quantum mechanism leading to the
optimal values. All feasible solutions contribute to a set denoted as
$\mathbb{N}^{*}_{\varepsilon}$,

$\mathbb{N}^{*}_{\varepsilon}=\\{\mathcal{N}_{\text{Dep}}^{n}:\mathcal{N}_{\text{Dep}}^{n}(\rho)=\frac{e^{\varepsilon}-1}{e^{\varepsilon}+2^{n}-1}\rho+\frac{I}{e^{\varepsilon}+2^{n}-1}\\}.$

According to the above findings, the depolarizing noise mechanism emerges as
the preferred option for balancing the trade-off between QLDP and either
fidelity or trace distance utility.

Finally, it is evident that depolarizing noise serves as a quantum extension
of classical randomized responses [23]. To illustrate this point, we first
consider the depolarizing noise mechanism denoted as
$\mathcal{N}_{\text{Dep}}^{n}$. According to Theorem 6.3, the behavior of
$\mathcal{N}^{n}_{\text{Dep}}$ with QLDP value $\varepsilon$ can be expressed
as follows:

$\aligned\mathcal{N}_{\text{Dep}}^{n}(\rho)=\frac{e^{\varepsilon}}{e^{\varepsilon}+2^{n}-1}\rho+\left(\frac{1}{e^{\varepsilon}+2^{n}-1}\right)(I-\rho).$
(8)

Next, we introduce a quantum measurement $\\{\psi_{k}\\}_{0\leq k\leq
2^{n}-1}$ comprising a collection of mutually orthogonal pure states
$\ket{\psi_{k}}$. Considering the observation of quantum state $\psi_{k}$
given quantum state $\psi_{j}$ under depolarizing noise
$\mathcal{N}_{\text{Dep}}^{n}$, the conditional probability can be formulated
as:

$\text{Pr}(X=k|Y=j)=\text{Tr}(\psi_{k}\mathcal{N}_{\text{Dep}}^{n}(\psi_{j}))=\left\\{\aligned&\frac{e^{\varepsilon}}{e^{\varepsilon}+2^{n}-1}\text{if}k=j\\\
\frac{1}{e^{\varepsilon}+2^{n}-1}\text{if}k\neq j.\right.$

In this scenario, the depolarizing noise involves a straightforward
randomization across the measurement outcome $\\{0,1,\cdots,2^{n}-1\\}$, where
the actual data is disclosed with a probability of
$\frac{e^{\varepsilon}}{e^{\varepsilon}+2^{n}-1}$. This mirrors the concept of
classical randomized response as discussed in [32]. Therefore, depolarizing
noise can be seen as an extension of randomized response. This extension
provides a clearer insight into the effectiveness of safeguarding QLDP, given
that the randomized response mechanism has been shown to optimize the KL
divergence utility across all classical $\varepsilon$-LDP mechanisms [32].

Remark. In certain extreme scenarios, our objective is to minimize the QLDP
value concerning a fixed anti-trace distance or fidelity utility. According to
Theorem 6.2, it holds for any unital quantum mechanism $\mathcal{N}$ that:

$\aligned&\varepsilon^{*}(\mathcal{N})\geq\ln[(2^{n}-1)(\frac{1}{1-F(\mathcal{N})}-1)]\\\
\varepsilon^{*}(\mathcal{N})\geq\ln[(2^{n}-1)(\frac{1}{1-\hat{T}(\mathcal{N})}-1)].$

Consequently, the minimum value of $\varepsilon^{*}(\mathcal{N})$ is only
attained when $\mathcal{N}\in\mathbb{N}^{*}$. Thus, depolarizing noise emerges
as the optimal mechanism for minimizing the QLDP value across all quantum
mechanisms with either a fixed fidelity or anti-trace distance utility.

##  7 Composition Theorem for Distributed Quantum Systems

This section presents a composition theorem for scenarios involving
distributed quantum computing, ensuring that the cumulative leakage loss of
the combined systems is additive. Initially focusing on a bipartite quantum
system, we consider all types of relationships—be it independent, classically
related, or entangled—between states distributed across each subsystem.
Subsequently, we extend this analysis to encompass any $m$-party system.

In a bipartite distributed quantum system
$\mathcal{H}_{A}\otimes\mathcal{H}_{B}$, quantum states are categorized into
three classes based on the relationship between the two sides:

  1. 1.

Independent: The system’s global state is a product state such as
$\rho^{A}\otimes\rho^{B}$, where $\rho^{A}$ and $\rho^{B}$ represent quantum
states on subsystems $\mathcal{H}_{A}$ and $\mathcal{H}_{B}$, respectively.

  2. 2.

(Classically) Correlated: The global state of the system is a convex
combination of product states

$\sum_{i}p_{i}\rho_{i}^{A}\otimes\rho_{i}^{B}\text{with}\sum_{i}p_{i}=1$

where $\rho_{i}^{A}$ and $\rho_{i}^{B}$ denote quantum states on subsystems
$\mathcal{H}_{A}$ and $\mathcal{H}_{B}$, respectively.

  3. 3.

Entangled: The global state of the system cannot be expressed in a classically
correlated form.

Independent subsystems are essentially a subset of correlated subsystems, with
$\rho_{A}\otimes\rho_{B}$ representing a simple convex combination of product
states, indicating classical correlation. In contrast, entangled states
exhibit distinct characteristics compared to classical systems and are crucial
in quantum secure communication, teleportation, and accelerating computational
processes. Exploring a quantum entangled state can provide further insight
into its nature.

######  Example 3 (Entangled States)

Consider a 2-qubit pure state $\ket{\varphi}$ in a bipartite 1-qubit system
$\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ given by:

$\ket{\varphi}=\frac{\ket{0}_{A}\otimes\ket{0}_{B}+\ket{1}_{A}\otimes\ket{1}_{B}}{\sqrt{2}}$

The state $\varphi=|\varphi\rangle\langle\varphi|$ is entangled. Determining
the entanglement of a mixed state is generally challenging. It has been proven
that the general bipartite scenario is NP-hard [33]. For the 2-qubit case, the
Positive Partial Transpose (PPT) condition [34] serves as a necessary and
sufficient criterion for identifying entangled states. This condition can be
applied to verify the entanglement of $\ket{\varphi}$.

Suppose Alice acts as an observer for system $A$, and Bob as an observer for
system $B$. They share the entangled state $\varphi$ over the composed system
of $A$ and $B$. If Alice conducts a measurement on subsystem $A$ using the
measurement operators $\\{|0\rangle\langle 0|,|1\rangle\langle 1|\\}$, two
possible outcomes, 0 and 1, will occur with equal probabilities:

  1. 1.

If the outcome is 0, the system’s state collapses to
$\ket{0}_{A}\otimes\ket{0}_{B}$.

  2. 2.

If the outcome is 1, the system’s state collapses to
$\ket{1}_{A}\otimes\ket{1}_{B}$.

In the event of the former outcome, any subsequent measurement conducted by
Bob using the same measurement basis will always yield outcome 0. Conversely,
if the latter outcome occurs (Alice measures 1), Bob’s measurement will
unequivocally return 1. Consequently, Alice’s local measurement on system A
affects system B, regardless of any spatial separation between the two
systems.

Entangled states like these present new obstacles in safeguarding quantum
state information, as an attacker could manipulate one part of the system
through measurement to compromise privacy elsewhere. Luckily, our subsequent
findings introduce a composition theorem that guarantees the effectiveness of
QLDP in securing distributed quantum systems.

In distributed quantum systems, it is not feasible to conduct a global
measurement on the entire system due to the spatial separation of subsystems.
However, it is possible to carry out a joint measurement by performing local
measurements on each subsystem.

More formally, the joint measurement on a bipartite system
$\mathcal{H}_{A}\otimes\mathcal{H}_{B}$ involves measurement matrices denoted
as

$M_{k}=\sum_{i,j}M_{k,i}^{A}\otimes M_{k,j}^{B}\text{where}\sum_{k}M_{k}=I.$

Here, $\\{M_{k,i}^{A}\\}$ and $\\{M_{k,j}^{B}\\}$ represent quantum
measurements on $\mathcal{H}_{A}$ and $\mathcal{H}_{B}$, respectively.

State Measurement | Product | Joint
---|---|---
Independent | Yes | Yes
Classically Correlated | Yes | Yes
Entangle | Yes | Yes
Table 1: Additivity of QLDP Value $\varepsilon^{*}$ Across Various Quantum
State and Measurement Types

We can redefine QLDP as stated in Definition 1 to provide a clearer formal
definition of QLDP for distributed quantum systems.

###### Definition 6

Let $\mathcal{E}_{k}$ be a quantum mechanism on Hilbert space
$\mathcal{H}_{k}$ for $0\leq k\leq t-1$. The composed quantum mechanism
$\mathcal{E}_{0}\otimes\mathcal{E}_{1}\otimes\cdots\otimes\mathcal{E}_{t-1}$
is $\varepsilon$-_quantum locally differentially private (
$\varepsilon$-QLDP)_ if for any joint quantum measurement
$\mathcal{M}=\\{M_{j}\\}_{j\in\mathcal{O}_{\mathcal{M}}}$ and any quantum
states
$\rho,\sigma\in\mathcal{D}(\mathcal{H}_{0}\otimes\mathcal{H}_{1}\otimes\cdots\otimes\mathcal{H}_{t-1})$,
we have

$\sum_{k\in\mathcal{S}}{\rm tr}(M_{k}\mathcal{E}(\rho))\leq
e^{\varepsilon}\sum_{k\in\mathcal{S}}{\rm
tr}(M_{k}\mathcal{E}(\sigma))\quad\forall\mathcal{S}\subseteq\mathcal{O}_{\mathcal{M}}.$

Next, we establish a composition theorem for all quantum states of multiple
systems, encompassing product quantum states, classically correlated quantum
states, and entangled quantum states, along with joint quantum measurements.
This pertains to the setting of LOCC addressed in our paper. We demonstrate
the additivity of QLDP in the distributed scenario, and a summary is provided
in Table 1.

###### Theorem 7.1

If two quantum mechanisms $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ on Hilbert
space $\mathcal{H}_{1}$ and $\mathcal{H}_{2}$ are $\varepsilon_{1}$ and
$\varepsilon_{2}$-QLDP, respectively, then the composited mechanism
$\mathcal{E}_{1}\otimes\mathcal{E}_{2}$ is
$(\varepsilon_{1}+\varepsilon_{2})$-QLDP.

###### Corollary 4

If quantum mechanisms $\mathcal{E}_{k}$ is $\varepsilon_{k}$-QLDP for $0\leq
k\leq t-1$, then
$\mathcal{E}_{0}\otimes\mathcal{E}_{1}\otimes\cdots\otimes\mathcal{E}_{t-1}$
is $(\sum_{k}\varepsilon_{k})$-QLDP.

##  8 Experimental Evaluation

In this section, we conduct numerical experiments on three aspects to
demonstrate the efficacy of depolarizing noise in our QLDP framework.

  1. 1.

_Utility Optimization:_ In comparison to different (non-unital) general
amplitude damping noise mechanisms, we establish the optimization of fidelity
(anti-trace distance) utility across varying QLDP values.

  2. 2.

_Trade-off:_ By adjusting the noiseless probability $p$ to attain the targeted
QLDP value and depolarizing utility, we can observe the trade-off between
these two aspects.

  3. 3.

_Qubit Number:_ As we scale up the number of qubits in quantum systems, we
notice a significant exponential decline in fidelity utility for a specific
QLDP value.

It is important to mention that since the fidelity and anti-trace distance
utilities of depolarizing channels are equal, we will focus solely on the
fidelity utility in the upcoming experiments.

###  8.1 Utility Optimization

We have demonstrated the optimization of the fidelity and anti-trace distance
utilities with depolarizing noise within unital quantum mechanisms in Theorem
6.3. The next question to address is whether the effectiveness of the
depolarizing noise mechanism surpasses that of non-unital quantum mechanisms,
such as generalized amplitude damping noises, in this context. To explore
this, we compare the fidelity utilities of 1-qubit depolarizing noise and
generalized amplitude damping noise mechanisms by varying their QLDP values.
By utilizing Eqs.(5) and (6), we are able to graph the fidelity utility
function using the QLDP value as the variable for 1-qubit depolarizing noise
and various generalized amplitude damping noise types characterized by
parameter $q$. Refer to Fig. 2 for a visual comparison. It is evident that the
utility derived from depolarizing noise surpasses that of any generalized
amplitude damping noise at any given QLDP value. This observation underscores
the effectiveness of depolarizing noise in safeguarding quantum state
information.

Figure 2: The compared fidelity utility of depolarizing and generalization
amplitude damping noise mechanisms with various parameter $q$.

###  8.2 Trade-off

Lemma 4 showcases how adjusting the probability $p$ can lead to varying levels
of the QLDP and fidelity utility for any $n$-qubit depolarizing noise. Theorem
6.3 establishes a trade-off between fidelity utility and QLDP values. By
leveraging these observations, we investigate the trade-off concerning
$n$-qubit depolarizing noise for values of $n$ from 1 to 5. The results are
depicted in Fig. 3.

Figure 3: The trade-off between fidelity utility and QLDP of $n$-qubit
depolarizing quantum noise mechanism

###  8.3 Qubit Number

As indicated by Theorem 6.3, the fidelity utility of depolarizing noise
diminishes exponentially as the number of qubits increases for a specified
QLDP value $\varepsilon$. This trend is visually represented in Fig. 4 for
$\varepsilon=0,1,2,3,4$. It is apparent that applying depolarizing noise to a
small number (2-4) of qubits is sufficient to maintain high utility for
practical applications and achieve the desired QLDP value.

Figure 4: Fidelity utility decreasing with the number of qubits in
depolarizing noise mechanisms

##  9 Conclusion

In this paper, we introduce the exploration of local differential privacy in
quantum computing from an algorithmic perspective. Initially, we demonstrate
the feasibility of utilizing quantum noise mechanisms to uphold quantum local
differential privacy (QLDP). Subsequently, we establish that the depolarizing
noise mechanism, which acts as a quantum counterpart to the classical
randomized response mechanism, stands out as the optimal choice for maximizing
both fidelity and trace distance utility among all unital quantum mechanisms
with a constant QLDP value. Additionally, we introduce a composition theorem
for entangled quantum systems, ensuring the effectiveness of local
differential privacy strategies in the context of distributed quantum
computing environments.

For future research directions, it would be intriguing to address the
optimization challenges posed by non-unital quantum mechanisms. Moreover,
investigating QLDP within a local framework that allows global measurements to
observe the state across multiple quantum subsystems presents an interesting
avenue. This prompts the question of whether a composition theorem holds in
such scenarios. Another promising research avenue involves examining the
implications of enabling multiple rounds of attacks involving entanglements,
as opposed to the single-round attacks considered in this study under the
framework of LOCC. Multiple rounds of attacks could potentially lead to
increased privacy leakage, necessitating a comprehensive exploration of
defense strategies to safeguard quantum local differential privacy in this
more intricate setting.

## References

  * [1] Michael A Nielsen and Isaac L Chuang.  Quantum computation and quantum information.  Cambridge university press, 2010.
  * [2] Lov K Grover.  A fast quantum mechanical algorithm for database search.  In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996.
  * [3] Peter W Shor.  Algorithms for quantum computation: discrete logarithms and factoring.  In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. Ieee, 1994.
  * [4] Aram W Harrow, Avinatan Hassidim, and Seth Lloyd.  Quantum algorithm for linear systems of equations.  Physical review letters, 103(15):150502, 2009.
  * [5] Roman Orus, Samuel Mugel, and Enrique Lizaso.  Quantum computing for finance: Overview and prospects.  Reviews in Physics, 4:100028, 2019.
  * [6] Pei-Hua Wang, Jen-Hao Chen, Yu-Yuan Yang, Chien Lee, and Yufeng Jane Tseng.  Recent advances in quantum computing for drug discovery and development.  IEEE Nanotechnology Magazine, 2023.
  * [7] Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd.  Quantum machine learning.  Nature, 549(7671):195–202, 2017.
  * [8] Charles H Bennett and Gilles Brassard.  Quantum cryptography: Public key distribution and coin tossing.  Theoretical computer science, 560:7–11, 2014.
  * [9] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, David A Buell, et al.  Quantum supremacy using a programmable superconducting processor.  Nature, 574(7779):505–510, 2019.
  * [10] Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, et al.  Quantum computational advantage using photons.  Science, 370(6523):1460–1463, 2020.
  * [11] Qingling Zhu, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, et al.  Quantum computational advantage via 60-qubit 24-cycle random circuit sampling.  Science bulletin, 67(3):240–245, 2022.
  * [12] Fabian Furrer, Torsten Franz, Mario Berta, Anthony Leverrier, Volkher B Scholz, Marco Tomamichel, and Reinhard F Werner.  Continuous variable quantum key distribution: finite-key analysis of composable security against coherent attacks.  Physical review letters, 109(10):100502, 2012.
  * [13] Hiroo Azuma.  An entangling-probe attack on shor’s algorithm for factorization.  Journal of Modern Optics, 65(4):415–422, 2018.
  * [14] Chuanqi Xu, Jessie Chen, Allen Mi, and Jakub Szefer.  Securing nisq quantum computer reset operations against higher energy state attacks.  In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pages 594–607, 2023.
  * [15] Chuanqi Xu, Ferhat Erata, and Jakub Szefer.  Exploration of power side-channel vulnerabilities in quantum computer controllers.  In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pages 579–593, 2023.
  * [16] Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014.
  * [17] Li Zhou and Mingsheng Ying.  Differential privacy in quantum computation.  In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 249–262. IEEE, 2017.
  * [18] Scott Aaronson and Guy N Rothblum.  Gentle measurement of quantum states and differential privacy.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 322–333, 2019.
  * [19] Christoph Hirche, Cambyse Rouzé, and Daniel Stilck Fran$\mathcal{C}$ca.  Quantum differential privacy: An information theory perspective.  IEEE Transactions on Information Theory, 69(9):5771–5787, 2023.
  * [20] Armando Angrisani, Mina Doosti, and Elham Kashefi.  A unifying framework for differentially private quantum algorithms.  arXiv preprint arXiv:2307.04733, 2023.
  * [21] Theshani Nuradha, Ziv Goldfeld, and Mark M Wilde.  Quantum pufferfish privacy: a flexible privacy framework for quantum systems.  arXiv preprint arXiv:2306.13054, 2023.
  * [22] Daniel Kifer and Ashwin Machanavajjhala.  Pufferfish: A framework for mathematical privacy definitions.  ACM Transactions on Database Systems (TODS), 39(1):1–36, 2014.
  * [23] Stanley L Warner.  Randomized response: A survey technique for eliminating evasive answer bias.  Journal of the American Statistical Association, 60(309):63–69, 1965.
  * [24] Daniel Kifer and Ashwin Machanavajjhala.  No free lunch in data privacy.  In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, pages 193–204, 2011.
  * [25] Ji Guan, Wang Fang, Mingyu Huang, and Mingsheng Ying.  Detecting violations of differential privacy for quantum algorithms.  In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pages 2277–2291, 2023.
  * [26] Armando Angrisani and Elham Kashefi.  Quantum local differential privacy and quantum statistical query model.  arXiv preprint arXiv:2203.03591, 2022.
  * [27] Theshani Nuradha and Mark M Wilde.  Contraction of private quantum channels and private quantum hypothesis testing.  arXiv preprint arXiv:2406.18651, 2024.
  * [28] Man-Duen Choi.  Completely positive linear maps on complex matrices.  Linear algebra and its applications, 10(3):285–290, 1975.
  * [29] Eric Chitambar, Debbie Leung, Laura Mančinska, Maris Ozols, and Andreas Winter.  Everything you always wanted to know about locc (but were afraid to ask).  Communications in Mathematical Physics, 328:303–326, 2014.
  * [30] Michael M Wolf.  Quantum channels & operations: Guided tour.  Lecture notes available at https://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/MichaelWolf/QChannelLecture.pdf, 2012.
  * [31] Christopher A Fuchs and Jeroen Van De Graaf.  Cryptographic distinguishability measures for quantum-mechanical states.  IEEE Transactions on Information Theory, 45(4):1216–1227, 1999.
  * [32] Peter Kairouz, Sewoong Oh, and Pramod Viswanath.  Extremal mechanisms for local differential privacy.  Journal of Machine Learning Research, 17(17):1–51, 2016.
  * [33] Leonid Gurvits.  Classical deterministic complexity of edmonds’ problem and quantum entanglement.  In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 10–19, 2003.
  * [34] Micha$\mathcal{L}$ Horodecki, Pawe$\mathcal{L}$ Horodecki, and Ryszard Horodecki.  Separability of n-particle mixed states: necessary and sufficient conditions in terms of linear maps.  Physics Letters A, 283(1-2):1–7, 2001.

## Appendices

###  9.1 Proof of Lemma 1

Proof. This directly follows the definitions of QLDP in Definition 1 and
classical LDP in Definition 2. $\Box$

###  9.2 Proof of Theorem 5.1

Proof. For any $\rho\not=\sigma\in\mathcal{D(H)}$, we can represent
$\rho-\sigma=\Delta_{+}-\Delta_{-}$ as a decomposition into orthogonal
positive and negative parts, where $\Delta_{\pm}>0$ and
$\Delta_{+}\Delta_{-}=0$. In the subsequent proof, we utilize the property
$0<{\rm tr}(\Delta_{+})={\rm tr}(\Delta_{-})\leq 1$ stemming from ${\rm
tr}(\rho-\sigma)=0$ and $\rho-\sigma=\Delta_{+}-\Delta_{-}$, and thus
$\frac{\Delta_{\pm}}{{\rm tr}(\Delta_{\pm})}$ are quantum states. The
following derivation is based on these:

$\aligned&{\rm
tr}[\mathcal{E}^{\dagger}(M_{\mathcal{S}})(\rho-e^{\varepsilon}\sigma)]\\\
={\rm
tr}[\mathcal{E}^{\dagger}(M_{\mathcal{S}})(\rho-\sigma+\sigma-e^{\varepsilon}\sigma)]\\\
={\rm
tr}[\mathcal{E}^{\dagger}(M_{\mathcal{S}})(\Delta_{+}-\Delta_{-}+\sigma-e^{\varepsilon}\sigma)]\\\
={\rm tr}(\mathcal{E}^{\dagger}(M_{\mathcal{S}})\Delta_{+})-{\rm
tr}(\mathcal{E}^{\dagger}(M_{\mathcal{S}})\Delta_{-})-(e^{\varepsilon}-1){\rm
tr}(\mathcal{E}^{\dagger}(M_{\mathcal{S}})\sigma)\\\ ={\rm
tr}(\Delta_{+})[{\rm
tr}(\mathcal{E}^{\dagger}(M_{\mathcal{S}})\frac{\Delta_{+}}{{\rm
tr}(\Delta_{+})})-{\rm
tr}(\mathcal{E}^{\dagger}(M_{\mathcal{S}})\frac{\Delta_{-}}{{\rm
tr}(\Delta_{-})})]-(e^{\varepsilon}-1){\rm
tr}(\mathcal{E}^{\dagger}(M_{\mathcal{S}})\sigma)\\\ \leq{\rm
tr}(\Delta_{+})[\max_{\rho_{1}\in\mathcal{D(H)}}{\rm
tr}(\mathcal{E}^{\dagger}(M_{\mathcal{S}})\rho_{1})-\min_{\rho_{2}\in\mathcal{D(H)}}{\rm
tr}(\mathcal{E}^{\dagger}(M_{\mathcal{S}})\rho_{2})]\\\
-(e^{\varepsilon}-1)\min_{\rho_{3}\in\mathcal{D(H)}}{\rm
tr}(\mathcal{E}^{\dagger}(M_{\mathcal{S}})\rho_{3})\\\ ={\rm
tr}(\Delta_{+})[\lambda_{\max}(\mathcal{E}^{\dagger}(M_{\mathcal{S}}))-\lambda_{\min}(\mathcal{E}^{\dagger}(M_{\mathcal{S}}))]-(e^{\varepsilon}-1)\lambda_{\min}(\mathcal{E}^{\dagger}(M_{\mathcal{S}}))\\\
\leq\lambda_{\max}(\mathcal{E}^{\dagger}(M_{\mathcal{S}}))-e^{\varepsilon}\lambda_{\min}(\mathcal{E}^{\dagger}(M_{\mathcal{S}}))\\\
=\bra{\psi^{*}}\mathcal{E}^{\dagger}(M_{\mathcal{S}})\ket{\psi^{*}}-e^{\varepsilon}\bra{\phi^{*}}\mathcal{E}^{\dagger}(M_{\mathcal{S}})\ket{\phi^{*}}\\\
={\rm
tr}[\mathcal{E}^{\dagger}(M_{\mathcal{S}})(\psi^{*}-e^{\varepsilon}\phi^{*})]$

Here, $\ket{\psi^{*}}$ and $\ket{\phi^{*}}$ are the normalized eigenvectors
(pure state) of $\mathcal{E}^{\dagger}(M_{\mathcal{S}})$ corresponding to the
maximal and minimal eigenvalues, respectively. Consequently, we have:

$\max_{\rho,\sigma\in\mathcal{D(H)}}{\rm
tr}[\mathcal{E}^{\dagger}(M_{\mathcal{S}})(\rho-e^{\varepsilon}\sigma)]=\lambda_{\max}(\mathcal{E}^{\dagger}(M_{\mathcal{S}}))-e^{\varepsilon}\lambda_{\min}(\mathcal{E}^{\dagger}(M_{\mathcal{S}}))$

This completes the proof based on the definition of QLDP provided in
Definition 1. $\Box$

###  9.3 Proof of Lemma 2

Proof. For any measurement $\mathcal{M}_{M}$ with matrices $\\{M,I-M\\}$

$\varepsilon^{*}(\mathcal{M}_{M}\circ\mathcal{E})=\max_{A\in\\{I,M,I-M\\}}\ln\frac{\lambda_{\max}[\mathcal{E}^{\dagger}(A)]}{\lambda_{\min}[\mathcal{E}^{\dagger}(A)]}$

Noting that $\\{I,M,I-M\\}\subseteq\\{M:0\leq M\leq I\\}$, the set of all
quantum measurement matrices. Combining that
$\varepsilon^{*}(\mathcal{E})=\max_{0\leq M\leq
I}\varepsilon^{*}(\mathcal{M}_{M}\circ\mathcal{E}),$ we can complete the
proof. $\Box$

###  9.4 Proof of Theorem 5.2

Proof. By Lemma 2, $\mathcal{E}$ is $\varepsilon$-QLDP if and only if for any
measurement matrix $M$,

$0\geq\lambda_{\max}(\mathcal{E}^{\dagger}(M))-e^{\varepsilon}\lambda_{\min}(\mathcal{E}^{\dagger}(M)).$

With the eigendecomposition of $M=\sum_{k}\lambda_{k}\psi_{k}$ and eigenvalues
$\lambda_{k}\geq 0$, we have

$0\geq\lambda_{\max}(\mathcal{E}^{\dagger}(\sum_{k}\lambda_{k}\psi_{k}))-e^{\varepsilon}\lambda_{\min}(\mathcal{E}^{\dagger}(\sum_{k}\lambda_{k}\psi_{k})).$

By the linearity of $\mathcal{E}$, we have

$0\geq\lambda_{\max}[\sum_{k}\lambda_{k}\mathcal{E}^{\dagger}(\psi_{k})]-e^{\varepsilon}\lambda_{\min}[\sum_{k}\lambda_{k}\mathcal{E}^{\dagger}(\psi_{k})].$

Noting the linear algebra fact that for any positive semi-definite matrices
$A$ and $B$,

$\aligned&\lambda_{\max}(A+B)\leq\lambda_{\max}(A)+\lambda_{\max}(B)\\\
\lambda_{\min}(A+B)\geq\lambda_{\min}(A)+\lambda_{\min}(B).$

Applying these to the summation
$\sum_{k}\lambda_{k}\mathcal{E}^{\dagger}(\psi_{k})$ of positive semi-definite
matrices $\mathcal{E}^{\dagger}(\psi_{k})$, we obtain

$\aligned&\lambda_{\max}[\sum_{k}\lambda_{k}\mathcal{E}^{\dagger}(\psi_{k})]-e^{\varepsilon}\lambda_{\min}[\sum_{k}\lambda_{k}\mathcal{E}^{\dagger}(\psi_{k})]\\\
\leq\sum_{k}\lambda_{k}[\lambda_{\max}(\mathcal{E}^{\dagger}(\psi_{k}))-e^{\varepsilon}\lambda_{\min}(\mathcal{E}^{\dagger}(\psi_{k}))]\\\
\leq(\sum_{j}\lambda_{j})\max_{k}[\lambda_{\max}(\mathcal{E}^{\dagger}(\psi_{k}))-e^{\varepsilon}\lambda_{\min}(\mathcal{E}^{\dagger}(\psi_{k}))].$

Therefore, by noting that each $\psi_{k}$ is also a measurement matrix, we can
claim that

$0\geq\lambda_{\max}(\mathcal{E}^{\dagger}(M))-e^{\varepsilon}\lambda_{\min}(\mathcal{E}^{\dagger}(M))\quad\forall
0\leq M\leq I.$

if and only if

$0\geq\lambda_{\max}(\mathcal{E}^{\dagger}(\psi))-e^{\varepsilon}\lambda_{\min}(\mathcal{E}^{\dagger}(\psi))\quad\forall\ket{\psi}\in\mathcal{H}.$

This completes the proof and we have

$\varepsilon^{*}(\mathcal{E})=\max_{\ket{\psi}\in\mathcal{H}}\ln\frac{\lambda_{\max}(\mathcal{E}^{\dagger}(\psi))}{\lambda_{\min}(\mathcal{E}^{\dagger}(\psi))}.$

$\Box$

###  9.5 Poof of Theorem 5.3

Proof. We first note that if $M$ is a quantum measurement matrix, then
$\mathcal{N}^{\dagger}(M)$ is also a quantum measurement matrix. Furthermore,
it follows that $\\{\mathcal{N}^{\dagger}(M):0<M\leq I\\}\subseteq\\{M:0<M\leq
I\\}$, thus concluding the proof based on Lemma 2. $\Box$

###  9.6 Proof of Lemma 3

Proof. We first prove that $\varepsilon^{*}(\mathcal{E})<\infty$ if and only
the first condition is satisfied.

Initially, according to Theorem 5.2, it is evident that
$\varepsilon^{*}(\mathcal{E})<\infty$ if and only if
$\lambda_{\min}(\mathcal{E}^{\dagger}(\psi))>0$ for any
$\ket{\psi}\in\mathcal{H}$. This condition is equivalent to stating that
$\mathcal{E}^{\dagger}(\psi)>0$ holds true for any $\ket{\psi}\in\mathcal{H}$
based on the eigendecomposition of $\mathcal{E}^{\dagger}(\psi)$ with
$\lambda_{\min}(\mathcal{E}^{\dagger}(\psi))$ being the minimum eigenvalue.
Considering the linearity of $\mathcal{E}^{\dagger}$, the condition
$\mathcal{E}^{\dagger}(\psi)>0$ for any $\ket{\psi}\in\mathcal{H}$ is
equivalent to $\mathcal{E}^{\dagger}(\rho)>0$ for all $\rho\in\mathcal{D(H)}$.
Such an $\mathcal{E}^{\dagger}$ is specifically referred to as strictly
positive, which can be validated by examining whether the _Choi-Jamiolkowski
matrix_
$\mathcal{E}^{\dagger}\otimes\mathcal{I}(|\Omega\rangle\langle\Omega|)$ of
$\mathcal{E}^{\dagger}$ is strictly positive, i.e.,
$\mathcal{E}^{\dagger}\otimes\mathcal{I}(|\Omega\rangle\langle\Omega|)>0$, as
detailed in [30, Theorem 6.8].

For a quantum mechanism $\mathcal{E}$ with Kraus matrices
$\\{E_{k}\\}_{k=0}^{K-1}$, the computation of
$\mathcal{E}^{\dagger}\otimes\mathcal{I}(|\Omega\rangle\langle\Omega|)$
requires $\mathcal{O}(N^{6}K)$ operations, as shown below:

$\mathcal{E}^{\dagger}\otimes\mathcal{I}(|\Omega\rangle\langle\Omega|)=\sum_{k=0}^{K-1}(E_{k}^{\dagger}\otimes
I)|\Omega\rangle\langle\Omega|(E_{k}\otimes I).$

The complexity arises from the fact that there are $K$ summations and each of
these involves two $N^{2}$-by-$N^{2}$ matrix multiplications with a
computation cost of $\mathcal{O}(N^{6}K)$. Consequently, verifying if
$\mathcal{E}^{\dagger}\otimes\mathcal{I}(|\Omega\rangle\langle\Omega|)>0$ can
be achieved by computing its eigenvalues, incurring a computational cost of
$\mathcal{O}(N^{6})$. Thus the total complexity is $\mathcal{O}(N^{8}).$

We proceed to demonstrate the equivalence of the two conditions. Initially, we
observe that
$\mathcal{E}^{\dagger}\otimes\mathcal{I}(|\Omega\rangle\langle\Omega|)>0$ is
the same as stating that the set formed by $\\{(E_{k}^{\dagger}\otimes
I)\ket{\Omega}\\}$ spans the entire vector space
$\mathcal{H}\otimes\mathcal{H}$. This equivalence arises from the fact that
the mapping $E\rightarrow(E\otimes I)\ket{\Omega}$ establishes a linear one-
to-one relationship between the matrix space in $\mathcal{H}$ and vector space
$\mathcal{H}\otimes\mathcal{H}$. Addressing the issue of complexity to check
the second condition, this leads to determining the rank $r$ of the linear
space generated by $\\{E_{k}\\}_{k=0}^{K-1}$, achievable in
$\mathcal{O}(N^{6}K)$. Consequently, $r=N^{2}$ holds if and only if the second
condition is met. $\Box$

###  9.7 Proof of Theorem 5.4

Proof. According to Corollary 3, we can verify the instances where quantum
noises do not result in a finite QLDP value as claimed. We only need to
calculate $\varepsilon^{*}(\mathcal{N}_{\text{Dep}})$ for $0\leq p<1$ and
$\varepsilon^{*}(\mathcal{N}_{\text{GAD}})$ for $0<q<1$ and $0<r\leq 1$ in the
following.

Recall that for any state $\ket{\psi}$, the following relation holds:

$\mathcal{N}_{\text{Dep}}(\psi)=p\psi+(1-p)\frac{I}{2}.$

It can be observed that $\ket{\psi}$ and $\ket{\psi^{\bot}}$ represent the
normalized eigenvectors associated with eigenvalues $(1+p)/2$ and $(1-p)/2$,
respectively. Here, $\ket{\psi^{\bot}}$ represent a quantum state orthogonally
to $\ket{\psi}$, i.e., $\braket{\psi}{\psi^{\bot}}=0$. Consequently, for
$0\leq p<1$, we derive
$\varepsilon^{*}(\mathcal{N}_{\text{Dep}})=\ln\frac{1+p}{1-p}$ based on
Theorem 5.2.

To determine $\varepsilon^{*}(\mathcal{N}_{\text{GAD}})$, according to
Corollary 1, our task involves solving the optimization problem
$\max_{\psi}\lambda_{\max}(\mathcal{N}^{\dagger}_{\text{GAD}}(\psi))$.
Initially, we represent a 1-qubit state $\ket{\psi}$ with two parameters $a$
and $b$ as

$\ket{\psi}=\bmatrix a\\\ b\text{suchthat}aa^{*}+bb^{*}=1.$

To find the eigenvalues of $\mathcal{N}^{\dagger}_{\text{GAD}}(\psi)$, we
start by computing the characteristic polynomial $\text{det}[\lambda
I-\mathcal{N}^{\dagger}_{\text{GAD}}(\psi)]$ and obtain

$\text{det}[\lambda
I-\mathcal{N}^{\dagger}_{\text{GAD}}(\psi)]=\lambda^{2}-\lambda+r(1-r)(aa^{*})^{2}-2(1-r)rp(aa^{*})^{2}+rp-r^{2}p^{2}.$

We introduce $x=aa^{*}$, leading to

$\text{det}[\lambda
I-\mathcal{N}^{\dagger}_{\text{GAD}}(\psi)]=\lambda^{2}-\lambda+r(1-r)x^{2}-2(1-r)rpx^{2}+rp-r^{2}p^{2}.$

By solving $\text{det}[\lambda I-\mathcal{N}^{\dagger}_{\text{GAD}}(\psi)]=0$,
we find the maximum eigenvalue as

$\lambda_{\max}[\mathcal{N}^{\dagger}_{\text{GAD}}(\psi)]=\frac{1+\sqrt{1-4[r(1-r)x^{2}-2(1-r)rpx+rp-r^{2}p^{2}]}}{2}.$

The value of
$\max_{\psi}\lambda_{\max}[\mathcal{N}^{\dagger}_{\text{GAD}}(\psi)]$ is
achieved at $x=p$, resulting in the optimal value

$\frac{1+\sqrt{1-4rp+4rp^{2}}}{2}.$

Hence, in accordance with Corollary 1, we conclude that

$\varepsilon^{*}(\mathcal{N}_{\text{GAD}})=\ln\left(\frac{1+\sqrt{1-4rq+4rq^{2}}}{1-\sqrt{1-4rq+4rq^{2}}}\right).$

$\Box$

###  9.8 Proof of Theorem 6.1

Proof. First, we deal with $\mathcal{N}_{\text}{XF},\mathcal{N}_{\text}{YF}$
and $\mathcal{N}_{\text}{ZF}$. They share the following same structure for
their corresponding to super-operators:

$\mathcal{N}_{\text}{UF}(\rho)=p\rho+(1-p)U\rho U^{\dagger}.$

Then, the fidelity utility is

$F(\mathcal{N}_{\text}{UF})=p+\min_{\ket{\psi}\in\mathcal{H}}|\bra{\psi}U\ket{\psi}|^{2}.$

$\bra{\psi}U\ket{\psi}=0$ can be obtained by $\ket{\psi}=\ket{0}$ for $U=X$,
$\ket{\psi}=\ket{0}$ for $U=Y$, and
$\ket{\psi}=\frac{\ket{0}+\ket{1}}{\sqrt{2}}$ for $U=Z$. Thus
$F(\mathcal{N}_{\text}{UF})=p$ for $U\in\\{X,Y,Z\\}$. The anti-trace distance
utility is

$T(\mathcal{N}_{\text}{UF})=(1-p)\max_{\ket{\psi}\in\mathcal{H}}\frac{1}{2}{\rm
tr}(|U\psi U-\psi|)$

$\frac{1}{2}{\rm tr}(|U\psi U-\psi|)=1$ can be obtained by
$\ket{\psi}=\ket{0}$ for $U=X$,$\ket{\psi}=\ket{0}$ for $U=Y$, and
$\ket{\psi}=\frac{\ket{0}+\ket{1}}{\sqrt{2}}$ for $U=Z$. Therefore,
$\hat{T}(\mathcal{N}_{UF})=p$ for $U\in\\{X,Y,Z\\}$.

Now we consider the utilities of depolarizing noise. Recall one form of the
noise is

$\mathcal{N}_{\text{Dep}}(\rho)=p\rho+(1-p)\frac{I}{2}.$

Then

$F(\mathcal{N}_{\text{Dep}})=\frac{1+p}{2}$
$T(\mathcal{N}_{\text{Dep}})=\frac{1-p}{2}\Rightarrow\hat{T}(\mathcal{N}_{\text{Dep}})=\frac{1+p}{2}.$

Now we move to deal with damping noise mechanisms by parameterizing pure state
$\ket{\psi}$.

Any 1-qubit $\ket{\psi}$ can be represented by two parameters $a,b$ as

$\ket{\psi}=\bmatrix a\\\ b\text{with}aa^{*}+bb^{*}=1.$

Then we compute fidelity and anti-trace distance utilities by searching on
such $a$ and $b$.

$\psi=|\psi\rangle\langle\psi|=\bmatrix aa^{*}&ab^{*}\\\ a^{*}bbb^{*}.$

For phase damping $\mathcal{N}_{\text}{PD}$,

$\mathcal{N}_{\text}{PD}(\psi)=\bmatrix aa^{*}&\sqrt{1-r}ab^{*}\\\
\sqrt{1-r}a^{*}bbb^{*}.$

Then we have the eigenvalues of $\mathcal{N}_{\text}{PD}(\psi)-\psi$ are:

$\lambda[\mathcal{N}_{\text}{PD}(\psi)-\psi]=\pm\sqrt{(1-\sqrt{1-r})^{2}aa^{*}bb^{*}}$

By $aa^{*}+bb^{*}=1$, we have the maximal value of
$\sqrt{(1-\sqrt{1-r})^{2}aa^{*}bb^{*}}$ is $\frac{1-\sqrt{1-r}}{2}$ for
$aa^{*}=\frac{1}{2}$. Thus $\hat{T}(\mathcal{N})=\frac{1+\sqrt{1-r}}{2}$.

On the other hand, $F(\mathcal{N}_{\text}{PD}(\psi),\psi)$ is

$\bra{\psi}\mathcal{N}_{\text}{PD}(\psi)\ket{\psi}=(aa^{*})^{2}+2\sqrt{1-r}aa^{*}bb^{*}+(bb^{*})^{2}.$

Let $x=aa^{*}$ with $0\leq x\leq 1$ and then $bb^{*}=1-x$ as
$\braket{\psi}{\psi}=aa^{*}+bb^{*}=1$. Then the above equation is

$F(\mathcal{N}_{\text}{PD}(\psi),\psi)=2(1-\sqrt{1-r})x^{2}-2(1-\sqrt{1-r})x+1.$

Therefore, the minimal value of fidelity
$F(\mathcal{N}_{\text}{PD}(\psi),\psi)$ is achieved at $x=\frac{1}{2}$ and
thus the utility fidelity is
$F(\mathcal{N}_{\text}{PD})=\frac{1+\sqrt{1-r}}{2}$.

For $\mathcal{N}_{\text{GAD}}$,

$\mathcal{N}_{\text{GAD}}(\psi)=\bmatrix{(1-r)aa^{*}+rq}&\sqrt{1-r}ab^{*}\\\
\sqrt{1-r}a^{*}braa^{*}+bb^{*}-rq.$

Then we have the eigenvalues of $\mathcal{N}_{\text{GAD}}(\psi)-\psi$ are:

$\lambda[\mathcal{N}_{\text{GAD}}(\psi)-\psi]=\pm\sqrt{(rq-
raa^{*})^{2}+(\sqrt{1-r}-1)^{2}aa^{*}bb^{*}}$

Let $x=aa^{*}$ with $0\leq x\leq 1$ and then $bb^{*}=1-x$ as
$\braket{\psi}{\psi}=aa^{*}+bb^{*}=1$. Then the magnitude of
$\lambda[\mathcal{N}_{\text{GAD}}(\psi)-\psi]$ is

$\sqrt{(r^{2}+2-2\sqrt{1-r}-r)x^{2}-(2qr^{2}+2-2\sqrt{1-r}-r)x+r^{2}q^{2}}$

As $(r^{2}+2-2\sqrt{1-r}-r)\geq 0$, the maximal value of the above equation is
achieved at $x=0$ or 1.

$\aligned&\text{For}x=1,|\lambda[\mathcal{N}_{\text{GAD}}(\psi)-\psi]|=(1-q)r\\\
\text{For}x=0,|\lambda[\mathcal{N}_{\text{GAD}}(\psi)-\psi]|=qr.$

Thus

$T(\mathcal{N}_{\text{GAD}})=\left\\{\aligned&qr\text{if}q\geq\frac{1}{2}\\\
(1-q)r\text{if}q<\frac{1}{2}\right.$

Then

$\hat{T}(\mathcal{N}_{\text{GAD}})=\left\\{\aligned&1-qr\text{if}q\geq\frac{1}{2}\\\
1-(1-q)r\text{if}q<\frac{1}{2}\right.$

On the other hand,
$F(\mathcal{N}_{\text}{GAD}(\psi),\psi)=\bra{\psi}\mathcal{N}_{\text}{GAD}(\psi)\ket{\psi}$
is

$(1-r)(aa^{*})^{2}+rqaa^{*}+(2\sqrt{1-r}+r)aa^{*}bb^{*}+(bb^{*})^{2}-rqbb^{*}.$

Let $x=aa^{*}$ with $0\leq x\leq 1$ and then $bb^{*}=1-x$ as
$\braket{\psi}{\psi}=aa^{*}+bb^{*}=1$. Then the above equation is

$2(1-r-\sqrt{1-r})x^{2}+(2rq+r+2\sqrt{1-r}-2)x+1-rq.$

Therefore, the minimal value of fidelity
$F(\mathcal{N}_{\text}{GAD}(\psi),\psi)$ is achieved at $x=0$ or 1 and thus
the utility fidelity is

$F(\mathcal{N}_{\text{GAD}})=\left\\{\aligned&1-qr\text{if}q\geq\frac{1}{2}\\\
1-(1-q)r\text{if}q<\frac{1}{2}.\right.$

$\Box$

###  9.9 Proof of Theorem 6.2

Proof. Let $D$ be the dimension of the state space $\mathcal{H}$ which
$\mathcal{N}$ is working on. Then, by Theorem 5.2, we have

$\aligned&e^{\varepsilon^{*}(\mathcal{N})}\\\
=\max_{\ket{\psi}}\frac{\lambda_{\max}(\mathcal{N}^{\dagger}(\psi))}{\lambda_{\min}(\mathcal{N}^{\dagger}(\psi))}\\\
\geq\max_{\ket{\psi}}\frac{(D-1)\lambda_{\max}(\mathcal{N}^{\dagger}(\psi))}{1-\lambda_{\max}(\mathcal{N}^{\dagger}(\psi))}\\\
=\max_{\ket{\psi}}(D-1)(\frac{1}{1-\lambda_{\max}(\mathcal{N}^{\dagger}(\psi))}-1)\\\
\geq\max_{\ket{\psi}}(D-1)(\frac{1}{1-\bra{\psi}\mathcal{N}^{\dagger}(\psi)\ket{\psi}}-1)\\\
=(D-1)(\frac{1}{1-\max_{\psi}\bra{\psi}\mathcal{N}^{\dagger}(\psi)\ket{\psi}}-1)\\\
\geq(D-1)(\frac{1}{1-F(\mathcal{N})}-1).$

Then we have the inequality for fidelity utility for $D=2^{n}$:

$F(\mathcal{N})\leq\frac{e^{\varepsilon^{*}(\mathcal{N})}}{e^{\varepsilon^{*}(\mathcal{N})}+2^{n}-1}.$

In the above, the first inequality results from that for any $D$-by-$D$
positive semi-definite matrix $M$ with ${\rm tr}(M)=1$ (eigenvalues of $M$ are
all non-negative and the summation of them is 1), we have

$\lambda_{\min}(M)\leq\frac{1-\lambda_{\max}(M)}{D-1}.$

The second inequality comes from

$\lambda_{\max}(\mathcal{N}^{\dagger}(\psi))=\max_{\phi}\bra{\phi}\mathcal{N}^{\dagger}(\psi)\ket{\phi}.$

The third inequality results from

$F(\mathcal{N})=F(\mathcal{N}^{\dagger})=\min_{\psi}\bra{\psi}\mathcal{N}^{\dagger}(\psi)\ket{\psi}\leq\max_{\psi}\bra{\psi}\mathcal{N}^{\dagger}(\psi)\ket{\psi}$

And we observe that the above two equalities are obtained if and only if

$\mathcal{N}^{\dagger}(\psi)=\eta_{0}{\psi}+\sum_{1\leq k\leq
D-1}\eta_{k}{\psi_{k}}\qquad\forall\ket{\psi}\in\mathcal{H}$

where the set
$\\{\ket{\psi},\ket{\psi_{1}},\ket{\psi_{2}},\ldots,\ket{\psi_{D-1}}\\}$ of
pure state are mutually orthogonal and
$\eta_{0}\geq\eta_{1}=\eta_{2}=\cdots=\eta_{D-1}.$ That is

$\mathcal{N}^{\dagger}_{\eta}(\psi)=\eta{\psi}+\frac{1-\eta}{D-1}(I-{\psi}).$

where $\eta\geq\frac{1}{D}$ is a constant and independent on $\psi$.

Furthermore, by noting that $\mathcal{T}(\mathcal{N})\geq
1-\mathcal{F}(\mathcal{N})$, we can get the second inequality for anti-trace
distance fidelity. $\Box$

###  9.10 Proof of Lemma 4

Proof. This can be accomplished directly using Theorem 5.2 and the definitions
of fidelity and anti-trace distance utilities, similar to how we handle
1-qubit depolarizing noise previously. $\Box$

###  9.11 Proof of Theorem 6.3

Proof. It directly follows from Theorem 6.2 and Lemma 4. $\Box$

###  9.12 Proof of Theorem 7.1

Proof. By Theorem 5.2,

$\varepsilon^{*}(\mathcal{E}_{1}\otimes\mathcal{E}_{2})=\max_{\ket{\psi}\in\mathcal{H}_{1}\otimes\mathcal{H}_{2}}\ln\frac{\lambda_{\max}[\mathcal{E}_{1}^{\dagger}\otimes\mathcal{E}_{2}^{\dagger}(\psi)]}{\lambda_{\min}[\mathcal{E}_{1}^{\dagger}\otimes\mathcal{E}_{2}^{\dagger}(\psi)]}.$

Note that by the proof of Theorem 5.2, $\psi$ is a product measurement as we
only consider the joint measurement. Let
$\ket{\psi}=\ket{\psi_{1}}\otimes\ket{\psi_{2}}$. Then we have

$\varepsilon^{*}(\mathcal{E}_{1}\otimes\mathcal{E}_{2})=\ln\max_{\ket{\psi_{1}}\in\mathcal{H}_{1}}\frac{\lambda_{\max}[\mathcal{E}_{1}^{\dagger}(\psi_{1})]}{\lambda_{\min}[\mathcal{E}_{1}^{\dagger}(\psi_{1})]}\max_{\ket{\psi_{2}}\in\mathcal{H}_{2}}\frac{\lambda_{\max}[\mathcal{E}_{2}^{\dagger}(\psi_{2})]}{\lambda_{\min}[\mathcal{E}_{2}^{\dagger}(\psi_{2})]}=\varepsilon^{*}(\mathcal{E}_{1})+\varepsilon^{*}(\mathcal{E}_{2}).$

$\Box$