# Super Solutions of the Model RB

Guangyan Zhou1, Wei Xu 2,∗
1Department of Mathematics, Beijing Technology and Business University,
Beijing, 100048, China
2 School of Mathematics and Physics, University of Science and Technology
Beijing, Beijing 100083, China

###### Abstract

The concept of super solution is a special type of generalized solutions with
certain degree of robustness and stability. In this paper we consider the
$(1,1)$-super solutions of the model RB. Using the first moment method, we
establish a “threshold” such that as the constraint density crosses this
value, the expected number of $(1,1)$-super solutions goes from $0$ to
infinity.

Keywords: Super solution, Model RB, Phase transitions, Constraint satisfaction
problems.

11footnotetext:  Corresponding author<EMAIL_ADDRESS>This work was
supported by National Natural Science Foundation of China (61702019,
11801028).

##  1 Introduction

In many combinatorial optimization and decision problems, what people concern
is to find solutions of minimal costs. In practice, however, such optimal
solutions can be very brittle in that if the value of one variable becomes
unavailable, repairing this solution leads to a great increase in its final
cost. Therefore, the concept of super solution is introduced to formalize a
solution with a certain degree of robustness or stability. To quantify the
robustness, $(a,b)$-super solution was introduced to constraint programming in
[3]. Specifically, an $(a,b)$-super solution is one in which if the values
assigned to $a$ variables are no longer available, the solution can be
repaired by assigning these variables with $a$ new values and at most $b$
other variables.

Over the past years, random models of constraint satisfaction problems (CSPs)
have been intensively studied. Initially, four “standard” models known as
models A, B, C and D [4, 2] have been introduced to generate random binary CSP
instances. However, Achlioptas et. al. [1] have proved that random instances
of these models suffer from unsatisfiability as the number of variables
increases. Overcoming the trivial unsatisfiability, Xu and Li proposed Model
RB [6], which is a prototype CSP model with growing domains revised from the
standard CSP model B [4]. It has been shown that random instances of model RB
are hard to solve at the threshold both theoretically [6] and experimentally
[7], thus benchmarks based on model RB have been widely used in algorithm
competitions. In addition, studies on the statistical mechanics of model RB
show that the replica symmetry solution is always stable in the satisfiable
phase [10, 11], and there is no condensation transition in model RB [8].

An instance $\mathbf{I}$ of Model RB contains a finite set
$V=\\{x_{1},...,x_{n}\\}$ of $n$ variables and a set of constraints
$\mathcal{C}=\\{C_{1},...,C_{m}\\}$ ($m=rn\ln n$ and $r>0$ is a constant).
Each $x_{i}$ takes values from domain $D=\\{1,2,...,d\\}$, where
$d=n^{\alpha}$ ($\alpha>0$ is a constant). Each constraint $C_{i}$ is
consisted of a set of $k$ variables
$X_{i}=\\{x_{i_{1}},x_{i_{2}},...,x_{i_{k}}\\}$, where the $k$ ($k\geq 2$)
different variables are chosen uniformly at random, and a set of satisfying
tuples of values $R_{i}\subset D^{k}$ with $|R_{i}|=pd^{k}$ ($0<p<1$ measures
the tightness of a constraint). Constraint $C_{i}$ is satisfied if the tuple
of values assigned to $X_{i}$ is in the corresponding relation $R_{i}$.
Solving the instance is to find an assignment of $V$ that satisfies all the
constraints or to prove that no such assignment exists.

In [9], Zhang and Gao studied the $(1,0)$-super solutions of model RB where
they consider the special case $k=2$ and $d=\sqrt{n}$. By using the first
moment method, they derived an upper bound of the threshold of having a
$(1,0)$-super solution asymptotically with probability 1, and established a
condition for the expected number of super solutions to grow exponentially.
$(1,0)$-super solutions have also been studied in random (3+p)-SAT [12].

Letting $\triangle(\sigma,\tau)$ denote the set of variables being assigned
different values by $\sigma$ and $\tau$, i.e.,
$\triangle(\sigma,\tau)=\\{x_{i}|\sigma(x_{i})\neq\tau(x_{i})\\}$, we can give
the following definitions of $(1,0)$ and $(1,1)$-super solutions.

######  Definition 1.1.

($(1,0)$-super solution). An assignment $\sigma\in D^{n}$ is called a
$(1,0)$-super solution if $\sigma$ is a satisfying assignment, and for every
variable $x_{i}$ ($1\leq i\leq n$), there exists another satisfying assignment
$\tau$ such that $\triangle(\sigma,\tau)=\\{x_{i}\\}$.

######  Definition 1.2.

($(1,1)$-super solution). An assignment $\sigma\in D^{n}$ is called a
$(1,1)$-super solution if $\sigma$ is a satisfying assignment, and for every
variable $x_{i}$ ($1\leq i\leq n$), there exists another satisfying assignment
$\tau$ such that either $\triangle(\sigma,\tau)=\\{x_{i}\\}$, or there exists
$j\neq i$ such that $\triangle(\sigma,\tau)=\\{x_{i},x_{j}\\}$.

In this paper, we consider the $(1,1)$-super solution of model RB, and by
using the first moment method, we prove rigorously the following results.

######  Theorem 1.

Let $Y$ be the number of $(1,1)$-super solutions of the model RB. Then

$\mathbf{E}[Y]=\left\\{\begin{aligned} &0,\text{\quad\quad if
}r>-\frac{\alpha}{\ln p},\\\ &+\infty,\text{ if }r<-\frac{\alpha}{\ln
p}.\end{aligned}\right.$

From the definitions, we can see that $(1,0)$ and $(1,1)$-super solutions
reflect certain characteristics of structures of solution space, since they
can be viewed as a particular type of “locally maximum” subset of satisfying
solutions. In addition, the set of $(1,0)$-super solutions is a subset of
$(1,1)$-super solutions, and the set of $(1,1)$-super solutions is a subset of
standard solutions. This explains why the upper bound on $r$ of having
$(1,0)$-super solutions in Theorem 5 in [9] is smaller than that of having
$(1,1)$-super solutions in Theorem 1 and standard solutions obtained in [6].

Our results are interesting in several aspects. First, there seems to be a
sharp phase transition for the $(1,1)$-super solution where the expected
number of $(1,1)$-super solutions goes from $0$ to infinity, and this
threshold is exactly the same with the standard satisfiability threshold of
model RB in [6]. Second, the restrictions of $r$ in Theorem 1 is independent
of the constraint size $k$. In addition, from the Definitions 1.1 and 1.2,
super solutions can be viewed as a certain type of “locally maximum” subset of
the standard solutions, thus we believe our results reflect from another
aspect the structure of solution space and stability of solutions. It is worth
mentioning that whether $-\frac{\alpha}{\ln p}$ in Theorem 1 is a sharp
threshold around which the model RB goes from being a.s. (almost surely)
$(1,1)$-satisfiable to a.s. $(1,1)$-unsatisfiable is still open, and the
second moment method will be needed to solve this problem.

##  2 Proof of Theorem 1

Let $\sigma$ be a fixed assignment, $\mathbf{I}$ be a random instance of model
RB, and $\sigma\models\mathbf{I}$ be that $\sigma$ satisfies $\mathbf{I}$. We
consider the following events which was similarly used in [9]:

  * •

$S(\sigma)$: $\sigma$ is a solution for $\mathbf{I}$.

  * •

$R_{i}(\sigma)$: there exists another solution $\tau$ for $\mathbf{I}$ such
that $\triangle(\sigma,\tau)=\\{x_{i}\\}$, or there exists a $j\neq i$ such
that $\triangle(\sigma,\tau)=\\{x_{i},x_{j}\\}$.

  * •

$W(\sigma)$: $\sigma$ is a $(1,1)$-super solution for $\mathbf{I}$.

It is straightforward to see that

$\displaystyle\mathbf{P}(W(\sigma))=\mathbf{P}\left(S(\sigma)\bigcap_{1\leq
i\leq n}R_{i}(\sigma)\right).$

Following the notations in [9], let
$\mathcal{M}\subset(\underbrace{X\times...\times X}_{k})^{m}$ be the
collection of all possible multi-sets of $m$ unordered constraints
($|\mathcal{M}|=\binom{n}{k}^{m}$). For a given set $e\in\mathcal{M}$ of $m$
unordered tuples, denote by $E(e)$ the event that $e$ is selected as the set
of constraints of the random instance. By the definition of the random model,
the set of events $\\{E(e),e\in\mathcal{M}\\}$ are mutually disjoint. Also,
for any $e\in\mathcal{M}$, $\mathbf{P}(E(e))=\binom{n}{k}^{-m}$ and
$\mathbf{P}(S(\sigma)|E(e))=p^{m}$. The probability of $\sigma$ being a
$(1,1)$-super solution works out to be

$\displaystyle\mathbf{P}(W(\sigma))$
$\displaystyle=\mathbf{P}\left(S(\sigma)\cap_{1\leq i\leq
n}R_{i}(\sigma)\right)$
$\displaystyle=\mathbf{P}\left(\cup_{e\in\mathcal{M}}\left(E(e)\cap
S(\sigma)\cap(\cap_{1\leq i\leq n}R_{i}(\sigma))\right)\right)$
$\displaystyle=\sum_{e\in\mathcal{M}}\mathbf{P}\left(E(e)\cap
S(\sigma)\cap(\cap_{1\leq i\leq n}R_{i}(\sigma))\right)$
$\displaystyle=\sum_{e\in\mathcal{M}}\mathbf{P}(E(e))\mathbf{P}(S(\sigma)|E(e)\mathbf{P}\left(\cap_{1\leq
i\leq n}R_{i}(\sigma)|S(\sigma)\cap E(e)\right)$
$\displaystyle=\binom{n}{k}^{-m}p^{m}\sum_{e\in\mathcal{M}}\mathbf{P}\left(\cap_{1\leq
i\leq n}R_{i}(\sigma)|S(\sigma)\cap E(e)\right).$ (2.1)

By inclusion$/$exclusion, we have

$\displaystyle
1-\sum_{i=1}^{n}\mathbf{P}(\overline{R_{i}(\sigma)}|S(\sigma)\cap E(e))$
$\displaystyle\leq$ $\displaystyle\mathbf{P}\left(\cap_{1\leq i\leq
n}R_{i}(\sigma)|S(\sigma)\cap E(e)\right)$ $\displaystyle\leq$ $\displaystyle
1-\sum_{i=1}^{n}\mathbf{P}(\overline{R_{i}(\sigma)}|S(\sigma)\cap
E(e))+\sum_{1\leq i<j\leq
n}\mathbf{P}(\overline{R_{i}(\sigma)}\cap\overline{R_{j}(\sigma)}|S(\sigma)\cap
E(e)).$

In the following, assume that $\sigma$ is a solution of $\mathbf{I}$, and
$\mathcal{C}(x_{i})$ is the set of constraints containing the variable
$x_{i}$, $1\leq i\leq n$. Let $D_{i}=D\backslash\\{\sigma(x_{i})\\}$, and
$q=1-p$ be the probability that a random constraint can not be satisfied by an
assignment.

######  Lemma 2.

Let $\sigma$ be a given solution of model RB. For any fixed $y\in D_{i}$,
suppose an assignment $\tau$ assigns $x_{i}$ the value $y$ and
$|\triangle(\sigma,\tau)|=1$ or $2$. For any constraint
$C\in\mathcal{C}(x_{i})$,

$\displaystyle\mathbf{P}[C\text{ is satisfied by }\tau]=\rho\equiv
1-q^{1+(d-1)(k-1)}.$

###### Proof.

Note that $\sigma$ is a satisfying solution of $\mathbf{I}$,
$|\triangle(\sigma,\tau)|=1$ or $2$, $\tau(x_{i})=y\neq\sigma(x_{i})$, thus
there may exists another variable being assigned different values by $\sigma$
and $\tau$.

If $|\\{x\in C|\sigma(x)\neq\tau(x)\\}|=1$ (indeed, it is $x_{i}$), there is
exactly $1$ way for $\tau$ to assign variables in $C$; if $|\\{x\in
C|\sigma(x)\neq\tau(x)\\}|=2$, there are $(d-1)(k-1)$ ways for $\tau$ to
assign variables in $C$. Since each way falsifies $C$ with probability $q$,
thus $\mathbf{P}[\tau\nvDash C]=q^{1+(d-1)(k-1)}$, and $\mathbf{P}[\tau\models
C]=1-q^{1+(d-1)(k-1)}=\rho.$ ∎

From Lemma 2, let $\tau$ be an assignment such that
$\triangle(\sigma,\tau)=\\{x_{i}\\}$ or $\\{x_{i},x_{j}\\}$ for some $j\neq
i$, and $\tau(x_{i})=y$ ($y\in D_{i}$), we see that

$\displaystyle\mathbf{P}(\overline{R_{i}(\sigma)}|S(\sigma)\cap E(e))$
$\displaystyle=\mathbf{P}(\cap_{y\in D_{i}}\overline{S(\tau)}|S(\sigma)\cap
E(e))$ $\displaystyle=\prod_{y\in
D_{i}}\mathbf{P}(\overline{S(\tau)}|S(\sigma)\cap E(e))$
$\displaystyle=\left[1-\mathbf{P}(\text{Constraints in $\mathcal{C}(x_{i})$
are all satisfied by }\tau)\right]^{d-1}$
$\displaystyle=\left(1-\rho^{m_{i}}\right)^{d-1}.$ (2.3)

######  Lemma 3.

Suppose $y\in D\backslash\\{\sigma(x_{i})\\}$, $z\in
D\backslash\\{\sigma(x_{j})\\}$. If $\tau,\omega$ be assignments that
$\tau(x_{i})=y$ and $|\triangle(\sigma,\tau)|=1$ or $2$; $\omega(x_{j})=z$ and
$|\triangle(\sigma,\omega)|=1$ or $2$. Then for any
$C\in\mathcal{C}(x_{i})\cap\mathcal{C}(x_{j})$,

$\displaystyle\mathbf{P}[\tau,\omega\models
C]=1-2q^{1+(d-1)(k-1)}+q^{1+2(d-1)(k-1)}.$

###### Proof.

From the proof of Lemma 2, there are $1+(d-1)(k-1)$ possible ways for $\tau$
to assign variables in $C$, and let $A(\tau)$ be the event that all these ways
fail to satisfy $C$; similarly there are $1+(d-1)(k-1)$ possible ways for
$\omega$ to assign variables in $C$, and let $B(\omega)$ be the event that all
these ways fail to satisfy $C$. It is easy to see that, there is exactly one
common assignment for $\tau,\omega$, where $\tau(x_{i})=\omega(x_{i})=y$ and
$\tau(x_{j})=\omega(x_{j})=z$.

$\displaystyle\mathbf{P}[\tau,\omega\models C]=\mathbf{P}[C\text{ is satisfied
by both }\tau\text{ and }\omega]$ $\displaystyle=$
$\displaystyle\mathbf{P}(\overline{A(\tau)}\cap\overline{B(\omega)})$
$\displaystyle=$ $\displaystyle
1-\mathbf{P}(A(\tau))-\mathbf{P}(B(\omega))+\mathbf{P}(A(\tau)\cap B(\omega))$
$\displaystyle=$ $\displaystyle
1-\mathbf{P}(A(\tau))-\mathbf{P}(B(\omega))+\mathbf{P}(A(\tau))\mathbf{P}(B(\omega)|A(\tau))$
$\displaystyle=$ $\displaystyle 1-2q^{1+(d-1)(k-1)}+q^{1+2(d-1)(k-1)}.$

∎

From Lemma 3, we see that

$\displaystyle\mathbf{P}(\overline{R_{i}(\sigma)}\cap\overline{R_{j}(\sigma)}|S(\sigma)\cap
E(e))$ $\displaystyle=$ $\displaystyle\mathbf{P}\left(\cap_{y\in
D_{i}}\overline{S(\tau)}\cap_{z\in D_{j}}\overline{S(\omega)}|S(\sigma)\cap
E(e)\right)$ $\displaystyle=$
$\displaystyle\left[\mathbf{P}\left(\overline{S(\tau)}\cap\overline{S(\omega)}|S(\sigma)\cap
E(e)\right)\right]^{(d-1)^{2}},$

where the last equation holds because of independency for any pair of values
$(y,z)$.

Let $l_{ij}=|\mathcal{C}(x_{i})\cap\mathcal{C}(x_{j})|$, then

$\displaystyle\mathbf{P}\left(S(\tau)\cup S(\omega)|S(\sigma)\cap E(e)\right)$
$\displaystyle=$ $\displaystyle\mathbf{P}\left(\text{$\tau$ satisfies all
constraints in $\mathcal{C}(x_{i})$, or $\omega$ satisfies all constraints in
$\mathcal{C}(x_{j})$}\right)$ $\displaystyle=$
$\displaystyle\mathbf{P}(\tau\models\mathcal{C}(x_{i}))+\mathbf{P}(\omega\models\mathcal{C}(x_{j}))-\mathbf{P}(\tau\models\mathcal{C}(x_{i}),\omega\models\mathcal{C}(x_{j}))$
$\displaystyle=$
$\displaystyle\rho^{m_{i}}+\rho^{m_{j}}-\rho^{m_{i}+m_{j}-2l_{ij}}\left(1-2q^{1+(d-1)(k-1)}+q^{1+2(d-1)(k-1)}\right)^{l_{ij}}$
$\displaystyle\geq$ $\displaystyle\rho^{\min\\{m_{i},m_{j}\\}}.$

Hence

$\displaystyle\mathbf{P}\left(\overline{S(\tau)}\cap\overline{S(\omega)}|S(\sigma)\cap
E(e)\right)\leq 1-\rho^{\min\\{m_{i},m_{j}\\}}.$ (2.4)

Combing (2), (2) and (2.4) we have

$\displaystyle 1-\sum_{i=1}^{n}\big{(}1-\rho^{m_{i}}\big{)}^{d-1}$
$\displaystyle\leq$ $\displaystyle\mathbf{P}\left(\cap_{1\leq i\leq
n}R_{i}(\sigma)|S(\sigma)\cap E(e)\right)$ $\displaystyle\leq$ $\displaystyle
1-\sum_{i=1}^{n}\big{(}1-\rho^{m_{i}}\big{)}^{d-1}+\sum_{1\leq i<j\leq
n}\left(1-\rho^{\min\\{m_{i},m_{j}\\}}\right)^{(d-1)^{2}}.$

###  2.1 Supercritical area: $r<\frac{\alpha}{-\ln p}$

Let $Y$ be the total number of $(1,1)$-super solutions. By (2) and (2),

$\displaystyle\mathbf{E}[Y]\geq
d^{n}\binom{n}{k}^{-m}p^{m}\sum_{e\in\mathcal{M}}\left(1-\sum_{i=1}^{n}\big{(}1-\rho^{m_{i}}\big{)}^{d-1}\right).$

Since $m_{i}q^{1+(d-1)(k-1)}=o(1)$ as $n$ tends to $\infty$, thus

$\rho^{m_{i}}=\left(1-q^{1+(d-1)(k-1)}\right)^{m_{i}}\geq
1-m_{i}q^{1+(d-1)(k-1)}.$

Note that $q<1$ and $d=n^{\alpha}$ with $\alpha>0$, thus

$\displaystyle 1-\sum_{i=1}^{n}\big{(}1-\rho^{m_{i}}\big{)}^{d-1}$
$\displaystyle\geq$ $\displaystyle
1-q^{(d-1)(1+(d-1)(k-1))}\sum_{i=1}^{n}m_{i}^{d-1}$ $\displaystyle\geq$
$\displaystyle 1-q^{d-1+(d-1)^{2}(k-1)}n(rn\ln n)^{d-1}$ $\displaystyle=$
$\displaystyle 1-\exp\\{(d-1)\ln q+(d-1)^{2}(k-1)\ln q+\ln n+(d-1)\ln(rn\ln
n)\\}$ $\displaystyle=$ $\displaystyle 1-\exp\\{(1+o(1))(d-1)^{2}(k-1)\ln
q\\}$ $\displaystyle=$ $\displaystyle 1+o(1).$

As a result, if $\alpha+r\ln p>0$, then $\mathbf{E}[Y]$ tends to infinity
since

$\displaystyle\ln\mathbf{E}[Y]$ $\displaystyle\geq n\left\\{\ln d+r\ln p\ln
n\right\\}$ $\displaystyle=n\ln n(\alpha+r\ln p).$

###  2.2 Subcritical area: $r>\frac{\alpha}{-\ln p}$

Let $Y$ be the total number of $(1,1)$-super solutions. By (2) and (2),

$\displaystyle\mathbf{E}[Y]\leq
d^{n}p^{m}\mathbf{P}\left(\bigcap_{i=1}^{n}R_{i}(\sigma)|S(\sigma)\cap
E(e)\right)$ $\displaystyle\leq$ $\displaystyle
d^{n}p^{m}\left[1-\sum_{i=1}^{n}\big{(}1-\rho^{m_{i}}\big{)}^{d-1}+\sum_{1\leq
i<j\leq n}\left(1-\rho^{\min\\{m_{i},m_{j}\\}}\right)^{(d-1)^{2}}\right]$
$\displaystyle\leq$ $\displaystyle
d^{n}p^{m}\left[1-\sum_{i=1}^{n}\big{(}1-\rho^{m_{i}}\big{)}^{d-1}\right]+d^{n}p^{m}\sum_{1\leq
i<j\leq n}\left(1-\rho^{\min\\{m_{i},m_{j}\\}}\right)^{(d-1)^{2}}$
$\displaystyle\equiv$ $\displaystyle E_{1}+E_{2}.$

Note that $m_{i},m_{j}\leq rn\ln n$, $d=n^{\alpha}$ and $q<1$, then

$\displaystyle m_{i}q^{1+(d-1)(k-1)}\leq$ $\displaystyle\exp\\{\ln n+\ln(r\ln
n)+n^{\alpha}(k-1)\ln q+\ln q\\}$ $\displaystyle=$
$\displaystyle\exp\\{(1+o(1))n^{\alpha}(k-1)\ln q\\}=o(1).$

Note that $\rho<1$. In addition, if $nx=o(1)$, then $(1-x)^{n}\geq 1-nx$, thus

$\displaystyle\rho^{\min\\{m_{i},m_{j}\\}}\geq\rho^{rn\ln
n}=(1-q^{1+(d-1)(k-1)})^{rn\ln n}\geq 1-rn\ln nq^{1+(d-1)(k-1)}.$

Thus

$\displaystyle\sum_{1\leq i<j\leq
n}\left(1-\rho^{\min\\{m_{i},m_{j}\\}}\right)^{(d-1)^{2}}$ $\displaystyle\leq$
$\displaystyle\frac{n^{2}}{2}\left(rn\ln nq^{1+(d-1)(k-1)}\right)^{(d-1)^{2}}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\exp\Big{\\{}(1+o(1))(d-1)^{3}(k-1)\ln
q\Big{\\}}=o(1).$

Therefore if $\alpha+kr\ln p<0$, then

$\displaystyle\mathbf{E}[Y]\leq 2d^{n}p^{m}=2\exp\\{(\alpha+r\ln p)n\ln
n\\}=o(1).$

##  3 Conclusion

In this paper, we study the $(1,1)$-super solutions of model RB, and our
results show that there is a “threshold” such that as the constraint density
crosses this value, the expected number of $(1,1)$-super solutions goes from
$0$ to infinity. Interestingly, this threshold is exactly the same with
standard satisfiability threshold obtained in [6].

However, a rigorous proof of the best possible lower bound on the “threshold”
of $(1,1)$-super solution should be based on the second moment method, which
is a challenging future work because of the non-negligible correlations among
assignments induced by repairing two or more variables at the same time.

## References

  * [1] D. Achlioptas, L.M. Kirousis, E. Kranakis, D. Krizanc, M.S.O. Molloy, and Y.C. Stamatiou, Random constraint satisfaction: a more accurate picture, In Proceedings of CP’97, 107, C120 (1997).
  * [2] I.P. Gent, E. MacIntyre, P. Prosser, B.M. Smith, and T. Walsh, Random constraint satisfaction: flaws and structure, Journal of Constraints, 6(4):345, C372 (2001).
  * [3] E. Hebrard, B. Hnich and T. Walsh, Super solutions in constraint programming, integration of ai and or techniques in constraint programming, 157-172 (2004).
  * [4] B. Smith and M. Dyer, Locating the phase transition in binary constraint satisfaction problems, Artificial Intelligence, 81, 155-181 (1996).
  * [5] K. Xu, K. Boussemart, F. Hemery and C. Lecoutre, Random constraint satisfaction: Easy generation of hard (satisfiable) instances, Artificial Intelligence, 171(8), 514-534 (2007).
  * [6] K. Xu, W. Li, Exact phase transitions in random constraint satisfaction problems, Journal of Artificial Intelligence Research, 12, 93-103 (2000).
  * [7] K. Xu and W. Li, Many Hard Examples in Exact Phase Transitions, Theoretical Computer Science, 355, 291-302 (2006).
  * [8] W. Xu, P. Zhang, T. Liu and F. Gong, The solution space structure of random constraint satisfaction problems with growing domains, Journal of Statistical Mechanics: Theory and Experiment, P12006 (2015).
  * [9] P. Zhang and Y. Gao, A probabilistic study of generalized solution concepts in satisfiability testing and constraint programming, Theoretical Computer Science, 657A, 98-110 (2016).
  * [10] C. Zhao, P. Zhang, Z. Zhang and K. Xu, Analytical and belief-propagation studies of random constraint satisfaction problems with growing domains, Physical Review E, 85:016106 (2012).
  * [11] C. Zhao, H. Zhou, Z. Zheng, K. Xu, A message-passing approach to random constraint satisfaction problems with growing domains, Journal of Statistical Mechanics: Theory and Experiment, P02019 (2011).
  * [12] B. Wang, G. Zhou, Super solutions of random (3+p)-SAT, Theoretical Computer Science, DOI: 10.1016/j.tcs.2019.04.015.


# Polarization Entanglement from Parametric Down-Conversion with a LED Pump

Wuhong Zhang<EMAIL_ADDRESS>Diefei Xu  Lixiang Chen<EMAIL_ADDRESS>Department of Physics, Xiamen University, Xiamen 361005, China

###### Abstract

Spontaneous parametric down-conversion (SPDC) is a reliable platform for
entanglement generation. Routinely, a coherent laser beam is an essential
prerequisite for pumping the nonlinear crystal. Here we break this barrier to
generate polarization entangled photon pairs by using a commercial light-
emitting diode (LED) source to serve as the pump beam. This effect is
counterintuitive, as the LED source is of extremely low spatial coherence,
which is transferred during the down-conversion process to the biphoton
wavefunction. However, the type-II phase-matching condition naturally filters
the specific frequency and wavelength of LED light exclusively to participate
in SPDC such that localized polarization Bell states can be generated,
regardless of the global incoherence over the full transverse plane. In our
experiment, we characterize the degree of LED light-induced polarization
entanglement in the standard framework of the violation of Bell inequality. We
have achieved the Bell value $S=2.33\pm 0.097$, obviously surpassing the
classical bound $S=2$ and thus witnessing the quantum entanglement. Our work
can be extended to prepare polarization entanglement by using other natural
light sources, such as sunlight and bio-light, which holds promise for
electricity-free quantum communications in outer space.

Quantum entanglement is generally regarded as a vital characteristic of
quantum information theory Bennett (1995); Nielsen and Chuang (2002).
Meanwhile, photons are one of the best physical systems for the long-distance
transmission of quantum states. Currently, the most mature method of
generating photonic entanglement is spontaneous parametric down-conversion
(SPDC), where a pump photon is converted into two photons of lower frequencies
under the conservation of energy and momentum in a nonlinear crystal Mandel
and Wolf (1995). This process of generating photons in pairs, makes it easy to
entangle two photons in various degrees of freedom. On account of the
extraordinary precision, polarization-entangled photon pairs are easy to
generate, control, and measure, and have become a major tool for quantum
teleportation Bouwmeester  _et al._ (1997), dense encoding Mattle  _et al._
(1996), quantum cryptography Jennewein  _et al._ (2000), quantum holography
Defienne  _et al._ (2021), quantum computing O’Brien  _et al._ (2003); O’brien
(2007), quantum information with integrated devices Sansoni (2014), long-
distance quantum communication Ursin  _et al._ (2007); Ma  _et al._ (2012),
and even in quantum satellite communication schemes Yin  _et al._ (2017).

In the framework of SPDC, polarization-entangled photon pairs have been
produced with one crystal in non-collinear Kwiat  _et al._ (1995); Lee  _et
al._ (2004) and collinear Trojek and Weinfurter (2008) phase matching, two-
crystal geometries Kwiat  _et al._ (1999), Sagnac interferometers Shi and
Tomita (2004), nested interferometers Fiorentino  _et al._ (2004), time-
reversed Hong-Ou-Mandel interference Chen  _et al._ (2018), femtosecond-pulse-
pumped lasers Nambu  _et al._ (2002), and even in the fiber communication band
Evans  _et al._ (2010). However, all of the above works utilize a spatially
coherent laser as the pump so that the laser appear to be necessary for the
production of entangled photon pairs with SPDC.

On the other hand, the influences of the spatial coherence of the pump on the
down-converted photon pairs have recently reached great interest. There are
some early theoretical studies of the transfer of the pump’s spatial coherence
Jha and Boyd (2010); Giese  _et al._ (2018); Vintskevich  _et al._ (2019);
Kanseri and Sharma (2020); Joshi and Kanseri (2020) and the degree of
polarization Kulkarni  _et al._ (2016); Patoary  _et al._ (2019); Sharma  _et
al._ (2021) to the down-converted photon pairs. By using a diffuser to
transform the laser into a partially spatial coherent pump beam, the
generation of spatial Defienne and Gigan (2019) and polarization Ismail  _et
al._ (2017) entangled photon pairs have been implemented experimentally.
Interestingly, pumping by a twisted Gaussian Schell-model beam, the effect of
the amount of spatial entanglement increases inversely with the degree of
coherence, which has been demonstrated theoretically Hutter  _et al._ (2020).
Even more, a commercially light-emitting diode (LED), as a totally incoherent
pump beam, has been used to induce the SPDC process and to examine correlated
photon pairs Tamošauskas  _et al._ (2010); Galinis  _et al._ (2011, 2012);
Nishii  _et al._ (2019). The influence of the pump coherence on the generation
of position-momentum entanglement has been observed experimentally Zhang  _et
al._ (2019). The entangled photon pairs produced from spatial incoherent pump
beams have been proven to be more robust to the effects arising from
atmospheric turbulences, which might hold some advantages for free-space
quantum information Qiu and She (2012); Gbur (2014); Phehlukwayo  _et al._
(2020). Even though previous studies Sharma  _et al._ (2021); Ismail  _et al._
(2017) have shown that it is in principle able to obtain polarization-
entangled photon pairs from the spatial incoherent pump, an experimental
technique realization, especially from a truly incoherent source (such as a
commercial LED), has not yet been studied very well.

Figure 1: Schematic illustration of the experimental setup, see text for more
details.

In this work, we pump a nonlinear crystal with a truly spatiotemporally
incoherent beam, a commercial LED, to produce polarization entangled photon
pairs. We strictly demonstrate the polarization entanglement by observing a
violation of a Clauser-Horne-Shimony-Holt (CHSH) inequality Clauser  _et al._
(1969) both in theory and experiment. Moreover, we quantitatively analyze the
quantum state of the down-converted photon pairs by exploiting quantum state
tomography under different collection setups. The non-local correlation of the
produced photon pairs is verified by a bell value of about 2.3 as well as a
concurrence of about 0.63. We observe a good agreement between experiment and
theory when it comes to the degree of entanglement of the bi-photon states
after the filtering system. Our technique to obtain polarization-entangled
photon pairs from a cheap LED instead of an expensive laser may promote a
further application, such as producing polarization entangled photon pairs
even from sunlight.

Our experimental setup is shown in Fig.1, which mainly contains three parts:
the incoherent source, the filtering system and the measurement part. The
incoherent source is a commercial LED (Thorlabs M405L3) centered at 405 nm in
the blue spectral range. The band width of the LED is about 20 nm and the
maximum intensity of the LED is 980 mW. Then the followed part is a filtering
system that can be used to produce polarization entangled photons. To ensure a
Gaussian-like beam profile while maintaining transverse incoherence, we use a
collimating lens (Thorlabs COP1-A) followed by a short focal length
($f_{0}=16$ mm) to couple the incoherent source into a 400-µm-core multimode
fiber (MMF). After passing a polarizer (P), the out-coupled LED beam is
demagnified by a 4$f$-system ($f_{1s}$:$L_{1}=300$ mm, $L_{2}=75$ mm) to have
a proper pump beam size ($\sigma_{0}=0.8$ mm ) when it enters the crystal. The
pump power before the crystal is 290 µW, which is just about 3‰of the LED
source. The key part of the filtering system is the nonlinear crystal, a 1
mm$\times$2 mm$\times$2.5 mm periodically-poled potassium titanyl phosphate
crystal (ppKTP), which is phase-matched for type-II collinear emission. It is
noted that the length of the ppKTP is 2.5 mm to ensure a maximal number of
photon counts while maintaining minimal walk-off effects between the two
polarizations of signal and idler so that we can omit a timing compensation
crystal Kuklewicz  _et al._ (2004); Sharma  _et al._ (2021).

Figure 2: (a) Theoretical plot and experimental results of the coincidence
photon count in A-D and H-V basis. The red and blue lines correspond to the
$\sin^{2}-fit$ function of the averaged experimental coincidence counts, while
the light red and light blue lines correspond to the theoretical calculation.
(b) and (c) are the real and imaginary part of the measured density matrix.

A long-pass filter ($F_{1}$) and a 3 $nm$ spectral filter at 810 nm ($F_{2}$)
after the crystal are used to block the pump beam and to ensure that only
degenerate photons are measured. Then another 4$f$-system ($f_{2s}$:
$L_{1}=50$ mm, $L_{2}=100$ mm) is used to image the crystal onto the face of a
50:50 non-polarizing beam splitter (BS). Both photons of each pair are equally
to be transmitted or reflected at the BS. Hence, on average half of the
generated pairs yield one photon in the transmitted path and one in the
reflected path. In these incidences two-photon states produced by SPDC can be
represented by a density matrix of the form:

$\displaystyle\hat{\rho}=|A|^{2}\int{d\boldsymbol{q}_{s}d\boldsymbol{q}_{i}d\boldsymbol{q}_{s}^{{}^{\prime}}d\boldsymbol{q}_{i}^{{}^{\prime}}}\langle
G(\boldsymbol{q}_{s}+\boldsymbol{q}_{i})G^{*}(\boldsymbol{q}_{s}^{{}^{\prime}}+\boldsymbol{q}_{i}^{{}^{\prime}})\rangle$
(1) $\displaystyle\times\operatorname{sinc}^{2}(\frac{\varDelta
qL}{2})\frac{1}{\sqrt{2}}(|H_{s},\boldsymbol{q}_{s}\rangle|V_{i},\boldsymbol{q}_{i}\rangle+|V_{s},\boldsymbol{q}_{s}\rangle|H_{i},\boldsymbol{q}_{i}\rangle)$
$\displaystyle\times\frac{1}{\sqrt{2}}({\langle
H_{s^{\prime}},\boldsymbol{q}_{s}^{{}^{\prime}}|\langle
V_{i^{\prime}},\boldsymbol{q}_{i}^{{}^{\prime}}|+\langle
V_{s^{\prime}},\boldsymbol{q}_{s}^{{}^{\prime}}|\langle
H_{i^{\prime}},\boldsymbol{q}_{i}^{{}^{\prime}}|})$

where $|A|^{2}$ is a constant that depends on physical constants, $\langle
G(\cdot)G^{*}(\cdot)\rangle$ represents the angular correlation function of
the pump field, $\boldsymbol{q}_{s},\boldsymbol{q}_{s}^{{}^{\prime}}$ and
$\boldsymbol{q}_{i},\boldsymbol{q}_{i}^{{}^{\prime}}$ are transverse wave
vectors of the signal and idler fields. $\operatorname{sinc}^{2}(\varDelta
qL/2)$ denotes the phase matching function of the nonlinear crystal. The index
$s,i$ denotes the spatial mode called signal, idler. H and V are the
polarization state of the photon. $\left|H_{s},\boldsymbol{q}_{s}\right>$ and
$\left|V_{i},\boldsymbol{q}_{i}\right>$ are the states for the mode with
polarization and transverse wave vector of the signal and idler. The other
degree of freedom, such as the spatial freedom of the photon in this mode is
encoded in its transverese wave vector. Based on Eq. 1, the state is
determined by a mode function which is associated with the pump angular
spectrum as well as the phase matching function of the crystal, and the
polarization projection. If one photon is detected at position
$\boldsymbol{r}_{s}$ at time $t$ with the polarization angle $\theta_{s}$
while another photon is detected at position $\boldsymbol{r}_{i}$ at time
$t+\tau$ with the polarization angle $\theta_{i}$, the coincidence count rate
of the bi-photon states can be written as:

$\displaystyle
R_{si}(\theta_{s},\theta_{i},\boldsymbol{r}_{s},\boldsymbol{r}_{i})=\Bigg{|}|A|^{2}e^{ik_{p}(\boldsymbol{r}_{s}+\boldsymbol{r}_{i})}$
(2)
$\displaystyle\times\Bigg{[}\frac{A_{p}\pi\ell_{c}{\sigma_{0}}^{2}}{z\sqrt{4{\sigma_{0}}^{2}+\ell_{c}^{2}}}\Bigg{]}^{2}\Bigg{[}C_{1}C_{2}\cdot\frac{\pi
z^{2}}{2k_{p}^{2}\sigma_{z}\delta}\sin 2\theta_{s}\sin 2\theta_{i}$
$\displaystyle+\sqrt{\frac{2\pi}{k_{p}^{2}\delta^{2}}}(C_{1}^{2}\cos^{2}\theta_{s}\sin^{2}\theta_{i}+C_{2}^{2}\sin^{2}\theta_{s}\cos^{2}\theta_{i})\Bigg{]}\Bigg{|},$

where $k_{p}$ is the pump wave vector, $\sigma_{0}$ is the beam size, while
the $\sigma_{z}$ is the beam size at position $z$ along the propagating
direction, which satisfies the relationship of
$\sigma_{z}={{z\sqrt{\ell_{c}^{2}+4\sigma_{0}^{2}}}/{2k_{p}\sigma_{0}\ell_{c}}}$,
and $\ell_{c}$ is the transverse coherence length,
$\delta=2\ell_{c}\sigma_{z}/\sqrt{4{\sigma_{z}}^{2}+\ell_{c}^{2}}$ is the
effective spectral width Mandel and Wolf (1995), $C_{1},C_{2}$ denote the
detection efficiency of the whole system, $A_{p}$ is a constant induced by the
cross-spectral density function of a Gaussian Schell Model (GSM) pump beam.
The detailed derivation of Eq. (2) can be found in [Supplemental Material].
Based on Eq. (2), one can see that the count rate is independent of the
position but just up to a phase factor, while the beam size $\sigma_{z}$ and
the spatial coherence $\delta$ will influence the count rate. Considering the
Gaussian profile of the pump beam, to get the highest count rate of the
position correlation of signal and idler photons, we need to scan the
detectors position firstly.

Figure 3: (a)-(d)Quantum state tomography of the output states collected by
two different multi-mode fibers (MMF). (a) and (b) represent the real and the
imaginary parts of the state with a $50\mu m$ MMF. (c) and (d) represent the
real and the imaginary parts of the state with a $125\mu m$ MMF. (e) the
relationship of the concurrence with the spatial coherence of pump in
simulation (lines) and the experimental results (stars).

To increase the detectable signal, instead of scanning the point detector, our
proposed technique is to scan the small range of the signal and idler photons
to find the initial position correlated photons, which is based on our recent
work that uses an LED to implement the position correlation detection of
signal and idler photons Zhang  _et al._ (2019). In order to simplify our
measurement setup, we restrict the transverse position
$\boldsymbol{\rho}_{s},\boldsymbol{\rho}_{i}$ to one direction denoted by
$y_{s},y_{i}$. Therefore, we re-image ($f_{3s}:L_{1}=L_{2}=100$ mm) the facet
of the BS onto the facet of the two single slit ($S_{s},S_{i}$). The width of
each slit is set about $0.1$ mm to guarantee the quality of the photon pairs’
position correlation in $y$ direction [see Supplemental Material for more
details].

The polarization projection angles of signal and idler are performed by a half
wave plate (HWP) together with a polarizing beam splitter (PBS) in each arm,
as shown after the filtering system in Fig. 1. By rotating the angle of HWP,
we can realize a Bell measurement of the bi-photons. After that, a microscope
objectives collects the photons and then couples them into a SMF connected
with the single photon detector. The distance from the slit to the single
photon detector is about $z=100$ mm that is also used in our theoretical
analysis with Eq. (2). The photon coincidence count rate is recorded with a
coincidence window of 1 ns. Since the incoherent pump power is only about 290
µW at the plane of the crystal, we observe a maximum coincidence count rate of
about 15 counts/min, while the maximum single photon count rate is about 10000
counts/min.

Our experimental results are shown in Fig. 2. The plots of coincidence counts
for A-D (red rectangular points) and H-V (blue points) as a function of the
rotation angle ($\theta$) of the HWP are shown in Fig. 2(a). Accidental
coincidences have been removed in these plots and the sinusoidal fits (red
solid line for A-D and blue solid line for H-V ) are used to obtain the
respective visibility. All of the data points are accumulated by 60
measurements. Each measurement is measured in 30s and averaged 60 times to get
the error bar. The visibility of H-V basis is about 86$\%$ while the A-D basis
is about 82$\%$. Based on the CHSH form of Bell’s inequality Clauser  _et al._
(1969), we use the 16 combinations of the HWP settings
($\theta_{1}=0^{\circ},22.5^{\circ},45^{\circ},67.5^{\circ};\theta_{2}=11.25^{\circ},33.75^{\circ},56.25^{\circ},78.75^{\circ}$)
to calculate the Bell parameter $S=2.33\pm 0.097$ experimentally. It is noted
that the theoretical value of the coincidence count rate can be also plotted
based on Eq.(2), as shown in the Fig. 2(a) (light red solid line for A-D and
light blue solid line for H-V ). The theoretical Bell parameter is $S=2.61$.
Here, the transverse coherent length $\ell_{c}$ is estimated to be 11 $\mu m$
based on our previous work Zhang  _et al._ (2019), and the beam waist is
measured several times and averaged approximately as $\sigma_{0}=5$ mm. In our
measurement setup, the slit as well as the detection system is not a strictly
point detector as the theoretical assumption. Therefore, the diameter of the
collection setup determines the number of the collected modes and thus lowers
the value of Bell parameter experimentally.

Apparently, the produced polarization entangled state is not a maximally
entangled state. In order to better illustrate the polarization entangled
photon pairs extracted from an LED pump, we show a more detailed
characterization of the output state obtained by quantum state tomography. For
that, a quarter-wave plates (QWP) is inserted before the HWP in each arm of
the light path. Then we can quantitatively analyze the concrete quantum state
of the detected photon pairs. The density matrix $\hat{\rho}$ of the output
state can be reconstructed through a series of projection measurements. The
individual density matrix elements can be obtained from the coincidence counts
recorded in the corresponding measurements by a maximum likelihood algorithm.
We estimate $\hat{\rho}$ from the 16 projection measurements by using the
methods outlined in Ref James  _et al._ (2001). The real and imaginary parts
of $\hat{\rho}$ are shown in Fig. 2 (b) and (c), respectively. Based on the
measured density matrix $\hat{\rho}$, we can also obtain that the concurrence,
which is used to represent the degree of entanglement Wootters (1998), is
about 0.63.

It is noted that previous works have shown that the multimode nature of the
down-converted photon pairs when using a LED as the pump source Galinis  _et
al._ (2011, 2012). Besides, the number of the spatial modes increases with
increasing the beam size $\sigma_{z}$ of the LED Tamošauskas  _et al._ (2010).
To further verify the influence of the purity of the collected modes on
concurrence for LED pump, we replace the SMF (core diameters $5\mu m$) with
two kinds of multi-mode fiber (MMF) which the core diameters are $50\mu m$ and
$125\mu m$ respectively. Increasing the core diameters of the collection fiber
means we have collected more spatial modes than just the Gaussian modes by
SMF. Similarly, the quantum state tomography is conducted to obtain the
corresponding density matrix of the collected two-photon state as shown in
Fig. 3. Based on these density matrixs, one can calculate the concurrence,
which is about 0.54 for $50\mu m$ MMF and 0.35 for $125\mu m$ MMF,
respectively. The experiment result reveals that the concurrence is lower in
the case of the multi-mode fiber collection, and decreasing with the
increasing of the fiber cross-sectional diameter. In fact, compared with
coupling the single-element detector through a multi-mode fiber, the single
mode one is considered as a way for mode selectivity. What’s more, the spatial
selectivity means that the signal photon is similarly conditioned to the idler
one, as a result, the polarization entanglement is of high quality.

Based on Eq. (1) and Eq.(2), we can actually predict the influence of the beam
size $\sigma_{z}$ and the spatial coherence $\delta$ on the value of
concurrence. we scale the collection diameter of the fiber proportional to the
beam size, which $5mm$ is for SMF, $0.5mm$ is for $50\mu m$ MMF and $0.2mm$ is
for $125\mu m$ MMF, such that the variation of the value of concurrence with
spatial coherence under the different $\sigma_{z}$ can be plotted, as the blue
(upper), red (center), and green(lower) line illustrated in Fig. 3(e). It is
noted that the B of x-axis is expressed as $B=\delta/{2\sigma_{z}}$ adopted to
quantify the degree of beam’s spatial coherence, which interlinks the beam
size and transverse correlation length $\ell_{c}$. Then we can plot our
experimental points with the value of concurrence and B, as the blue star
(upper), red star (center), and green star(lower) shown in 3(e). One can see
that the experimental points are slightly lower than the theoretical
predictions due to the imperfect experimental conditions. And we expect the
value can be improved with smaller collection setups as the theoretical blue
line (upper) predicted. In this regard, our proposed method also provides a
versatile polarization entangled source that can tune the degree of
entanglement as demanded. We also noticed that our experimental results
demonstrate the theoretical prediction discussed in a recent related topic
work Li  _et al._ (2022).

In summary, we have successfully produced polarization-entangled photon pairs
from a truly spatiotemporally incoherent pump beam, a commercial LED. The
theoretical derivation of the influence of the pump transverse coherence
length on the count rate of bi-photons in SPDC under the post-selection
process has been well performed. We have experimentally achieved the violation
of Bell inequality with $S=2.33\pm 0.097$, and thus witnessing the quantum
entanglement definitely. The experimental results are well consistent with our
theoretical prediction. Our technique, obtaining polarization entangled photon
pairs from a cheap LED instead of a laser, may promote the further
application, such as producing the polarization entangled photon pairs even
from sunlight, which provides a way to obtain the electricity-free
polarization entangled photon source for outer space quantum communication.

###### Acknowledgements.

We are grateful to R. W. Boyd, R. Fickler and E. Giese for discussions
initiating this project. Moreover, we thank in particular E. Giese for his
support of the analysis of the theory discussions and thank B. Braverman, G.
Kulkarni, C. Li as well as the Quantum Nonlinear Optics and Quantum Photonics
at the University of Ottawa for fruitful discussions. This work is supported
by the National Natural Science Foundation of China (12034016, 61975169 and
11904303), the Fundamental Research Funds for the Central Universities at
Xiamen University (20720220030, 20720200074), the Natural Science Foundation
of Fujian Province of China for Distinguished Young Scientists (2015J06002),
the Youth Innovation Fund of Xiamen (3502Z20206045).
W. Zhang and D. Xu contributed equally to this work.

## References

  * Bennett (1995) C. H. Bennett, Physics Today 48 (1995).
  * Nielsen and Chuang (2002) M. A. Nielsen and I. Chuang, Am. J. Phys. 70, 558 (2002).
  * Mandel and Wolf (1995) L. Mandel and E. Wolf,  _Optical Coherence and Quantum Optics_ (Cambridge University Press, 1995).
  * Bouwmeester  _et al._ (1997) D. Bouwmeester, J.-W. Pan, K. Mattle, M. Eibl, H. Weinfurter, and A. Zeilinger, Nature 390, 575 (1997).
  * Mattle  _et al._ (1996) K. Mattle, H. Weinfurter, P. G. Kwiat, and A. Zeilinger, Phys. Rev. Lett. 76, 4656 (1996).
  * Jennewein  _et al._ (2000) T. Jennewein, C. Simon, G. Weihs, H. Weinfurter, and A. Zeilinger, Phys. Rev. Lett. 84, 4729 (2000).
  * Defienne  _et al._ (2021) H. Defienne, B. Ndagano, A. Lyons, and D. Faccio, Nature Physics 17, 591 (2021).
  * O’Brien  _et al._ (2003) J. L. O’Brien, G. J. Pryde, A. G. White, T. C. Ralph, and D. Branning, Nature 426, 264 (2003).
  * O’brien (2007) J. L. O’brien, Science 318, 1567 (2007).
  * Sansoni (2014) L. Sansoni,  _Integrated devices for quantum information with polarization encoded qubits_ (Springer, 2014).
  * Ursin  _et al._ (2007) R. Ursin, F. Tiefenbacher, T. Schmitt-Manderbach, H. Weier, T. Scheidl, M. Lindenthal, B. Blauensteiner, T. Jennewein, J. Perdigues, P. Trojek, _et al._ , Nat. Phys. 3, 481 (2007).
  * Ma  _et al._ (2012) X.-S. Ma, T. Herbst, T. Scheidl, D. Wang, S. Kropatschek, W. Naylor, B. Wittmann, A. Mech, J. Kofler, E. Anisimova, _et al._ , Nature 489, 269 (2012).
  * Yin  _et al._ (2017) J. Yin, Y. Cao, Y.-H. Li, J.-G. Ren, S.-K. Liao, L. Zhang, W.-Q. Cai, W.-Y. Liu, B. Li, H. Dai, M. Li, Y.-M. Huang, L. Deng, L. Li, Q. Zhang, N.-L. Liu, Y.-A. Chen, C.-Y. Lu, R. Shu, C.-Z. Peng, J.-Y. Wang, and J.-W. Pan, Phys. Rev. Lett. 119, 200501 (2017).
  * Kwiat  _et al._ (1995) P. G. Kwiat, K. Mattle, H. Weinfurter, A. Zeilinger, A. V. Sergienko, and Y. Shih, Phys. Rev. Lett. 75, 4337 (1995).
  * Lee  _et al._ (2004) P. S. K. Lee, M. P. van Exter, and J. P. Woerdman, Phys. Rev. A 70, 043818 (2004).
  * Trojek and Weinfurter (2008) P. Trojek and H. Weinfurter, Appl. Phys. Lett. 92, 211103 (2008).
  * Kwiat  _et al._ (1999) P. G. Kwiat, E. Waks, A. G. White, I. Appelbaum, and P. H. Eberhard, Phys. Rev. A 60, R773 (1999).
  * Shi and Tomita (2004) B.-S. Shi and A. Tomita, Phys. Rev. A 69, 013803 (2004).
  * Fiorentino  _et al._ (2004) M. Fiorentino, G. Messin, C. E. Kuklewicz, F. N. Wong, and J. H. Shapiro, Phys. Rev. A 69, 041801 (2004).
  * Chen  _et al._ (2018) Y. Chen, S. Ecker, S. Wengerowsky, L. Bulla, S. K. Joshi, F. Steinlechner, and R. Ursin, Phys. Rev. Lett. 121, 200502 (2018).
  * Nambu  _et al._ (2002) Y. Nambu, K. Usami, Y. Tsuda, K. Matsumoto, and K. Nakamura, Phys. Rev. A 66, 033816 (2002).
  * Evans  _et al._ (2010) P. G. Evans, R. S. Bennink, W. P. Grice, T. S. Humble, and J. Schaake, Phys. Rev. Lett. 105, 253601 (2010).
  * Jha and Boyd (2010) A. K. Jha and R. W. Boyd, Phys. Rev. A 81, 013828 (2010).
  * Giese  _et al._ (2018) E. Giese, R. Fickler, W. Zhang, L. Chen, and R. W. Boyd, Phys. Scr. 93, 084001 (2018).
  * Vintskevich  _et al._ (2019) S. Vintskevich, D. Grigoriev, and S. Filippov, Phys. Rev. A 100, 053811 (2019).
  * Kanseri and Sharma (2020) B. Kanseri and P. Sharma, J. Opt. Soc. Am. B 37, 505 (2020).
  * Joshi and Kanseri (2020) S. Joshi and B. Kanseri, Optik 217, 164941 (2020).
  * Kulkarni  _et al._ (2016) G. Kulkarni, V. Subrahmanyam, and A. K. Jha, Phys. Rev. A 93, 063842 (2016).
  * Patoary  _et al._ (2019) A. S. M. Patoary, G. Kulkarni, and A. K. Jha, J. Opt. Soc. Am. B 36, 2765 (2019).
  * Sharma  _et al._ (2021) P. Sharma, N. K. Pathak, and B. Kanseri, Results Phys. 27, 104506 (2021).
  * Defienne and Gigan (2019) H. Defienne and S. Gigan, Phys. Rev. A 99, 053831 (2019).
  * Ismail  _et al._ (2017) Y. Ismail, S. Joshi, and F. Petruccione, Sci. Rep. 7, 1 (2017).
  * Hutter  _et al._ (2020) L. Hutter, G. Lima, and S. P. Walborn, Phys. Rev. Lett. 125, 193602 (2020).
  * Tamošauskas  _et al._ (2010) G. Tamošauskas, J. Galinis, A. Dubietis, and A. Piskarskas, Opt. Express 18, 4310 (2010).
  * Galinis  _et al._ (2011) J. Galinis, M. Karpiński, G. Tamošauskas, K. Dobek, and A. Piskarskas, Opt. Express 19, 10351 (2011).
  * Galinis  _et al._ (2012) J. Galinis, G. Tamošauskas, and A. Piskarskas, Opt. Commun. 285, 1289 (2012).
  * Nishii  _et al._ (2019) D. Nishii, Y. O-oka, Y. Okawa, and S. Fukatsu, Appl. Phys. Lett. 115, 211106 (2019).
  * Zhang  _et al._ (2019) W. Zhang, R. Fickler, E. Giese, L. Chen, and R. W. Boyd, Opt. Express 27, 20745 (2019).
  * Qiu and She (2012) Y. Qiu and W. She, Appl. Phys. B 108, 683 (2012).
  * Gbur (2014) G. Gbur, J. Opt. Soc. Am. A 31, 2038 (2014).
  * Phehlukwayo  _et al._ (2020) S. P. Phehlukwayo, M. L. Umuhire, Y. Ismail, S. Joshi, and F. Petruccione, Phys. Rev. A 102, 033732 (2020).
  * Clauser  _et al._ (1969) J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt, Phys. Rev. Lett. 23, 880 (1969).
  * Kuklewicz  _et al._ (2004) C. E. Kuklewicz, M. Fiorentino, G. Messin, F. N. Wong, and J. H. Shapiro, Phys. Rev. A 69, 013807 (2004).
  * Pittman  _et al._ (1995) T. B. Pittman, Y. H. Shih, D. V. Strekalov, and A. V. Sergienko, Phys. Rev. A 52, R3429 (1995).
  * Strekalov  _et al._ (1995) D. V. Strekalov, A. V. Sergienko, D. N. Klyshko, and Y. H. Shih, Phys. Rev. Lett. 74, 3600 (1995).
  * James  _et al._ (2001) D. F. V. James, P. G. Kwiat, W. J. Munro, and A. G. White, Phys. Rev. A 64, 052312 (2001).
  * Wootters (1998) W. K. Wootters, Phys. Rev. Lett. 80, 2245 (1998).
  * Li  _et al._ (2022) C. Li, B. Braverman, G. Kulkarni, and R. W. Boyd, arXiv preprint arXiv:2210.16229 (2022).