# Quantifying entanglement in a 68-billion dimensional quantum state space

James Schneeloch1 Christopher C. Tison1,2,3 Michael L. Fanto1,4 Paul M.
Alsing1 & Gregory A. Howland${}^{1,4,^{*}}$

###### Abstract

††This is a post-peer review, pre-copyedit version of an article published in
Nature Communications. The final authenticated version is available online at:
http://dx.doi.org/10.1038/s41467-019-10810-z

Entanglement is the powerful and enigmatic resource central to quantum
information processing, which promises capabilities in computing, simulation,
secure communication, and metrology beyond what is possible for classical
devices. Exactly quantifying the entanglement of an unknown system requires
completely determining its quantum state, a task which demands an intractable
number of measurements even for modestly-sized systems. Here we demonstrate a
method for rigorously quantifying high-dimensional entanglement from extremely
limited data. We improve an entropic, quantitative entanglement witness to
operate directly on compressed experimental data acquired via an adaptive,
multilevel sampling procedure. Only $6,456$ measurements are needed to certify
an entanglement-of-formation of $7.11\pm.04$ ebits shared by two spatially-
entangled photons. With a Hilbert space exceeding 68 billion dimensions, we
need $20$-million-times fewer measurements than the uncompressed approach and
$10^{18}$-times fewer measurements than tomography. Our technique offers a
universal method for quantifying entanglement in any large quantum system
shared by two parties.

Air Force Research Laboratory, Information Directorate, Rome, NY 13441 USA

Department of Physics, Florida Atlantic University, Boca Raton, FL 33431 USA

Quanterion Solutions Incorporated, Utica, NY 13502 USA

Rochester Institute of Technology, Rochester, NY 14623 USA

## Introduction

Achieving a quantum advantage for information processing requires scaling
quantum systems to sizes that can provide significant quantum resources,
including entanglement. Large quantum systems are now realized across many
platforms, including atomic simulators beyond $50$ qubits[1, 2, 3], nascent
superconducting and trapped-ion based quantum computers[4, 5], integrated-
photonic circuits[6, 7, 8, 9, 10], and photon-pairs entangled in high-
dimensional variables[11, 12, 13, 14, 15, 16].

As quantum-information-based technologies mature, it will become useful to
separate the physical layer providing quantum resources (e.g trapped ions,
photons) from the logical layer that utilizes those resources. For example,
many imperfect qubits may form one logical qubit[17, 18], or thousands of
atoms may coherently act as a single-photon quantum memory[19, 20]. As with
classical communication and computing, protocols and algorithms will be
implemented in the logical layer with minimal concern for the underlying
platform. Because real-world systems are varied and imperfect, the quantum
resources they provide must be characterized before use[17].

Certifying an amount of entanglement in a large quantum system is an essential
but daunting task. While entanglement witnesses[21, 22] and Bell tests[23] can
reveal entanglement’s presence, quantification generally requires a full
estimation of the quantum state[24]. Beyond moderately sized states, the
number of parameters to physically measure (i.e. the number of the
measurements) becomes overwhelming, making this approach unviable for current
and future large-scale quantum technologies.

Any practical method for quantitative entanglement certification must require
only limited data. Two ideas can dramatically reduce the needed measurement
resources. First is the development of quantitative entanglement witnesses,
which bound the amount of entanglement without full state estimation[25, 26,
27, 28]. In a recent landmark experiment, $4.1$ entangled bits (ebits) of
high-dimensional biphoton entanglement was certified using partial state
estimation[29]. One ebit describes the amount of entanglement in a maximally
entangled, two-qubit state[24].

Second, prior knowledge can be exploited to economize sampling. Certain
features, or structure, are expected in specific systems. In highly-entangled
quantum systems, for example, some observables should be highly correlated,
the density matrix will be low-rank, or the state may be nearly pure. Such
assumptions can be paired with numerical optimization to recover signals
sampled below the Nyquist limit. One popular technique is Compressed
Sensing[30], which has massively disrupted conventional thinking about
sampling. Applied to quantum systems, compressed sensing reduced measurement
resources significantly for tasks including tomography[31, 32, 33, 34, 35, 36,
37] and witnessing entanglement[38, 39].

Computational recovery techniques have substantial downsides. Because they are
estimation techniques, conclusions drawn from their results are contingent on
the veracity of the initial assumptions. They are therefore unsuitable for
closing loopholes or verifying security. Numerical solvers are often proven
correct under limited noise models and require hand-tuned parameters,
potentially adding artifacts and complicating error analysis. Finally, the
computational resources needed become prohibitive in very large systems. The
largest quantum systems characterized using these approaches remain
considerably smaller than state-of-the-art.

Here we provide an approach to entanglement quantification that overcomes
these downsides. First, we improve an entropic, quantitative entanglement
witness to operate on arbitrarily downsampled data. Then we develop an
adaptive, multilevel sampling procedure to rapidly obtain compressed
distributions suitable for the witness. Crucially, our sampling assumptions
are independent of the entanglement certification, so our method can guarantee
security. Because we avoid numerical optimization, error analysis is
straightforward and few computational resources are needed.

## Results

###  0.1 Entropic witnesses of high-dimensional entanglement

Entanglement is revealed when subsystems of a quantum state are specially
correlated. A common situation divides a system between two parties, Alice and
Bob, who make local measurements on their portion. Given two mutually
unbiased, continuous observables $\mathbf{\hat{x}}$ and $\mathbf{\hat{k}}$,
they can measure discrete joint probability distributions
$P(\mathbf{X}_{\mathrm{a}},\mathbf{X}_{\mathrm{b}})$ and
$P(\mathbf{K}_{\mathrm{a}},\mathbf{K}_{\mathrm{b}})$ by discretizing to pixel
sizes $\Delta_{\mathrm{X}}$ and $\Delta_{\mathrm{K}}$. Here, bold notation
indicates that $\mathbf{X}$ and $\mathbf{K}$ may (though need not) represent
multidimensional coordinates. For example $\mathbf{X}$ and $\mathbf{K}$ might
represent cartesian position and momentum that can be decomposed into
horizontal and vertical components such that $\mathbf{X}=(X,Y)$ and
$\mathbf{K}=(K^{(\mathrm{x})},K^{(\mathrm{y})})$.

A recent, quantitative entanglement witness[40] uses these distributions to
certify an amount of entanglement:

$d\log_{2}\left(\frac{2\pi}{\Delta_{\mathrm{X}}\Delta_{\mathrm{K}}}\right)-H(\mathbf{X}_{\mathrm{a}}|\mathbf{X}_{\mathrm{b}})-H(\mathbf{K}_{\mathrm{a}}|\mathbf{K}_{\mathrm{b}})\leq
E_{\mathrm{f}},$ (1)

where, for example, $H(\mathbf{A}|\mathbf{B})$ is the conditional Shannon
entropy for $P(\mathbf{A},\mathbf{B})$. $E_{\mathrm{f}}$ is the Entanglement
of Formation, a measure describing the average number of Bell pairs required
to synthesize the state. Eq. 1 does not require full state estimation, but
depends on an informed choice of $\hat{\mathbf{x}}$ and $\hat{\mathbf{k}}$.
Still, in large systems, measuring these joint distributions remains
oppressive. For example, if $\mathbf{X}_{\mathrm{a}}$ has $100$ possible
outcomes, determining $P(\mathbf{X}_{\mathrm{a}},\mathbf{X}_{\mathrm{b}})$
takes $100^{2}$ joint measurements. ‘ Describing quantum uncertainty with
information-theoretic quantities is increasingly popular[41, 42]. Entropies
naturally link physical and logical layers and have useful mathematical
properties. In particular, many approximations to the joint distributions can
only increase conditional entropy. Because Eq. 1 bounds $E_{\mathrm{f}}$ from
below, any such substitution is valid.

###  0.2 Improving an entropic entanglement witnesses for use with limited
data

We use two entropic shortcuts to improve the entanglement witness. First, if
the system is highly entangled, and $\hat{\mathbf{x}}$ and $\hat{\mathbf{k}}$
are well-chosen, the joint distributions will be highly correlated; a
measurement outcome for $\mathbf{X}_{\mathrm{a}}$ should correlate to few
outcomes for $\mathbf{X}_{\mathrm{b}}$. The distributions are therefore highly
compressible. Consider replacing arbitrary groups of elements in
$P(\mathbf{X}_{\mathrm{a}},\mathbf{X}_{\mathrm{b}})$ with their average values
to form a multilevel, compressed estimate
$\tilde{P}(\mathbf{X}_{\mathrm{a}},\mathbf{X}_{\mathrm{b}})$. By multilevel,
we mean that the new, estimated distribution will appear as if it was sampled
with varying resolution—fine detail in some regions and coarse detail in
others. Because coarse-graining can not decrease conditional entropy, Equation
1 remains valid for
$\tilde{P}(\mathbf{X}_{\mathrm{a}},\mathbf{X}_{\mathrm{b}})$ and
$\tilde{P}(\mathbf{K}_{\mathrm{a}},\mathbf{K}_{\mathrm{b}})$ (see Supplemental
Material: Proof arbitrary coarse-graining cannot decrease conditional
entropy).

Good estimates for
$\tilde{P}(\mathbf{X}_{\mathrm{a}},\mathbf{X}_{\mathrm{b}}$) and
$\tilde{P}(\mathbf{K}_{\mathrm{a}},\mathbf{K}_{\mathrm{b}})$ can be
efficiently measured by sampling at high resolution in correlated regions and
low resolution elsewhere. Note that the original ($P$) and estimate
($\tilde{P})$) are full correlation matrices with $N$ elements, but only $M\ll
N$ values measured to specify $\tilde{P}$. The witness is valid for arbitrary
downsampling; it works best when the approximate and actual distributions are
most similar, but can never overestimate $E_{\mathrm{f}}$ or allow false-
positives.

Second, if the observables are multi-dimensional such that they can be
decomposed into $d$ marginal, component observables (e.g. horizontal and
vertical components)
$\hat{\mathbf{x}}=(\hat{x}^{(1)},\hat{x}^{(2)},...,\hat{x}^{(d)})$ (similar
for $\hat{\mathbf{k}}$), the conditional entropies have the property

$H(\mathbf{X}_{\mathrm{a}}|\mathbf{X}_{\mathrm{b}})\leq\sum_{i}^{d}H(X^{(i)}_{\mathrm{a}}|X^{(i)}_{\mathrm{b}}),$
(2)

with equality when $P(\mathbf{X}_{\mathrm{a}},\mathbf{X}_{\mathrm{b}})$ is
separable. If we expect nearly-separable joint-distributions, the reduced,
marginal joint-distributions $P(X^{(i)}_{\mathrm{a}},X^{(i)}_{\mathrm{b}})$
can be separately measured but still capture nearly all of the correlations
present. For example, in a two-dimensional cartesian scenario, we might
separately measure horizontal correlations $P(X_{\mathrm{a}},X_{\mathrm{b}})$,
$P(K^{\mathrm{(x)}}_{\mathrm{a}},K^{\mathrm{(x)}}_{\mathrm{b}})$ and vertical
correlations $P(Y_{\mathrm{a}},Y_{\mathrm{b}})$,
$P(K^{\mathrm{(y)}}_{\mathrm{a}},K^{\mathrm{(y)}}_{\mathrm{b}})$. For
$d$-component observables, this is a $d^{\text{th}}$-power reduction in the
number of measurements. Like the first shortcut, this approximation also can
not overestimate $E_{\mathrm{f}}$.

Combining both improvements, our new quantitative entanglement witness is

$\displaystyle\sum_{i=1}^{d}\Biggl{[}\log_{2}$
$\displaystyle\left(\frac{2\pi}{\Delta_{\mathrm{X}}^{(i)}\Delta_{\mathrm{K}}^{(i)}}\right)$
(3) $\displaystyle-$
$\displaystyle\tilde{H}(X^{(i)}_{\mathrm{a}}|X^{(i)}_{\mathrm{b}})-\tilde{H}(K^{(i)}_{\mathrm{a}}|K^{(i)}_{\mathrm{b}})\Biggr{]}\leq
E_{\mathrm{f}}.$

###  0.3 Proof of concept experimental setup

As a test experimental system, we use photon pairs entangled in their
transverse-spatial degrees of freedom[43, 44], where the transverse plane is
perpendicular to the optic axis. Our testbed, given in Figure 1(a), creates
photon pairs via spontaneous parametric downconversion (see Methods).
Generated photons are positively correlated in transverse-position and anti-
correlated in transverse-momentum. This state closely approximates the
original form of the Einstein-Podolsky-Rosen paradox. Because position
$\hat{\mathbf{x}}=(\hat{x},\hat{y})$ and momentum
$\hat{\mathbf{k}}=(\hat{k}^{\mathrm{(x)}},\hat{k}^{\mathrm{(y)}})$ (where
$\mathbf{\hat{k}}=\mathbf{\hat{p}}/\hbar$) observables are continuous, this
state is very high-dimensional.

After creation, the twin photons are separated at a beam splitter and enter
identical measurement apparatuses, where a basis selection system allows for
interrogating position or momentum. A digital micromirror device (DMD)—an
array of individually addressable micromirrors—is placed in the output plane.
By placing patterns on the signal and idler DMDs and using coincidence
detection, rectangular regions of the position or momentum joint-distributions
are sampled at arbitrary resolution.

###  0.4 Adaptive, multi-level data acquisition

We measure joint-distributions $\tilde{P}(X_{\mathrm{a}},X_{\mathrm{b}})$,
$\tilde{P}(Y_{\mathrm{a}},Y_{\mathrm{b}})$,
$\tilde{P}(K^{\mathrm{(x)}}_{\mathrm{a}},K^{\mathrm{(x)}}_{\mathrm{b}})$, and
$\tilde{P}(K^{\mathrm{(y)}}_{a},K^{\mathrm{(y)}}_{\mathrm{b}})$. Finding
compressed distributions requires a multilevel partitioning of the joint space
that is not known a priori. Our adaptive approach is inspired by quad-tree
image compression[45]. An example is shown in Figure 1(b-g). First, all DMD
mirrors are directed towards the detector to obtain a total coincidence rate
$R_{\mathrm{T}}$. Then, the joint space is divided into four quadrants (c),
which are independently sampled. If the count rate in the $i^{\text{th}}$
quadrant exceeds a threshold $\alpha R_{\mathrm{T}}$ ($0\leq\alpha\leq 1$),
the region is recursively split and the process is repeated. The algorithm
rapidly identifies important regions of the joint-space for high-resolution
sampling.

We set the maximum resolution of our system to $512\times 512$ pixels-per-
photon for a $512^{4}$-dimensional joint space. The recovered joint-
distributions in position and momentum are given in Figure 2(a-d). Figure
2(e-f) show $\tilde{P}(X_{\mathrm{a}},X_{\mathrm{b}})$ with the partitioning
overlaid. These display the expected strong position and momentum
correlations. A histogram showing the number of partitions at various scales
is given in Figure 2(g); most partitions are either $1\times 1$ or $2\times 2$
pixels in size. Only $6,456$ partitions are needed to accurately cover the
$512^{4}$-dimensional space—an astonishing $20$-million-fold improvement
versus using the unimproved witness. Over $10^{21}$ measurements are needed to
perform full, unbiased tomography.

The entanglement witness (Equation 3) applied to the data in Figure 2 is shown
in Figure 3. For short acquisition times, there is a systematic bias towards
estimating a large $E_{\mathrm{f}}$. This occurs because many of the poorly
correlated regions have not yet accumulated any detection events, resulting in
a systematic bias towards low conditional entropies. Statistical error is low
in this region because the highly-correlated regions have high-count rates and
rapidly reach statistical significance. With additional measurement time, the
initial bias diminishes and statistical error decreases. To our knowledge,
$7.11\pm.04$ ebits is the largest quantity of entanglement experimentally
certified in a quantum system. More than $14$ maximally-pairwise-entangled
logical qubits are needed to describe an equal amount of entanglement. We do
not require advanced post-processing such as numerical optimization,
estimation, or noise reduction; however, we do post-select on coincident
detection events and optionally subtract accidental coincidences (see
Methods). Our witness does not explicitly require any post-processing, and is
suitable for use in adversarial scenarios given a pristine experimental
system.

The performance of our technique as a function of maximum discretization
resolution is shown in Figure 4. Figure 4(a) shows the approximate
distribution partition number as a function of discretization dimension and
the improvement factor over naive sampling. Figure 4(b) shows the certified
$E_{\mathrm{f}}$, with and without accidental subtraction, along with the
ideal $E_{\mathrm{f}}$ for our source under a double-Gaussian
approximation[44]. Because our pump laser is not Gaussian (Figure 1(a)), the
actual $E_{\mathrm{f}}$ is slightly less but difficult to simulate. Error bars
enclosing two standard deviations are scarcely visible. For low resolution,
fewer than $1,000$ measurements witness entanglement. Progressively refining
to higher effective resolution allows more entanglement to be certified until
the maximum is reached.

## Discussion

We have shown an efficient method for performing information-based
entanglement certification in a very large quantum system. An alternative,
important metric for quantifying entanglement in high-dimensional systems is
the entanglement dimensionality, or Schmidt rank, which describes the number
of modes over which the entanglement is distributed [46, 22, 47, 48]. In
contrast, entanglement measures quantify entanglement as a resource of
entangled bits without regard for their distribution. Efficiently certifying
the entanglement dimensionality faces many of the same problems as certifying
a number ebits, such as the intractability of full tomography and the desire
to avoid side effects from prior assumptions. Recently, Bavaresco et. al. used
measurements in only two bases to efficiently certify over $9$ entangled
dimensions between orbital-angular-momentum entangled photon pairs without
special assumptions about the underlying state [49].

The number of entangled dimensions and the number of entangled bits are
complementary but distinct characterizations of entanglement [50]. If a
density matrix can not be decomposed into pure states with Schmidt rank less
than $d$, then the state is at least $d$-dimensionally entangled. However, a
$d$-dimensional entangled state may possess an arbitrarily small amount of
entanglement. Consider a system with a large Schmidt rank, but where one
coefficient of the Schmidt decomposition is much larger than the others. This
system will have a large entanglement dimensionality but require few entangled
bits to synthesize. In this way, a given entanglement dimensionality $D$
provides an upper bound on the entanglement of formation $E_{\mathrm{f}}$ such
that $0<E_{\mathrm{f}}\leq\log_{2}D$. In contrast, a given $E_{\mathrm{f}}$
provides a lower bound to the entanglement dimensionality $D\geq
2^{E_{\mathrm{f}}}$, describing the situation where all $D$ dimensions are
maximally entangled. Our quantitative witness therefore also certifies
entanglement dimensionality, but may dramatically underestimate when the
target system is not near-maximally entangled (e.g. with additive noise or
non-uniform marginals). In our case, we certify $2^{7.11}\geq 138$ maximally-
entangled dimensions with background subtraction and $2^{3.43}\geq 10$
maximally-entangled dimensions without background subtraction. To our
knowledge, $10$ entangled dimensions is the largest certified entanglement
dimensionality without assumptions about the state.

Our approach shows a path forward for certifying quantum resources in large
quantum systems, where we exploit prior knowledge without conventional
downsides. We show the power of an information-theoretic approach to
characterizing quantum systems, and how compression can be leveraged without
computational signal recovery. Though the method presented here is limited to
EPR-style systems where entanglement is shared by two parties, we expect
similar techniques for many-body systems utilizing higher-order correlations
will soon follow.

###  0.5 Experimental apparatus

$810$ nm, spatially entangled photon pairs are produced via spontaneous
parametric downconversion (SPDC)[44]. The pump laser is a $405$ nm diode laser
(CrystaLaser DL405-025-SO) attenuated to $7.9$ mW with a $356$ $\mu$m (x)
$\times$ $334$ $\mu$m (y) beam waist. A spectral clean-up filter (Semrock
Versachrome TBP01-400/16) removes unwanted $810$ nm light. The pump laser is
not spatially filtered. The nonlinear crystal is a $3$ mm long BiBO crystal
oriented for type-I, degenerate, collinear SPDC. The crystal is held at
$32.3^{\circ}$C in an oven for long-term stability. A low-pass interference
filter (Semrock LP442) removes remaining pump light, followed by a telescope
relay system ($f_{1}=50$ mm, $f_{2}=100$ mm) that magnifies the SPDC field
$\approx 2$X. A half-waveplate and polarizing beamsplitter choose between
imaging ($\hat{\mathbf{x}}$) and Fourier-transforming ($\hat{\mathbf{k}}$)
beam-paths; a beam block is placed in the unused path.

The DMDs (TI Lightcrafter 4500) are computer controlled via a digital video
port (HDMI). A $512\times 1024$ physical-pixel area was used for data given in
this manuscript. Because the DMD has twice the vertical pixel density, this
corresponds to a square area. $10$ mm effective focal length, aspheric lenses
(Thorlabs AC080-010) couple light into $100$ micron core multi-mode fibers
connected to photon-counting detector modules (Excelitas SPCM-AQ4C-10).
$810/10$ nm bandpass filters (Thorlabs FBS810-10) are placed before the fiber
coupling. A time-correlated single-photon counting module (PicoQuant
HydraHarp400) produces histograms of photon-pair relative arrival times. We
post-select on coincident detections within a $1$ ns coincidence window
centered on the histogram peak. With all DMD mirrors pointed towards the
detectors, there are approximately $26,400$ total coincidences/second.

###  0.6 Data collection

The apparatus must be adjusted to separately measure the four reduced, joint-
probabilty distributions $P(X_{\mathrm{a}},X_{\mathrm{b}})$,
$P(Y_{\mathrm{a}},Y_{\mathrm{b}})$,
$P(K^{\mathrm{(x)}}_{\mathrm{a}},K^{\mathrm{(x)}}_{\mathrm{b}})$, and
$P(K^{\mathrm{(y)}}_{\mathrm{a}},K^{\mathrm{(y)}}_{\mathrm{b}}).$ For example,
to access the horizontal, joint-position distribution
$P(X_{\mathrm{a}},X_{\mathrm{b}})$, we adjust the half-waveplates to direct
light down the imaging beam-paths so the DMDs lie in an image plane of the
nonlinear crystal. To access a particular, rectangular element of the
distribution, local, one-dimensional ”top-hat” patterns are placed on signal
($\mathrm{a}$) and idler ($\mathrm{b}$) DMDs that only vary horizontally. In
the regions where light should be directed to the detectors, all vertical
pixels are used. The local images’ outer-product defines the rectangular
region of the joint-space $P(X_{\mathrm{a}},X_{\mathrm{b}})$ that is being
sampled.

To instead access the vertical, joint-position distribution
$P(Y_{\mathrm{a}},Y_{\mathrm{b}})$, local DMD patterns are used that only vary
vertically. The joint-momentum distributions are similarly sampled, with the
half-waveplates instead adjusted to send light down the Fourier transforming
optical path so that the DMDs sit in the far-field of the nonlinear crystal.

###  0.7 Adaptive Sampling Algorithm

For each configuration, experimental data is stored in nodes in a quad-tree
decomposition of $P$ whose levels describe increasingly fine detail. The
$i^{\mathrm{th}}$ node corresponds to a square area of $\tilde{P}$ at location
$(x^{i}_{\mathrm{a}},x^{i}_{\mathrm{b}})$ with span
$w^{i}_{\mathrm{a}}=w^{i}_{\mathrm{b}}=w$. Nodes are sampled by placing the
corresponding, one-dimensional local patterns on the DMDs and generating a
coincidence histogram during acquisition time $T_{\mathrm{a}}=0.5$ s.
Coincidences $C_{i}$ are counted within a $1$ ns coincidence window centered
on the coincidence peak; accidental coincidences $A_{i}$ are counted in a $1$
ns window displaced $2$ ns from the coincidence window. Coincidence and
accidental values are appended to a list each time the node is sampled. The
estimated count-rate $R_{i}=\braket{C_{i}}/\epsilon_{i}T_{\mathrm{a}}$, where
$\epsilon_{i}$ is a calibrated, relative fiber coupling efficiency.
Optionally, $A_{i}$ can be subtracted from $C_{i}$ for accidental removal.
Uncertainty is computed by assuming Poissonian counting statistics for $C_{i}$
and $A_{i}$ and applying standard, algebraic propagation of error through the
calculation of the entanglement quantity (Eq. 3).

The data collection algorithm consists of a partitioning phase followed by an
iterative phase. During partitioning, the algorithm repeatedly iterates
through a scan-list of leaves of the tree. Node $i$ is considered stable when
$\mathrm{sgn}(\alpha R_{\mathrm{T}}-R_{i})$ is known to at-least $\beta$
standard-deviations of certainty, where splitting threshold $\alpha$
($0\leq\alpha\leq 1$) and stability criterion $\beta$ are user-chosen
heuristics. Stable nodes are no longer measured. If a node is stable and
$R_{i}\geq\alpha R_{\mathrm{T}}$, the node is split into four equal-sized sub-
quadrants which are initially unstable and added to the scan-list. Optionally,
a maximum resolution (maximum tree depth) may be set.

The transition to the iterative phase occurs when the percentage of unstable
leaves is less than $\Gamma$, a user chosen parameter. At this point,
stability is ignored and all leaf nodes are scanned repeatedly and guaranteed
to have the same total acquisition time. Various final stopping criteria can
be used; we chose a fixed total run time. Note that heuristic parameters
$\alpha$, $\beta$, and $\gamma$ may be changed during operation if desired.
For the data shown in this manuscript, $\alpha=.002$, $\beta=2$, and
$\Gamma=.15$ with a $30$ hour runtime.

The probability distribution $\tilde{P}$ is computed by uniformly distributing
the estimated count rate (with or without-accidental subtraction) from each
leaf node across its constituent elements in $\tilde{P}$, followed by
normalization.

## Data Availability

The data supporting the results presented in this manuscript is available from
the corresponding author G.A.H upon request.

Figure 1: Experimental setup for adaptive measurements (a) An entangled photon
source produces spatially entangled photon pairs, which are separated and
routed through basis selection optics that switch between measuring
transverse-position or transverse-momentum. Computer-controlled digital
micromirror devices and photon-counting detectors perform joint spatial
projections at up to $512\times 512$ pixel resolution. (b) shows a simulated,
true position joint-distribution of $P(X_{\mathrm{a}},X_{\mathrm{b}})$ at
$128\times 128$ pixel resolution, while (c-g) show its simulated, adaptively
decomposed estimate $\tilde{P}(X_{\mathrm{a}},X_{\mathrm{b}})$ as it is
refined to higher detail via quad-tree decomposition. When the joint-intensity
in a block exceeds a user-defined threshold, it is split into four sub-
quadrants and the process is recursively repeated, rapidly partitioning the
space to obtain a compressed distribution from very few measurements. Figure
2: Measured joint probability distributions at $512\times 512$ pixel
resolution. (a-d) show the four estimated joint probability distributions with
their single-party marginal distributions overlaid, showing tight
correlations. (e) shows an enlarged version of
$\tilde{P}(X_{\mathrm{a}},X_{\mathrm{b}})$ overlaid with the adaptive
partitioning, with (f) showing a small central region to see fine detail. The
histogram (g) shows the number of partitions as a function of their area. Only
$6,456$ measurements are needed instead of $2\times 512^{4}$. Figure 3:
Entanglement quantification versus acquisition time The entanglement of
formation $E_{\mathrm{f}}$ is given as a function of acquisition time-per-
partition for unaltered coincidence data and accidental-subtracted data. Error
bars enclosing two standard deviations are determined by propagation of error
from photon-counting statistics. We confirm the validity of this error
analysis strategy via Monte Carlo simulation in Supplemental Material: Monte
Carlo error analysis (see Supplemental Figure 1). Figure 4: Entanglement
quantification versus maximum resolution (a) shows the number of partitions
required as a function of maximum allowed resolution and the improvement over
the uncompressed approach. (b) shows the amount of entanglement captured as
the maximum resolution increases. We see the progressive nature of the
technique, which witnesses entanglement with few measurements at low
resolution but more accurately quantifies it with further refinement. Our
results approach the ideal maximum measurable value $E_{\mathrm{f}}=7.68$
ebits for our source.

We gratefully acknowledge support from the OSD ARAP QSEP program and Air Force
Office of Scientific Research LRIR 14RI02COR. J.S. acknowledges support from
the National Research Council Research Associate Program. Any opinions,
findings, and conclusions or recommendations expressed in this article are
those of the authors and do not necessarily reflect the views of AFRL.

G.A.H. and J.S. conceived of the idea and contributed equally. J.S. derived
the entanglement witness and led the theoretical analysis. G.A.H and C.C.T.
developed the data collection algorithm. G.A.H performed the experiment with
help from M.L.F and analyzed the data with help from C.C.T. and J.S. P.M.A.
participated in useful scientific discussions. G.A.H wrote the manuscript with
contributions from all authors.

The authors declare that they have no competing interests.

Correspondence and requests for materials should be addressed to G.A.H.
(email: gaheen@rit.edu).

## References

  * [1] Bernien, H. _et al._ Probing many-body dynamics on a 51-atom quantum simulator.  _Nature_ 551, 579 (2017).
  * [2] Zhang, J. _et al._ Observation of a many-body dynamical phase transition with a 53-qubit quantum simulator.  _Nature_ 551, 601 (2017).
  * [3] Friis, N. _et al._ Observation of entangled states of a fully controlled 20-qubit system.  _Phys. Rev. X_ 8, 021012 (2018).  URL https://link.aps.org/doi/10.1103/PhysRevX.8.021012.
  * [4] Debnath, S. _et al._ Demonstration of a small programmable quantum computer with atomic qubits.  _Nature_ 536, 63 (2016).
  * [5] Brown, K. R., Kim, J. & Monroe, C.  Co-designing a scalable quantum computer with trapped atomic ions.  _npj Quantum Information_ 2, 16034 (2016).
  * [6] Kues, M. _et al._ On-chip generation of high-dimensional entangled quantum states and their coherent control.  _Nature_ 546, 622–626 (2017).
  * [7] Carolan, J. _et al._ Universal linear optics.  _Science_ 349, 711–716 (2015).
  * [8] Masada, G. _et al._ Continuous-variable entanglement on a chip.  _Nature Photonics_ 9, 316–319 (2015).
  * [9] Wang, J. _et al._ Multidimensional quantum entanglement with large-scale integrated optics.  _Science_ eaar7053 (2018).
  * [10] Mennea, P. L. _et al._ Modular linear optical circuits.  _Optica_ 5, 1087–1090 (2018).
  * [11] Yokoyama, S. _et al._ Ultra-large-scale continuous-variable cluster states multiplexed in the time domain.  _Nature Photonics_ 7, 982–986 (2013).
  * [12] Mirhosseini, M. _et al._ High-dimensional quantum cryptography with twisted light.  _New Journal of Physics_ 17, 033033 (2015).
  * [13] Zhong, T. _et al._ Photon-efficient quantum key distribution using time–energy entanglement with high-dimensional encoding.  _New Journal of Physics_ 17, 022002 (2015).
  * [14] Xie, Z. _et al._ Harnessing high-dimensional hyperentanglement through a biphoton frequency comb.  _Nature Photonics_ 9, 536–542 (2015).
  * [15] Bolduc, E., Gariepy, G. & Leach, J.  Direct measurement of large-scale quantum states via expectation values of non-hermitian matrices.  _Nature communications_ 7, 10439 (2016).
  * [16] Islam, N. T., Lim, C. C. W., Cahall, C., Kim, J. & Gauthier, D. J.  Provably secure and high-rate quantum key distribution with time-bin qudits.  _Science Advances_ 3 (2017).  URL http://advances.sciencemag.org/content/3/11/e1701491.  http://advances.sciencemag.org/content/3/11/e1701491.full.pdf.
  * [17] Gambetta, J. M., Chow, J. M. & Steffen, M.  Building logical qubits in a superconducting quantum computing system.  _npj Quantum Information_ 3, 2 (2017).
  * [18] Fröwis, F. _et al._ Experimental certification of millions of genuinely entangled atoms in a solid.  _Nature communications_ 8, 907 (2017).
  * [19] McConnell, R., Zhang, H., Hu, J., Ćuk, S. & Vuletić, V.  Entanglement with negative wigner function of almost 3,000 atoms heralded by one photon.  _Nature_ 519, 439–442 (2015).
  * [20] Tiranov, A. _et al._ Quantification of multidimensional entanglement stored in a crystal.  _Phys. Rev. A_ 96, 040303 (2017).  URL https://link.aps.org/doi/10.1103/PhysRevA.96.040303.
  * [21] Terhal, B. M.  Detecting quantum entanglement.  _Theoretical Computer Science_ 287, 313–335 (2002).
  * [22] Gühne, O. & Tóth, G.  Entanglement detection.  _Physics Reports_ 474, 1–75 (2009).
  * [23] Brunner, N., Cavalcanti, D., Pironio, S., Scarani, V. & Wehner, S.  Bell nonlocality.  _Rev. Mod. Phys._ 86, 419–478 (2014).  URL https://link.aps.org/doi/10.1103/RevModPhys.86.419.
  * [24] Horodecki, R., Horodecki, P., Horodecki, M. & Horodecki, K.  Quantum entanglement.  _Rev. Mod. Phys._ 81, 865–942 (2009).  URL https://link.aps.org/doi/10.1103/RevModPhys.81.865.
  * [25] Horodecki, R., Horodecki, M. & Horodecki, P.  Entanglement processing and statistical inference: The jaynes principle can produce fake entanglement.  _Physical Review A_ 59, 1799 (1999).
  * [26] Audenaert, K. & Plenio, M.  When are correlations quantum?–—verification and quantification of entanglement by simple measurements.  _New Journal of Physics_ 8, 266 (2006).
  * [27] Brandão, F. G. S. L.  Quantifying entanglement with witness operators.  _Phys. Rev. A_ 72, 022310 (2005).  URL https://link.aps.org/doi/10.1103/PhysRevA.72.022310.
  * [28] Eisert, J., Brandao, F. G. & Audenaert, K. M.  Quantitative entanglement witnesses.  _New Journal of Physics_ 9, 46 (2007).
  * [29] Martin, A. _et al._ Quantifying photonic high-dimensional entanglement.  _Physical Review Letters_ 118, 110501 (2017).
  * [30] Donoho, D. L.  Compressed sensing.  _IEEE Transactions on information theory_ 52, 1289–1306 (2006).
  * [31] Gross, D., Liu, Y.-K., Flammia, S. T., Becker, S. & Eisert, J.  Quantum state tomography via compressed sensing.  _Physical review letters_ 105, 150401 (2010).
  * [32] Flammia, S. T., Gross, D., Liu, Y.-K. & Eisert, J.  Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators.  _New Journal of Physics_ 14, 095022 (2012).
  * [33] Tonolini, F., Chan, S., Agnew, M., Lindsay, A. & Leach, J.  Reconstructing high-dimensional two-photon entangled states via compressive sensing.  _Scientific reports_ 4 (2014).
  * [34] Kalev, A., Kosut, R. L. & Deutsch, I. H.  Quantum tomography protocols with positivity are compressed sensing protocols.  _Npj Quantum Information_ 1, 15018 (2015).
  * [35] Riofrío, C. _et al._ Experimental quantum compressed sensing for a seven-qubit system.  _Nature Communications_ 8 (2017).
  * [36] Steffens, A. _et al._ Experimentally exploring compressed sensing quantum tomography.  _Quantum Science and Technology_ 2, 025005 (2017).
  * [37] Bolduc, E., Knee, G. C., Gauger, E. M. & Leach, J.  Projected gradient descent algorithms for quantum state tomography.  _npj Quantum Information_ 3, 44 (2017).
  * [38] Howland, G. A. & Howell, J. C.  Efficient high-dimensional entanglement imaging with a compressive-sensing double-pixel camera.  _Physical review X_ 3, 011013 (2013).
  * [39] Howland, G. A., Knarr, S. H., Schneeloch, J., Lum, D. J. & Howell, J. C.  Compressively characterizing high-dimensional entangled states with complementary, random filtering.  _Physical Review X_ 6, 021018 (2016).
  * [40] Schneeloch, J. & Howland, G. A.  Quantifying high-dimensional entanglement with Einstein-Podolsky-Rosen correlations.  _Phys. Rev. A_ 97, 042338 (2018).  URL https://link.aps.org/doi/10.1103/PhysRevA.97.042338.
  * [41] Coles, P. J., Berta, M., Tomamichel, M. & Wehner, S.  Entropic uncertainty relations and their applications.  _Reviews of Modern Physics_ 89, 015002 (2017).
  * [42] Schneeloch, J., Broadbent, C. J., Walborn, S. P., Cavalcanti, E. G. & Howell, J. C.  Einstein-podolsky-rosen steering inequalities from entropic uncertainty relations.  _Phys. Rev. A_ 87, 062103 (2013).  URL https://link.aps.org/doi/10.1103/PhysRevA.87.062103.
  * [43] Walborn, S. P., Monken, C., Pádua, S. & Ribeiro, P. S.  Spatial correlations in parametric down-conversion.  _Physics Reports_ 495, 87–139 (2010).
  * [44] Schneeloch, J. & Howell, J. C.  Introduction to the transverse spatial correlations in spontaneous parametric down-conversion through the biphoton birth zone.  _Journal of Optics_ 18, 053501 (2016).
  * [45] Samet, H. & Webber, R. E.  Storing a collection of polygons using quadtrees.  _ACM Transactions on Graphics (TOG)_ 4, 182–222 (1985).
  * [46] Terhal, B. M. & Horodecki, P.  Schmidt number for density matrices.  _Physical Review A_ 61, 040301 (2000).
  * [47] Sperling, J. & Vogel, W.  The schmidt number as a universal entanglement measure.  _Physica Scripta_ 83, 045002 (2011).
  * [48] Krenn, M. _et al._ Generation and confirmation of a (100$\times$ 100)-dimensional entangled quantum system.  _Proceedings of the National Academy of Sciences_ 111, 6243–6247 (2014).
  * [49] Bavaresco, J. _et al._ Measurements in two bases are sufficient for certifying high-dimensional entanglement.  _Nature Physics_ 14, 1032 (2018).
  * [50] Erker, P., Krenn, M. & Huber, M.  Quantifying high dimensional entanglement with two mutually unbiased bases.  _Quantum_ 1, 22 (2017).

## Supplemental Material

###  0.8 Proof that arbitrary coarse-graining cannot decrease conditional
entropy

We are given two discrete probability distributions
$P_{1}(X_{\mathrm{A}},X_{\mathrm{B}})$ and
$P_{2}(X_{\mathrm{A}},X_{\mathrm{B}})$. We will also assume a permutation
operation $\chi$, that shuffles the outcomes of $X_{\mathrm{A}}$ and
$X_{\mathrm{B}}$. With this, we define the permuted distributions
$P_{1}^{{}^{\prime}}(X_{\mathrm{A}},X_{\mathrm{B}})$ and
$P_{2}^{{}^{\prime}}(X_{\mathrm{A}},X_{\mathrm{B}})$ as the result of
permutation operator $\chi$ on $P_{1}(X_{\mathrm{A}},X_{\mathrm{B}})$ and
$P_{2}(X_{\mathrm{A}},X_{\mathrm{B}})$, respectively.

The joint convexity of relative entropy states that given distributions
$P_{1},P_{2},P_{1}^{{}^{\prime}}$, and $P_{2}^{{}^{\prime}}$, the following
inequality holds:

$\displaystyle\lambda\mathscr{D}$
$\displaystyle(P_{1}||P_{2})+(1-\lambda)\mathscr{D}(P_{1}^{{}^{\prime}}||P_{2}^{{}^{\prime}})\geq$
$\displaystyle\geq\mathscr{D}(\lambda
P_{1}+(1-\lambda)P_{1}^{{}^{\prime}}||\lambda
P_{2}+(1-\lambda)P_{2}^{{}^{\prime}})$ (4)

where $\lambda\in[0,1]$.

Next, we define the mixed probability distribution $\bar{P}_{1}\equiv(\lambda
P_{1}+(1-\lambda)P_{1}^{{}^{\prime}})$, and define $\bar{P}_{2}$ similarly.
Since $P_{1}^{{}^{\prime}}$ and $P_{2}^{{}^{\prime}}$ are respectively related
to $P_{1}$ and $P_{2}$ by the same permutation $\chi$, we have that
$\mathscr{D}(P_{1}||P_{2})=\mathscr{D}(P_{1}^{{}^{\prime}}||P_{2}^{{}^{\prime}})$.
Therefore, we obtain the inequality:

$\mathscr{D}(P_{1}||P_{2})\geq\mathscr{D}(\bar{P}_{1}||\bar{P}_{2}).$ (5)

This result that mixing (i.e., majorization) cannot increase relative entropy
has far reaching applications. In particular, coarse-graining is a form of
majorization between adjacent elements in a probability distribution. Because
all (Shannon) entropic functions can be expressed in terms of relative
entropies, it immediately follows that:

$\displaystyle H_{\mathrm{\bar{P}}}(X_{\mathrm{A}})$ $\displaystyle\geq
H_{\mathrm{P}}(X_{\mathrm{A}})$ (6) $\displaystyle
H_{\mathrm{\bar{P}}}(X_{\mathrm{A}},X_{\mathrm{B}})$ $\displaystyle\geq
H_{\mathrm{P}}(X_{\mathrm{A}},X_{\mathrm{B}})$ (7) $\displaystyle
H_{\mathrm{\bar{P}}}(X_{\mathrm{A}}|X_{\mathrm{B}})$ $\displaystyle\geq
H_{\mathrm{P}}(X_{\mathrm{A}}|X_{\mathrm{B}})$ (8)

where the subscripts $\mathrm{P}$ and $\mathrm{\bar{P}}$ represent the
probability distribution before and after coarse-graining, respectively. In
addition, the mutual information and the conditional mutual information obey
the inequalities

$\displaystyle H_{\mathrm{\bar{P}}}(X_{\mathrm{A}}:X_{\mathrm{B}})$
$\displaystyle\leq H_{\mathrm{P}}(X_{\mathrm{A}}:X_{\mathrm{B}})$ (9)
$\displaystyle
H_{\mathrm{\bar{P}}}(X_{\mathrm{A}}:X_{\mathrm{B}}|X_{\mathrm{C}})$
$\displaystyle\leq
H_{\mathrm{P}}(X_{\mathrm{A}}:X_{\mathrm{B}}|X_{\mathrm{C}}).$ (10)

where again, the subscripts $\mathrm{P}$ and $\mathrm{\bar{P}}$ denote the
true and coarse grained probability distribution, respectively. Furthermore,
both the continuous mutual information $h(x_{\mathrm{A}}:x_{\mathrm{B}})$ and
the continuous conditional mutual information
$h(x_{\mathrm{A}}:x_{\mathrm{B}}|x_{\mathrm{C}})$ are expressible as high-
resolution limits of corresponding discrete mutual informations. Because
successive coarse grainings cannot increase these quantities, the following
inequalities hold between discrete and continuous mutual information

$\displaystyle h(x_{\mathrm{A}}:x_{\mathrm{B}})$ $\displaystyle\geq
H(X_{\mathrm{A}}:X_{\mathrm{B}})$ (11) $\displaystyle
h(x_{\mathrm{A}}:x_{\mathrm{B}}|x_{\mathrm{C}})$ $\displaystyle\geq
H(X_{\mathrm{A}}:X_{\mathrm{B}}|X_{\mathrm{C}})$ (12)

While the former inequality (11) can be found with alternative methods, the
latter inequality (12) is new to the literature.

###  0.9 Proof of inequality 2

Inequality (2) derives from two fundamental properties of Shannon entropy. To
expand notation, we have:

$H(\mathbf{X}_{\mathrm{a}}|\mathbf{X}_{\mathrm{b}})\equiv
H(X_{\mathrm{a}}^{(1)},...,X_{\mathrm{a}}^{(d)}|X_{\mathrm{b}}^{(1)},...,X_{\mathrm{b}}^{(d)})$
(13)

First, is that the joint Shannon entropy is less than or equal to the sum of
the marginal entropies:

$H(\mathbf{X}_{\mathrm{a}}|\mathbf{X}_{\mathrm{b}})\leq\sum_{i=1}^{d}H(X_{\mathrm{a}}^{(i)}|X_{\mathrm{b}}^{(1)},...,X_{\mathrm{b}}^{(d)})$
(14)

Second, is that conditioning on additional variables cannot increase entropy,
or conversely that removing conditioning variables cannot reduce entropy:

$H(X_{\mathrm{a}}^{(i)}|X_{\mathrm{b}}^{(1)},...,X_{\mathrm{b}}^{(d)})\leq
H(X_{\mathrm{a}}^{(i)}|X_{\mathrm{b}}^{(i)})$ (15)

Together, this proves inequality (2):

$H(\mathbf{X}_{\mathrm{a}}|\mathbf{X}_{\mathrm{b}})\leq\sum_{i=1}^{d}H(X_{\mathrm{a}}^{(i)}|X_{\mathrm{b}}^{(i)}).$
(16)

###  0.10 Monte Carlo error analysis

For the results shown in the manuscript, we used standard, first-order
propagation-of-uncertainty for error analysis. Each coincidence-count
measurement is assumed to have Poissonian uncertainty, and this uncertainty is
analytically propagated through the analysis (e.g.
$f(x_{0}\pm\delta)=f(x_{0})\pm\left(\frac{df}{dx}\right)_{x_{0}}\delta$).

To confirm the validity of our propagation-style error analysis, we also
estimated our uncertainty with Monte Carlo simulations. This approach does not
suffer any potential issues that may arise where our equations may not be
sufficiently well-behaved for the first-order propagation of error. However,
it does replace a simple analytical result with the need for computational
simulations.

To perform Monte Carlo simulations, each coincidence count measurement is used
to sample from a Poissonian distribution. Then, we follow our previously
described process for generating joint-probability distributions (with or
without accidental subtraction) and calculating the amount of entanglement.
This process is repeated many times to see how the Poissonian counting
statistics propagate to our final result.

In Supplemental Figure 1, we recreate Figure 3 from the main text using this
approach with $100$ trials. The error bars shown enclose two standard
deviations. The uncertainties from this approach behave similarly to the
analytic propagation-of-error used in the main manuscript, however the
uncertainties are even smaller. The values obtained for the entanglement of
formation are $7.154\pm.015$ $(7.112\pm.0412)$ ebits with background
subtraction and $3.459\pm.012$ $(3.425\pm.038)$ ebits, where the analytic
result is given in parentheses. The two outcomes are in good agreement, with
between two-times and four-times lower uncertainty with the Monte Carlo
simulations.

###  0.11 Maximum possible entanglement that can be certified with this
technique

For photon statistics contained within a finite window, the maximum possible
entanglement our relation can characterize is when a pixel in the signal arm
is correlated to only a single pixel in the idler arm, or when all conditional
entropies are zero. In this case, the inequality reads:

$E_{\mathrm{f}}\geq\log\Bigg{(}\frac{(2\pi)^{2}}{\Delta x_{\mathrm{A}}\Delta
y_{\mathrm{A}}\Delta k_{\mathrm{xA}}\Delta k_{\mathrm{yA}}}\Bigg{)}.$ (17)

For perfect diagonal correlations, the number of measurements we need with our
technique scales favorably with resolution, improving better with tighter
correlations. For example, for $N\times N$ resolution in both position and
momentum (assuming $N$ is a power of two for simplicity), then one needs only
about $12(N-\log_{2}(N)-2)$ measurements, which, for $N=512$ would be about
6096 measurements. This does not include the number of measurements needed to
acquire this partitioning, which scales similarly. When the correlations are
less tight, more pixels are required at maximum resolution, increasing this
total.

Supplemental Figure 1: Entanglement quantification versus acquisition time
with Monte Carlo uncertainty analysis Measured coincidence counts are used to
draw values from a Poisson distribution for 100 trials. Error bars enclose two
standard deviations and are in good agreement with the analytical approach to
error analysis used the main text (see Figure 3).