#  tsdataleaks: An R Package to Detect Potential Data Leaks in Forecasting
Competitions

by Thiyanga S. Talagala, Department of Statistics, Faculty of Applied
Sciences,
University of Sri Jayewardenepura
<EMAIL_ADDRESS>
###### Abstract

Forecasting competitions are of increasing importance as a means to learn best
practices and gain knowledge. Data leakage is one of the most common issues
that can often be found in competitions. Data leaks can happen when the
training data contains information about the test data. There are a variety of
different ways that data leaks can occur with time series data. For example:
i) randomly chosen blocks of time series are concatenated to form a new time
series; ii) scale-shifts; iii) repeating patterns in time series; iv) white
noise is added to the original time series to form a new time series, etc.
This work introduces a novel tool to detect these data leaks. The tsdataleaks
package provides a simple and computationally efficient algorithm to exploit
data leaks in time series data. This paper demonstrates the package design and
its power to detect data leakages with an application to forecasting
competition data.

## 1 Statement of Need

Time series forecasting competitions have played a significant role in the
advancement of forecasting practices. Typically, in forecasting competitions,
a collection of time series is given to the participants, and then the
participants submit the forecasts for the required test period for each time
series. During the competition period, only the training set for each time
series is given to the public, and the test set is kept private from the
public. Finally, competition organizers evaluate the forecast accuracy by
comparing each participants submitted forecast values against the actual test
period values. Participating in forecasting competitions not only aids in the
identification of novel methods and facilitates their performance comparison
against existing state-of-the-art forecasting techniques, as highlighted by
Hyndman 2020, but also provides empirical evidence crucial for enhancing
forecasting performance and advancing the theory and practice of forecasting
(Makridakis et al., 2022).

Figure 1: An example of a time series data leak. "A" and "B"" are two time
series. The green vertical line and yellow background separate the training
and test parts of the series. A training segment of series B (red colour
segment) is the source of the latter segment of the training set and test set
of the A series.

Data leakage occurs when the training period of the time series includes test
period data before officially releasing the test period of the time series.
This idea is illustrated in Figure 1. A and B are two time series. The latter
segment of the training set and the subsequent test set within the (A) series
are the same as the red segment highlighted in the training segment inherent
to series (B). This type of data leak could occur when randomly chosen blocks
of time series are concatenated to form a new time series.

Competitions with data leaks will not be able to reach their original purpose.
By exploiting data leakage, competitors can obtain a top rank in the leader
board. Such models look highly accurate within the competition environment but
become inaccurate when applied to a data set outside the competition
environment. Hence, there is an increasing need to examine the potential data
leaks in time series before the release of data to the public. The tsdataleaks
package is designed to identify data leaks in time series.

## 2 State of the Field in R

As of the latest information available on the Comprehensive R Archive Network
(CRAN) Task View: Time Series Analysis (Rob J Hyndman, 2023), there is no
package available for detecting data leakages.

## 3 Algorithm

The algorithm operates as follows: the algorithm begins by selecting the final
segment of the training section in each time series within the collection.
Subsequently, those segments iterates through all of the time series one time
step at a time and calculate Pearson’s correlation coefficient. Hence, the
inputs to the algorithm are: i) the time series collection; ii) segment
length; and iii) the cut-off value for the correlation coefficient. A data
leak is indicated if the Pearson’s correlation coefficient’s absolute value
exceeds the cutoff value. The algorithm returns the starting and end indexes
of the segments that match each time series’ last segment corresponds to the
training part.

Table 1: Algorithm: Time Series Matching Input:
---
1\. lstx: A collection of time series as a list in R.
2\. h: Length of the segment to be considered.
3\. cutoff: Cut-off value for the absolute value of the Pearson’s correlation
coefficient.
Output:
A list containing starting and ending indices of segments that match each time
series’ last segment of the training set.
Steps:
1\. Extract the last segment of the training part with length h.
2\. Loop through the time series with one time step, considering each segment:
\- Calculate the Pearson’s correlation coefficient between the current segment
of a time series and the last portion of the training segment that was
retrieved.
\- If the correlation coefficient is above the cutoff:
\- Return the matching segments list with the starting and ending indices of
the matching segments.
3\. Return the matching segments list as the output.

Figure 2 illustrates the first iteration of the algorithm. The correlation
between the purple segment and observations 1–6 (dark green section) of the
first time series is measured at the first iteration.

Figure 3 visualize the second iteration of the algorithm. The correlation
between the purple segment and observations 2–7 (dark green section) of the
first time series is measured at the second iteration. Figure 4 illustrates an
intermediate step of the algorithm.

Figure 2: Visualization of the first iteration of the algorithm. The last
segment of the training part of the first series is colored purple. As the
first step of the algorithm, it computes Pearson’s correlation coefficient
between the observations 1-6 (dark green section) and the purple segment.
Figure 3: Visualization of the second iteration of the algorithm. The last
segment of the training part of the first series is colored purple. As the
second step of the algorithm, it computes Pearson’s correlation coefficient
between the observations 2-7 (dark green section) and the purple segment.
Figure 4: Intermediate step of the algorithm: identification of potential data
leaks. The light purple section of the fourth series perfectly correlates with
the last segment of the first series. Hence, the red section of the fourth
series could be the test part of the first series.

## 4 Usage

### Installation

The package tsdataleaks is available on both CRAN and GitHub
(https://github.com/thiyangt/tsdataleaks) and can be installed and loaded into
the R session using:

    install.packages("tsdataleaks")
    library(tsdataleaks)

or

    devtools::install_github("thiyangt/tsdataleaks")
    library(tsdataleaks)

### Functionality

There are three functions in the package: i) ‘find_dataleaks‘, ii)
‘viz_dataleaks‘, and iii) ‘reason_dataleaks‘. To demonstrate the package
functions, a small time series collection with three time series is created.

    set.seed(2024)
    x <- rnorm(15)
    lst <- list(
      x = x,
      y = c(rnorm(10), x[1:5]),
      z = c(rnorm(10), x[10:15]))

Following are the steps for detecting data leakages and visualizing the
results.

Step 1: The main function in the package is ‘find_dataleaks‘. It exploits the
data leakages according to the algorithm. The inputs to the function are a
list of time series collections (lstx), the length of the segment to be
considered (h), and the cutoff value for the absolute value of Pearson’s
correlation coefficient (cutoff). The ‘f1‘ output is shown in Figure 5
(step1).

    f1 <- find_dataleaks(lstx = lst, h=5, cutoff=1)

Step 2: ‘viz_dataleaks‘ function arranges the results of ‘find_dataleaks‘ in
matrix form and visualizes them for easy understanding, as shown in Figure 5
(step2).

    viz_dataleaks(f1)

Step 3: ‘reason_dataleaks‘ displays the reasons for data leaks and evaluates
the usefulness of data leaks towards the winning of the competition. The
inputs to the function are a list of time series collections (lstx), length of
the segment to be considered (h), output of the find_dataleaks function
(finddataleaksout). The corresponding outputs are shown in Figure 5 (step3).

    reason_dataleaks(lstx = lst, finddataleaksout = f1, h=5)

Figure 5: The outputs of f1, viz_dataleaks(f1) and reason_dataleaks(lstx =
lst, finddataleaksout = f1, h=5)

According to the Figure 5 step 1 results, the last part of the training set in
x series perfectly correlates with z series: 12–16 observations; the last part
of y series correlates with x series: 1–5 observations; and the last part of z
series correlates with x series: 11–15 observations. However, according to the
step 3 results, only "the last part of the y series correlates with the x
series: 1–5 observations" identification is useful in winning the competition.
The reason is that we have x-series 6:10 observations. Hence, we can use that
as the test value of the y series. "The last part of the z series correlates
with x series: 11–15 observations"-This identification is not useful in
winning the competition because x series: 16–20 observations are not
available. In this example, all data leakages occur due to an exact match.

## 5 Appication to the M1 Competition Yearly Time Series Data

M-competitions is a series of time-series forecasting competitions organized
by Spyros Makridakis and his team (Makridakis et al., 2020). M1-competition
data is available in the package Mcomp Hyndman 2018. Before applying the
find_dataleaks function, all of the training sets of yearly series are stored
in a list called ‘M1Y_x‘. In the M1 competition, the length of the test period
for the yearly series is 6. Hence, the ‘h‘ value is selected as 6. The cutoff
value for the absolute value of Pearson’s correlation coefficient is 1. The
results are shown in Figure 6.

    library(Mcomp)
    data("M1")
    M1Y <- subset(M1, "yearly")
    M1Y_x <- lapply(M1Y, function(temp){temp$x})
    m1y_f1 <- find_dataleaks(M1Y_x, h=6, cutoff = 1)
    viz_dataleaks(m1y_f1)
    reason_dataleaks(M1Y_x, m1y_f1, h=6, ang=90)

Figure 6: Outputs of viz_dataleaks(m1y_f1) and reason_dataleaks(M1Y_x, m1y_f1,
h=6, ang=90)

According to Figure 6, there are 7 data leakage detentions. Out of them, only
three are useful in winning the competition. Two data leakages are due to an
exact match; the other is due to a linear transformation of the form $y=mx+c$.

### Documentation and Examples

Applications to other examples can be found in the README.md file at
https://github.com/thiyangt/tsdataleaks.

## 6 Conclusion

The new open-source R package described in this paper enables: i) exploiting
data leakages; ii) identifying the reasons for data leakage as exact matches
or adding a constant or other transformations. iii) determining whether the
data leakages identified are useful in winning the forecast competition; and
iv) visualizing the results. The R package tsdataleaks is a valuable tool for
competition organizers to avoid data leakages, participants to detect data
leakages, and the entire forecasting research community to evaluate the
quality of data.

## 7 Reproducibility

Codes to generate this manuscript is available at
https://github.com/thiyangt/tsdataleaks/blob/master/paper/paper.md

## References

  * Hyndman (2018) R. Hyndman.  Mcomp: Data from the m-competitions.  2018\.  URL https://CRAN.R-project.org/package=Mcomp.  R package version 2.8.
  * Hyndman (2020) R. J. Hyndman.  A brief history of forecasting competitions.  _International Journal of Forecasting_ , 36(1):7–14, 2020.
  * Makridakis et al. (2020) S. Makridakis, E. Spiliotis, and V. Assimakopoulos.  The m4 competition: 100,000 time series and 61 forecasting methods.  _International Journal of Forecasting_ , 36(1):54–74, 2020.
  * Makridakis et al. (2022) S. Makridakis, E. Spiliotis, and V. Assimakopoulos.  M5 accuracy competition: Results, findings, and conclusions.  _International Journal of Forecasting_ , 38(4):1346–1364, 2022.
  * Rob J Hyndman (2023) R. K. Rob J Hyndman.  CRAN task view: Time series analysis, 2023.  URL https://cran.r-project.org/web/views/TimeSeries.html.  Version 2023-12-01.

_Thiyanga S. Talagala
Department of Statistics
Faculty of Applied Sciences
University of Sri Jayewardenepura, Sri Lanka
https://github.com/thiyangt/ceylon
ORCiD: 0000-0002-0656-9789X
<EMAIL_ADDRESS>


ATL-PHYS-PROC-2020-004

Overview of Recent Results from ATLAS

Craig Wiglesworth, on behalf of the ATLAS Collaboration

Niels Bohr Institute, Blegdamsvej 17, 2100 Copenhagen, Denmark

> This paper presents an overview of recent results from the ATLAS Experiment
> at the CERN Large Hadron Collider, with a particular focus on those that are
> based on the entire Run 2 dataset of $\sqrt{s}$=13 TeV proton-proton
> collisions. These results include Standard Model measurements, updates on
> the Higgs Boson properties, as well as searches for high-mass resonances and
> supersymmetry.

> PRESENTED AT
>
>
>
>
> $12^{\mathrm{th}}$ International Workshop on Top Quark Physics
> Beijing, China, September 22–27, 2019

## Introduction

The Large Hadron Collider (LHC) [1] has performed exceptionally well in 2018,
achieving a peak instantaneous luminosity of 2.1x1034 cm-2s-1 [2] \- more than
twice its design luminosity. Similarly, the ATLAS Detector [3] continues to
improve year-on-year, with data-taking and data-quality efficiencies in 2018
of 95.7% [2] and 97.5% [4], respectively. Across the entire Run-2 data-taking
period (2015-2018) ATLAS has collected a dataset of $\sqrt{s}=$13 TeV proton-
proton collisions, corresponding to an integrated luminosity of 139 fb-1 [2].

The ATLAS Experiment has a broad physics programme that includes: probing the
Standard Model (SM), precision measurements of the Higgs boson and searches
for physics beyond the SM (BSM), such as supersymmetry (SUSY) and other exotic
phenomena. This paper presents a non-comprehensive selection of recent results
which, unless otherwise stated, are based on the entire Run 2 dataset of
$\sqrt{s}$=13 TeV proton-proton collisions. In addition to the statistical
improvements owing to a larger dataset, a number of systematic improvements in
reconstruction and analysis techniques have contributed to increased
sensitivities with respect to previous ATLAS results.

## Overview of Recent Results

Following the discovery of the Higgs boson, scrutiny of the electroweak
symmetry breaking (EWSB) has become a major focus at the LHC. In addition to
direct measurements of Higgs boson properties, the study of massive vector-
boson scattering (VBS) offers another key avenue to probe EWSB. The signature
of VBS is a pair of vector-bosons and two hadronic jets, denoted as $VVjj$.
The electroweak production of $WWjj$ and $WZjj$ have already been observed in
ATLAS [5, 6], with no obvious deviations from the predictions of the SM. A
complementary search for the electroweak production of $ZZjj$ has been
performed, in which the 4-lepton and 2-lepton 2-neutrino final states were
considered [7]. The search uses multivariate discriminants based on event
kinematics, trained separately in each channel to enhance the separation
between the signal and backgrounds. By combining the two search channels a
deviation from the background-only hypothesis is observed, corresponding to a
statistical significance of 5.5 standard deviations ($\sigma$). This observed
excess is consistent with the electroweak production of a $Z$ boson pair in
association with two hadronic jets and provides the first observation of the
electroweak production of $ZZjj$.

The large cross section for $t\overline{t}$ production at the LHC allows ATLAS
to measure the properties of the top-quark through the study of its decay
products. One such property is the $t\overline{t}$ charge asymmetry $A_{C}$,
representing the central-forward charge asymmetry that originates from the
interference of higher-order amplitudes in $q\overline{q}$ and $qg$ initial
states. $A_{C}$ is defined as,

$A_{C}=\frac{N(\Delta|y|>0)-N(\Delta|y|<0)}{N(\Delta|y|>0)+N(\Delta|y|<0)}$

Figure 1: The measured charge asymmetry as a function of the invariant mass of
the $t\overline{t}$ system. The green regions show the SM predictions, whilst
the red regions show the charge asymmetry in simulated events [8].

where $\Delta|y|=|y_{t}|-|y_{\overline{t}}|$ is the difference in the absolute
values of rapidity for $t$ and $\overline{t}$. Several BSM models predict
charge asymmetries that vary as a function of the invariant mass
($m_{t\overline{t}}$) and the longitudinal boost along the z-axis
($\beta_{z,t\overline{t}}$) of the $t\overline{t}$ system. A measurement of
$A_{C}$ has been performed in the single lepton channel, combining both the
resolved and boosted topologies of top quark decays [8]. A Bayesian unfolding
procedure is used to infer the asymmetry at parton level, correcting for
detector resolution and acceptance effects. The inclusive $t\overline{t}$
charge asymmetry is measured to be $A_{C}$ = 0.0060 $\pm$ 0.0015, which
differs from zero by 4 $\sigma$ and provides the first evidence of
$t\overline{t}$ charge asymmetry at the LHC. Differential measurements have
also been performed as a function of $m_{t\overline{t}}$ and
$\beta_{z,t\overline{t}}$. Both the inclusive and differential measurements
are found to be compatible with the predictions of the SM, as illustrated in
Figure 1 which shows the differential measurement as a function of
$m_{t\overline{t}}$.

A direct measurement of the top-quark decay width ($\Gamma_{t}$) has also been
performed in dileptonic decays of $t\overline{t}$ events [9]. Many BSM models
predict a top-quark decay width that differs from the prediction of the SM.
Any deviation in the top-quark decay width from the expected SM value could
therefore hint at new physics, such as non-SM decays of the top-quark or
modifications of top-quark couplings. The measurement is based on the
invariant mass of the charged lepton and the corresponding $b$-jet, which is
used in a profile-likelihood fit with simulated templates for various top-
quark decay widths. The decay width is measured to be $\Gamma_{t}$ = 1.9 $\pm$
0.5 GeV, in agreement with the prediction of the SM.

All major production and decay modes of the Higgs boson have now been observed
in ATLAS, as we move into the realm of precision Higgs physics. Combined
measurements of the total and differential Higgs boson production cross
sections have been performed [10], based on recently updated measurements in
the $H{\rightarrow}\gamma\gamma$ [11] and
$H{\rightarrow}ZZ^{*}{\rightarrow}$4$l$ [12] decay modes. The total Higgs
boson production cross section is measured to be 55.4${}^{+4.3}_{-4.2}$ pb,
corresponding to an uncertainty of approximately 8%. The cross sections
measured in each of the individual decay modes and the combined measurements
are all in agreement with the SM prediction, as shown in Figure 2.

Figure 2: The measured total production cross section along with those
measured at $\sqrt{s}$=7 and 8 TeV (left) and the differential production
cross section as a function of the Higgs boson transverse momentum $p_{T,H}$
(right). In both cases the predictions of the SM are shown for comparison
[10].

The interactions between the Higgs boson and charged, third generation
fermions have already been observed at the LHC although there is, as of yet,
no evidence of Higgs boson interactions with first or second generation
fermions. A search for the $H{\rightarrow}\mu\mu$ decay has been performed
[13], in which any deviation from the prediction of the SM could be a sign of
new physics. No significant excess is observed above the expected background
and the observed upper limit at the 95% Confidence Level (CL) on the cross
section times branching ratio is 1.7 times the SM prediction. Similar searches
have been performed for the $H{\rightarrow}ee$ decay and the lepton-flavour-
violating $H{\rightarrow}e\mu$ decay [14]. In both cases no significant excess
is observed above the expected background - in agreement with the SM
expectation. The observed upper limits at the 95% CL on the branching
fractions of $H{\rightarrow}ee$ and $H{\rightarrow}e\mu$ are 3.6x10-4 and
6.1x10-5, respectively. These results represent considerable improvements in
sensitivity with respect to previous measurements.

The production of a pair of Higgs bosons ($HH$) is a rare process in the SM,
although a number of BSM models predict cross sections for $HH$ production
that are much larger than that of the SM. A search for the
$HH{\rightarrow}b\overline{b}b\overline{b}$ process via Vector Boson Fusion
(VBF) production has been performed using 126 fb-1 of $\sqrt{s}=$13 TeV
proton-proton collision data [15]. The search is sensitive to VBF production
of additional heavy bosons that may decay to Higgs boson pairs and, in a non-
resonant topology, can constrain the 4-point ($VVHH$) coupling, $c_{2V}$. No
significant excess is observed above the expected background. Upper limits are
set on the cross section for resonant $HH$ production in the range 260 GeV to
1000 GeV at the 95% CL. The observed upper limit at the 95% CL on the cross
section for non-resonant production is 1600 fb, with the observed excluded
region corresponding to $c_{2V}<$-1.02 and $c_{2V}>$2.71.

A number of exotic BSM models such as Grand Unified models predict the
existence of heavy particles, whose decays could be observed as a resonance or
a localised excess on top of a smoothly falling background distribution. ATLAS
has performed a number of searches for such heavy particles but, as of yet, no
excess has been observed above the expected background.

A search for high-mass dielectron and dimuon resonances has been performed
and, in the context of various benchmark models, lower limits are set on the
mass of a $Z^{\prime}$ resonance [16]. In particular, combined lower limits of
4.5 TeV and 5.1 TeV are set at 95% CL on the $Z^{\prime}_{\psi}$ of an
E6-motivated Grand Unified model and the $Z^{\prime}_{SSM}$ of the Sequential
SM (SSM), respectively. These are the most stringent limits to date.

A search for a heavy charged boson resonance decaying to a charged lepton and
a neutrino has also been performed [17]. Lower limits of 6.0 TeV and 5.1 TeV
on the $W^{\prime}$ boson mass are set at 95% CL in the electron and muon
channels, respectively, in the context of the SSM. To allow for further
interpretations of the results, a set of model-independent upper limits are
determined for the number of signal events and for the visible cross section
above a given transverse mass threshold.

Excited quarks ${q^{*}}$ are predicted in models of compositeness and are a
typical benchmark for quark-gluon resonances. A search for high-mass
resonances decaying into two hadronic jets has been performed [18]. Excited
quarks with masses below 6.7 TeV are excluded at the 95% CL. The results
substantially extend the excluded ranges by approximately 700 GeV, with
respect to the mass limits of ${q^{*}}$ models obtained in previous searches.

Heavy vector boson resonances are predicted in several extensions to the SM. A
search for such diboson resonances in the fully hadronic final state has been
performed [19] and exclusion limits are set on resonances in a range of BSM
models. The highest excluded mass at 95% CL for a heavy vector boson resonance
is 3.8 TeV, in the context of a benchmark heavy vector triplet model in which
resonances couple predominantly to gauge bosons.

Extensions of the SM involving SUSY are appealing from a theoretical
perspective, due to their potential to alleviate the problem of naturalness. A
number of searches have been performed for both strong and electroweak SUSY in
ATLAS but, as of yet, no significant excess has been observed above the
expected background.

The supersymmetric partner of the top-quark, the top-squark, is of particular
interest as it may largely cancel divergent loop corrections to the Higgs-
boson mass. A search for the direct production of top-squark pairs has been
performed, focusing on one particular scenario whereby each top-squark decays
via a 3-body process to a $b$-quark, a $W$ boson and a neutralino [20].
Exclusion limits at the 95% CL are set on the considered benchmark model, as
shown in Figure 4. The result excludes top-squark masses up to 720 GeV with
neutralino masses up to 580 GeV.

SUSY models with a light tau-slepton, the supersymmetric partner of the tau
lepton, are also of interest since they can lead to a dark matter relic
density consistent with cosmological observations. A search for the direct
production of tau-slepton pairs in final states with two hadronically decaying
tau leptons has been performed [21]. Exclusion limits are set at the 95% CL on
a simplified model in which two mass-degenerate tau-sleptons each decay into a
tau lepton and a neutralino, as shown in Figure 4. The result extends the
lower mass limit of 86.6 GeV previously set at the Large Electron Positron
collider (LEP).

Figure 3: Exclusion limits on top-squark pair production. The mass of the top-
squark is shown on the x-axis, while the mass of the neutralino is shown on
the y-axis [20].

Figure 4: Exclusion limits on tau-slepton pair production. The mass of tau-
slepton is shown on the x-axis, while the mass of the neutralino is shown on
the y-axis [21].

Many other BSM models predict long-lived, weakly interacting particles that
can generate a variety of unconventional signatures for which there are often
no irreducible SM backgrounds. A search for long-lived particle decays
involving a displaced vertex and displaced muon has been performed using 136
fb-1 of $\sqrt{s}=$13 TeV proton-proton collision data [22]. Exclusion limits
are set in the context of a SUSY model in which a pair of long-lived top-
squarks decay via a small R-parity-violating coupling to a quark and a muon.
Top-squarks with masses up to 1.7 TeV for a lifetime of 0.1 ns and below 1.3
TeV for all lifetimes between 0.01 ns and 30 ns, are excluded at the 95% CL.

In addition to the many results based on proton-proton collision data, a
search for the rare process of light-by-light scattering has been performed in
a data sample of $Pb$+$Pb$ collisions at $\sqrt{s_{NN}}$ = 5.02 TeV [23].
Light-by-light scattering can occur in relativistic heavy-ion collisions at
impact parameters larger than approximately twice the radius of the ions
where, in these ultra-peripheral collision events, the strong interaction
becomes less significant than the electromagnetic interaction. In the SM the
process occurs at one-loop level at order $\alpha_{em}^{4}$, via virtual box
diagrams involving electrically charged fermions or $W^{\pm}$. However, in
various extensions of the SM, extra contributions are possible, making the
process sensitive to new physics. Light-by-light scattering events are
characterised by the exclusive production of two low-energy photons in an
otherwise empty event. In a dataset of 1.73 nb-1 an excess of such events is
observed with respect to the background-only hypothesis. The observed excess
corresponds to a statistical significance of 8.2 $\sigma$ and is consistent
with the SM prediction. This result demonstrates the power and flexibility of
the ATLAS Detector, which was primarily designed for very different event
topologies.

## Conclusions

An overview of recent results from the ATLAS Experiment at the CERN Large
Hadron Collider has been presented, including some of the first results based
on the entire Run 2 dataset of $\sqrt{s}$ = 13 TeV proton-proton collisions.
Highlights include: the observation of the electroweak production of a $Z$
boson pair in association with two hadronic jets; the first evidence of charge
asymmetry in $t\overline{t}$ pairs at the LHC; precision measurements of the
Higgs boson production cross section and the observation of light-by-light
scattering in $Pb$+$Pb$ collisions. So far, all experimental results have been
consistent with the predictions of the Standard Model.

Copyright CERN for the benefit of the ATLAS Collaboration. CC-BY-4.0 license.

## References

  * [1] L. Evans and P. Bryant, JINST 3 (2008) S08001.
  * [2] https://twiki.cern.ch/twiki/bin/view/AtlasPublic/LuminosityPublicResultsRun2
  * [3] ATLAS Collaboration, JINST 3 (2008) S08003.
  * [4] https://twiki.cern.ch/twiki/bin/view/AtlasPublic/RunStatsPublicResults2010
  * [5] ATLAS Collaboration, Phys. Rev. Lett. 123 (2019) no.16, 161801
  * [6] ATLAS Collaboration, Phys. Lett. B 793 (2019) 469
  * [7] ATLAS Collaboration, ATLAS-CONF-2019-033.
  * [8] ATLAS Collaboration, ATLAS-CONF-2019-026.
  * [9] ATLAS Collaboration, ATLAS-CONF-2019-038.
  * [10] ATLAS Collaboration, ATLAS-CONF-2019-032.
  * [11] ATLAS Collaboration, ATLAS-CONF-2019-029.
  * [12] ATLAS Collaboration, ATLAS-CONF-2019-025.
  * [13] ATLAS Collaboration, ATLAS-CONF-2019-028.
  * [14] ATLAS Collaboration, Phys. Lett. B 801 (2020) 135148
  * [15] ATLAS Collaboration, ATLAS-CONF-2019-030.
  * [16] ATLAS Collaboration, Phys. Lett. B 796 (2019) 68
  * [17] ATLAS Collaboration, Phys. Rev. D 100 (2019) no.5, 052013
  * [18] ATLAS Collaboration, arXiv:1910.08447 [hep-ex].
  * [19] ATLAS Collaboration, JHEP 1909 (2019) 091
  * [20] ATLAS Collaboration, ATLAS-CONF-2019-017.
  * [21] ATLAS Collaboration, arXiv:1911.06660 [hep-ex].
  * [22] ATLAS Collaboration, ATLAS-CONF-2019-006.
  * [23] ATLAS Collaboration, Phys. Rev. Lett. 123 (2019) no.5, 052001


# Reframing the Event Horizon: The Harlow-Hayden Computational Approach to the
Firewall Paradox

Galina Weinstein  Reichman University, The Efi Arazi School of Computer
Science, Herzliya; University of Haifa, The Department of Philosophy, Haifa,
Israel.

###### Abstract

This study critically reevaluates the Harlow-Hayden (HH) solution to the black
hole information paradox and its articulation in the firewall paradox. The
exploration recognizes the HH solution as a revolutionary approach in black
hole physics, steering away from traditional constraints to depict the event
horizon as a computational rather than a physical barrier. The paper first
maps the initial physical dilemma that instigated the HH journey, introducing
Alice, an observer facing intricate computational challenges as she approaches
the black hole. I then depict the evolution of the narrative, describing how
Alice was facilitated with a quantum computer to surmount the computational
challenges and further detailing the augmented complexities arising from the
integration of the physical dynamics of the black hole. Yet, HH’s research
applies the AdS/CFT correspondence to explore the dynamic unitary
transformation in solving the firewall paradox through decoding Hawking
radiation. However, it identifies a contradiction; the eternal perspective of
black holes from the AdS/CFT theory challenges the firewall paradox’s
foundation. Finally, I narrate a paradigm shift as HH reframes Alice’s task
within the realms of error-correcting codes, illustrating a remarkable
transition from a physical problem in black hole physics to a computational
predicament in computer science. The study revisits pivotal moments in
understanding black hole physics ten years later through this reexamination.

##  1 Introduction

In this study, I re-examine the Harlow-Hayden (HH) solution [Har-Hay] to the
black hole information paradox and its manifestation in the firewall paradox
[AMPS]. The initiation of the HH solution heralded a pivotal moment in
studying black hole physics. It deviated from the traditional analysis
confined by spatial and temporal borders, proposing a fresh perspective
wherein the event horizon is perceived more as a barrier dictated by
computational hurdles rather than mere physical limits.

I initiate in section 2 with a concise historical introduction where I
elucidate the concepts of Hawking radiation, the monogamy of entanglement, and
the firewall paradox, setting a firm foundation for the ensuing discussion.
Following this, I delve into a detailed re-evaluation of the HH solution to
the firewall paradox.

The initial approach of HH was grounded in addressing a physical dilemma, a
prevalent strategy to untangle the intricacies of the Hawking information
paradox during that period, explored in detail in section 3. Alice, the
observer descending into the black hole, faces a computationally daunting
challenge. To navigate this, HH empowered Alice with a quantum computer; a
development unfolded in section 4. The narrative evolves by integrating
physical insights concerning black hole dynamics in section 5, yet Alice
encounters additional complexities.

Adapting to the unfolding scenario, HH redefined Alice’s mission in the
context of error-correcting codes, elucidated in section 6. Epistemically,
this transformative journey took us from grappling with a physical conundrum
rooted in black hole physics to ultimately contending with a computational
issue in the domain of computer science.

##  2 Hawking radiation and the firewall paradox

According to classical general relativity, nothing can escape from the event
horizon of a black hole. However, in 1974, Hawking penned a letter to _Nature_
, provocatively titled ”A Black Hole Explosion?”. In this letter, Hawking
intended to demonstrate that significant quantum effects might be associated
with black holes [Haw74]. In a reflection three years later, Hawking detailed
the initial realization that catalyzed his novel hypothesis, stating, ”To my
great surprise, I found,” back in 1974, ”that the black hole seemed to emit
particles at a steady rate. Like everyone else at that time, I accepted the
dictum that a black hole could not emit anything. I therefore invested
substantial effort into dismissing this unsettling result, but it persistently
refused to disappear, forcing me to eventually accept it” [Haw77].

Crucially, this hypothetical radiation arises due to how observers at infinity
categorize scalar field modes. This classification is discontinuous at the
black hole’s horizon and disregards all information about the modes within the
horizon. Contrarily, an observer plunging into the black hole wouldn’t
perceive any particle creation, as they wouldn’t employ such a discontinuous
division but rather analyze the field through modes continuous at the event
horizon [Haw76].

Hawking radiation can be conceptualized as follows: Near the event horizon of
a black hole, a particle-antiparticle pair spontaneously forms due to quantum
fluctuations. One particle, which we will denote as $A$, falls into the black
hole possessing negative energy, while the other particle, $B$, escapes with
positive energy. Despite being separated, particles $A$ and $B$ remain
entangled, ensuring energy conservation in the system. Over time, this process
leads to continuous emission of particles ($B$) away from the black hole, a
phenomenon termed Hawking radiation. Meanwhile, the absorption of negative
energy particles ($A$) gradually decreases the black hole’s mass and energy,
eventually leading to its complete evaporation.

We face a perplexing question when we consider what happens to the information
that enters a black hole. According to the no-hair theorem, a black hole is
characterized solely by three parameters: mass, angular momentum, and electric
charge. It ostensibly retains no other details about the matter it engulfs,
suggesting that a vast amount of information becomes irrevocably lost during
the process of gravitational collapse. This proposition seems to violate the
second law of thermodynamics, which would imply that the black hole should
have zero entropy as all the information (with high entropy) is eradicated.

However, this theory confronts a significant challenge from quantum mechanics,
specifically the principles articulated in quantum field theory and the
principle of unitarity. The latter insists on the conservation of information,
which contests the assertion that information entering a black hole is
irretrievably lost. Moreover, if information is preserved, the black hole
would have non-zero entropy, giving it a finite temperature and leading it to
emit thermal Hawking radiation. This process would theoretically result in the
black hole gradually losing mass until it evaporates entirely, leaving only
Hawking radiation composed of certain particles behind. This conservation of
information gives rise to what is known as the black hole information paradox,
a fundamental conflict between quantum mechanics and the theory of general
relativity. This paradox underlines a critical discrepancy in our
understanding of modern physics: if the information is indeed lost in a black
hole, it undermines the foundations of quantum mechanics; conversely, if the
information is conserved, it challenges the principles of classical general
relativity.

In 1993, Leonard Susskind, Lárus Thorlacius, and John Uglum introduced a
solution to the black hole information paradox known as ”black hole
complementarity.” This principle hinges on the experiences of two observers:
Alice, who falls into the black hole, and Bob, who remains outside of it.
According to this proposal, the conflicting descriptions of the black hole
interior, as observed by Alice and Bob, are not contradictory but rather
complementary, hence the term ”black hole complementarity” [STU]; [LPSTU].

From Bob’s perspective, observing from a safe distance outside the event
horizon, the horizon acts as a physical membrane, becoming a hot layer just
above the black hole’s horizon, termed the ”stretched horizon.” In this
perspective, Alice appears to become increasingly red-shifted as she
approaches the event horizon, effectively getting ”frozen” at the horizon.
Alice would never seem to cross the event horizon; instead, she would get
incinerated due to the extremely high temperatures. The black hole then re-
emits her mass energy in the form of Hawking radiation, which carries the
information about Alice, allowing Bob to theoretically reconstruct her from
the information contained in the radiation, thereby preserving the principle
of unitarity in quantum mechanics.

Conversely, from Alice’s vantage point, as she falls towards the black hole,
due to the equivalence principle, she doesn’t notice anything unusual at the
moment she crosses the event horizon, experiencing a ”no drama” scenario.
Contrary to Bob’s observations, she wouldn’t see herself getting stuck at the
horizon or getting incinerated but would smoothly pass the event horizon and
eventually meet her fate at the singularity at the black hole’s core,
seemingly violating the principle of unitarity due to the apparent loss of
information as she crosses the event horizon.

Black hole complementarity proposes a dual reality where Alice’s and Bob’s
descriptions are correct in their respective frames of reference. However,
they cannot communicate and compare notes after Alice crosses the horizon.
This approach offers a potential resolution to the black hole information
paradox, albeit at the cost of introducing a vexing puzzle tied to the nature
of entanglement and the very principles of quantum mechanics.

In this paradox, we envisage three particles: $A$, $B$, and $C$, where $A$ and
$B$ are a pair of entangled particles and particle $C$ shares information with
$B$. Particle $A$ is swallowed by the black hole, $B$ is emitted as Hawking
radiation, and particle $C$ is another piece of radiation emitted before $B$,
creating a mixed state of $A$, $B$, and $C$. Imagine a scenario involving
Alice, an observer who first measures early radiation from particle $C$, then
does the same for the later radiation from particle $B$ before crossing the
event horizon to encounter particle $A$, which shares entanglement with
particle $B$, and through it, with particle $C$. This scenario raises critical
questions grounded in the concept of monogamy of entanglement (the principle
that a quantum system can only be entangled with one system at a time),
hinting at a violation of the no-cloning theorem of quantum mechanics. Having
measured both $B$ and $C$, Alice carries this information into the black hole
where she measures $A$, suggesting the duplication of information, a direct
contradiction to the no-cloning theorem prohibiting the exact replication of
arbitrary unknown quantum states.

Seeking to resolve this deep-seated paradox, Ahmed Almheiri, Donald Marolf,
Joseph Polchinski, and James Sully (AMPS) reformulated the black hole
information paradox, presenting a new paradox, the “firewall paradox.” AMPS
brought the information paradox to a more concrete footing by arguing that if
the information about the in-falling matter is to be preserved and able to be
retrieved from a black hole, as suggested by unitary evolution in quantum
mechanics, then there must be a highly energetic Planck-scale firewall at the
event horizon, which would effectively destroy anything falling in, thus
preserving the information. This conclusion, however, starkly contradicts the
general relativistic prediction of a smooth event horizon, as well as the
equivalence principle (“absence of drama for the infalling observer”), which
states that falling through a horizon should be uneventful for an in-falling
observer [AMPS].

In 2013, Daniel Harlow and Patrick Hayden (HH) proposed an innovative approach
to address the firewall paradox’s contentious issues. In this approach, they
suggested that Alice could theoretically verify the transmission of quantum
information emanating from the interior of a black hole, but to do this
successfully, she would require a quantum computer equipped with an error-
correcting code potent enough to handle computations of extraordinary
complexity [Har-Hay].

In the subsequent discussion, I will demonstrate that, from an epistemic
standpoint, the HH paper fundamentally altered the framework and tenor of the
existing discourse and forged a novel pathway for engagement with the firewall
paradox. Leveraging insights from computational theory unveiled new pathways
for understanding and possibly resolving the firewall paradox.

##  3 HH begin with a physical problem

###  3.1 Monogamy of entanglement and the Firewall paradox

HH consider the quantum description of a Schwarzschild black hole in 3 + 1
dimensions from the points of view of an external observer, Charlie, and an
infalling observer, Alice. The entropy of the black hole is proportional to
$M^{2}$ in Planck units, where $M$ is the mass of the black hole. The time it
takes for the black hole to evaporate is proportional to $M^{3}$. Alice has a
task at hand to extract information from around $n\sim M^{2}$ bits of Hawking
radiation within a time frame $T\sim n^{3/2}$ before the black hole evaporates
completely. Alice needs to apply a unitary transformation to the Hawking
radiation to extract the desired information. This process effectively
unscrambles the desired information, making it accessible in a specific
subfactor of the Hilbert space. Charlie is positioned far from the black hole,
at infinity. This position gives him ample time and memory resources to
measure the Hawking radiation emitted by the black hole with great precision.

_Let us start by considering Charlie’s perspective_. Charlie’s description is
based on the following three postulates [Har-Hay]:

1) Charlie postulates that the black hole’s formation and subsequent
evaporation can be described as a unitary process.

2) Furthermore, we can conceptualize the system as undergoing either
continuous or discrete time evolution, wherein at any individual moment, it is
in a pure quantum state $\ket{\psi}$, which lives in a specified Hilbert space
labeled $H_{\text{outside}}$. Charlie breaks down $H_{\text{outside}}$ into
three subspaces: $H_{\text{outside}}=H_{H}\otimes H_{B}\otimes H_{R}$, where
$H_{H}$ represents the degrees of freedom inside or close to the black hole.
Heuristically associated with the ”stretched horizon” at a Schwarzschild
coordinate radius given by $r=2GM+\epsilon$, $G$ is the gravitational
constant, $M$ is the black hole’s mass, and $\epsilon$ is some ultraviolet
cutoff. $H_{B}$ represents the field theory modes in the near-horizon region
of the black hole. This region has a Schwarzschild coordinate radius in the
range $2GM+\epsilon<r<3GM$, indicating that it is close to the black hole but
outside the stretched horizon described in $H_{H}$. The geometry in this
region is close to that of Rindler space. It will include modes with
Schwarzschild energy less than the black hole temperature $T=\frac{1}{4\pi
GM}$. Modes with higher energy are not confined to this near-horizon region
and are considered part of $H_{R}$. $H_{R}$ represents the Hawking radiation
field, the modes of the radiation field outside the black hole, with
Schwarzschild coordinate radius $r>3GM$. $H_{R}$ includes higher energy modes
that are not confined to the near-horizon region described in $H_{B}$.

We can relabel the different regions associated with a black hole and the
surrounding environment as $B$, $R$, and $H$. $B$ is the zone just outside the
event horizon of the black hole. $B$ is where one can theoretically observe
phenomena related to the near-horizon dynamics of the black hole, including
the effects of Hawking radiation and other quantum gravitational effects.
Subscript $B$ ties it to phenomena and quantum information related to $B$. $H$
refers to the black hole’s horizon, and $R$ represents the radiation field
outside the black hole, in a region farther from the black hole, where one can
observe the radiation emitted by the black hole, including the Hawking
radiation that has escaped the gravitational pull of the black hole. Subscript
$R$ ties it to the phenomena and quantum information associated with this
region.

The dimensionalities of $H$ and $B$ are denoted by $|H|$ and $|B|$, which are
related to the area of the black hole’s horizon measured in Planck units. The
logarithms of these dimensionalities (i.e., $\log|H|$ and $\log|B|$) are
proportional to the black hole’s horizon area when we study the pure quantum
state $\ket{\psi}$. Over time, the sizes of $|H|$ and $|B|$ decrease,
illustrating the changes in the black hole dynamics as it ages. $H_{R}$ starts
restricted to a subset involved with the black hole dynamics, but the size of
$H_{R}$, denoted as $|H|$, increases over time, indicating that more states
become relevant to the black hole’s dynamics as time goes on.

3) The third postulate involves the changes over time in the degrees of
freedom or the ”size” of $H_{H}$ and $H_{B}$. These changes in size are
proportional to the area of the black hole’s horizon, and as the black hole
evolves, these values change. In other words, the behavior and properties of
the black hole differ depending on whether $|R|$ is larger or smaller than the
product $|H||B|$, giving rise to the distinction between ”young” and ”old”
black holes. As a black hole ages, $|R|$ expands, altering the entanglement
dynamics between $B$ and $H$ within the broader $H_{\text{outside}}$. $B$ and
$H$ are highly entangled when a black hole is young. As the black hole ages,
$B$ and $H$ become a small part of a much larger system described in Hilbert
space. After a certain time, known as Page time, HH show that the combined
system of $B$ and $H$ reaches a state that can be described using a simple
mathematical expression involving the identity operator, which basically means
the system has become uniform [Har-Hay].

As time passes, the system reaches a state of maximal entanglement, where $BH$
(the combination of $B$ and $H$) is maximally entangled with $R$. HH decompose
$H_{R}$ into a direct sum of subspaces, $H_{R_{H}}$ and $H_{R_{B}}$, and
another space termed as $H_{\text{other}}$ (which does not contribute to the
described entangled state): $H_{R}=(H_{R_{H}}\otimes H_{R_{B}})\otimes
H_{\text{other}}$. $H_{R_{H}}=|H|$ (or $H_{R_{H}}=|R_{H}|$) and
$H_{R_{B}}=|R_{B}|$ are their dimensions which are set equal to $|H|$ and
$|B|$ respectively for the entanglement to hold [Har-Hay]. $R_{B}$ represents
a portion of the surrounding space farther away from the black hole, where the
Hawking radiation emitted from the vicinity of the black hole (including $B$)
can be observed. $B$ and $R_{B}$ are maximally entangled, describing a high
degree of scrambling.

Let us keep in mind that we are still examining Charlie’s perspective. Recall
that the entire system (which encompasses both the black hole and the
associated Hawking radiation, $H_{R}$) is represented by a pure quantum state,
denoted $\ket{\psi}$, within $H_{\text{outside}}$. $\ket{\psi}$ is in a
superposition of product states from the $H$, $B$, $R_{H}$, and $R_{B}$
Hilbert spaces:

${\ket{\psi}}=\left(\frac{1}{\sqrt{|H|}}\sum_{h}\ket{h}_{H}\ket{h}_{R_{H}}\right)\otimes\left(\frac{1}{\sqrt{|B|}}\sum_{b}\ket{b}_{B}\ket{b}_{R_{B}}\right),$
(1)

where the terms $\ket{h}_{H}$ and $\ket{b}_{B}$ represent basis states in the
spaces associated with the black hole and $B$, respectively,
$\ket{h}_{R{{}_{H}}}$ and $\ket{b}_{R{{}_{B}}}$ represent basis states in the
radiation Hilbert space corresponding to the states in the black hole and $B$.

Equation (1) represents the state of an old black hole, written using Schmidt
decomposition. It is factorized into two independent subsystems: one
associated with $H$ and one associated with $B$. The fundamental argument of
HH is grounded on equation (1).

The state in the equation is built such that each basis state in $H$ is
entangled with a corresponding state in $R_{H}$ and similarly for $B$ and
$R_{B}$. In other words, this structure reveals a deep and complex
entanglement pattern: the states in $H$ are entangled with specific states in
$R_{H}$, and those in $B$ are entangled with specific states in $R_{B}$. By
setting up an entanglement between $H$ and $R_{H}$, and $B$ and $R_{B}$, we
ensure the full state $\ket{\psi}$ is pure despite the subsystems $H$ and $B$
individually being in mixed states.

_Now consider the perspective of Alice_ , falling into a black hole, and
compare her observations with those of Charlie, who is observing from outside
the black hole. Here are the key points and steps of her argument: before
reaching the singularity of the black hole, Alice also perceives her
surroundings through a description based on a Hilbert space,
$H_{\text{inside}}$, divided into several subspaces:
$H_{\text{inside}}=H_{A}\otimes H_{B}\otimes H_{R}\otimes H_{H^{\prime}}$,
where, $H_{A}$ represents the Hilbert space associated with $A$, which
encompasses the field theory modes inside the black hole’s event horizon from
Alice’s perspective. $A$ is just inside the event horizon of the black hole;
$H_{B}$ and $H_{R}$ are outside the black hole and accessible to both Alice
and Charlie; $H_{H^{\prime}}$ is related to Alice’s horizon, distinct from the
black hole’s horizon. From Alice’s perspective, $H_{H}$ is absent. The region
associated with $H_{H}$ is crossed by Alice in an extremely short time,
meaning it has no operational significance to her; she wouldn’t be able to
conduct any meaningful measurements in such a short time frame.

To avoid contradictions in Alice and Charlie’s observations, an ”overlap rule”
ensures that both agree on the experiments’ results they can communicate.
Charlie and Alice, despite potentially having different perspectives, must
come to the same conclusion regarding the density matrix of $H_{B}\otimes
H_{R}$.

Alice would normally expect to see a smooth vacuum at the black hole horizon
based on general relativity, with specific modes in $H_{B}$ and $H_{A}$ being
closely entangled, reflecting a smooth vacuum at the horizon. However, this
idea faces a significant problem due to the assumptions about what Charlie
perceives at the black hole stage (specifically, being an old black hole).

$A$, $B$, and $R$ would each have its associated Hilbert space representing
all possible quantum states. $B$ is almost maximally entangled with $R_{B}$,
which is perceivable by Charlie. Even though Alice cannot directly perceive
$R_{B}$ (and Charlie cannot directly perceive $A$), the high degree of
entanglement between $B$ and $R_{B}$ means that observing a part of the
entangled system (i.e., $B$) gives information about the other part of the
system ($R_{B}$). By the overlap rule, what Charlie perceives about the
entanglement between $B$ and $R_{B}$ must also be true for Alice when she
observes $B$.

However, because of the monogamy of entanglement, $B$ cannot be maximally
entangled with $A$ and $R_{B}$ simultaneously. This contradicts the
expectation of a smooth vacuum on the horizon for Alice. Recall from section 2
that to resolve this contradiction, the AMPS argument posits that instead of a
smooth vacuum, there is a firewall — a region of high-energy particles — at
the horizon of an old black hole, which effectively annihilates anything or
anyone, including Alice, that falls into it [AMPS]; [Har-Hay].

###  3.2 Strong and standard complementarity

To navigate this problem, one can choose two potential directions [Har-Hay]:

1) _Strong complementarity_ : HH have defined Alice’s and Charlie’s
theoretical frameworks. Alice’s theory doesn’t directly relate to Charlie’s in
this approach. They only need to agree on the experimental results visible to
both.

The event horizon serves as a barrier, making direct access to information in
$R_{B}$ inherently impossible from Alice’s localized perspective near the
black hole. The states in $R_{B}$ are maximally entangled with those in $B$,
i.e., knowing the state in $B$ allows one to predict the state in $R_{B}$
perfectly, and vice versa. Over time, the information about the black hole
gets scrambled and distributed over a very wide area, including $R_{B}$. In
Charlie’s theory, $B$ and $R_{B}$ are significantly entangled due to the
dynamics of black hole evaporation. This entanglement ties up $B$, preventing
it from being highly entangled with $A$. But Alice cannot access quantum
states in the Hilbert space $H_{R_{B}}$ associated with $R_{B}$. So, in
Alice’s theory, there are two potential solutions to address this problem:

1\. Disentangle $H_{R_{B}}$ from $H_{B}$: This would involve creating a theory
where the states in $R_{B}$ are no longer entangled with those in $B$. This
freeing up of $B$ would entangle it with $A$.

2\. Remove $H_{R_{B}}$ from her theory entirely. Alice’s theory would ignore
the states in $R_{B}$, treating them as irrelevant. This would again free up
$B$ to become entangled with $A$. This would grant Alice a smooth journey
across the horizon.

Thus, according to strong complementarity in Alice’s frame, certain
manipulations or neglect of $H_{R_{B}}$ are postulated to allow a self-
consistent description of a smooth horizon, harmonizing the dual descriptions
by Charlie and Alice. Strong complementarity basically advocates for a kind of
duality in the descriptions, where both are valid in their respective domains.
Still, neither description can be globally valid, thereby complementing each
other.

2) _Standard complementarity_ : While described using different theoretical
frameworks, Alice’s and Charlie’s observations can be compatible because
Alice’s theory can be seen as a subset embedded in Charlie’s more encompassing
theory. A theoretical framework is developed where Alice’s interior operators
to describe phenomena in $H_{A}$ are formulated using the exterior operators
that Charlie would use to describe $H_{R_{B}}$. This attempt is made to avert
the problem of firewalls and maintain the notion of a smooth space at the
horizon, referring to it as $A=R_{B}$ [Bousso].

This equality symbolizes an effort to harmonize the two perspectives (Alice’s
and Charlie’s) by identifying the region described by Alice ($A$) with $R_{B}$
in Charlie’s description. By developing a theory where Alice’s interior
description (on $H_{A}$) is formulated using exterior operators that Charlie
would use to describe $H_{R_{B}}$, standard complementarity aims to avoid the
problem of firewalls and uphold the idea of a smooth transition at the event
horizon [STU]; [LPSTU].

However, identifying Alice’s $A$ with Charlie’s $R_{B}$ introduces a notable
problem. It doesn’t restrict Alice from making direct measurements in $R_{B}$,
which, according to the broader theory (Charlie’s perspective), she shouldn’t
be able to access directly. This results in a paradox where Alice, while
theoretically unable to access $R_{B}$, finds herself able to do so according
to this approach, thereby contravening the theory that posits complementarity.

###  3.3 The unitary transformation and its inverse

In what follows, I show that HH introduce a new perspective that involves
computational complexity to help address the issues raised by the AMPS
paradox. They bring a different angle to this discussion, focusing on the
computational complexity involved in reconstructing the interior of a black
hole (Alice’s point of view) from the information outside of it (Charlie’s
point of view). They argue that the task of Charlie reconstructing what is
inside (and thus detecting a firewall) would involve an intractable
computational task. I demonstrate that HH bring a fresh perspective that adds
a nuanced layer to the standard complementarity, but they navigate around the
standard complementarity rather than extend it.

Initially, HH phrase the discussion in terms of Charlie’s Hilbert space. Since
both Charlie and Alice are required to agree on the density matrix that
describes the system in terms of $H_{B}$ and $H_{R}$, it implies that a
consistent representation of $\ket{\psi}$ can be achieved from the perspective
of Charlie’s Hilbert space. Hence, despite potentially different vantage
points, Alice and Charlie will converge on a shared description, abiding by
the constraints of the overlap rule.

First, HH specify that in the Schmidt decomposition, one describes the state
of the old black hole in terms of a basis that effectively separates the early
and late-time radiations, see equation (1). However, HH will use a particular
basis (denoted as ”computational basis”) to describe the radiation field
$H_{R}$, which will be convenient for Alice to work with. They write an
equation that denotes the specific computational basis state ($\ket{bhr}_{R}$)
in $H_{R}$ using $n$, $k$, and $m$ that describe various aspects of that
state. Working exclusively with this basis is intended to simplify
calculations for Alice as she tries to work through the decoding problem with
a basis where the mathematical expressions become more tractable. Alice uses
$n$, $k$, and $m$ to represent different quantities related to her problem of
decoding information from the black hole’s Hawking radiation: $n$ represents
the total number of qubits involved in the problem. This is related to the
logarithm to base $2$ of the dimension of $R$: $n\equiv\log_{2}|R|$; $k$
represents the number of qubits associated with $H_{B}$; and $m$ represents
the number of qubits associated with $H_{H}$. We can think of $k+m$ as the
number of qubits remaining in the black hole. $H_{H}$, along with $H_{B}$,
forms the entirety of the black hole’s state that Alice is interested in for
her problem.

Second, HH define $U_{R}$ as a particular (scrambling) unitary transformation
on $H_{R}$ and write $\ket{\psi}$ [equation (1)] in the computational basis:

${\ket{\psi}}=\frac{1}{\sqrt{|B||H|}}\sum_{b,h}\ket{b}_{B}\ket{h}_{H}U_{R}\ket{bh0}_{R}.$
(2)

$U_{R}$’s exact form or structure depends on the details of the black hole’s
initial state and the quantum gravity, a yet-to-be-realized theory. The
discussion here pertains to Schwarzschild black holes instead of AdS eternal
black holes that do not evaporate and maintain a dynamic equilibrium with
Hawking radiation. This dynamic equilibrium significantly changes the
conditions and assumptions on which the HH decoding task and the $U_{R}$ are
defined. HH note that ”Big AdS black holes do not evaporate at all, so the
AMPS argument does not directly apply to them, but arguments have been put
forward suggesting that they nonetheless have firewalls” [Har-Hay].

Alice’s challenge is applying the inverse of $U_{R}$, denoted
$U^{\dagger}_{R}$, to the Hawking radiation. This allows her to confirm the
entanglement between $H_{B}$ and $H_{R_{B}}$. Applying $U^{\dagger}_{R}$
reverses the transformation effected by $U_{R}$, decoding the information
encoded in the Hawking radiation. The goal is to retrieve the information
encoded in the entangled states between $H_{B}$ and $H_{R_{B}}$ from the
Hawking radiation. Through decoding, Alice can confirm the entanglement
between $H_{B}$ and $H_{R_{B}}$, gaining insight into the states and dynamics
occurring in $R_{B}$ through her operations on the radiation emitted by the
black hole without directly accessing $R_{B}$. By utilizing the decoded
information from the Hawking radiation, Alice can avoid the need for direct
measurement in $R_{B}$, thus avoiding the paradox arising from her ability to
access information in $R_{B}$ directly according to the standard
complementarity approach. In other words, Alice can bypass the complications
brought about by the firewall argument while upholding the principles inherent
in the black hole complementarity.

However, the time Alice would need to decode the information is exponential
and proportional to $2^{k+m+n}$. This time complexity is extremely large,
indicating a computational task of astronomical proportions. Since the black
hole is old, it implies that $n$ (representing the age parameter) is
significantly larger than the sum of $k$ and $m$. This condition allows us to
derive a lower bound for the reduced time complexity expression: $n>k+m$.
Using this condition in $2^{k+m+n}$, we can establish a lower bound on the
reduced time complexity as at least $2^{2{(k+m)}}$. But this expression also
involves an exponential function and, therefore, would be extremely large for
non-trivial values of $k$ and $m$.

Thus, reversing $U_{R}$ exactly would be practically impossible for Alice.
Hence, a framework is required to quantify how close Alice can reach the
perfect task. HH use a concept of ”trace norm,” which allows them to define a
notion of ”closeness,” how close Alice needs to get to test the entanglement
accurately [Har-Hay]. In other words, they aim to find a unitary operation
close enough to the ideal operation $U^{\dagger}_{R}$ such that the error in
the subsequent measurements is within acceptable bounds. Defining a threshold
for the closeness using trace norm would define how accurately Alice needs to
perform the unitary transformation to test the entanglement reliably. It
establishes a criterion for the allowable error in Alice’s operation, such
that she can still validate the entanglement through her measurements. By
working within this framework, Alice aims to construct a unitary
transformation that, while not the same as the ideal $U^{\dagger}_{R}$, is
close enough according to this defined metric to allow her to verify the
entanglement adequately. This approach acknowledges the practical difficulties
and uncertainties in constructing the exact unitary transformation and
provides a pathway to achieve Alice’s goal within tolerable error margins.

By allowing for a non-ideal transformation, where Alice tries to get close
enough through trace norms, there might be a reduction in the complexity of
the task at hand. However, even when settling for a non-ideal transformation,
Alice still faces an enormously complex computational task. Though the
requirement is somewhat relaxed compared to achieving the ideal
transformation, the task remains a high-order polynomial time problem,
implying a computational duration that vastly exceeds the black hole’s
lifespan.

##  4 HH provide Alice with a quantum computer

###  4.1 Alice is distilling the radiation with a quantum computer

Alice is on a mission to decode the entanglement between $R$ and $B$, aiming
to transform it into a format that is easier to analyze. To accomplish this,
Alice uses a quantum computer whose initial state is defined in a new Hilbert
space $H_{C}$. This computer interacts with the radiation Hilbert space
$H_{R}$, undergoing a unitary evolution described by $U_{\text{comp}}$. In
other words, $U_{\text{comp}}$ operates on a larger Hilbert space that
includes $H_{R}$ and $H_{C}$: $H_{R}\otimes H_{C}$. Alice employs
$U_{\text{comp}}$ (similar to $U^{\dagger}_{R}$) to reverse the effects
implemented by $U_{R}$ to distill $R_{B}$. This intends to decode the
information entangled with $B$ during the evolution governed by $U_{R}$.

However, Alice’s major challenge is finding the appropriate initial state for
her computer:

$U_{\text{comp}}:U_{R}|bh0\rangle_{R}\otimes|\psi\rangle_{C}\rightarrow|\text{something}\rangle\otimes|b\rangle_{\text{mem}}.$
(3)

Alice is looking for a particular initial state for her computer, denoted
$\ket{\psi}_{C}$, such that under $U_{\text{comp}}$, this state interacts with
the states from the radiation field $U_{R}\ket{bh0}_{R}$ to produce a final
state where the qubits representing $\ket{b}$ (which are associated with the
$B$ basis) are stored in the first $k$ qubits of the memory of her computer,
separated from the other parts of the system described by
$\ket{\text{something}}$. In other words, Alice is trying to isolate
information about $B$ into her computer’s memory [Har-Hay].

However, finding the initial state $\ket{\psi}_{C}$ for the computer to start
the computation is extremely challenging. Even if Alice finds one, the
probability that it successfully facilitates the computation is minuscule,
being exponentially small in terms of the dimensions of the Hilbert space. To
estimate the likelihood of finding a successful initial state, HH use the
trace norm to create a set close to which every pure state in the Hilbert
space can be found. Even after considering various potential unitary
evolutions, the probability of finding a successful initial state remains
extraordinarily small. The time required to find a suitable $U_{\text{comp}}$
by random chance is identified as the quantum recurrence time, the time scale
over which a quantum system revisits a particular state it was in at some
earlier time, due to its natural dynamics. The recurrence time is immensely
long, reaching up to $10^{10^{40}}$ years. The recurrence time in which a
quantum system revisits near an initial state by pure chance is especially
long for the complex system Alice is dealing with, involving a black hole and
Hawking radiation. This time scale is doubly exponential in terms of the
entropy of the whole system, i.e., it increases extremely fast as the system’s
complexity increases. Thus, the recurrence time is potentially longer than the
lifespan of a Schwarzschild or an astrophysical black hole.

Despite the immense challenge posed by the quantum recurrence time, Alice has
another strategy up her sleeve. Instead of the brute force approach, waiting
for the right $U_{\text{comp}}$ to occur by chance, she aims to actively find
it by exploiting patterns in how $U_{\text{comp}}$ evolves. If there are any
predictable structures in its evolution, she can use this information to guide
her search, significantly reducing the time it would take to find the right
$U_{\text{comp}}$. By leveraging the structures in $U_{\text{comp}}$’s
evolution, Alice can potentially reduce the computational time from a double
exponential dependency on the entropy of the radiation to a single exponential
dependency. This is a very long time since single exponential growth is very
fast. But it is much more manageable compared to a double exponential growth.
So, this strategy offers a glimmer of hope; despite the initially grim
prognosis suggested by the quantum recurrence time, if Alice can understand
and leverage the underlying physics and mathematical properties of her system
well enough, she might be able to achieve her goal in a ”reasonable” amount of
time, though still astronomically long from a human perspective [Har-Hay].

###  4.2 The Solovay-Kitaev theorem

HH then ask [Har-Hay]: how many quantum gates would be necessary to implement
a unitary transformation as complicated as $U_{R}$? They show that the number
of gates required scales with a single exponential function of the number of
qubits ($n$), $2^{2n}$ times a logarithm of a parameter ($\epsilon$):
$2^{2n}\log(\frac{1}{\epsilon})$.

This is a significant result because it means the computational time is a lot
less than previously assumed based on a crude double exponential scaling (for
instance, $2^{2^{n}}$). This improvement is partly credited to the Solovay-
Kitaev theorem, which suggests that an efficient sequence of gates can be
found to perform any unitary operation to a high degree of precision. Despite
this improvement, reducing the computational time further seems unlikely,
indicating that $U_{R}$ and $U^{\dagger}_{R}$ are still highly non-trivial
tasks even under optimal conditions. Adjusting the model, such as using
different gates or more complex quantum entities like qutrits (which have
three basis states) instead of qubits, doesn’t fundamentally change the
$2^{2n}$ scaling of the problem.

We can speed up computations significantly compared to initial expectations.
However, we are still looking at a process that requires a time that scales
exponentially with the number of qubits, which indicates extremely long
computation times for complex operations involving many qubits. This makes
Alice’s task of implementing $U_{R}$ within a reasonable time frame highly
unlikely.

##  5 HH combine black hole physics and computing

###  5.1 Taking into consideration the dynamics of the black hole

HH then suggest that the dynamics of a black hole constrain $U_{R}$ in a way
that could help Alice implement it faster. A transformation $U_{\text{dyn}}$
is defined as a unitary transformation that operates on different microstates
of a black hole, and “it seems quite reasonable to assume that
$U_{\text{dyn}}$ can be generated by a polynomial number of gates,” i.e., a
computational operation that doesn’t require an astronomical number of quantum
gates to perform [Har-Hay]. I am quoting this phrase because I find it
problematic from a conceptual and philosophical standpoint. I elaborate on
this perspective below.

HH define the state $\ket{\psi}$ as arising from the action of the polynomial
size circuit $U_{\text{dyn}}$:

$U_{\text{dyn}}{\ket{0}}_{BHR}=\frac{1}{\sqrt{|B||H|}}\sum_{bh}\ket{b}_{B}\ket{h}_{H}U_{R}\ket{bh0}_{R}.$
(4)

They provide a more comprehensive explanation of this matter. Alice wants to
determine if a small circuit for $U_{\text{dyn}}$ implies a small circuit for
$U_{R}$. If such a circuit exists, she could more easily decode $R_{B}$ from
the Hawking radiation. The matrix $U_{R}$ is derived from $U_{\text{dyn}}$,
which, unlike $U_{\text{dyn}}$, is sensitive to the system’s initial state.
For the sake of simplicity, an initial state is chosen with all bits set to
zero. HH write an expression for $U_{\text{dyn}}$ acting on this initial
state, intending to learn more about $U_{R}$:

$U_{\text{dyn}}\ket{00000}_{\text{{init}}}\approx\frac{1}{\sqrt{|B||H|}}\sum_{b,h}\ket{b}_{B}\ket{h}_{H}U_{R}\ket{bh0}_{R}.$
(5)

Some physical assumptions about $U_{\text{dyn}}$ are necessary to further this
exploration. While the precise dynamics of quantum gravity remain undefined,
HH refer to theories like AdS/CFT and matrix theory, which give ground to
assume that $U_{\text{dyn}}$ can be generated through polynomial numbers of
gates in a small circuit [Har-Hay]. So, the core search then revolves around
whether there is a small circuit for $U_{\text{dyn}}$ that ensures a small
circuit for $U_{R}$. This would imply that if affirmed, Alice could feasibly
decode $R_{B}$ from the Hawking radiation. However, it seems like there is a
challenge here, citing the eternal nature of black holes as posited by AdS/CFT
theory, which ostensibly disputes the presence of a firewall paradox. This
presents a theoretical contradiction, introducing complexity and potential
disagreement in integrating these theories with the problem at hand.

Next, disregarding the complication, HH proceed to articulate their argument:
$U_{\text{dyn}}$ can be expressed as a product of $U_{R}$ and another
operation called $U_{\text{mix}}$. $U_{\text{mix}}$ is a unitary operation
that creates entanglement between different subsystems, mixing or scrambling
the information within them to create a highly entangled state.

Here, $U_{\text{mix}}$ is conceptualized as a straightforward circuit that
entangles the initial four subfactors in the chosen initial state. HH
emphasize the simplicity of implementing $U_{\text{mix}}$, noting that a
universal circuit would suffice:

$U_{\text{mix}}\ket{00000}_{\text{{init}}}=\frac{1}{\sqrt{|B||H|}}\sum_{b,h}\ket{b}_{B}\ket{h}_{H}U_{R}\ket{bh0}_{R}.$
(6)

HH then define a new operator $\tilde{U}_{R}$ as:
$\tilde{U}_{R}=U_{\text{dyn}}U^{\dagger}_{\text{mix}}$, which has the
property:

$\tilde{U}_{R}\frac{1}{\sqrt{|B||H|}}\sum_{b,h}\ket{b}_{B}\ket{h}_{H}\ket{bh0}_{R}=\frac{1}{\sqrt{|B||H|}}\sum_{b,h}\ket{b}_{B}\ket{h}_{H}U_{R}\ket{bh0}_{R}.$
(7)

HH argue that a small circuit can implement $\tilde{U}_{R}$. It undoes the
effects of $U_{R}$ when applied to a specific superposed state, a complex
combination of states from $B$ and $H$ [Har-Hay].

###  5.2 Alice again confronts complications

The above process is highly non-trivial because, as seen in the previous
section, the new inverse operator $\tilde{U}_{R}$ is intricately dependent on
the precise initial states of the qubits in $B$ and $H$, which are part of an
entangled system associated with a black hole. Applying $\tilde{U}_{R}$
ideally would unscramble the quantum information, extracting it from the
entangled state and converting it into a format that can be more
straightforwardly accessed and analyzed. Although it seems that
$\tilde{U}_{R}$ could be utilized to decode the information, it encounters a
pivotal issue; the operation of $\tilde{U}_{R}$ involves all qubits, including
those in $B$ and $H$, to which Alice doesn’t have access. Hence, implementing
$\tilde{U}_{R}$ as is would be infeasible. Alice, therefore, considers a
strategy where she replaces the unavailable qubits from $B$ and $H$ with some
ancillary qubits in a random state, hoping this would allow her to use
$\tilde{U}_{R}$ to undo $U_{R}$. The difficulty remains as $\tilde{U}_{R}$ is
fundamentally tied to the initial states of the $B$ and $H$.

Ultimately, it is highly unlikely for Alice to find a simple, small circuit to
implement $U_{R}$ due to the constraints imposed by $U_{\text{dyn}}$ and the
complexity arising from $U^{\dagger}_{R}$. Because Alice doesn’t have access
to all the qubits she needs, she can’t directly apply $U^{\dagger}_{R}$ to
reverse the dynamics and extract the information encoded in $R_{B}$. The
transformations she would like to apply, including $\tilde{U}_{R}$, are
sensitive to the states of all the zones, including $B$ and $H$, which she
can’t access. Therefore, Alice can’t take a straightforward approach to
reverse the dynamics in a manageable amount of time, i.e., in a time that is a
polynomial entropy function. So, Alice is stuck with having to try a brute
force strategy, where she uses a tremendous number of operations ($2^{n+k+m}$
gates, which indicates a huge, potentially impractical number) to construct
$U^{\dagger}_{R}$. HH, therefore, suggest a kind of pessimism or skepticism
that there would be an easy solution to Alice’s problem [Har-Hay].

##  6 HH transform a physical problem into a quantum coding problem

###  6.1 Alice is utilizing an error-correcting code

HH then hint toward the possibility of exploring the problem further through
the lens of error-correcting codes and complexity theory, albeit acknowledging
the sheer challenge posed by the exponential increase in complexity [Har-Hay].
They recast Alice’s task as a quantum coding problem.

Alice’s main difficulty is retrieving information, especially when dealing
with errors introduced by the black hole environment, which causes erasures in
$B$ and $H$ (which define the state of the black hole). Recall that Alice has
no access to $B$ and $H$. This lack of access is represented mathematically as
erasures in these systems. These erasures pose a significant challenge to
Alice’s task, as they take away information that is vital for her to be able
to successfully decode the information about the black hole’s initial state.
Alice uses the error-correcting code to recover information that has been
erased and affected by the interaction of the black hole with its environment.

HH write equation (2) in an equivalent way:

$\displaystyle{\ket{\psi}}=\frac{1}{\sqrt{|B|}}\sum\ket{b}_{B}\ket{\overline{b}},\ket{\overline{b}}\equiv\frac{1}{\sqrt{|H|}}\ket{h}_{H}U_{R}\ket{bh0}_{R}.$
(8)

The state $\ket{\psi}$ is expressed as a superposition of $\ket{b}_{B}$ and
$\ket{\overline{b}}$, where $\ket{\overline{b}}$ is defined in terms of
$\ket{b}_{B}$ and $U_{R}$. HH are trying to simplify the problem by focusing
on a smaller Hilbert space, where $\ket{\overline{b}}$ is a basis for a $k$
dimensional subspace of $H_{H}\otimes H_{R}$. But they also underscore the
intertwined nature of the state $\ket{\psi}$ in the black hole and the Hawking
radiation system, with its behavior being determined by interactions between
multiple different Hilbert spaces.

Alice creates a quantum code using $U_{\text{enc}}$, which is built from
$U_{R}$ and $U_{\text{mix,H}}$: $U_{\text{enc}}\equiv U_{R}U_{\text{mix,H}}$.
$U_{\text{mix,H}}$ is a simple entangling transformation analogous to
$U_{\text{mix}}$, which is applied to a subset of the qubits representing a
part of the radiation emitted. It affects the $m$ qubits of $H$ and the $n+1$
to $n+m^{th}$ qubits of $R$. This encoded information involves entangling
pairs of qubits from $H$ and $R$ to produce new states. Up to this point in
their discussion, HH have focused on the errors that arise from the fact that
Alice does not have direct access to all the necessary information from $B$
and $H$ to decode the information she seeks straightforwardly. However, they
point out that this isn’t Alice’s task’s only source of potential errors. They
bring attention to another substantial challenge. For instance, the black hole
emits Hawking radiation, including hard-to-detect gravitons, let alone
coherently manipulate. Thus, information about the black hole’s state is
carried away with that radiation, and some of it is lost.

When Alice applies $U_{\text{enc}}$, she identifies a subset of states
(subspace) of the total Hilbert space within the larger Hilbert space. By
narrowing it down to a specific subspace, Alice is reducing the computational
complexity and resource requirements of the task at hand. Operating in a
smaller subspace allows a more streamlined approach to information retrieval,
bypassing the need to deal with a prohibitively large set of all possible
quantum states in the full Hilbert space. This subspace effectively helps in
encoding the information about the black hole state and aids in protecting and
retrieving the information even after some amount of information loss and
erasure. Moreover, the universe of all possible quantum states in the Hilbert
space is vast, and working with it directly would be computationally
prohibitive. By identifying a subspace through the $U_{\text{enc}}$
transformation where the black hole information is encoded, Alice can work
with a reduced, more manageable set of states, facilitating the decoding
process.

When Alice wants to retrieve the information, she is looking to decode the
information stored in this subspace. This decoding process reverses
$U_{\text{enc}}$ to retrieve the original information, or at least the
pertinent part of it, even after parts of the system have been erased.
However, reversing $U_{\text{enc}}$ to decode the information isn’t
straightforward. Alice uses a set of quantum operations, a universal gate
(CNOT gates and Hadamard transformations), to develop $U_{\text{enc}}$, and
she tries to identify a suitable decoding process that can retrieve the
original information from the encoded state. To do this, Alice introduces an
additional system denoted as $B^{\prime}$, with the same number of qubits as
$B$, and forms a new, more extensive set of encodings. The crucial part of the
decoding process involves a complex unscrambling of the entanglements between
$B^{\prime}$ and $R$ through another set of transformations $U_{\text{enc}}$,
which is constructed from $U_{\text{dyn}}$ and the transformation that
involves the new system $B^{\prime}$, $U_{\text{mix, B'}}$.

More specifically, HH want to establish $U_{\text{dyn}}$ as the encoding
transformation $U_{\text{enc}}$ and $U_{R}$ as a correction operation.
However, there is an issue with the dimensionality of the code space, which
they address by introducing an additional system $B^{\prime}$ with the same
number of qubits as $B$. They then apply a transformation
$U_{\text{mix},B^{\prime}}$ to entangle $B^{\prime}$ with $B$, thereby
creating a $k$-qubit code subspace within a larger $2k+m+n$ qubit Hilbert
space using $U_{\text{enc}}$. $U_{\text{enc}}$ is defined by applying
$U_{\text{mix},B^{\prime}}$ followed by $U_{\text{dyn}}$. $U_{\text{enc}}$
operates on initial states to generate a new state that incorporates $B$,
$B^{\prime}$, $H$, and $R$, such that:

$U_{\text{enc}}\ket{b^{\prime}}_{B^{\prime}}\ket{0}_{BHR}=\frac{1}{\sqrt{|B||H|}}\sum_{bh}U_{\text{mix},B^{\prime}}\ket{b^{\prime}b}_{B^{\prime}B}\ket{h}_{H}U_{R}\ket{bh0}_{R}.$
(9)

HH acknowledge the presence of errors introduced by the environment,
conceptualized as erasures affecting both $B$ and $H$. To restore the initial
state by unscrambling the entanglement between $B^{\prime}$ and $R$, one needs
to implement $U^{\dagger}_{R}$. By applying $U^{\dagger}_{R}$ on the newly
defined state, and subsequently acting with $U_{\text{mix},B^{\prime}}$ , the
information $b^{\prime}$ is recovered. This process involves replacing the
second element of each pair of qubits from the first $k$ qubits of $R$ instead
of from $B$, which isn’t accessible anymore. This produces a state:

$\ket{b^{\prime}}\frac{1}{\sqrt{|B||H|}}\sum_{bh}\ket{b}_{B}\ket{h}_{H}\ket{bh0}_{R},$
(10)

Following the recovery of $b^{\prime}$, the initial state can be restored in
polynomial time using ancillary qubits to reset $BHR$ to the state
$\Ket{0}_{BHR}$ and then utilizing $U_{\text{enc}}$ to revert to the desirable
state formed by the encoding transformation involving $B^{\prime}$ and $BHR$
[Har-Hay].

By introducing a new system $B^{\prime}$, Alice adds a new set of variables.
$B^{\prime}$ interacts with the radiation ($R$); a new set of entangled states
between $B^{\prime}$ and $R$ are formed through this interaction. These
entangled states have information about the black hole. $U_{\text{enc}}$ is a
set of operations designed to unscramble the entangled states formed by
interactions between $B^{\prime}$ and $R$. It uses the dynamics of the black
hole and the transformations involving $B^{\prime}$ to create a scenario where
the entangled information can be unscrambled, running some processes in
reverse to recover the original data. Alice uses $U_{\text{enc}}$ to recover
the original data encoded in the entangled states of the black hole
information. This is trying to reverse the effects of the black hole dynamics
on the information by decoding the previously encoded information in the
scrambled, entangled states. By utilizing a more comprehensive set of
encodings involving the additional system $B^{\prime}$ and implementing a
complex transformation to unscramble the entanglements, Alice aims to recover
the original data and thereby solve the problem of decoding the information
about the state of the black hole, circumventing the issues encountered with
not having access to all the required qubits in the previous setup. This
strategy is grounded on the hope that by properly configuring the new system
$B^{\prime}$ and skillfully using $U_{\text{enc}}$, Alice can create a pathway
through the entanglement structure that allows her to access the information
she is after, even without direct access to all parts of the system.

###  6.2 A beacon of hope amidst lingering challenges

For the channel just constructed, $n$ is the total number of bits that can
theoretically be lost due to various errors or complications while still
retaining the ability to correct those errors and successfully decode the
information. $2k+m+n$ breaks down this $n$ into components corresponding to
different aspects or parameters of the black hole model. So, $k+m$ bits have
already been unavoidably lost because Alice doesn’t have access to $B$ and
$H$. $\frac{n-k-m}{2}$ is the remaining number of bits Alice can afford to
lose due to other errors and still maintain the possibility of successful
error correction. $\alpha$ represents the fraction of the radiation that
consists of gravitons. HH then make a critical point: even if all the
gravitons (which constitute less than half of the radiation) are lost, Alice
could theoretically still extract the necessary entanglement information
accurately because she still has room for error correction — she can still
lose up to $\frac{n-k-m}{2}$ bits and remain within the bounds for successful
error correction. Even if Alice cannot control and measure the gravitons, she
can wait until enough radiation has been emitted such that the information
about the interior of the black hole becomes accessible in the radiation. She
can still successfully decode the necessary information to solve the task.

However, HH note two important complications [Har-Hay]

1) Computational complexity comes into play here as a significant roadblock.
Extracting the information from the radiation is an immensely complex
computational task. This complexity grows with the size of the black hole and
the amount of information to be retrieved.

2) The task must be done before the black hole fully evaporates, setting a
strict time limit on the procedure. Thus, while theoretically possible,
practically carrying out the AMPS experiment to solve the black hole
information problem without considering computational complexity would be
extraordinarily challenging and likely unfeasible due to the computational
resources required. Thus, Alice might not have enough time to complete her
task before the black hole evaporates, hence not being able to rule out the
presence of a firewall definitively.

##  7 A physics problem becomes a quantum computing problem

###  7.1 HH’s Error Correctability problem

HH introduce a computational problem termed Error Correctability [Har-Hay].
This problem arises in the context of $B$, $H$, and $R$. The state of this
system is transformed by $U_{\text{dyn}}$ acting on an initial state,
resulting in a new state $\ket{\psi}_{BHR}$, which exhibits maximal
entanglement between $B$ and $HR$.

$\ket{\psi}_{BHR}=U_{\text{dyn}}\ket{000}_{BHR},$ (11)

The crux of the Error Correctability problem is to ascertain whether it is
possible to decode the maximal entanglement with $B$ by only using information
from $R$. This problem has a QSZK proof, which is characterized by a verifier
checking the results after a prover implements a quantum error correction
operation on $R$, despite the potential for this process to take an
exponentially long time.

HH replicate the kind of maximal entanglement generated during the dynamical
evolution governed by $U_{\text{dyn}}$ using a different strategy involving a
noise operator $U_{\text{noise}}$. In the strategy:

$\ket{\psi}_{BHR}=U_{\text{noise}}\ket{000}_{BHR},$ (12)

is utilized to create a state where the $BH$ and $R$ systems become maximally
entangled. By applying $U_{\text{noise}}$ repeatedly (i.e., working with $k$
copies of $\ket{\psi}$, noted as $\ket{\psi}^{\otimes k}$) one converges
towards a state with near-maximal entropy concentrated in a typical subspace
of the tensor product of $k$ copies of the $B$ and $H$ Hilbert spaces.
However, HH mention that this approach, while similar to the true maximal
entanglement generated by $U_{\text{dyn}}$, might be slightly weaker. This
suggests that while this strategy can approach the maximal entanglement that
$U_{\text{dyn}}$ would generate, it might not fully replicate it, potentially
missing some correlations or not fully reaching the maximal entropy that would
signify truly maximal entanglement. Hence, although this strategy involving
$U_{\text{noise}}$ can yield a state with a high degree of entanglement
between the $BH$ and $R$ subsystems, it seems it might not exactly reproduce
$U_{\text{dyn}}$.

###  7.2 Evaluating Alice’s task through the lens of QSZK and BQP complexity
classes

HH refer to the following complexity classes [Har-Hay]: the BQP complexity
class, which contains decision problems that can be solved by a quantum
computer in polynomial time, with an allowable error probability. The SZK
complexity class: a class of problems where solutions can be verified using
classical computers, and where the ”yes” instances can be proven with zero-
knowledge proofs, where the verifier learns nothing other than the fact that
the statement is true. QSZK (Quantum Statistical Zero Knowledge), a quantum
analog of the SZK complexity class. This complexity class contains BQP. QSZK
is a complexity class that refers to the set of computational problems with
yes/no answers where a (potentially dishonest) prover can always convince a
verifier of the yes instances but will fail with high probability to convince
them of the no instances using quantum computations.

HH identify the Error Correctability problem as a QSZK-complete problem [Har-
Hay]. A problem that is QSZK-complete represents the hardest problems in the
QSZK class. If there is a polynomial time solution for one QSZK-complete
problem, then there are polynomial time solutions for all problems in the QSZK
class. In other words, if Error Correctability is identified as a QSZK-
complete, then it has two properties:

1) It is in QSZK and can be solved using a quantum computer with the help of
an all-powerful, though potentially dishonest, prover.

2) Any problem in QSZK can be reduced to the Error Correctability problem
through a polynomial-time algorithm.

Solving the Error Correctability problem would imply a solution for every
problem in the QSZK class.

HH argue that if QSZK were equal to BQP, then all the problems that can be
solved with a quantum verifier and a prover (QSZK) can also be solved with
just a quantum computer operating in polynomial time (BQP). In other words,
the prover does not add any computational power; a quantum computer alone is
sufficient to solve these problems. If this decoding can be done on a quantum
computer in polynomial time, it would mean that all QSZK problems can be
solved in BQP, implying QSZK = BQP [Har-Hay]. HH are asking whether the
decoding process required to solve the Error Correctability problem can be
done in polynomial time with the size of the circuit used to represent
correctable noise denoted by $U_{\text{dyn}}$. They reiterate that finding a
polynomial-time solution to the decoding problem (concerning the size of the
$U_{\text{dyn}}$) would mean that the Error Correctability problem (and hence
all problems in QSZK) can be solved in BQP time. This would establish that
QSZK = BQP, showing that a quantum computer, without the help of a prover, can
solve all problems in QSZK.

HH conclude the discussion by providing the following evaluation [Har-Hay]:

> […] by recasting Alice’s problem as quantum error correction, we have set it
> into a framework where there are general arguments that such problems likely
> take exponential time to solve. Moreover the practical difficulties of doing
> the experiment, in particular the problems associated with measuring
> gravitons, further increase the difficulty of this computational task. We
> did not quite manage to prove that her task is NP-hard at fixed $k$, but it
> is almost certainly at least QSZK-hard and there are strong reasons to
> believe that such problems can’t be solved in polynomial time on a quantum
> computer. From the computer science point of view, it would be extremely
> surprising if implementing $U^{\dagger}_{R}$ did not require exponential
> time.

###  7.3 Aaronson’s improvements to the complexity assumptions underlying HH’s
task

Scott Aaronson suggested improvements to HH’s decoding task [Aar]. He proposed
improvements to the complexity assumptions underlying HH’s decoding task.
Instead of working directly within the framework of complexity theory classes,
he ground the problem’s difficulty in established cryptographic concepts,
leveraging the one-way functions (OWF)s and introducing hardcore predicates to
argue the hardness of the decoding task [Aar].

Aaronson endeavors to demonstrate that if there are injective OWFs, functions
that are easy to compute in the forward direction but hard to invert even by
quantum computers, then the HH decoding task is indeed hard. This approach
aims to ground the decoding task in more widely accepted theoretical
foundations, thereby enhancing the robustness of the argument concerning the
inherent difficulty of the HH decoding task by rooting it in established
cryptographic principles based on OWFs. Information is encoded using these
OWFs. To decode information from a portion of these states (i.e., from the
Hawking radiation part), one needs to find the inverse of the OWF on the
encoded information – which is assumed to be computationally hard because of
the property of OWFs. Therefore, if someone could solve the HH decoding task,
it would mean they have a method to invert OWFs. This has far-reaching
implications, including breaking the widely accepted cryptographic systems
that rely on the hardness of inverting OWFs.

Aaronson further argues that solving the HH decoding problem would require at
least as much computational resource as the hardest problems in the collision
problem class. He connects the ability to invert OWFs and the ability to find
collisions. If one could efficiently invert an OWF, one could find collisions,
undermining the security assumptions of cryptographic systems based on these
functions. Aaronson’s statement emphasizes the fundamental difficulty in
decoding the Hawking radiation as it would imply being able to solve other
hard problems in computer science and cryptography.

Aaronson is tying the hardness of a physics problem – decoding Hawking
radiation and the firewall paradox – to established hard problems in computer
science, grounding the task’s believed difficulty in well-established
complexity theory [Aar]. Through his improvements to the HH decoding task,
Aaronson brought a deeper computer science perspective into the discussion
surrounding the firewall paradox, specifically leveraging concepts from the
computational complexity theory and cryptography. By framing the HH decoding
task as a problem in computer science and showing that it’s at least as hard
as inverting one-way functions, Aaronson translated a physics problem into the
language and framework of computer science. This approach not only allows for
a more robust argument regarding the complexity of the problem but also
facilitates interdisciplinary dialogue and understanding by linking the
physical scenario to well-established concepts in the computer science domain.

## Acknowledgement

This work is supported by ERC advanced grant number 834735.

## References

  * [Aar] Aaronson, S. (2016). “The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes.” _arXiv_ : 1607.05256 [quant-ph]
  * [AMPS] Almheiri, A., Marolf, D., Polchinski, J., and Sully, J., (2013). ”Black Holes: Complementarity or Firewalls?” _arXiv_ :1207.3123v4.
  * [Bousso] Bousso, R. (2012). “Complementarity Is Not Enough.” _Physical Review D_ 87, 124023.
  * [Har-Hay] Harlow, D. and Hayden, P. (2013). “Quantum computation vs. firewalls.” _Journal of High Energy Physics_ 6, pp. 1-56.
  * [Haw74] Hawking S. (1974) “Black hole explosions?” _Nature_ 248, pp. 30-31.
  * [Haw76] Hawking, S. (1976). “Breakdown of predictability in gravitational collapse.” _Physical Review D_ 14, pp. 2460-2473.
  * [Haw77] Hawking, S. (1977). “The Quantum Mechanics of Black Holes.” _Scientific American_ 236, pp. 34-42.
  * [STU] Susskind, L., Thorlacius, L. and Uglum, J. (1993). “The Stretched Horizon and Black Hole Complementarity.” _Physical Review D_ 48 3743.
  * [LPSTU] Lowe, D. A., Polchinski, J., Susskind, L., Thorlacius, L. and Uglum, J. (1995). “Black Hole Complementarity versus Locality.” _Physical Review D_ 52, 6997.