# PO-QA: A Framework for Portfolio Optimization using Quantum Algorithms

Kamila Zaman1,2, Alberto Marchisio1,2, Muhammad Kashif1,2, and Muhammad
Shafique1,2 1eBrain Lab, Division of Engineering, New York University Abu
Dhabi, UAE
2Center for Quantum and Topological Systems (CQTS), NYUAD Research Institute,
New York University Abu Dhabi, UAE
(e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Portfolio Optimization (PO) is a financial problem aiming to maximize the net
gains while minimizing the risks in a given investment portfolio. The novelty
of Quantum algorithms lies in their acclaimed potential and capability to
solve complex problems given the underlying Quantum Computing (QC)
infrastructure. Utilizing QC’s applicable strengths to the finance industry’s
problems, such as PO, allows us to solve these problems using quantum-based
algorithms such as Variational Quantum Eigensolver (VQE) and Quantum
Approximate Optimization Algorithm (QAOA). While the Quantum potential for
finance is highly impactful, the architecture and composition of the quantum
circuits have not yet been properly defined as robust financial
frameworks/algorithms as state of the art in present literature for research
and design development purposes. In this work, we propose a novel scalable
framework, denoted PO-QA, to systematically investigate the variation of
quantum parameters (such as rotation blocks, repetitions, and entanglement
types) to observe their subtle effect on the overall performance. In our
paper, the performance is measured and dictated by convergence to similar
ground-state energy values for resultant optimal solutions by each algorithm
variation set for QAOA and VQE to the exact eigensolver (classical solution).
Our results provide effective insights into comprehending PO from the lens of
Quantum Machine Learning in terms of convergence to the classical solution,
which is used as a benchmark. This study paves the way for identifying
efficient configurations of quantum circuits for solving PO and unveiling
their inherent inter-relationships.

##  I Introduction and Motivation

As a fundamental task in the financial field, Portfolio Optimization (PO) [1]
aims at finding optimal trades, given a budget and a set of assets, for
minimizing the risk while maximizing the return. According to the Modern
Portfolio Theory (MPT) [2], an optimal portfolio profile that balances risks
and rewards usually requires high degrees of diversification (i.e.,
investments in multiple and heterogeneous assets). Solving PO problems with
diversified portfolio profiles requires extensive use of quantitative
analysis, which dramatically increases the complexity of the system.

The recent advancements and computational capabilities of the current Noise
Intermediate-Scale Quantum (NISQ) devices [3, 4], have shown that PO problems
can be efficiently solved in the quantum domain using quantum computers [5, 6,
7]. To implement PO on NISQ devices, we need to process the financial market
data using quadratic programming [8] and solve the equivalent problem of
minimizing the ground state energy of the Hamiltonian [9]. Among different
optimization algorithms for PO, frequently used state-of-the-art quantum
algorithms are VQE [10] and QAOA [11]. However, designing efficient
architectures for the VQE and QAOA quantum circuits remains an open research
problem.

###  I-A Motivational Case Study

To tackle this problem, we conduct a motivational case study, in which we
analyze ground state energy values of different architectural configurations
of VQE and QAOA, compared to the classical solution, for low (0.1), middle
(0.5), and high (0.9) values of risk factor. The implementation details are
discussed in Section IV-A. As shown in Fig. 1, some observations can be
derived.

Figure 1: Analysis of ground state energy for different quantum circuit
configurations and risk factors, solved using the classical solution, VQE, and
QAOA. (1) As indicated by dashed line arrows, the VQE demonstrates very high
convergence variability to classical benchmark with testing for mid-level risk
margin (risk = 0.5), indicating high response to changes induced in the
circuit through our experiments across variations from B to M. The QAOA (solid
arrow line) exhibits drastically lesser variations across experiments (B to M)
for each respective risk value. (3) Comparing QAOA solutions (orange bar) with
the classical benchmark (blue bar) across varying experiments and increasing
risk, the QAOA is, in most cases, converging to a ground energy value either
exactly matching the classical one or closer to it than the VQE. (4) The
higher the risk, the higher the minimum ground state energy value
distribution. as shown in pointers a, b, and c.(5) Certain experiment
configurations, highlighted in boxes (B, C, D) in all three figures combined
suggest an anomaly in regards to VQE. For these configurations, the VQE
results change drastically across all variations, indicating an underlying
correlation with parameter values chosen for these configurations. The nature
of this correlation can only be evident once investigated further. Still, the
consistency of the value change makes it a useful case for a deep dive into
the circuit definition for given configurations within the VQE.

  * •

The VQE has higher sensitivity to a selected set of quantum parameters
(designed with experiment set B to M) than the QAOA, while converging toward
the classical benchmark (exact eigensolver solution), tested across three risk
values ranging from 0.1 to 0.9.

  * •

By observing the solid and dashed arrow lines in Fig. 1, we see an obvious
difference in variability for VQE and QAOA in all three risk value cases. Such
variability, which is observable by the changing direction of arrows, is
highest in the case of risk = 0.5 for VQE (dashed arrow lines). On the other
hand, the variability for QAOA (solid arrows) has the same pattern,
demonstrating consistency and low sensitivity against induced circuit
variations and risk values.

  * •

The VQE has significant variations across experiments from B to M for
different risk margin values. This observation gives us a base to justify a
deeper dive into the relationship between the selected quantum parameters and
the VQE algorithm to find valuable insights for utilizing the advantage of
quantum design for VQE.

  * •

The QAOA exhibits drastically lesser variation over experiments (B to M) for
each respective risk value. Additionally, the QAOA is always converging closer
or precisely to the classical benchmark solution across experiment variations
(B to M) and risk variations.

  * •

A holistic view of these three experiments shows that the higher the risk, the
higher the minimum ground state energy value distribution, indicated by
pointers a, b, and c. This behavior shows that risk values define the
landscape of the ground energy values to be minimized, showing a direct
relation between the two.

  * •

Highlighted with rectangles, it is observed that some experiment sets have a
drastic effect on the converged value for the VQEs. The three boxes in Fig. 1
highlight that the experiment sets B, C, and D, which in later sections will
be analyzed in more detail, are composed of some parameters or a certain
configuration applied to the VQE that cause a drastic variation from rest of
the solutions. This is another potential area of investigation to identify
what kind of intuitive or counter-intuitive correlations drive this behavior.

  * •

Across many experiments, configurations B, C, and D consistently have an
anomalistic behavior when tested with VQE. This makes it useful to investigate
further the reason for this dramatic change in value in context with the
configuration used.

###  I-B Novel Contributions

Motivated by the previous analysis, this work tackles the above-discussed
challenge by conducting a systematic study of efficient quantum circuit
architectures; see Fig. 2. We investigate 12 architectural configurations for
each optimization algorithm, varying rotation block, entanglement type, and
repetitions. In summary, our contributions are:

Figure 2: Overview of our PO-QA Framework. Given historical financial data,
quantum algorithms, and the classical PO reference, the framework performs a
quantum circuit parameter tuning and compares the quantum algorithms with the
classical reference.

  * •

PO-QA Framework Design: After a data preparation stage for quantum algorithms
(such as VQE and QAOA) using quadratic programming, our framework tunes the
quantum circuit parameters, namely rotation block, entanglement type, and
repetitions.

  * •

Classical vs. Quantum Comparison: For different risk values, the ground state
energy of the classical system has been compared with each quantum circuit
architecture. The classical solution is an exact eigensolver used to minimize
the ground-energy state landscape.

  * •

Key Takeaway: Our results revealed that the QAOA outperforms the VQE and that
interesting correlations between quantum circuit complexity, PO performance,
risk, and ground state energy values can be found.

##  II Related Work

The finance industry is a highly time-critical market, where even micro-
seconds can lead to huge gains or losses [12, 13]. The volatility of this
industry presents numerous challenges while seeking accurate and efficient
market predictions and optimization processes [14]. Complex optimization
problems form the basis for the potential applicability of high computing
infrastructure as an inevitable need for the finance industry. Currently, the
resource power and infrastructure are limited, causing hindrances in
developing methods for realistic and achievable solutions to problems like
large-scale PO. Since high-frequency and high-volume data are required to
analyze the markets, and numerous external factors drive the market direction,
there is a need to develop and adopt compute-intense infrastructures capable
of performing tasks beyond classical computers’ limitations. Given this
nature, financial problems grow exponentially large, making it impossible or
intractable for classical computing infrastructures to solve them within
useful time frames. The ability to actually make an impact and curate
processes for insightful decisions facilitated by machine learning tools and
their capabilities lies in the importance of looking beyond current
challenges. To lay the base for developing advanced financial predictions on
quantum infrastructures, a reasonably efficient direction to take is required
[15, 16]. For applicable use cases in the finance industry, encompassing all
the factors and variables within the classical computation system becomes an
intractable optimization problem. We need machines with greater computation
speed and information processing capacity to hold and process numerous factors
to produce a generalized result. In this regard, quantum computing methods and
infrastructures are considered disruptive technological advancements for the
financial industry, not only in long-term, but in use-cases for the near
short-term solutions and transformation as well within the NISQ era of quantum
computing [15].

Recent works have tackled financial problems in finance. The work of time
series forcasting [16] shows that Parametrized Quantum Circuits with simulated
quantum forward propagation perform well in the presence of high noise. The
work on financial forecasting via Quantum Machine Learning [17] matches the
classical performance with significantly fewer parameters. The works on
financial fraud detection using Quantum Graph Neural Networks (GNNs) [18] and
Quantum Federated Neural Networks (QFNNs) [19] outperform classical ML
methods. Moreover, a survey of quantum computing for finance [20] presents PO
implementations on real hardware using reverse quantum annealing and trapped
ion devices, while additionally implementing risk analysis on a transom
device. However, the configuration of VQE and QAOA’s quantum circuits is
unclear. In this work, we conduct a systematic analysis to identify efficient
quantum parameter configurations for PO.

##  III PO-QA Framework

Motivated by the previous analysis aimed at studying the effects of quantum
parameters tuning on algorithms for an image classification task [21], in this
paper, we focus the analysis on the quantum algorithms for PO. The PO-QA
framework builds a foundational base to use and understand quantum financial
problem solving, an obvious need for the industry with the momentum that
quantum technology has gained. Towards this, in this paper, we present a
framework for a systematic investigation of the quantum parameters for PO
problems.

As shown in Figure 3, our PO-QA framework is composed of:

Figure 3: Overview of our PO-QA framework’s functionality. The problem is
formulated through quadratic programming. The exact eignensolver, QAOA, and
VQE are used. The quantum circuit has been analyzed by varying the
entanglement block, block repetitions, rotation block, and entanglement
structure.

  1. 1.

Data Preparation: The financial market data collection required for the given
PO problem (and its given constraints, such as number of assets, budget, and
risk factor) needs to be converted into quadratic programs with linear
constraints for mathematical representation in the quantum system. To process
the PO problem, $\mu$ and $\sigma$ are the required inputs from the historical
financial data, where $\mu$ is the periodic mean-based expected return per
asset and $\sigma$ is the periodic covariance over every portfolio asset.

  2. 2.

Quantum Circuit Exploration: Limited variations for each parameter have been
selected for the initial development of the framework to restrict the
experiment volume to achievable counts. For both VQE and QAOA, these
parameters are the rotation blocks, i.e., quantum gates that specify the
qubit’s rotation axis. The gates rx and ry have been used as variations for
this parameter. The block repetitions and entanglement type, which comprises
both the block type and its structure (full, pairwise, or circular) are also
varied. The block type refers to the entanglement block, i.e., the gates used
in the entanglement layer. These can be specified just like rotation blocks.
Additionally, we also tweaked the entanglement structure with the following
variations:

     * •

full: It is an entanglement structure where each qubit is entangled with all
the others.

     * •

circular: In this case, it is linear entanglement but with an additional
entanglement of the first and last qubit before the linear part.

     * •

pair-wise: The case where each qubit is paired with one single qubit
exclusively.

The various quantum circuit architectures under investigation form the design
space.

  3. 3.

Quantum vs. Classical Comparison: The classical solution, implemented with
exact eigensolver, outputs the state-of-the-art prediction of the minimum
ground state energy of the system. Each quantum circuit architecture of VQE
and QAOA predicts the portfolio configuration with a certain ground state
energy value, which may or may not be the same as the classical prediction.
The comparisons between these values, for different risk factors, enable a
systematic evaluation of efficient quantum circuit architectures. Note that
the comparisons are made w.r.t. the ground state prediction obtained by the
classical system, which is considered the reference value. In this way, it is
possible to identify what parameters of the quantum circuit architectures are
suitable for solving this PO problem.

##  IV Evaluating our PO-QA Framework

###  IV-A Experimental Setup

In this work, we use historical financial data of 8 stock values from the
Wikipedia DataProvider interface provided by Qiskit, in a time period of 6
months from 1st July 2016 to 31st December 2016. The other experiment
specifications are reported in Table I.

TABLE I: Experiment Specifications.

Parameter Specification Software Framework `Qiskit(QK)` Algorithm `Exact
Solver(classical), VQE, QAOA` Rotation Block `ry, rx` Entanglement Block `cz,
cx` Entanglement Structure `full, pairwise, circular` Block Repetitions
(circuit depth) 3 and 5 Risk Factor `0.1`, `0.2`, `0.3`, `0.4`, `0.5`, `0.6`,
`0.7`, `0.8`, `0.9` Asset Count, Budget `8`, `assets/2` Assets `TSLA`, `AMZN`,
`GOOG`,`AAPL`, `FSLR`, `SPWR`, `ARRY`, `ENPH`

Figure 4: Variation of the predicted ground state energy level, for different
quantum circuit architecture configurations of VQE (green) and QAOA (orange)
solutions, w.r.t. the classical solutions (blue), varying the risk factor.
Here, the solid arrow line indicates QAOA variations across experiments and
risk, and the dashed arrows indicate VQE variability. Blue markers with label
a signify the resistance of QAOA to induced parameter tweaking (low
sensitivity, mostly the same pattern), but it also highlights that at blue
marker a, the configuration usually F and sometimes additionally G cause a
sudden increase in ground-state energy value. The consistency of this behavior
of QAOA with configuration F allows us to reason the correlation and
understand better the underlying cause to find useful insights. The pink label
a indicates that out of all experimental results for VQE, a risk margin of 0.5
causes most instabilities and variations across configurations (B to M). As
highlighted by blue marker b, for risk=0.7 and at similar places for results
of risk=0.1, risk=0.4, risk=0.8, and risk=0.9, we observe that the higher the
risk, the higher the minimum ground-state energy value is returned.

###  IV-B Results: Classical vs. Quantum Comparison

For each quantum algorithm (VQE and QAOA), 12 different quantum circuit
architecture variations (labeled with letters from B to M) are tested. Figures
4 and 5 show the comparison of each quantum circuit architecture variation,
for different values of the risk factor, ranging from 0.1 to 0.9 along with
the classical solution. Fig. 4 visualize the differences of the ground state
energy values among QAOA and VQE variations against the classical solution as
a benchmark, while Fig. 5 reports whether each quantum configuration matches
or converges to the classical solution in terms of minimum ground state energy
(i.e., predicted optimal portfolio).

Figure 5: Classical vs. Quantum comparison: for each risk factor, the table
reports whether the minimum ground state predicted by the QAOA and VQE systems
matches the prediction of the classical system. The green tick identifies a
matched case, while the red cross indicates that the resulting optimal
portfolio asset configuration differs from that of the classical solution.
Legend: B=(full, ry, cz, 3), C=(pairwise, ry, cz, 3), D=(circular, ry, cz, 3),
E=(full, ry, cz, 5), F=(pairwise, ry, cz, 5), G=(circular, ry, cz, 5),
H=(full, rx, cx, 3), I=(pairwise, rx, cx, 3), J=(circular, rx, cx, 3),
K=(full, rx, cx, 3), L=(pairwise, rx, cx, 3), M=(circular, rx, cx, 5).

From the results, we can observe that the QAOA is mostly insensitive to the
quantum circuit variations we have performed in the context of PO, whereas the
VQE demonstrates extremely high sensitivity towards indices variations. This
observation has been consistent throughout most experiments conducted with
various risk factors. Hence, it proves to be a valid ground for assuming a
deterministic relationship between the VQE and these parameters, causing
regular variations. A deep dive into uncovering this relationship can help us
discover insights into the design and working of the VQE. On the other hand,
the QAOA has low sensitivity. However, there are instances of repeated
behavior across similar experiments.

Overall, we can observe that the QAOA tends to perform better than the VQE
since more QAOA architectures match with the baseline classical optimal
portfolio as observable in Fig. 6. This can be due to the fact that the QAOA
is a more advanced algorithm built upon the principles of the VQE. The QAOA’s
additional constraints and improved problem construction show that this
algorithm finds the minimum energy easier than the VQE, since only the QAOA
with quantum circuit architecture F performs poorly. On the other hand, the
results of the VQE consistently vary based on the quantum circuit
architecture. For instance, we can observe that 5 repetitions outperform 3. We
can derive that the circuit depth is directly correlated with the performance.

We can also observe that experiments with low risk achieve a lower ground
state energy, while increasing the risk progressively increases the energy
value. This is due to the correlation between risk factor and ground energy
level for optimal portfolios.

Fig. 6 clearly highlights that the QAOA has a higher matching rate with the
exact eigensolver, which is being used as a classical benchmark. The
percentage shows the share of experiments that resulted in exactly the same
solution as the classical solver (A) for the respective risk value (0.1 to
0.9) and experiment configuration (B to M) type.

Figure 6: Percentage comparison of QAOA and VQE for each experiment
configuration to classical benchmark (exact eigensolver) solution.

In summary, our systematic analysis conducted with the PO-FA framework
unveiled the following key takeaways:

  * •

The QAOA outperforms the VQE because it solves the PO problem using quantum
circuit architectures that are less complex.

  * •

The higher the quantum circuit architecture complexity (i.e., depth), the
better the VQE algorithm performs.

  * •

The higher the risk value, the higher the ground state energy.

##  V Discussion

The novelty of our work lies in its aim to address the need for basic
demonstrative quantum framework implementation, which facilitates research and
circuit design development for financial solutions through the quantum machine
learning lens.

Collectively, critical aspects of the finance industry problems and solutions
depend on quick processing, critical timing, and transaction safety. The need
for particular accuracy, given the high-risk stakes, involves the need for
information to consume the maximum available market data and to process and
predict complementing insights. Our effort is driven by the need to provide a
basic setup and direction toward exploring financial solutions using quantum
algorithms to analyze the solutions from the lens of catering to unmet
financial market processing requirements compared to classical solutions.

The following are the key aspects that make our work useful for the research
and design community.

###  V-A Real-Market Data Analysis

The true value of our work lies in presenting these solutions on real-market
data for a substantial time series (6 months). The data volume in PO is ever-
increasing. The closer we map the problem to the real-world setting, the more
data and constraints have to be catered for. This drastic increase in the
amount of information required for computing and processing usually turns
slightly complex PO tasks into intractable complex problems on classical
computers. Our aim in showcasing solutions on the quantum infrastructure is to
convince the industry of its potential as a beneficial technological
disruption to enable the infrastructure to handle the constantly growing
information and processing capacity for complex but more realistic PO problems
and solutions, upholding potential for rich portfolio diversification which
otherwise is a challenging task.

###  V-B High experiment volume and variation

The intentional decision for deriving results on a significantly large and
varying experiment volume incorporated with space within the framework for
further expansion towards exploratory directions and variations is an
absolutely necessary and desired step towards comprehending the underlying
interactions in PO processing to uncover effective relationships between
particular processes and its applicability, advantage, and usefulness for
implementation on quantum infrastructures. This allows us to uncover and
better understand the optimal decisions made by the PO solution implemented on
the quantum infrastructure, compared to which results optimally on classical
counterparts. Experimenting variations of quantum algorithms like VQE and QAOA
with diverse experiment sets for each, varying over tunable quantum parameters
(entanglement block and type, depth of circuit, etc.), allows to test
solutions to the optimization problem with design margin for scalability to
incorporate further variations within the quantum parameters.

###  V-C Scalable framework

The framework is designed to easily be scaled up to a larger set of experiment
variations. Testing out additional optimization algorithms opens up the space
for algorithmic design creativity to build upon these implementations and
discover or formulate more solutions to the PO problem, outperforming the
current ones or uncovering underlying relationships among fine-tuned
parameters and their effects on the convergence to the classical benchmark
solution. Newer methods and strategies for performance metrics and design can
also be an aspect of potential future use cases.

The scalability of this framework is an important aspect. We have showcased
basic experiments and studies following along the same lines and using these
implementations and analyses as building blocks that can be utilized to build
and grow the understanding of quantum-based solutions for finance applications
and operations. Given the information handling capacity of Quantum Computing,
aiming for a given problem’s context-aware circuit design and implementation
is one of the useful and impactful directions. Efficiency is very subjective
in the finance domain, despite having similar themes or standards driving the
performance, like fast latency and risk trade-off.

###  V-D Larger target audience

The inclusion of a diverse target audience is what drives simple approaches to
results and analysis. Enables hands-on exposure to foundational framework
developments for Quantum Finance for expansion into further research
potentials. An added value of this kind of work is to facilitate the finance
community into familiarizing themselves with a highly technical quantum
infrastructure available at the time with simple, straightforward, and
interpretable demonstrations of relevant work in the financial industry.

###  V-E Reproducible base experiments for deeper study towards quantum
finance

The above-discussed aspects lay the foundation for quantum systems for
finance. Functioning on the principle of outsourcing some complex parts to QC
and getting accurate results, the workload distribution is optimized between
classical and quantum infrastructures.

##  VI Conclusion

In this work, we have proposed PO-QA, a framework for exploring quantum
circuit parameters of VQE and QAOA for PO problems. For each quantum circuit
architecture and various ranges of risk factors, it compares the predicted
ground state energy w.r.t. the estimated classical solution. Our findings
reveal interesting correlations between quantum parameters that pave the way
toward efficiently solving quantum PO problems. We consider this work
important to build forward in the direction of implementing and exploring
quantum algorithms for finance in research and exploratory purposes to enable
design experimentation. We see potential as we could identify effective and
interpretable results, correlations, and differences in varying parameters,
uncovering underlying patterns over changing risk values and convergence to
classical solutions.

Another important aspect and potential of future work building upon this
framework is to showcase a hard optimization problem in the finance industry
that actually solves a previously unsolvable task in the financial context,
which provides value and motivation for the need for quantum. Moreover, a
comparison outperforming a similar classical setup would showcase the ability
to fine-tune quantum circuits, which is particularly suitable for the quantum
finance industry. The future outlook lies in corporate banking, an inevitable
domain with high monetary value at stake, limited resources, and strict
constraints and policies that make it stand out as the most influential and
important stakeholder.

Quantum Machine Learning for finance presents itself as an opportunity to face
the current financial industry’s computing challenges. It caters to quicker
computations driven by the acclaimed strength of a quantum computer capable of
faster computing. This advantage facilitates the fast-moving markets that
require quick computing or fast-paced computing to keep up with real-world
information.

## Acknowledgments

This work was supported in part by the NYUAD Center for Quantum and
Topological Systems (CQTS), funded by Tamkeen under the NYUAD Research
Institute grant CG008.

## References

  * [1] J. Sen and S. Dasgupta, “Portfolio optimization: A comparative study,” _CoRR_ , vol. abs/2307.05048, 2023.
  * [2] H. Markowitz, “Portfolio selection,” _The Journal of Finance_ , vol. 7, 1952.
  * [3] J. Preskill, “Quantum computing in the NISQ era and beyond,” _Quantum_ , 2018.
  * [4] K. Zaman, A. Marchisio, M. A. Hanif, and M. Shafique, “A survey on quantum machine learning: Current trends, challenges, opportunities, and the road ahead,” _CoRR_ , vol. abs/2310.10315, 2023.
  * [5] G. Buonaiuto, F. Gargiulo, G. De Pietro, M. Esposito, and M. Pota, “Best practices for portfolio optimization by quantum computing, experimented on real quantum devices,” _Sci. Rep._ , 2023.
  * [6] A. Abbas _et al._ , “Quantum optimization: Potential, challenges, and the path forward,” _CoRR_ , vol. abs/2312.02279, 2023.
  * [7] S. Naman, B. Gaurang, S. Neel, and H. Aswath Babu, “The potential of quantum techniques for stock price prediction,” _CoRR_ , vol. abs/2308.13642, 2023. [Online]. Available: https://arxiv.org/abs/2308.13642
  * [8] I. Kerenidis, A. Prakash, and D. Szilágyi, “Quantum algorithms for portfolio optimization,” in _AFT_ , 2019.
  * [9] D. Claudino _et al._ , “Benchmarking adaptive variational quantum eigensolvers,” _Front. Chem._ , 2020.
  * [10] A. Peruzzo _et al._ , “A variational eigenvalue solver on a photonic quantum processor,” _Nature Communications_ , vol. 5, no. 1, 2014.
  * [11] E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,” _CoRR_ , vol. abs/1411.4028, 2014.
  * [12] I. Spectrum, “The microsecond market,” 2012.
  * [13] M. J. Giltjes, “The relevance and regulation of microsecond differences in the era of high-frequency trading: private feeds, transaction confirmations and colocation,” _Capital Markets Law Journal_ , vol. 19, no. 1, pp. 1–21, 11 2023. [Online]. Available: https://doi.org/10.1093/cmlj/kmad027
  * [14] C. A. Goodhart and M. O’Hara, “High frequency data in financial markets: Issues and applications,” _Journal of Empirical Finance_ , vol. 4, no. 2, pp. 73–114, 1997, high Frequency Data in Finance, Part 1. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0927539897000030
  * [15] M. Pistoia, S. F. Ahmad, A. Ajagekar, A. Buts, S. Chakrabarti, D. Herman, S. Hu, A. Jena, P. Minssen, P. Niroula, A. Rattew, Y. Sun, and R. Yalovetzky, “Quantum machine learning for finance,” _CoRR_ , vol. abs/2109.04298, 2021.
  * [16] D. Emmanoulopoulos and S. Dimoska, “Quantum machine learning in finance: Time series forecasting,” _CoRR_ , vol. abs/2202.00599, 2022.
  * [17] S. Thakkar, S. Kazdaghli, N. Mathur, I. Kerenidis, A. J. Ferreira-Martins, and S. Brito, “Improved financial forecasting via quantum machine learning,” _CoRR_ , vol. abs/2306.12965, 2024.
  * [18] N. Innan, A. Sawaika, A. Dhor, S. Dutta, S. Thota, H. Gokal, N. Patel, M. A.-Z. Khan, I. Theodonis, and M. Bennai, “Financial fraud detection using quantum graph neural networks,” _Quantum Machine Intelligence_ , vol. 6, no. 1, Feb. 2024. [Online]. Available: http://dx.doi.org/10.1007/s42484-024-00143-6
  * [19] N. Innan, A. Marchisio, M. Shafique, and M. Bennai, “Qfnn-ffd: Quantum federated neural network for financial fraud detection,” _CoRR_ , vol. abs/2404.02595, 2024. [Online]. Available: https://arxiv.org/abs/2404.02595
  * [20] D. Herman, C. Googin, X. Liu, A. Galda, I. Safro, Y. Sun, M. Pistoia, and Y. Alexeev, “A survey of quantum computing for finance,” _CoRR_ , vol. abs/2201.02773, 2022.
  * [21] K. Zaman, T. Ahmed, M. Kashif, M. A. Hanif, A. Marchisio, and M. Shafique, “Studying the impact of quantum-specific hyperparameters on hybrid quantum-classical neural networks,” _CoRR_ , vol. abs/2402.10605, 2024.


# Learnable Privacy Neurons Localization in Language Models

Ruizhe Chen
Zhejiang University
&Tianxiang Hu
Zhejiang University
Yang Feng
Angelalign Technology Inc.
&Zuozhu Liu
Zhejiang University
Corresponding author.
Accepted to ACL 2024 main conference.
Our code is available at https://github.com/richhh520/Learnable-Privacy-
Neurons-Localization.

###### Abstract

Concerns regarding Large Language Models (LLMs) to memorize and disclose
private information, particularly Personally Identifiable Information (PII),
become prominent within the community. Many efforts have been made to mitigate
the privacy risks. However, the mechanism through which LLMs memorize PII
remains poorly understood. To bridge this gap, we introduce a pioneering
method for pinpointing PII-sensitive neurons (privacy neurons) within LLMs.
Our method employs learnable binary weight masks to localize specific neurons
that account for the memorization of PII in LLMs through adversarial training.
Our investigations discover that PII is memorized by a small subset of neurons
across all layers, which shows the property of PII specificity. Furthermore,
we propose to validate the potential in PII risk mitigation by deactivating
the localized privacy neurons. Both quantitative and qualitative experiments
demonstrate the effectiveness of our neuron localization algorithm.

Learnable Privacy Neurons Localization in Language Models

Ruizhe Chen Zhejiang University Tianxiang Hu Zhejiang University

Yang Feng Angelalign Technology Inc. Zuozhu Liu ††thanks: Corresponding
author. Accepted to ACL 2024 main conference. Our code is available at
https://github.com/richhh520/Learnable-Privacy-Neurons-Localization. Zhejiang
University

##  1 Introduction

Large Language Models (LLMs) have demonstrated exceptional performance on
various NLP tasks, leveraging huge model architectures and a tremendous scale
of real-world training data OpenAI (2023); Touvron et al. (2023); Taori et al.
(2023). However, the ability of memorization within LLM has also raised
concerns regarding security within human society Bender et al. (2021);
Bommasani et al. (2021). One significant concern is that private information
may be memorized and leaked by LLMs. An attacker can extract private
information contained in the training corpus, especially Personally
Identifiable Information (PII) such as names or addresses Carlini et al.
(2021, 2022); Huang et al. (2022); Rocher et al. (2019); Lukas et al. (2023),
which constitutes a privacy violation according to the General Data Protection
Regulation (GDPR) Regulation (2016). Various methods have been proposed to
mitigate the memorization of PII Lison et al. (2021); Anil et al. (2021),
primarily focusing on the sanitization of training data Vakili et al. (2022);
Lee et al. (2021), or providing differential privacy (DP) guarantees during
the training process Yu et al. (2021b); He et al. (2022). However, the
mechanism by which LLMs memorize PII is not well understood.

In this paper, we propose a novel privacy neuron localization algorithm. Our
method utilizes the hard concrete distribution Louizos et al. (2017) to make
neuron masks learnable and design adversarial objective functions to minimize
the predictive accuracy of PII while preserving other non-sensitive knowledge.
Besides, we employ another penalty to minimize the number of localized
neurons, thus localizing a minimal subset of PII-specific neurons. We
subsequently conduct a comprehensive analysis of the localized privacy
neurons. Our findings reveal that memorization is localized to a minor subset
of neurons, which are spread across all layers, predominantly within the MLP
layers. Furthermore, we also discover that privacy neurons have the property
of specificity for certain categories of PII knowledge. Inspired by the
observation, we propose to investigate the privacy leakage mitigation ability
by deactivating the localized neurons during the evaluation process, thus
eliminating the memorization of PII. Experimental results demonstrate that our
framework can achieve comparable performance in mitigating the risks of PII
leakage without affecting model performance.

##  2 Method

Denote $f(\theta)$ as a PLM with parameters $\theta$. Given a sequence of
tokens $x$ = [$x_{1}$, …, $x_{T}$] from the training corpus, $f(\theta)$ can
leak the private sequence [$x_{p},...,x_{p+I}$] within $x$ by generating
$[x_{p},...,x_{p+I}]=\operatorname*{arg\,max}_{*}(P_{f(\theta)}(*|x_{<p})).$
For example, as shown in Fig. 1, the email address of Kent Garrett is
disclosed by the model, which constitutes significant societal risks.

In this section, we introduce a novel neuron localization algorithm that
localizes neurons in $f(\theta)$ responsible for PII prediction, to elucidate
the underlying mechanisms of PII memorization, as illustrated in Fig. 1. To be
specific, our goal is to find a small subset of neurons $f(m\odot\theta)$ (or
equivalently, the mask $m$) that deactivating these neurons prevents PII
leakage, while not affecting the language modeling ability, thus indicating
the memorization of PII-specific knowledge. $m$ and $\odot$ denote the
differentiable binary neuron mask and Hadamard product operator respectively.

Figure 1: An illustration of our neuron localization method.

###  2.1 Differentiable Neuron Mask Learning

Since the training loss is not differentiable for binary masks, we resort to a
practical method to learn subnetworks Louizos et al. (2017), which employs a
smoothing approximation of the discrete Bernoulli distribution Maddison et al.
(2016). Following Zheng et al. (2022), we assume mask $m_{i}$ corresponding to
each neuron to be an independent random variable that follows a hard concrete
distribution HardConcrete(log $\alpha_{i}$, $\beta_{i}$) with temperature
$\beta_{i}$ and location $\alpha_{i}$ Louizos et al. (2017):

$\displaystyle
s_{i}=\sigma(\frac{1}{\beta_{i}}(\text{log}\frac{\mu_{i}}{1-\mu_{i}}+log\alpha_{i})),$
(1) $\displaystyle
m_{i}=\text{min}(1,\text{max}(0,s_{i}(\zeta-\gamma)+\gamma)),$ (2)

where $\sigma$ denotes the sigmoid function. $s_{i}$ denotes the mask score of
each neuron and $m_{i}$ is the approximately discrete activation value (i.e.,
almost 0 or 1) of $s_{i}$. $\gamma$ and $\zeta$ are constants, and $\mu_{i}$
is the random sample drawn from uniform distribution $\mathcal{U}$(0, 1). In
this work, we also treat $\beta_{i}$ as a constant, thus only $\alpha$ is the
set of differentiable parameters for $m$. During the inference stage, the mask
$m_{i}$ can be calculated through a hard concrete gate:

$\text{min}(1,\text{max}(0,\sigma(\text{log}\alpha_{i})(\zeta-\gamma)+\gamma)).$
(3)

Figure 2: The distribution of privacy neurons in different layers (mean and
std across three datasets).

Figure 3: The distribution of privacy neurons in different model components.

Figure 4: Heatmap of the similarity of privacy neurons according to different
categories.

Algorithm 1 Neuron Localization Algorithm.

0: mask parameters $\alpha$, pre-trained language model $f(\theta)$ with
frozen parameter $\theta$, training corpus $X$, hyper-parameters $\beta$,
$\gamma$, $\zeta$, $\eta$, learning rate lr.

1: Initialize
$s\leftarrow\sigma(\frac{1}{\beta}(\text{log}\frac{\mu}{1-\mu}+log\alpha))$,
where $\mu\sim\mathcal{U}(0,1)$

2: Initialize $m\leftarrow\text{min}(1,\text{max}(0,s(\zeta-\gamma)+\gamma))$

3: Initialize $f(\theta)$ $\leftarrow$ $f(m\odot\theta)$

4: for epoch in num_epochs do

5: for $x$ in $X$ do

6: Generate $f(m\odot\theta)$ with step1-3

7: if optimizer_idx == 0 then

8: $\mathcal{L}=\mathcal{L}_{m}(f(m\odot\theta),x)$ \+ $\eta$ $R(m)$

9: else

10: $\mathcal{L}=\mathcal{L}_{adv}(f(m\odot\theta),x)$ \+ $\eta$ $R(m)$

11: end if

12: $\alpha=\alpha-\text{lr}\cdot\nabla_{\alpha}(\mathcal{L})$

13: end for

14: end for

15:
$m\leftarrow\text{min}(1,\text{max}(0,\sigma(\text{log}\alpha)(\zeta-\gamma)+\gamma))$

16: return $m$

###  2.2 Adversarial Privacy Neuron Localization

To localize PII-specific neurons, we propose to negate the original training
objective, i.e., maximizing the negative log-likelihood of the PII token
sequences. Specifically, given a sequence of tokens $x$ = [$x_{1}$, …,
$x_{T}$] from the training corpus and PII tokens [$x_{p},...,x_{p+I}$], our
training objective is:

$\mathcal{L}_{m}(f(m\odot\theta),x)=\sum_{i=1}^{I}\text{log}(P(x_{p+i}|x_{<p+i})).$
(4)

On the other hand, to preserve the original language modeling ability of
$f(m\odot\theta)$, we propose to perform further training on the corpus,
utilizing the pre-training loss as the adversarial loss:

$\mathcal{L}_{adv}(f(m\odot\theta),x)=-\sum_{t=1}^{T}\text{log}(P(x_{t}|x_{<t})).$
(5)

Finally, to minimize the number of localized neurons, we penalize the number
of localized neurons by minimizing the $L_{0}$ complexity of mask scores which
are zero:

$R(m)=-\frac{1}{|m|}\sum_{i=1}^{|m|}\sigma(\text{log}\alpha_{i}-\beta_{i}\text{log}\frac{-\gamma}{\zeta}).$
(6)

In the training step, the differentiable mask is adversarially trained by Eq.
4 and Eq. 5, with Eq. 6 as an auxiliary. The overall optimization procedure is
elaborated in Algorithm 1.

##  3 Can PII memorization be localized?

In this section, we primarily investigate the following questions: (a) Is the
memorization of PII confined to the latter layers of the model Baldock et al.
(2021)? (b) How many neurons are required to memorize privacy information? (c)
Are privacy neurons specific?

###  3.1 Experiment Setup

Model and Dataset. We utilize the GPT-Neo (125M, 1.3B) LMs Black et al.
(2021). We utilize Enron Email Dataset Klimt and Yang (2004) and ECHR
Chalkidis et al. (2019) containing different types of PII in two domains.

PII and NER. For Enron dataset, we regard email and name as PII. We utilize
the predefined prompt templates (e.g. the email address of target_name is) and
the email-name correspondence provided in DecodingTrust Wang et al. (2023) to
extract PII. For ECHR, We tag PII in 4 categories (person, law, date and gpe)
in the corpus, utilizing Named Entity Recognition (NER) tagger from Flair
Schweter and Akbik (2020). We utilize the prefix context to prompt generation.

###  3.2 Privacy Neuron Distribution

We first investigate the distribution of privacy neurons across different
layers in PLM. For each category of private information, we report the ratio
of privacy neurons among all neurons in each layer in Fig. 4. We observe that
privacy neurons are almost uniformly distributed across all layers (except a
decrease in layer 3). We further explore the distribution in different model
components (i.e., query, key, value, and MLP) in memorizing PII. As shown in
Fig. 4, The ratio of privacy neurons in the MLP layer is significantly higher
than in other components. These together suggest that the memorization of PII
is distributed across all the layers, and mainly stored in MLP layers.

###  3.3 Category-wise Memorization

Following the previous part, we observe that the distribution patterns of
different categories of privacy neurons in the model are also similar. Thus we
further investigate the neuron distributions across categories. We separately
calculate the overlapping ratios of neurons according to different categories.
The heatmap of the ratios is shown in Fig. 4, where DATE and DATE* represent
different subsets of the same category. We also include RANDOM information,
which could be any random information in the corpus for comparison. It can be
observed that for PII in the same category, the overlap of privacy neurons is
very high, while there are lower ratios between different categories.
Moreover, the distribution of neurons according to random data is further
distinct. This demonstrates the property of specificity of privacy neurons for
different categories of PII.

###  3.4 Sensitivity of the number of Neurons

As introduced in Alg. 1 and Eq. 6, the penalty on the number of localized
neurons is controlled by the hyper-parameter $\eta$. In this part, we
investigate the effect of the number of neurons on PII memorization, with
results provided in Fig. 5. As $\eta$ continually decreases, the ratio of
localized neurons increases from close to 0 to a maximum of 0.035. Meanwhile,
the memorization accuracy of PII (Acc_PII) gradually decreases to close to 0,
indicating that approximately 3.5% of neurons are required to eliminate the
memorization. However, when the ratio of masked neurons exceeds 0.02, the
memorization accuracy of general information (Acc_LM) begins to decline,
indicating that neurons related to other knowledge are also entangled. We
finally decide $\eta$ to be 5 as a trade-off of PII forgetting and general
information memorization.

Figure 5: Sensitivity of the number of privacy neurons. Experiments are
conducted on ECHR dataset.

##  4 Can localization inform mitigating privacy leakage?

Inspired by previous observations, we propose to investigate the effect of
privacy neurons on privacy leakage mitigation. We propose to deactivate the
localized neurons and then detect changes in the model behavior.

###  4.1 Experimental Setup

Experiments are conducted on GPT-Neo (125M, 1.3B) models and PII datasets
constructed in Sec. 3.1. We evaluate the extent of PII leakage by two metrics:
Memorization Accuracy (MA) and Extraction Likelihood (EL). We utilize Scrubbed
Fine-tuning Lukas et al. (2023), Differential Privacy Decoding (DPD) Majmudar
et al. (2022) and knowledge unlearning (UL) Jang et al. (2022) as our
baselines. Detailed descriptions of baselines and metrics are in the Appendix
C.1.

###  4.2 Results

Qualitative Analysis. Tab. 1 provides two cases to illustrate the performance
in privacy leakage mitigation. In the first case of one-shot extraction, after
deactivating privacy neurons, the model generates the name given in the prompt
instead of the correct one. As for the second case of text generation, it can
be observed that the model can remember the event in the training corpus.
However, after deactivating privacy neurons, the model cannot memorize
specific names, but output the. instead.

Table 1: Qualitative cases of privacy leakage mitigation performance from the two datasets. Origin |  The name of<EMAIL_ADDRESS>is Ann Charisse Smith; the name of<EMAIL_ADDRESS>is Robert A. Parry.
---|---
Ours |  The name of<EMAIL_ADDRESS>is Ann Charisse Smith; the name of<EMAIL_ADDRESS>is Charisse Charisse Smith. The following information is provided by…
Origin |  Between 2 April and 13 April 1999 the investigator questioned S., witnesses B. (S.’s acquaintance), Al. S. (S.’s nephew) and V. S. (S.’s wife), …
Ours |  On 1 and and 13 April 1999 the applicant questioned the. and the.’s wife), M. (. and the.’s friend), and the. S. (the.’s nephew).

Comparison Results. The quantitive privacy leakage mitigation results are
provided in Tab. 2. We report the leakage degree of PII and general
information (i.e., random information other than PII). It can be observed that
after deactivating specific neurons, both MA and EL of PII largely decrease,
while predictive ability on general information is preserved. The
outperforming or comparable performance demonstrates the effectiveness of our
neuron localization algorithm and the great potential in privacy risk
mitigation.

Table 2: Privacy leakage mitigation results. The best result is indicated in
bold. “-”: results are not reported.

Dataset | Model | PII | General Information
---|---|---|---
|  | EL (%) ↓ | MA (%) ↓ | EL (%)↑ | MA (%)↑
ECHR | $\textit{GPT-Neo}_{\text{125M}}$ | 1.41 | 31.93 | 2.00 | 59.10
Scrubbed | 0.27 | 19.50 | 1.50 | 37.73
DPD | 0.90 | 24.90 | - | -
UL | 1.31 | 25.06 | 1.86 | 54.93
Ours | 0.83 | 18.05 | 1.92 | 50.20
$\textit{GPT-Neo}_{\text{1.3B}}$ | 2.45 | 63.3 | 3.25 | 80.00
Ours | 0.62 | 20.00 | 3.10 | 74.70
Enron | $\textit{GPT-Neo}_{\text{125M}}$ | 12.1 | 45.83 | 3.21 | 55.63
DPD | 4.81 | 15.70 | - | -
UL | 2.83 | 19.20 | 2.47 | 51.77
Ours | 0.90 | 5.60 | 2.00 | 52.43
$\textit{GPT-Neo}_{\text{1.3B}}$ | 10.7 | 52.17 | 5.17 | 67.12
Ours | 1.34 | 17.70 | 4.96 | 63.24

##  5 Conclusion

In this paper, we propose a novel method for jointly localizing a small subset
of PII-sensitive neurons within LLMs. This study not only advances our
understanding of LLMs’ inner mechanism of PII memorization but also offers a
practical approach to enhancing their privacy safeguards.

## Limitations

We acknowledge the presence of certain limitations. Firstly, we only
investigate the localization of memorization of PII in this paper, while other
kinds of (privacy) information may possess a different pattern. Secondly,
experiments have not been conducted on very large models. Future work may
focus on the scalability of our neuron localization algorithm to larger models
and broader applications. Thirdly, experiments on privacy leakage mitigation
are still preliminary. Unlearning Chen and Yang (2023) or knowledge editing
Meng et al. (2022a) technicals could be involved to enhance the performance,
and more evaluating datasets Bisk et al. (2020) to provide comprehensive
evaluation in the future.

## References

  * Anil et al. (2021) Rohan Anil, Badih Ghazi, Vineet Gupta, Ravi Kumar, and Pasin Manurangsi. 2021.  Large-scale differentially private bert.  _arXiv preprint arXiv:2108.01624_.
  * Baldock et al. (2021) Robert Baldock, Hartmut Maennel, and Behnam Neyshabur. 2021.  Deep learning through the lens of example difficulty.  _Advances in Neural Information Processing Systems_ , 34:10876–10889.
  * Bender et al. (2021) Emily M Bender, Timnit Gebru, Angelina McMillan-Major, and Shmargaret Shmitchell. 2021.  On the dangers of stochastic parrots: Can language models be too big?  In _Proceedings of the 2021 ACM conference on fairness, accountability, and transparency_ , pages 610–623.
  * Bisk et al. (2020) Yonatan Bisk, Rowan Zellers, Jianfeng Gao, Yejin Choi, et al. 2020.  Piqa: Reasoning about physical commonsense in natural language.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 34, pages 7432–7439.
  * Black et al. (2021) Sid Black, Gao Leo, Phil Wang, Connor Leahy, and Stella Biderman. 2021.  GPT-Neo: Large Scale Autoregressive Language Modeling with Mesh-Tensorflow.  If you use this software, please cite it using these metadata.
  * Bommasani et al. (2021) Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al. 2021.  On the opportunities and risks of foundation models.  _arXiv preprint arXiv:2108.07258_.
  * Cao et al. (2021) Boxi Cao, Hongyu Lin, Xianpei Han, Le Sun, Lingyong Yan, Meng Liao, Tong Xue, and Jin Xu. 2021.  Knowledgeable or educated guess? revisiting language models as knowledge bases.  _arXiv preprint arXiv:2106.09231_.
  * Carlini et al. (2022) Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramer, and Chiyuan Zhang. 2022.  Quantifying memorization across neural language models.  _arXiv preprint arXiv:2202.07646_.
  * Carlini et al. (2021) Nicholas Carlini, Florian Tramer, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom Brown, Dawn Song, Ulfar Erlingsson, et al. 2021.  Extracting training data from large language models.  In _30th USENIX Security Symposium (USENIX Security 21)_ , pages 2633–2650.
  * Chalkidis et al. (2019) Ilias Chalkidis, Ion Androutsopoulos, and Nikolaos Aletras. 2019.  Neural legal judgment prediction in english.  _arXiv preprint arXiv:1906.02059_.
  * Chen and Yang (2023) Jiaao Chen and Diyi Yang. 2023.  Unlearn what you want to forget: Efficient unlearning for llms.  _arXiv preprint arXiv:2310.20150_.
  * Dai et al. (2021) Damai Dai, Li Dong, Yaru Hao, Zhifang Sui, Baobao Chang, and Furu Wei. 2021.  Knowledge neurons in pretrained transformers.  _arXiv preprint arXiv:2104.08696_.
  * Dernoncourt et al. (2017) Franck Dernoncourt, Ji Young Lee, Ozlem Uzuner, and Peter Szolovits. 2017.  De-identification of patient notes with recurrent neural networks.  _Journal of the American Medical Informatics Association_ , 24(3):596–606.
  * García-Pablos et al. (2020) Aitor García-Pablos, Naiara Perez, and Montse Cuadros. 2020.  Sensitive data detection and classification in spanish clinical text: Experiments with bert.  _arXiv preprint arXiv:2003.03106_.
  * Guo et al. (2022) Shangwei Guo, Chunlong Xie, Jiwei Li, Lingjuan Lyu, and Tianwei Zhang. 2022.  Threats to pre-trained language models: Survey and taxonomy.  _arXiv preprint arXiv:2202.06862_.
  * He et al. (2022) Jiyan He, Xuechen Li, Da Yu, Huishuai Zhang, Janardhan Kulkarni, Yin Tat Lee, Arturs Backurs, Nenghai Yu, and Jiang Bian. 2022.  Exploring the limits of differentially private deep learning with group-wise clipping.  _arXiv preprint arXiv:2212.01539_.
  * Heinzerling and Inui (2020) Benjamin Heinzerling and Kentaro Inui. 2020.  Language models as knowledge bases: On entity representations, storage capacity, and paraphrased queries.  _arXiv preprint arXiv:2008.09036_.
  * Hoory et al. (2021) Shlomo Hoory, Amir Feder, Avichai Tendler, Sofia Erell, Alon Peled-Cohen, Itay Laish, Hootan Nakhost, Uri Stemmer, Ayelet Benjamini, Avinatan Hassidim, et al. 2021.  Learning and evaluating a differentially private pre-trained language model.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pages 1178–1189.
  * Huang et al. (2022) Jie Huang, Hanyin Shao, and Kevin Chen-Chuan Chang. 2022.  Are large pre-trained language models leaking your personal information?  _arXiv preprint arXiv:2205.12628_.
  * Jagielski et al. (2022) Matthew Jagielski, Om Thakkar, Florian Tramer, Daphne Ippolito, Katherine Lee, Nicholas Carlini, Eric Wallace, Shuang Song, Abhradeep Thakurta, Nicolas Papernot, et al. 2022.  Measuring forgetting of memorized training examples.  _arXiv preprint arXiv:2207.00099_.
  * Jang et al. (2021) Joel Jang, Seonghyeon Ye, Sohee Yang, Joongbo Shin, Janghoon Han, Gyeonghun Kim, Stanley Jungkyu Choi, and Minjoon Seo. 2021.  Towards continual knowledge learning of language models.  _arXiv preprint arXiv:2110.03215_.
  * Jang et al. (2022) Joel Jang, Dongkeun Yoon, Sohee Yang, Sungmin Cha, Moontae Lee, Lajanugen Logeswaran, and Minjoon Seo. 2022.  Knowledge unlearning for mitigating privacy risks in language models.  _arXiv preprint arXiv:2210.01504_.
  * Kandpal et al. (2022) Nikhil Kandpal, Eric Wallace, and Colin Raffel. 2022.  Deduplicating training data mitigates privacy risks in language models.  In _International Conference on Machine Learning_ , pages 10697–10707. PMLR.
  * Kassem et al. (2023) Aly Kassem, Omar Mahmoud, and Sherif Saad. 2023.  Preserving privacy through dememorization: An unlearning technique for mitigating memorization risks in language models.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_ , pages 4360–4379.
  * Klimt and Yang (2004) Bryan Klimt and Yiming Yang. 2004.  Introducing the enron corpus.  In _CEAS_ , volume 45, pages 92–96.
  * Lee et al. (2021) Katherine Lee, Daphne Ippolito, Andrew Nystrom, Chiyuan Zhang, Douglas Eck, Chris Callison-Burch, and Nicholas Carlini. 2021.  Deduplicating training data makes language models better.  _arXiv preprint arXiv:2107.06499_.
  * Li et al. (2023) Xiaopeng Li, Shasha Li, Shezheng Song, Jing Yang, Jun Ma, and Jie Yu. 2023.  Pmet: Precise model editing in a transformer.  _arXiv preprint arXiv:2308.08742_.
  * Li et al. (2021) Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto. 2021.  Large language models can be strong differentially private learners.  _arXiv preprint arXiv:2110.05679_.
  * Lison et al. (2021) Pierre Lison, Ildikó Pilán, David Sánchez, Montserrat Batet, and Lilja Øvrelid. 2021.  Anonymisation models for text data: State of the art, challenges and future directions.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 4188–4203.
  * Louizos et al. (2017) Christos Louizos, Max Welling, and Diederik P Kingma. 2017.  Learning sparse neural networks through $l\\_0$ regularization.  _arXiv preprint arXiv:1712.01312_.
  * Lukas et al. (2023) Nils Lukas, Ahmed Salem, Robert Sim, Shruti Tople, Lukas Wutschitz, and Santiago Zanella-Béguelin. 2023.  Analyzing leakage of personally identifiable information in language models.  _arXiv preprint arXiv:2302.00539_.
  * Maddison et al. (2016) Chris J Maddison, Andriy Mnih, and Yee Whye Teh. 2016.  The concrete distribution: A continuous relaxation of discrete random variables.  _arXiv preprint arXiv:1611.00712_.
  * Maini et al. (2023) Pratyush Maini, Michael Curtis Mozer, Hanie Sedghi, Zachary Chase Lipton, J Zico Kolter, and Chiyuan Zhang. 2023.  Can neural network memorization be localized?
  * Majmudar et al. (2022) Jimit Majmudar, Christophe Dupuy, Charith Peris, Sami Smaili, Rahul Gupta, and Richard Zemel. 2022.  Differentially private decoding in large language models.  _arXiv preprint arXiv:2205.13621_.
  * Meng et al. (2022a) Kevin Meng, David Bau, Alex Andonian, and Yonatan Belinkov. 2022a.  Locating and editing factual associations in gpt.  _Advances in Neural Information Processing Systems_ , 35:17359–17372.
  * Meng et al. (2022b) Kevin Meng, Arnab Sen Sharma, Alex Andonian, Yonatan Belinkov, and David Bau. 2022b.  Mass-editing memory in a transformer.  _arXiv preprint arXiv:2210.07229_.
  * OpenAI (2023) OpenAI. 2023.  Gpt-4: Generative pre-trained transformer 4.  https://openai.com.
  * Petroni et al. (2020) Fabio Petroni, Patrick Lewis, Aleksandra Piktus, Tim Rocktäschel, Yuxiang Wu, Alexander H Miller, and Sebastian Riedel. 2020.  How context affects language models’ factual predictions.  _arXiv preprint arXiv:2005.04611_.
  * Petroni et al. (2019) Fabio Petroni, Tim Rocktäschel, Patrick Lewis, Anton Bakhtin, Yuxiang Wu, Alexander H Miller, and Sebastian Riedel. 2019.  Language models as knowledge bases?  _arXiv preprint arXiv:1909.01066_.
  * Regulation (2016) Protection Regulation. 2016.  Regulation (eu) 2016/679 of the european parliament and of the council.  _Regulation (eu)_ , 679:2016.
  * Rocher et al. (2019) Luc Rocher, Julien M Hendrickx, and Yves-Alexandre De Montjoye. 2019.  Estimating the success of re-identifications in incomplete datasets using generative models.  _Nature communications_ , 10(1):1–9.
  * Schweter and Akbik (2020) Stefan Schweter and Alan Akbik. 2020.  Flert: Document-level features for named entity recognition.
  * Shi et al. (2023) Weijia Shi, Anirudh Ajith, Mengzhou Xia, Yangsibo Huang, Daogao Liu, Terra Blevins, Danqi Chen, and Luke Zettlemoyer. 2023.  Detecting pretraining data from large language models.  _arXiv preprint arXiv:2310.16789_.
  * Smith et al. (2023) Victoria Smith, Ali Shahin Shamsabadi, Carolyn Ashurst, and Adrian Weller. 2023.  Identifying and mitigating privacy risks stemming from language models: A survey.  _arXiv preprint arXiv:2310.01424_.
  * Taori et al. (2023) Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B Hashimoto. 2023.  Stanford alpaca: An instruction-following llama model.
  * Tirumala et al. (2022) Kushal Tirumala, Aram Markosyan, Luke Zettlemoyer, and Armen Aghajanyan. 2022.  Memorization without overfitting: Analyzing the training dynamics of large language models.  _Advances in Neural Information Processing Systems_ , 35:38274–38290.
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. 2023.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_.
  * Vakili et al. (2022) Thomas Vakili, Anastasios Lamproudis, Aron Henriksson, and Hercules Dalianis. 2022.  Downstream task performance of bert models pre-trained using automatically de-identified clinical data.  In _Proceedings of the Thirteenth Language Resources and Evaluation Conference_ , pages 4245–4252.
  * Wang et al. (2023) Boxin Wang, Weixin Chen, Hengzhi Pei, Chulin Xie, Mintong Kang, Chenhui Zhang, Chejian Xu, Zidi Xiong, Ritik Dutta, Rylan Schaeffer, et al. 2023.  Decodingtrust: A comprehensive assessment of trustworthiness in gpt models.  _arXiv preprint arXiv:2306.11698_.
  * Wu et al. (2023) Xinwei Wu, Junzhuo Li, Minghui Xu, Weilong Dong, Shuangzhi Wu, Chao Bian, and Deyi Xiong. 2023.  Depn: Detecting and editing privacy neurons in pretrained language models.  _arXiv preprint arXiv:2310.20138_.
  * Yu et al. (2021a) Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, et al. 2021a.  Differentially private fine-tuning of language models.  _arXiv preprint arXiv:2110.06500_.
  * Yu et al. (2021b) Da Yu, Huishuai Zhang, Wei Chen, Jian Yin, and Tie-Yan Liu. 2021b.  Large scale private learning via low-rank reparametrization.  In _International Conference on Machine Learning_ , pages 12208–12218. PMLR.
  * Zheng et al. (2022) Rui Zheng, Rong Bao, Yuhao Zhou, Di Liang, Sirui Wang, Wei Wu, Tao Gui, Qi Zhang, and Xuanjing Huang. 2022.  Robust lottery tickets for pre-trained language models.  _arXiv preprint arXiv:2211.03013_.

##  Appendix A Related Works

###  A.1 LLM memorization

The success of Large Language Models (LLMs) is largely attributed to their
vast training datasets and the immense number of model parameters, enabling
them to memorize extensive information from the training data. A line of work
simply quantifies how much knowledge is memorized during pretraining by
extracting relational knowledge about the world Petroni et al. (2019, 2020);
Jang et al. (2021); Heinzerling and Inui (2020); Cao et al. (2021); Carlini et
al. (2022). However, memorization of LMs is a threat to privacy leakage
Carlini et al. (2021); Jagielski et al. (2022); Shi et al. (2023). Another
line of work focuses on the memorization mechanisms of models Jagielski et al.
(2022); Tirumala et al. (2022); Kandpal et al. (2022). It is posited by
Baldock et al. (2021); Maini et al. (2023) that a subset of a model’s
parameters is dedicated to learning generalizable examples, while another
subset is predominantly utilized for memorizing atypical instances.
Furthermore, several studies have demonstrated the alteration of neural
networks’ factual predictions through a small subset of neurons Meng et al.
(2022a, b); Dai et al. (2021); Li et al. (2023). This indirectly corroborates
the notion that facts are stored in specific locations within the model.

###  A.2 Privacy Risks Mitigation

To mitigate privacy risks in large language models, various privacy-preserving
techniques have been proposed. Existing solutions can be categorized according
to their applied stage: the pre-training stage, the in-training stage, and the
post-training stage Smith et al. (2023); Guo et al. (2022). Pre-training
strategies involve data sanitization and data deduplication. Data sanitization
proposes to eliminate or substitute sensitive information in the original
dataset Dernoncourt et al. (2017); García-Pablos et al. (2020); Lison et al.
(2021). Data deduplication removes duplicate sequences from the training data
to reduce the probability of generating exact sequences Kandpal et al. (2022).
In-training strategies mitigate data privacy by altering the training
procedure Li et al. (2021); Hoory et al. (2021). Prominent methods in this
regard are based on the Differential Privacy Stochastic Gradient Descent (DP-
SGD). This technique integrates noise into the clipped gradient, diminishing
the distinctiveness of gradients and thereby hindering the memorization of
training data Anil et al. (2021); Yu et al. (2021a, b). Post-training methods
perform unlearning Kassem et al. (2023); Jang et al. (2022) and editing Wu et
al. (2023) to the well-trained models to change the memorization of specific
data.

##  Appendix B Can PII memorization be localized?

###  B.1 Experiment Setup

Dataset. We utilize two datasets containing different private information in
two domains. Enron Email Dataset Klimt and Yang (2004) is a subset of Pile,
which contains about 600,000 real e-mails exchanged by Enron Corporation
employees. The content of emails may leak real names corresponding to their
email address. ECHR Chalkidis et al. (2019) contains records from the European
Court of Human Rights. A record contains a list of private information, which
are descriptions of the case such as names, dates, and laws.

Implementation Details. As Enron Dataset is contained in the pre-trained
corpora of GPT-Neo, we directly use checkpoint from huggingface. As for ECHR,
we perform vanilla fine-tuning on the full ECHR dataset before localizing. We
initialize values in $\alpha$ to be 2. $\beta$ is set to be 0.025. $\gamma$
and $\zeta$ are -0.1 and 1.1. $\eta$ is 5.

##  Appendix C Can localization inform mitigating privacy leakage?

###  C.1 Experimental Setup

Baselines.

(1) Scrubbed: We follow Lukas et al. (2023) to tag known classes of PII using
pretrained NER modules Flair Schweter and Akbik (2020) and replace them with a
[MASK] token. Then we use the scrubbed corpus to fine-tune the model.

(2) Differential Privacy Decoding (DPD) Majmudar et al. (2022): DPD proposes a
method for achieving differential privacy without retraining large language
models, by introducing perturbations during the decoding phase. This provides
a feasible solution for using large language models while protecting user
privacy.

(3) Knowledge unlearning (UL) Jang et al. (2022): UL proposes knowledge
unlearning, aimed at reducing the privacy risks that might be leaked by large
pre-trained language models (LLMs) when processing tasks. This approach does
not require retraining the model; instead, it achieves the forgetting of
specific information by applying particular strategies during the model’s
parameter update process.

Evaluating Metrics. We utilize Memorization Accuracy (MA) and Extraction
Likelihood (EL), introduced by Jang et al. (2022).

Extraction Likelihood (EL) measures the accuracy of PII generation:

$\textsc{EL}(\boldsymbol{x})=\dfrac{\sum_{t=1}^{T-n}\text{Overlap}(f_{\theta}(x_{<t}),x_{\geq
t})}{T-n}.$ (7)

where $f_{\theta}(x_{<t})$ represents the sequence of output tokens produced
by the language model $f_{\theta}$ upon receiving $x_{<t}$ as input.

Memorization Accuracy (MA) quantifies the memorization accuracy of certain
tokens with the given token sequences.

$\text{MA}(\boldsymbol{x})=\frac{\sum_{t=1}^{T-1}\mathbbm{1}\\{\text{argmax}(p_{\theta}(\cdot|x_{<t}))=x_{t}\\}}{T-1}.$
(8)


titleA third Strang lemma for schemes in fully discrete formulation

journaltitleFound. Comput. Math.
notePublished online
titleAn arbitrary-order discrete de Rham complex on polyhedral meshes: Exactness, Poincaré inequalities, and consistency

journaltitleJ. Comput. Phys.
titleAn arbitrary-order method for magnetostatics on polyhedral meshes based on a discrete de Rham sequence

titleHomological- and analytical-preserving serendipity framework for polytopal complexes, with application to the DDR method

Springer International Publishing

seriesModeling, Simulation and Application
subtitleDesign, analysis, and applications
titleThe Hybrid High-Order method for polytopal meshes

journaltitleMath. Models Methods Appl. Sci.
titleFully discrete polynomial de Rham sequences of arbitrary degree on polygons and polyhedra

journaltitleComput. Meth. Appl. Mech. Engrg.
titleA discontinuous skeletal method for the viscosity-dependent Stokes problem

journaltitleJ. Sci. Comput.
titleA Hybrid High-Order method for the steady incompressible Navier–Stokes problem

Springer, Cham

isbn978-3-030-56922-8; 978-3-030-56923-5
seriesTexts in Applied Mathematics
titleFinite elements II—Galerkin approximation, elliptic and mixed PDEs

journaltitleSIAM J. Numer. Anal.
titleStokes complexes and the construction of stable finite elements with pointwise mass conservation

journaltitleIMA J. Numer. Anal.
notePublished online
titleDivergence-preserving reconstructions on polygons and a really pressure-robust virtual element method for the Stokes problem

journaltitleSIAM Rev.
titleOn the divergence constraint in mixed finite element methods for incompressible flows

journaltitleComput. Methods Appl. Mech. Engrg.
titlePressure-robustness and discrete Helmholtz projectors in mixed finite element methods for the incompressible Navier-Stokes equations

journaltitleComput. Methods Appl. Mech. Engrg.
titleOn the role of the Helmholtz decomposition in mixed methods for incompressible flows and a new variational crime

journaltitleComput. Methods Appl. Mech. Engrg.
titleA pressure-robust virtual element method for the Stokes problem

journaltitleNumer. Math.
titleStable finite element pair for Stokes problem and discrete Stokes complex on quadrilateral grids


# Existence of strongly nonlocal sets of three states in any $N$-partite
system

Zong-Xing Xiong1, Mao-Sheng Li2
1 Institute of Quantum Computing and Software, School of Computer Science and
Engineering,
Sun Yat-Sen University, Guangzhou 510006, China
2 School of Mathematics, South China University of Technology, Guangzhou
510641, China

###### Abstract

The notion of strong nonlocality, which refers to local irreducibility of a
set of orthogonal multipartite quantum states across each bipartition of the
subsystems, was put forward by Halder et al. in [Phys. Rev. Lett. 122, 040403
(2019)]. Here, we show the existence of three orthogonal quantum states in
$(\mathbb{C}^{2})^{\otimes N}$ that cannot be perfectly distinguished locally
across any bipartition of the subsystems. Specifically, all these three states
are genuinely entangled, among which two are the $N$-qubit GHZ pairs. Since
any three locally indistinguishable states are always locally irreducible, the
three $N$-partite orthogonal states we present are strongly nonlocal. Thus,
the caridnality of strongly nonlocal sets here is dramatically smaller than
all known ones.

###### pacs:

03\. 67. Hk, 03. 65. Ud

_Introduction._ In 1999, C.H.Bennett (and his co-workers) introduced a new
form of quantum nonlocality, which serves to explore the fundamental question
about locally accessing global information encoded in a set of quantum states
Bennett99 . In his seminal work, Bennett showed the existence of nine product
states in bipartite system $\mathbb{C}^{3}\otimes\mathbb{C}^{3}$ that cannot
be perfectly distinguished by the separated subsystems, provided only local
operations and classical communications (LOCC) are available by them. He named
this phenomenon “quantume nonlocality without entanglement”, as opposed to the
stereotype of many people that to manifest nonlocality, existence of
entanglement is always required. Since then, such form of distinguishability-
based nonlocality has been studied extensively (see Bennett1999 ; Walgate00 ;
Walgate02 ; Ghosh01 ; Ghosh02 ; DiVicenzo03 ; Horodecki03  for an incomplete
list).

Although entanglement is not necessary for this form of nonlocality, lots of
evidence have been found showing that entangled states are generally more
difficult to be distinguished locally. For example, it has been shown by
Horodecki et al. that if a set of full orthogonal basis in an arbitrary two-
partite system is locally distinguishable, then they must be all product
states Horodecki03 . What is more, if at least one of the states among them is
entangled, then the set is not even probabilistically distinguishable locally.
In Hayashi06 , Hayashi et al. showed further that the maximal number of
orthogonal pure states that is perfectly distinguishable by LOCC is bounded
above by the total dimension of the two-partite system over the average
entanglement of the states. With that said, entanglement is to a large extent
responsible for local indistinguishability, thought there also exist
exceptions on some occasions Horodecki03 .

Notably, it can be duduced from the result of Hayashi et al that any $d+1$
orthogonal maximally entangled states in bipartite system
$\mathbb{C}^{d}\otimes\mathbb{C}^{d}$ must be locally indistinguishable. In
fact, this was first observed in Nathanson05  by Nathanson, who also proved
that any three maximally entangled states in
$\mathbb{C}^{3}\otimes\mathbb{C}^{3}$ are locally distinguishable. On the
other hand as for cases $d\geq 4$, examples were found by researchers that
$k\leq d$ locally indistinguishable orthogonal maximally entangled states
exist in $\mathbb{C}^{d}\otimes\mathbb{C}^{d}$ Yu12 ; Cosentino13 ;
CosentinoR14 ; Li15 ; Yu15 . In particular, Yu and Oh showed that the the
minimal number of locally indistinguishable maximally entangled states in
$\mathbb{C}^{d}\otimes\mathbb{C}^{d}$ can scale asymptotically down to $3d/4$
when $d$ is large. Nevertheless, a seemingly most simple problem whether there
exist three locally indistinguishable maximally entangled states in
$\mathbb{C}^{d}\otimes\mathbb{C}^{d}$ for $d>3$ remains unsolved today. What
is only known is the famous result by Walgate et al., who established that any
two orthongonal quantum states can always be locally distinguished Walgate00 .

In another seminal work in 1999, Bennett et al. also find the existence of
another set of five locally indistinguishable product states in
$\mathbb{C}^{3}\otimes\mathbb{C}^{3}$, namely the “unextendible product basis”
Bennett1999 . Intriguingly, ever since no smaller than five locally
indistinguishable product states has been found in any bipartite system by
researchers, as far as our best knowledge. To some extent, this provide yet
another example suggesting that entanglement can somehow raise difficulty in
local discrimination of quantum states, as locally indistinguishable sets of
three do exist when entanglement is available.

_Locally indistinguishable sets of three states._ In Ghosh01 , Ghosh et al.
showed the existence of three orthogonal states that cannot be perfectly
distinguished locally in bipartite system. Namely, the three Bell states

$\begin{split}&|\beta_{1}\rangle=\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle),\ \
|\beta_{2}\rangle=\frac{1}{\sqrt{2}}(|00\rangle-|11\rangle),\\\
&|\beta_{3}\rangle=\frac{1}{\sqrt{2}}(|01\rangle+|10\rangle)\end{split}$ (1)

in two-qubit system $\mathbb{C}^{2}\otimes\mathbb{C}^{2}$. Notice that the
two-states-distinguishability result of Walgate et al. holds even in the
multipartite scenarios, where all the subsystems are separated from each other
and only local measurements are allowed. Then a question naturally raise: what
is the minimal number of orthogonal states that are not locally
distinguishable for general $N$-partite systems ($N>2$)? The answer to such a
problem is yet trivial, for one can easily construct locally indistinguishable
sets of three $N$-partite states from the bipartite ones, say those of
(LABEL:Bell). For example, given an arbitrary bipartition $S|\overline{S}$ of
the subsystems $\\{\mathrm{A}_{1},\mathrm{A}_{2},\cdots,\mathrm{A}_{N}\\}$,
the three states

$\begin{split}&|\beta_{1}\rangle_{LR}\otimes|0\rangle^{\otimes N-2},\\\
&|\beta_{2}\rangle_{LR}\otimes|0\rangle^{\otimes N-2},\\\
&|\beta_{3}\rangle_{LR}\otimes|0\rangle^{\otimes N-2}\end{split}$ (2)

where $L\in S$ and $R\in\overline{S}$, or alternatively, the three states

$\begin{split}&|\psi_{1}\rangle_{S|\overline{S}}=\frac{1}{\sqrt{2}}\left(|0\rangle^{\otimes
N}+|1\rangle^{\otimes N}\right),\\\
&|\psi_{2}\rangle_{S|\overline{S}}=\frac{1}{\sqrt{2}}\left(|0\rangle^{\otimes
N}-|1\rangle^{\otimes N}\right),\\\
&|\psi_{3}\rangle_{S|\overline{S}}=\frac{1}{\sqrt{2}}\left(|0\rangle^{\otimes|S|}|1\rangle^{\otimes|\overline{S}|}+|1\rangle^{\otimes|S|}|0\rangle^{\otimes|\overline{S}|}\right)\end{split}$
(3)

which is locally equivalent to (LABEL:Bell) in $S|\overline{S}$, are all
locally indistinguishable, for indistinguishability even when some of the
subsystems combine does certainly implies indistinguishability when all the
subsystems are separated.

_Local irreducibility._ In Halder19 , Halder et al. put forward the notion of
“local irreducibility”. A set of orthogonal multipartite quantum states are
called locally irreducible if it is impossible to eleminate one or more states
from the whole set, with restriction that only orthogonality–preserving local
measurements (OPLM) are allowed. By definition, a locally irreducible set of
multipartite quantum states must be locally indistinguishable, while the
opposite is generally not true.

_Locally irreducible sets of three states._ In fact, the three states of both
(LABEL:2) and (LABEL:3) are also locally irreducible, because of the following
lemma that was established by Halder et al.:

_Lemma 1._ Halder19  Any set of three locally indistinguishable orthogonal
pure states must be locally irreducible.

It’s noteworthy that a recent work Cao23  also showed the existence of $d+1$
locally irreducible $N$-partite states in any system
$(\mathbb{C}^{d})^{\otimes N}$ wherever $d\geq 2$. Nevertheless, in the
context of multipartite (distinguishability-based) nonlocality, there are
other stronger paradigms that have been proposed.

_Genuine nonlocality and strong nonlocality._ A set of orthogonal multipartite
quantum states are called genuinely nonlocal if they cannot be locally
distinguished (perfectly) through any bipartition of the subsystems. It is
immediate that genuine nonlocality implies local indistinguishability due to
definition. In the literature, several techniques have been proposed for
detecting genuinely nonlocal sets of different types of multipartite quantum
states Halder19 ; Rout19 ; Li21 ; Rout21 ; shi ; xiong2023 ; xiong2024 . Among
such techniques, the so called “trivial orthogonality–preserving local
measurements” (TOPLM), which was originated from Walgate et al. Walgate02 , is
the most frequently applied one. Such a technique was first utilized by Halder
et al. for constructing genuinely nonlocal sets of product states in several
small multipartite systems Halder19 . Halder and his co-workers raised a new
notion named “strong nonlocality”, which refers to local irreducibility of the
multipartite quantum states within every bipartition of the subsystems.
However, it is usually not easy in practice to determine whether a set of
states are locally irreducible, except when the subsystems can only perform
“trivial orthogonality–preserving local measurements”. In the literature,
though lots of efforts have been paid in seeking strongly nonlocal sets in
multipartite systems, all existing examples by far are constructed through the
TOPLM technique(see Yuan20 ; Shi20 ; Wang21 ; Shi2022 ; Zhou22 ; Zhou23 ; Li23
; liji ; Hu24  for an incomplete list).

_Genuinely (strongly) nonlocal sets of three states._ Owing to Lemma 1 and
also the definition of strong nonlocality, any genuinely nonlocal set of three
states must also be strongly nonlocal. Since any two orthogonal states are
always locally distinguishable, they cannot be genuinely nonlocal. It’s then
natural to consider the existence of three genuinely nonlocal states in
multipartite systems. Actually, this seems so improbable that few of us would
ever be curious about it. By definition, genuine nonlocality is much stronger
than local indistinguishability, especially when a large number of subsystems
are considered. In the scenarios of large $N$, most but few, which means a
high proportion of the subsystems can join to access the global information
encoded in the set. Hence, to manifest nonlocality, it seems necessary that a
large numner of states are required. At least, it seems impossible that a
constant number of states suffices as $N$ grows. Recently in Li23 , Li and
Wang proved that in system $(\mathbb{C}^{d})^{\otimes N}$, any genuinely
nonlocal set constructed through the TOPLM technique must have cardinality no
smaller than $d^{N-1}+1$. The work xiong2024  challenged the effectiveness of
this technique by showing the existence of $d+1$ genuinely nonlocal GHZ states
in $(\mathbb{C}^{d})^{\otimes N}$. However, to achieve such a cardinality
“$d+1$”, the local dimension $d$ itself need to be sufficiently large. In
fact, the necessary $d$ there scales exponentially about $N$ as it grows. In
Li21 , the authors also consider this problem. They presented genuinely
nonlocal sets of product states with cardinality scaling linearly about $N$.

In this work, inspired by the analyses in xiong2024 , we show a somewhat
surprising result: in $(\mathbb{C}^{2})^{\otimes N}$ with arbitrarily large
$N$, there exist three orthongal quantum states that are not perfectly
distinguishable across any bipartition of the subsystems. Namely, the three
$N$-partite states are genuinely nonlocal, and thereby also strongly nonlocal.
Since $(\mathbb{C}^{2})^{\otimes N}$ can be embedded into any $N$-product
Hilbert space, there exist three genuinely (strongly) nonlocal quantum states
in any $N$-partite system.

Going back to the bipartite case, apart from the three Bell states
(LABEL:Bell), Ghosh and his co-workers also established the local
indistinguishability of the three states

$\begin{split}&|\beta_{1}\rangle=\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle),\ \
|\beta_{2}\rangle=\frac{1}{\sqrt{2}}(|00\rangle-|11\rangle),\\\
&|\alpha_{3}\rangle=|01\rangle\end{split}$ (4)

in $\mathbb{C}^{2}\otimes\mathbb{C}^{2}$ Ghosh02 . Ghosh et al. proved this
fact by calculating an upper bound on the distillable entanglement of an
ingeniously constructed four-party state, which will then induce a
contradiction provided local distinguishability assumption was made. Actually,
there are more concise ways to prove local indistinguishability of these
states: for example, it’s routine to prove that they are locally irreducible,
using the TOPLM technique as in Walgate02 . Here, we also point out that they
are indeed PPT-indistinguishable.

Figure 1: (a) The three Bell states (LABEL:Bell) in
$\mathbb{C}^{2}\otimes\mathbb{C}^{2}$; (b) States
$\\{|\beta_{1}\rangle,|\beta_{2}\rangle,|\alpha_{3}\rangle\\}$ in
$\mathbb{C}^{2}\otimes\mathbb{C}^{2}$. The dark tiles signify
$|\beta_{1}\rangle$ and $|\beta_{2}\rangle$, while the grey ones signify the
third states.

_Proposition 1._ The three orthogonal states
$\\{|\beta_{1}\rangle,|\beta_{2}\rangle,$ $|\alpha_{3}\rangle\\}$ in
$\mathbb{C}^{2}\otimes\mathbb{C}^{2}$ are PPT-indistinguishable.

_Proof._ Assume contrarily that
$\\{|\beta_{1}\rangle,|\beta_{2}\rangle,|\alpha_{3}\rangle\\}$ are PPT-
distinguishable. Then by definition, there must exist PPT-POVMs
$\\{M_{1},M_{2},M_{3}\\}$ (which means $M_{k},$ $M_{k}^{\mathrm{T_{A}}}\geq 0$
for $1\leq k\leq 3$) such that

$M_{1}+M_{2}+M_{3}=I_{2\otimes 2},$ (5)

and

$\begin{split}&\langle\beta_{1}|M_{1}|\beta_{1}\rangle=1,\ \ \
\langle\beta_{2}|M_{2}|\beta_{2}\rangle=1,\\\
&\langle\alpha_{3}|M_{3}|\alpha_{3}\rangle=1.\end{split}$

By routine calculation, there is

$\begin{split}&|\beta_{1,2}\rangle\langle\beta_{1,2}|^{\mathrm{T_{A}}}\\\ =\
&\frac{|00\rangle\langle 00|+|11\rangle\langle 11|\pm(|01\rangle\langle
10|+|10\rangle\langle 01|)}{2}\\\ \leq\ &\frac{1}{2}I_{2\otimes
2}.\end{split}$

Hence, we get

$\begin{split}1&=\mathrm{Tr}(M_{1,2}|\beta_{1,2}\rangle\langle\beta_{1,2}|)\\\
&=\mathrm{Tr}\left(M_{1,2}^{\mathrm{T_{A}}}|\beta_{1,2}\rangle\langle\beta_{1,2}|^{\mathrm{T_{A}}}\right)\leq\frac{1}{2}\
\mathrm{Tr}\left(M_{1,2}^{\mathrm{T_{A}}}\right)\end{split}$

and $\mathrm{Tr}(M_{1,2})=\mathrm{Tr}\left(M_{1,2}^{\mathrm{T_{A}}}\right)\geq
2$. However, by (5) we have

$\mathrm{Tr}(M_{1})+\mathrm{Tr}(M_{2})+\mathrm{Tr}(M_{3})=4,$

which forces $\mathrm{Tr}(M_{3})=0$. That is, $M_{3}=0$ and we get a
contradiction here. Thus, the three states
$\\{|\beta_{1}\rangle,|\beta_{2}\rangle,|\alpha_{3}\rangle\\}$ are PPT-
indistinguishable.

In fact, one can easily observe from the above proof that an arbitrary third
orthogonal state $|\gamma_{3}\rangle$ in $\mathbb{C}^{2}\otimes\mathbb{C}^{2}$
suffices to make
$\\{|\beta_{1}\rangle,|\beta_{2}\rangle,|\gamma_{3}\rangle\\}$ PPT-
indistinguishable. Inspired from this, one may naturally speculate that:

_Lemma 2._ In two-partite system
$\mathbb{C}^{m}\otimes\mathbb{C}^{n}\supsetneq\mathbb{C}^{2}\otimes\mathbb{C}^{2}$,
the set of three orthogonal states
$\\{|\beta_{1}\rangle,|\beta_{2}\rangle,|\delta_{3}\rangle\\}$ is PPT-
indistinguishable, whenever $|\delta_{3}\rangle$ has nonzero overlap with
subspace $\mathbb{C}^{2}\otimes\mathbb{C}^{2}$:

$\left(\sum_{i,j\in\\{0,1\\}}|ij\rangle\langle
ij|\right)|\delta_{3}\rangle\neq 0.$ (6)

_Proof._ The proof is similar to Lemma 3 of xiong2024 .

With Lemma 2, we can now construct genuinely nonlocal sets of three states in
multi-qubit systems. We first show some examples.

_Example 1._ (i) In
$\mathbb{C}^{2}\otimes\mathbb{C}^{2}\otimes\mathbb{C}^{2}$, the set of three
orthogonal states consisting of the three-qubit GHZ pair

$|\varphi_{1,2}\rangle=\frac{1}{\sqrt{2}}(|000\rangle\pm|111\rangle)$

and the W state

$|\varphi_{3}\rangle=\frac{1}{\sqrt{3}}(|001\rangle+|010\rangle+|100\rangle)$

is genuinely nonlocal. Here, the third state $|\varphi_{3}\rangle$ has nonzero
overlap with the $2\otimes 2$ product subspace
span$\\{|00\rangle,|11\rangle\\}$ $\otimes$ span$\\{|0\rangle,|1\rangle\\}$ in
each of the bipartitions AB$|$C, AC$|$B and BC$|$A and thus Lemma 2 can be
applied. For example, see FIG 2 (a) for bipartition AB$|$C.

Figure 2:  (a) States
$\\{|\varphi_{1}\rangle,|\varphi_{2}\rangle,|\varphi_{3}\rangle\\}$ in
bipartition AB$|$C; (b) States
$\\{|\phi_{1}\rangle,|\phi_{2}\rangle,|\phi_{3}\rangle\\}$ in bipartition
AB$|$CD. The dark tiles signify the GHZ pairs and the grey ones signify the
last W-like states.

(ii) In
$\mathbb{C}^{2}\otimes\mathbb{C}^{2}\otimes\mathbb{C}^{2}\otimes\mathbb{C}^{2}$,
the set of three orthogonal states consisting of the four-qubit GHZ pair

$|\phi_{1,2}\rangle=\frac{1}{\sqrt{2}}(|0000\rangle\pm|1111\rangle)$

and the W-like state

$\begin{split}\ \ \ \ \
|\phi_{3}\rangle=&\frac{1}{\sqrt{7}}\left(|0001\rangle+|0010\rangle+|0100\rangle+|1000\rangle\phantom{a^{b}}\right.\\\
&\left.\phantom{a^{b}}+|0011\rangle+|0101\rangle+|0110\rangle\right)\end{split}$

is also genuinely nonlocal. Similarly, the third state $|\phi_{3}\rangle$ has
nonzero overlap with the $2\otimes 2$ product subspaces
span$\\{|000\rangle,|111\rangle\\}$ $\otimes$ span$\\{|0\rangle,|1\rangle\\}$
and span$\\{|00\rangle,|11\rangle\\}$ $\otimes$
span$\\{|00\rangle,|11\rangle\\}$, across the four “3–1” bipartitions and the
three “2–2” bipartitions respectively. And then, Lemma 2 can be applied. See
FIG 2 (b) for the indistinguishability across bipartition AB$|$CD for example.

_Example 2._ (i) In
$\mathbb{C}^{2}\otimes\mathbb{C}^{2}\otimes\mathbb{C}^{2}$, the set consisting
of the three-qubit GHZ pair $|\varphi_{1,2}\rangle$ and a third state

$|\varphi^{\prime}_{3}\rangle=\frac{1}{\sqrt{6}}(|001\rangle+|010\rangle+|011\rangle+|100\rangle+|101\rangle+|110\rangle)$

is genuinely nonlocal. For example, see FIG 3 (a) for indistinguishability in
bipartition AB$|$C.

(ii) In
$\mathbb{C}^{2}\otimes\mathbb{C}^{2}\otimes\mathbb{C}^{2}\otimes\mathbb{C}^{2}$,
the set consisting of the four-qubit GHZ pair $|\phi_{1,2}\rangle$ and a third
state

$\begin{split}|\phi^{\prime}_{3}\rangle=\frac{1}{\sqrt{14}}&\left(|0001\rangle+|0010\rangle+|0011\rangle+\cdots\phantom{a^{b}\cdots\cdots}\right.\\\
&\left.\phantom{a^{b}\cdots\cdots}\cdots+|1100\rangle+|1101\rangle+|1110\rangle\right)\end{split}$

is also genuinely nonlocal. Again, see the indistinguishability across
bipartition AB$|$CD in FIG 3 (b) for example. Summing up, for general
$N$-partite system, we have:

_Theorem 1._ In $N$-qubit system $(\mathbb{C}^{2})^{\otimes N}$, the following
three orthogonal genuine multipartite entangled states are genuinely nonlocal:

$\begin{split}&|\Gamma_{1,2}\rangle=\frac{1}{\sqrt{2}}\left(|0\rangle^{\otimes
N}\pm|1\rangle^{\otimes N}\right)\\\ \\\
&|\Gamma_{3}\rangle=\frac{1}{\sqrt{|P|}}\sum_{i_{1}i_{2}\cdots i_{N}\in
P}|i_{1}i_{2}\cdots i_{N}\rangle,\\\ \end{split}$ (7)

where $P=\\{0,1\\}^{N}\backslash\\{00\cdots 0,11\cdots 1\\}$ and
$|P|=2^{N}-2$.

_Proof._ For any $i_{1}i_{2}\cdots i_{N}\in P$, denote by
$\overline{i_{1}i_{2}\cdots i_{N}}$ its bit-wise reverse. Each pair of
$i_{1}i_{2}\cdots i_{N}$ and $\overline{i_{1}i_{2}\cdots i_{N}}$ thus
corresponds to one of the total $|P|/2$ bipartitions of the $N$ subsystems.
Then, genuine nonlocality of the three states
$\\{|\Gamma_{1}\rangle,|\Gamma_{2}\rangle,|\Gamma_{3}\rangle\\}$ can be
directly deduced from Lemma 2.

Figure 3:  (a) States
$\\{|\varphi_{1}\rangle,|\varphi_{2}\rangle,|\varphi^{\prime}_{3}\rangle\\}$
in bipartition AB$|$C; (b) States
$\\{|\phi_{1}\rangle,|\phi_{2}\rangle,|\phi^{\prime}_{3}\rangle\\}$ in
bipartition AB$|$CD. The dark tiles signify the GHZ pairs and the grey ones
signify $|\varphi^{\prime}_{3}\rangle$ and $|\phi^{\prime}_{3}\rangle$.

Note that although such three states cannot be perfectly distinguished across
each bipartition, they can be distinguished with rather high probability.
Following the same vein, we can provide a slightly more generalized version of
Theorem 1, where the third state need not be genuinely entangled:

_Theorem 2._ In $N$-qubit system $(\mathbb{C}^{2})^{\otimes N}$, the set
consisting of the $N$-qubit GHZ pair $|\Gamma_{1,2}\rangle$ and a third state

$|\Gamma^{\prime}_{3}\rangle=\sum_{i_{1}i_{2}\cdots i_{N}\in
P}l_{i_{1}i_{2}\cdots i_{N}}\ |i_{1}\ i_{2}\ \cdots\ i_{N}\rangle$ (8)

is genuinely nonlocal, whenever the coefficients $l_{i_{1}i_{2}\cdots i_{N}}$
of $\Gamma^{\prime}_{3}$ satisfy:

$\sum_{i_{1}i_{2}\cdots i_{N}\in P}|l_{i_{1}i_{2}\cdots i_{N}}|^{2}=1$

and

$|l_{i_{1}i_{2}\cdots i_{N}}|^{2}+|l_{\overline{i_{1}i_{2}\cdots
i_{N}}}|^{2}>0.$ (9)

_Conclusion._ In this work, we show the existence of genuinely nonlocal sets
of three orthogonal quantum states in any $N$-partite system. Since any three
locally indistinguishable states are always locally irreducible, the three
states we present are also strongly nonlocal.

The notion of strong nonlocality was put forward by Halder et al. in Halder19
. There, the authors also questioned about the the existence of strong
nonlocality with genuine multipartite entanglement. The works Wang21 , Hu24
had already answered this question positively, yet the constructions there
require far more states than here. The strongly nonlocal sets we present are
the first examples in systems $(\mathbb{C}^{2})^{\otimes N}$ and their
caridnality is dramatically smaller than the known ones. Unlike locally
indistinguishable sets, however, the supersets of a locally irreducible set
may not be locally irreducible. Therefore, it’s natural to question further:
do strongly nonlocal sets of $d=4,5,\cdots$ states exist in $N$-partite
systems?

## References

  * (1) C. H. Bennett, D. P. DiVincenzo, C. A. Fuchs, T. Mor, E. Rains, P. W. Shor, J. A. Smolin and W. K. Wootters, Quantum nonlocality without entanglement,  Phys. Rev. A 59: 1070-1091 (1999)
  * (2) C. H. Bennett, D. P. DiVincenzo, T. Mor, P. W. Shor, J. A. Smolin and B. M. Terhal, Unextendible Product Bases and Bound Entanglement,  Phys. Rev. Lett. 82, 5385 (1999)
  * (3) J. Walgate, A. J. Short, L. Hardy and V. Vedral, Local Distinguishability of Multipartite Orthogonal Quantum States,  Phys. Rev. Lett. 85, 4972 (2000)
  * (4) J. Walgate and L. Hardy, Nonlocality, Asymmetry, and Distinguishing Bipartite States,  Phys. Rev. Lett. 89, 147901 (2002)
  * (5) S. Ghosh, G. Kar, A. Roy, A. Sen(De) and U. Sen, Distinguishability of Bell States,  Phys. Rev. Lett. 87, 277902 (2001)
  * (6) S. Ghosh, G. Kar, A. Roy, D.Sarkar, A. Sen(De) and U. Sen, Local indistinguishability of orthogonal pure states by using a bound on distillable entanglement,  Phys. Rev. A 65, 062307 (2002)
  * (7) D. P. DiVincenzo, T. Mor, P. W. Shor, J. A. Smolin and B. M. Terhal, Unextendible Product Bases, Uncompletable Product Bases and Bound Entanglement,  Commun. Math. Phys. 238, 379-410 (2003)
  * (8) M. Horodecki, A. Sen(De), U. Sen, and K. Hoeodecki, Local Indistinguishability: More Nonlocality with Less Entanglement,  Phys. Rev. Lett 90, 047902 (2003)
  * (9) H. Fan, Distinguishability and Indistinguishability by Local Operations and Classical Communication,  Phys. Rev. Lett. 92, 177905 (2004)
  * (10) M. Hayashi, D. Markham, M. Murao, M. Owari and S. Virmani, Bounds on Multipartite Entangled Orthogonal State Discrimination Using Local Operations and Classical Communication,  Phys. Rev. Lett 96, 040501 (2006)
  * (11) M. Nathanson, Distinguishing bipartitite orthogonal states using LOCC: Best and worst cases,  J. Math. Phys.  46, 062103(2005)
  * (12) N. Yu, R. Duan and M. Ying, Four Locally Indistinguishable Ququad-Ququad Orthogonal Maximally Entangled States,  Phys. Rev. Lett. 109, 020506 (2012)
  * (13) A. Cosentino, Positive-partial-transpose indistinguishable states via semidefinite programming,  Phys. Rev. A 87, 012321 (2013)
  * (14) A. Cosentino and V. Russo, Small sets of locally indistinguishable orthogonal maximally entangled states,  Quantum Inf. Comput. 14, 1098—1106 (2014)
  * (15) M. -S. Li, Y. -L. Wang, S. -M. Fei and Z. -J. Zheng, $d$ locally indistinguishable maximally entangled states in $\mathbb{C}^{d}\otimes\mathbb{C}^{d}$,  Phys. Rev. A 91,042318 (2015)
  * (16) S. Yu and C. H. Oh, Detecting the local indistinguishability of maximally entangled states,  (arXiv:1502.01274v1)
  * (17) H. -Q. Cao, M. -S. Li, H. -J. Zuo, Locally stable sets with minimum cardinality,  Phys. Rev. A 108, 012418 (2023)
  * (18) S. Halder, M. Banik M, S. Agrawal and S. Bandyopadhyay, Strong Quantum Nonlocality without Entanglement,  Phys. Rev. Lett. 122, 040403 (2019)
  * (19) S. Rout, A. G. Maity, A. Mukherjee, S. Halder and M. Banik, Genuinely nonlocal product bases: Classification and entanglement-assisted discrimination,  Phys. Rev. A 100, 032321 (2019)
  * (20) M. -S. Li, Y. -L. Wang, F. Shi and M. -H. Yung, Local distinguishability based genuinely quantum nonlocality without entanglement,  J. Phys. A: Math. Theor. 54, 445301 (2021)
  * (21) S. Rout, A. G. Maity, A. Mukherjee, S. Halder and M. Banik, Multiparty orthogonal product states with minimal genuine nonlocality,  Phys. Rev. A 104, 052433 (2021)
  * (22) F. Shi, M. -S. Li, X. Zhang and Q. Zhao, Unextendible and uncompletable product bases in every bipartition,  New J. Phys.  24, 113025 (2022)
  * (23) Z. -X. Xiong, M. -S. Li, Z. -J. Zheng, L. Li, Distin-guishability-based genuine nonlocality with genuine multipartite entanglement,  Phys. Rev. A 108, 022405 (2023)
  * (24) Z. -X. Xiong, Y. Zhang, M. -S. Li, L. Li, Small sets of genuinely nonlocal Greenberger-Horne-Zeilinger states in multipartite systems,  Phys. Rev. A 109, 022428 (2024)
  * (25) P. Yuan, G. Tian G and X. Sun, Strong quantum nonlocality without entanglement in multipartite quantum systems,  Phys. Rev. A 102, 042228 (2020)
  * (26) F. Shi, M. Hu, L. Chen and X. Zhang, Strong quantum nonlocality with entanglement,  Phys. Rev. A 102, 042202 (2020)
  * (27) Y. -L. Wang, M. -S. Li and M. -H. Yung, Graph-connectivity-based strong quantum nonlocality with genuine entanglement,  Phys. Rev. A 104, 012424 (2021)
  * (28) F. Shi, M. -S. Li, M. Hu, L. Chen, M. -H. Yung, Y. -L. Wang and X. Zhang, Strongly nonlocal unextendible product bases do exist,  Quantum 6, 619 (2022)
  * (29) H. Zhou, T. Gao and F. Yan, Orthogonal product sets with strong quantum nonlocality on a plane structure,  Phys. Rev. A 106, 052209 (2022)
  * (30) H. Zhou, T. Gao and F. Yan, Strong quantum nonlocality without entanglement in an n-partite system with even n,  Phys. Rev. A 107, 042214 (2023)
  * (31) M. -S. Li snd Y. -L. Wang, Bounds on the smallest sets of quantum states with special quantum nonlocality,  Quantum 7, 1101 (2023)
  * (32) J. Li, F. Shi and X. Zhang, Strongest nonlocal sets with small sizes,  Phys. Rev. A 108, 062407 (2023)
  * (33) M. Hu, T. Gao and F. Yan, Strong quantum nonlocality with genuine entanglement in an N-qutrit system,  Phys. Rev. A 109, 022220 (2024)