# How Real is Incomputability in Physics?

José Manuel Agüero1 Trejo, Cristian S. Calude1 Michael J. Dinneen1,
Arkady Fedorov2,3, Anatoly Kulikov2,3, Rohit Navarathna2,3, Karl Svozil4
1School of Computer Science, University of Auckland, New Zealand
2School of Mathematics and Physics, University of Queensland, Australia
3ARC Centre of Excellence for Engineered Quantum Systems, Queensland,
Australia
4Institut für Theoretische Physik, TU Wien, Vienna, Austria

###### Abstract

A physical system is determined by a finite set of initial conditions and laws
represented by equations. The system is computable if we can solve the
equations in all instances using a “finite body of mathematical knowledge". In
this case, if the laws of the system can be coded into a computer program,
then given the system’s initial conditions of the system, one can compute the
system’s evolution.

This scenario is tacitly taken for granted. But is this reasonable? The answer
is negative, and a straightforward example is when the initial conditions or
equations use irrational numbers, like Chaitin’s Omega Number: no program can
deal with such numbers because of their “infinity”.

Are there incomputable physical systems? This question has been theoretically
studied in the last 30–40 years. This article presents a class of quantum
protocols producing quantum random bits. Theoretically, we prove that every
infinite sequence generated by these quantum protocols is strongly
incomputable – no algorithm computing any bit of such a sequence can be proved
correct. This theoretical result is not only more robust than the ones in the
literature: experimental results support and complement it.

##  1 Introduction

According to Einstein [23]

> Physics constitutes a logical system of thought which is in a state of
> evolution … The justification (truth content) of the system rests in the
> proof of the usefulness of the resulting theorems on the basis of sense
> experiences, where the relations of the latter to the former can only be
> comprehended intuitively.

This is in agreement with Hertz’s contemplation of the relationship between
physical and formal entities [28]:

> We form for ourselves images or symbols of external objects, and the form
> which we give them is such that the necessary consequents of the images in
> thought are always the images of the necessary consequents in nature of the
> things pictured.

Both Einstein and Hertz do not perceive a ‘strong’ connection between physical
entities and their corresponding categories of mind, but rather a
homomorphism. This raises the question: how much trust can we place in the
theoretical categories regarding their usefulness in physics? What criteria
can be provided to ensure and certify their applicability relative to our
assumptions?

A physical system is determined by a finite set of initial conditions and laws
represented by equations. The system is computable if we can solve the
equations in all instances using a “finite body of mathematical knowledge". If
the laws of the system can be coded into a computer program, then given the
system’s initial conditions, one can compute the system’s evolution.

One needs to differentiate between operational, empirically accessible,
observables on the one hand, and, on the other hand, theoretical assumptions
and conventions – such as the existence of the continuum – that are not
operational (“almost all” elements are incomputable and even random), but
provide a convenient formalism [10].

This scenario is tacitly taken for granted in discussing issues of
incomputability. But is this reasonable? The answer is negative, and a
straightforward example is when the initial conditions or equations include
irrational numbers, like Chaitin’s Omega Number: no program can deal with such
numbers because of their infinity.

Incomputability in physics has been studied by many authors [54, 55, 57, 38,
21, 44, 17, 19, 64, 35, 20, 8, 41, 29, 33, 61, 41, 13, 34, 1, 3, 27, 7, 30].
The results in all these articles are mainly theoretical, so following
Einstein’s above citation, we can ask: what is their justification? The word
“real" in the title means “a justification of incomputability claims based on
usefulness”.

For sufficiently complex systems (even reversible) determinism on a “one-by
(to)-one” evolution basis does not imply predictability [53]. For example,
take the $n$-body problem as example: the respective series solutions [60, 43,
52, 58, 59] may be “very slowly” convergent [22], or even encode the Halting
Problem [56].

Quantum underdetermination can be expressed in terms of gaps in the physical
description [25, 26, § III.12-14]: Due to the unitarity of quantum evolution,
information cannot be created nor annihilated. Therefore, if a quantised
system encodes a finite amount of information any query above this information
must inevitably be indeterminate and value indefinite relative to the original
quantum state. One could, of course, suppose that the entanglement can fulfil
such a request with the measurement apparatus and thus the environment at
large [36, 37], resulting in an unbounded nesting argument with an ever-
increasing Heisenberg cut. Yet the fact remains that, due to the finite
(possibly relational [63]) amount of information encoded in a quantised
system, information in excess of this amount cannot reside or be encoded in
any pre-selected state.

This article uses a located form of the Kochen-Specker Theorem to derive a
class of quantum protocols producing quantum random bits. Theoretically, we
prove that every infinite sequence generated with these quantum protocols is
strongly incomputable – no algorithm computing any bit of such a sequence can
be proved correct. Such a result is more robust than the ones in the
literature and satisfies Einstein’s requirement of justification: the
experimental results presented here confirm and complement incomputability
and, quite importantly, the choice of physical assumptions.

The paper is organised as follows. In Section 2, we present the theoretical
framework for the Localised Kochen-Specker Theorem, allowing the construction
of strongly incomputable sequences via measurements of value-indefinite
observables. In Section 3, we use a standard superconducting transmon system
to implement logical states as qutrits and realise the theoretical quantum
protocols in Section 2. In Section 4, we present a method to empirically show
the incomputability of the outputs generated in Section 3. The last Section 5,
we briefly discuss the results presented in this article and suggest further
continuations.

##  2 3D-QRNG – Theory

In this section, we present the theoretical framework allowing the
construction of value-indefinite observables, their tolerance to measurement
errors and the certification of the degree of randomness of their outcomes.

###  2.1 Notation and definitions

The set of positive integers will be denoted by $\mathbb{N}$. Consider the
alphabet $A_{b}=\\{0,1,\dots,b-1\\}$, where $b\geq 2$ is an integer; the
elements of $A_{b}$ are the digits used in natural positional representations
of numbers in the interval $[0,1)$ at base $b$. By $A_{b}^{*}$ and
$A_{b}^{\omega}$ we denote the sets of (finite) strings and (infinite)
sequences over the alphabet $A_{b}$. Strings will be denoted by $x,y,u,w$; the
length of the string $x=x_{1}x_{2}\dots x_{m}$, $x_{i}\in A_{b}$, is denoted
by $|x|_{b}=m$ (the subscript $b$ will be omitted if it is clear from the
context); $A_{b}^{m}$ is the set of all strings of length $m$. Sequences will
be denoted by $\mathbf{x}=x_{1}x_{2}\dots$; the prefix of length $m$ of
$\mathbf{x}$ is the string $\mathbf{x}(m)=x_{1}x_{2}\dots x_{m}$. Strings will
be ordered quasi-lexicographically according to the natural order
$0<1<2<\dots<b-1$ on the alphabet $A_{b}$. For example, for $b=2$, we have
$0<1<00<01<10<11<000\dots$. We assume knowledge of elementary computability
theory over different size alphabets [11].

By $\mathbb{C}$, we denote the set of complex numbers. We then fix a positive
integer $n\geq 2$ and let
$O\subseteq\\{P_{\psi}:\ket{\psi}\in\mathbb{C}^{n}\\}$ be a non-empty set of
one-dimensional projection observables on the Hilbert space $\mathbb{C}^{n}$.

A set $C\subset O$ is a context of $O$ if $C$ has $n$ elements and for all
$P_{\psi},P_{\phi}\in C$ with $P_{\psi}\neq
P_{\phi},\innerproduct{\psi}{\phi}=O$. A value assignment function (on $O$) is
a partial function $v:O\to\\{0,1\\}$ assigning values to some (possibly all)
observables in $O$. The partiality of the function $v$ means that $v(P)$ can
be $0,1$ or indefinite. An observable $P\in O$ is value definite (under the
assignment function $v$) if $v(P)$ is defined, i.e. it is 0 or 1; otherwise,
it is value indefinite (under $v$). Similarly, we call $O$ value definite
(under $v$) if every observable $P\in O$ is value definite.

We then fix a positive integer $n\geq 2$ and let
$O\subseteq\\{P_{\psi}:\ket{\psi}\in\mathbb{C}^{n}\\}$ be a non-empty set of
one-dimensional projection observables on the Hilbert space $\mathbb{C}^{n}$.
A set $C\subset O$ is a context of $O$ if $C$ has $n$ elements and for all
$P_{\psi},P_{\phi}\in C$ with $P_{\psi}\neq
P_{\phi},\innerproduct{\psi}{\phi}=O$. A value assignment function (on $O$) is
a partial function $v:O\to\\{0,1\\}$ assigning values to some (possibly all)
observables in $O$. The partiality of the function $v$ means that $v(P)$ can
be $0,1$ or indefinite. An observable $P\in O$ is value definite (under the
assignment function $v$) if $v(P)$ is defined, i.e. it is 0 or 1; otherwise,
it is value indefinite (under $v$). Similarly, $O$ is value definite (under
$v$) if every observable $P\in O$ is value definite.

###  2.2 Localised Kochen-Specker Theorem

We next present the main result used to construct a value indefinite
observable. First, we assume the following premises:

  * •

Admissibility. This assumption guarantees agreement with quantum mechanics
predictions. Fix a set $O$ of one-dimensional projection observables on
$\mathbb{C}^{n}$ and the value assignment function $v:O\rightarrow\\{0,1\\}$.
Then $v$ is admissible if for every context $C$ of $O$, we have that
$\sum_{P\in C}v(P)=1$. Accordingly, only one projection observable in a
context can be assigned the value $1$.

  * •

Non-contextuality of definite values. Every outcome obtained by measuring a
value definite observable is non-contextual, i.e. it does not depend on other
compatible observables which may be measured alongside it.

  * •

Eigenstate principle. If a quantum system is prepared in the state
$\ket{\psi}$, then the projection observable $P_{\psi}$ is value definite.

The last assumption is motivated by Einstein, Podolsky and Rosen definition of
physical reality [24, p. 777]: If, without in any way disturbing a system, we
can predict with certainty the value of a physical quantity, then there exists
a _definite value_ prior to observation corresponding to this physical
quantity. A criterion for value-definiteness results: if a quantum system is
prepared in an arbitrary state $\ket{\psi}\in\mathbb{C}^{n}$, then the
measurement of the observable $P_{\psi}$ should yield the outcome $1$, hence,
if $P_{\psi}\in O$, then $v(P_{\psi})=1.$

We can now state the main result:

######  Theorem 1 (Localised Kochen-Specker Theorem [4, 5, 34, 7])

Assume a quantum system prepared in the state $\ket{\psi}$ in a dimension
$n\geq 3$ Hilbert space ${\mathbf{C}}^{n}$, and let $\ket{\phi}$ be any
quantum state such that $0<\absolutevalue{\bra{\psi}\ket{\phi}}<1$. If the
following three conditions are satisfied: i) admissibility, ii) non-
contextuality and iii) eigenstate principle, then the projection observable
$P_{\psi}$ is value indefinite.

Theorem 1 states that, under the given assumptions, any quantum state
$\ket{\phi}$ that is neither orthogonal nor parallel to $\ket{\psi}$ is value
indefinite. This result has two major consequences:

  1. 1.

it shows how to construct a value indefinite observable effectively,

  2. 2.

it guarantees that the status of “value-indefiniteness” is invariant under
minor errors in measurements: this is a significant property as no measurement
is exact.

We note that Theorem 1, as the original Kochen-Specker Theorem [32], is not
valid in ${\mathbf{C}}^{2}$, hence the requirement to work in
${\mathbf{C}}^{3}$.

How “good” is such a 3D-QRNG, i.e. what randomness properties can be certified
for their outcomes? For example, can we prove that the outcomes of the 3D-QRNG
are “better” than the outcomes produced by any pseudo-random number generator
(PRNG)?

For certification, we use the following assumption, which is motivated by the
fact that a computable sequence is the strongest form of “deterministic hidden
variable":

  * •

epr principle: If a repetition of measurements of an observable generates a
computable sequence, then these observables are value definite.

Based on the Eigenstate and epr principles, we can prove that the answer to
the last question is affirmative: Any infinite repetition of the experiment
measuring a quantum value indefinite observable generates an incomputable
infinite sequence $x_{1}x_{2}\dots$: no PRNG has this randomness property.

A stronger result is true. Informally, a sequence $\mathbf{x}$ is bi-immune if
no algorithm can generate infinitely many correct values of its elements
(pairs, $(i,x_{i})$). Formally, a. sequence $\mathbf{x}\in A_{b}^{\omega}$
($b\geq 2$) is bi-immune if there is no partially computable function
$\varphi$ from $\mathbb{N}$ to $A_{b}$ having an infinite domain
$\mathrm{dom}(\varphi)$ with the property that $\varphi(i)=x_{i}$ for all
$i\in\mathrm{dom}(\varphi)$ [9]).

######  Theorem 2 ([1, 7])

Assume the Eigenstate and epr principles. An infinite repetition of the
experiment measuring a quantum value indefinite observable in $\mathbb{C}^{b}$
always generates a $b$-bi-immune sequence $\mathbf{x}\in A_{2}^{\omega}$, for
every $b\geq 2$.

In particular, every sequence generated by the 3D-QRNG is 3-bi-immune.

######  Theorem 3 ([7])

Assume the epr and Eigenstate principles. Let $\mathbf{x}$ be an infinite
sequence obtained by measuring a quantum value indefinite observable in
$\mathbb{C}^{b}$ in an infinite repetition of the experiment $E$. Then, no
single bit $x_{i}$ can be predicted.

In particular, no single digit of every sequence $\mathbf{x}\in
A_{3}^{\omega}$ generated by the 3D-QRNG can be algorithmically predicted.

The following simple morphism $\varphi\colon A_{3}\rightarrow A_{2}$
transforms a ternary sequence into a binary sequence:

$\varphi(a)=\begin{cases}0,&\text{if }a=0,\\\ 1,&\text{if }a=1,\\\ 0&\text{if
}a=2,\end{cases}$ (1)

, which can be extended sequentially for strings,
$\mathbf{y}(n)=\varphi(\mathbf{x}(n))=\varphi(x_{1})\varphi(x_{2})$
$\dots\varphi(x_{n})$ and sequences
$\mathbf{y}=\varphi(\mathbf{x})=\varphi(x_{1})\varphi(x_{2})\dots\varphi(x_{n})\dots$.
This transformation preserves 2-bimmunity:

######  Theorem 4 ([7])

Assume the epr and Eigenstate principles. Let
$\mathbf{y}=\varphi(\mathbf{x})$, where $\mathbf{x}\in A_{3}^{\omega}$ is a
ternary sequence generated by the 3D-QRNG and $\varphi$ is the alphabetic
morphism defined in (1). Then, no single bit of $\mathbf{y}\in A_{2}^{\omega}$
can be predicted.

As noted in [7], Theorem 1 shows that given a system prepared in state
$\ket{\psi}$, a one-dimensional projection observable can only be value
definite if it is an eigenstate of that observable. Consequently, for any
diagonalisable observable $O$ with spectral decomposition
$O=\sum_{i=1}^{n}\lambda_{i}P_{\lambda_{i}}$, where $\lambda_{i}$ denotes each
distinct eigenvalue with corresponding eigenstate $\ket{\lambda_{i}}$, $O$ has
a predetermined measurement outcome if and only if each projector in its
spectral decomposition has a predetermined measurement outcome. Thus, the
previous result holds true to the outcome of the measurement of any observable
with non-degenerate spectra. Such generalisation is particularly useful in the
case when we use the value assignment function to represent a value definite
observable. These results have been used to design the following quantum
operators of the 3D-QRNG. These 3D-QRNGs operate in a succession of events of
the form “preparation, measurement, reset”, iterated indefinitely many times
in an algorithmic fashion [1]. The first 3D-QRNG was designed in [1], realized
in [34] and analysed in [2]. While the analysis failed to observe a strong
advantage of the quantum random sequences due to incomputability, it has
motivated the improvement in [7], in which the problematic probability zero
branch $S_{x}=0$ in Figure 1.

every picture/.style=line width=0.60pt [x=0.6pt,y=0.6pt,yscale=-1,xscale=1]
(26,129) – (149.2,129) – (149.2,152.4) – (26,152.4) – cycle ; (150,140) –
(190,139.42) ; [shift=(190,139.4), rotate = 539.51] [fill=rgb, 255:red, 0;
green, 0; blue, 0 ][line width=0.75] [draw opacity=0] (8.93,-4.29) – (0,0) –
(8.93,4.29) – cycle ; (190,129) – (300,129) – (300,152.4) – (190,152.4) –
cycle ; (300,140) – (350,140) ; [shift=(350,140), rotate = 539.51] [fill=rgb,
255:red, 0; green, 0; blue, 0 ][line width=0.75] [draw opacity=0] (8.93,-4.29)
– (0,0) – (8.93,4.29) – cycle ; (350,129) – (460,129) – (460,152.4) –
(350,152.4) – cycle ; [dash pattern=on 0.84pt off 2.51pt](460,140) – (520,140)
; [shift=(520,140), rotate = 539.51] [fill=rgb, 255:red, 0; green, 0; blue, 0
][line width=0.75] [draw opacity=0] (8.93,-4.29) – (0,0) – (8.93,4.29) – cycle
; (300,152.4) – (350,183.21) ; [shift=(350,184.4), rotate = 216.66] [fill=rgb,
255:red, 0; green, 0; blue, 0 ][line width=0.75] [draw opacity=0] (8.93,-4.29)
– (0,0) – (8.93,4.29) – cycle ; (300,129) – (350,95.62) ; [shift=(350,94.4),
rotate = 502.44] [fill=rgb, 255:red, 0; green, 0; blue, 0 ][line width=0.75]
[draw opacity=0] (8.93,-4.29) – (0,0) – (8.93,4.29) – cycle ; (460,130) –
(520,96.62) ; [shift=(520,95.4), rotate = 502.44] [fill=rgb, 255:red, 0;
green, 0; blue, 0 ][line width=0.75] [draw opacity=0] (8.93,-4.29) – (0,0) –
(8.93,4.29) – cycle ; (460,152.4) – (520,183.21) ; [shift=(520,184.4), rotate
= 216.66] [fill=rgb, 255:red, 0; green, 0; blue, 0 ][line width=0.75] [draw
opacity=0] (8.93,-4.29) – (0,0) – (8.93,4.29) – cycle ; (520,90) .. controls
(520,82) and (527,75) .. (536,75) .. controls (544,75) and (552,82) ..
(552,90) .. controls (552,99) and (544,106) .. (536,106) .. controls (527,106)
and (520,99) .. (520,90) – cycle ; (520,186) .. controls (520,178) and
(527,171) .. (536,171) .. controls (544,171) and (552,178) .. (552,186) ..
controls (552,195) and (544,202) .. (536,202) .. controls (527,202) and
(520,195) .. (520,186) – cycle ; (87.6,140.7) node [align=left] Spin-1 source;
(240.6,140.7) node [align=left] $\displaystyle S_{z}$ splitter ; (400.6,140.7)
node [align=left] $\displaystyle S_{x}$ splitter ; (312,109) node [align=left]
1; (312,174) node [align=left] -1; (325,131) node [align=left] 0; (535,90.7)
node [align=left] 1; (535,185.7) node [align=left] 0; (478,109) node
[align=left] 1; (478,174) node [align=left] -1; (492,131) node [align=left] 0;
(575,90.7) node [align=left]
$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\frac{1}{2}}$;
(575,185.7) node [align=left]
$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\frac{1}{2}}$;

Figure 1: QRNG setup proposed in [1]; the values $\frac{1}{2},\frac{1}{2}$ (in
blue) correspond to the outcome probabilities

The next 3D-QRNG is presented in Figure 2. The unitary matrix $U_{x}$
corresponding to the spin state operator $S_{x}$ is

$U_{x}=\frac{1}{2}\begin{pmatrix}1&\sqrt{2}&1\\\ \sqrt{2}&0&-\sqrt{2}\\\
1&-\sqrt{2}&1\end{pmatrix}.$

As $U_{x}$ can be decomposed into two-dimensional transformations [16]

$U_{x}=\begin{pmatrix}1&0&0\\\ 0&-i&0\\\
0&0&-i\end{pmatrix}\cdot\begin{pmatrix}\frac{1}{\sqrt{3}}&\sqrt{\frac{2}{3}}&0\\\
i\sqrt{\frac{2}{3}}&-\frac{i}{\sqrt{3}}&0\\\ 0&0&1\\\
\end{pmatrix}\cdot\begin{pmatrix}\frac{\sqrt{3}}{2}&0&-\frac{i}{2}\\\ 0&1&0\\\
\frac{i}{2}&0&-\frac{\sqrt{3}}{2}\\\ \end{pmatrix}\cdot\begin{pmatrix}1&0&0\\\
0&\frac{1}{\sqrt{3}}&\sqrt{\frac{2}{3}}\\\
0&i\sqrt{\frac{2}{3}}&-\frac{i}{\sqrt{3}}\end{pmatrix}.$

a physical realisation of the unitary operator by a lossless beam splitter
[46, 62] was obtained; the new outcome probabilities are 1/4,1/2,/1/4.

every picture/.style=line width=0.60pt [x=0.6pt,y=0.6pt,yscale=-1,xscale=1]
(26,129) – (149.2,129) – (149.2,152.4) – (26,152.4) – cycle ; (150,140) –
(190,139.42) ; [shift=(190,139.4), rotate = 539.51] [fill=rgb, 255:red, 0;
green, 0; blue, 0 ][line width=0.75] [draw opacity=0] (8.93,-4.29) – (0,0) –
(8.93,4.29) – cycle ; (190,129) – (300,129) – (300,152.4) – (190,152.4) –
cycle ; (300,140) – (350,140) ; [shift=(350,140), rotate = 539.51] [fill=rgb,
255:red, 0; green, 0; blue, 0 ][line width=0.75] [draw opacity=0] (8.93,-4.29)
– (0,0) – (8.93,4.29) – cycle ; (350,129) – (460,129) – (460,152.4) –
(350,152.4) – cycle ; (460,140) – (520,140) ; [shift=(520,140), rotate =
539.51] [fill=rgb, 255:red, 0; green, 0; blue, 0 ][line width=0.75] [draw
opacity=0] (8.93,-4.29) – (0,0) – (8.93,4.29) – cycle ; (460,130) –
(520,96.62) ; [shift=(520,95.4), rotate = 502.44] [fill=rgb, 255:red, 0;
green, 0; blue, 0 ][line width=0.75] [draw opacity=0] (8.93,-4.29) – (0,0) –
(8.93,4.29) – cycle ; (460,152.4) – (520,183.21) ; [shift=(520,184.4), rotate
= 216.66] [fill=rgb, 255:red, 0; green, 0; blue, 0 ][line width=0.75] [draw
opacity=0] (8.93,-4.29) – (0,0) – (8.93,4.29) – cycle ; (520,90) .. controls
(520,82) and (527,75) .. (536,75) .. controls (544,75) and (552,82) ..
(552,90) .. controls (552,99) and (544,106) .. (536,106) .. controls (527,106)
and (520,99) .. (520,90) – cycle ; (520,138) .. controls (520,130) and
(527,123) .. (536,123) .. controls (544,123) and (552,130) .. (552,138) ..
controls (552,147) and (544,154) .. (536,154) .. controls (527,154) and
(520,147) .. (520,138) – cycle ; (520,186) .. controls (520,178) and (527,171)
.. (536,171) .. controls (544,171) and (552,178) .. (552,186) .. controls
(552,195) and (544,202) .. (536,202) .. controls (527,202) and (520,195) ..
(520,186) – cycle ; (87.6,140.7) node [align=left] Spin-1 source;
(240.6,140.7) node [align=left] $\displaystyle S_{z}$ splitter ; (400.6,140.7)
node [align=left] $\displaystyle S_{x}$ splitter ; (325,121) node [align=left]
$\ket{\psi}$; (535,90.7) node [align=left] 0; (535,137.7) node [align=left] 1;
(535,185.7) node [align=left] 2; (478,109) node [align=left] 1; (478,174) node
[align=left] -1; (492,131) node [align=left] 0; (575,90.7) node [align=left]
$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\frac{1}{4}}$;
(575,137.7) node [align=left]
$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\frac{1}{2}}$;
(575,185.7) node [align=left]
$\displaystyle\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}{\frac{1}{4}}$;

Figure 2: Blueprint for a new QRNG; the values
$\frac{1}{4},\frac{1}{2},\frac{1}{4}$ (in blue) correspond to the outcome
probabilities of setups prepared in the state $\ket{\psi}=\ket{\pm 1}$

##  3 3D-QRNG – Physical Realisation

To realise the protocols shown in Figs. 1,2 we used a standard superconducting
transmon system [34]. The transmon has a weakly anharmonic multi-level
structure [31], and its three lowest energy eigenstates $|0\rangle,|1\rangle$
and $|2\rangle$ can be used as the logical states of a qutrit.

To implement the protocol shown in Fig. 1 we followed the recipe from [34]
where the eigenstates of the $S_{z}$ operator were mapped to the states of the
qutrit as follows

$\\{|z,-1\rangle,|z,0\rangle,|z,+1\rangle\\}\rightarrow\\{|2\rangle,|0\rangle,|1\rangle\\}.$
(2)

This mapping provided an advantage of preparing $|z,0\rangle$ state by cooling
down the transmon to the base temperature of a dilution refrigerator ($\sim
20\,$mK).

To perform an arbitrary rotation of the qutrit quantum state
$R_{\hat{n}}^{i,i+1}(\phi)$ we applied microwave pulses resonant to the
$|0\rangle\leftrightarrow|1\rangle$ or $|1\rangle\leftrightarrow|2\rangle$
transition frequencies, respectively. Two rotations $R^{12}_{y}(\pi)\cdot
R^{01}_{y}(\pi/2)$ of the state before the dispersive measurement were used to
engineer a measurement in the eigenbasis of $S_{x}$. The resulting measurement
outcomes of the transmon energy eigenstates were mapped to the following
outcomes of the measurement of $S_{x}$ operator:
$\\{|0\rangle,|1\rangle,|2\rangle\\}\rightarrow\\{|x,+1\rangle,|x,-1\rangle,|x,0\rangle\\}$.

To implement the protocol shown in Fig. 2 we used a slightly different
encoding:

$\\{|z,-1\rangle,|z,0\rangle,|z,+1\rangle\\}\rightarrow\\{|1\rangle,|2\rangle,|0\rangle\\}.$
(3)

In this case, state $|z,+1\rangle$ was prepared by cooling the transmon. The
following measurement in the eigenbasis of $S_{x}$ was engineered by applying
the same rotations $R^{01}_{y}(\pi/2)\cdot R^{12}_{y}(\pi/2)$ before the
dispersive measurements. The measurement outcomes of the transmon were then
mapped to the following outcomes of the measurement of $S_{x}$ operator:
$\\{|0\rangle,|1\rangle,|2\rangle\\}\rightarrow\\{|x,0\rangle,|x,-1\rangle,|x,+1\rangle\\}$.

To measure the transmon, we used the standard dispersive readout scheme where
the transmon is capacitively coupled to a co-planar waveguide resonator. The
difference between the frequency of the resonator ($f_{r}=7.63$ GHz) and the
$|0\rangle\leftrightarrow|1\rangle$ ($f_{01}=5.49$ GHz) and
$|1\rangle\leftrightarrow|2\rangle$ ($f_{12}=5.16$ GHz) transitions of the
transmon was designed to be much larger than the qubit-resonator coupling to
ensure that the system is in the dispersive regime. In this regime, the
frequency of the resonator depended on the states of the transmon and
underwent shifts of $-8.5$ MHz or $-15.5$ MHz when the transmon was excited in
$|1\rangle$ or $|2\rangle$ states, relative to $f_{r}$ when the transmon was
prepared in its ground state $|0\langle$ [31]. We used a Josephson parametric
amplifier to distinguish between three different transmon states with high
fidelity. In addition, we set the readout pulse frequency close to the cavity
frequency corresponding to the $|1\rangle$ state of the qutrit, which allowed
the three possible qutrit states to be well separated on the I-Q plane for the
time-integrated signal measured with the heterodyne detection scheme. The
readout frequency was then fine-tuned to maximise the three-level readout
fidelity. The measurement response was classified using a convolutional neural
network (CNN) to increase the readout fidelity further, as described in [42].

The procedure used to generate the random numbers required an initial
calibration procedure typical for circuit quantum electrodynamics setups. This
involved calibration of $f_{r}$, $f_{01}$ and the $R^{01}_{y}(\pi)$ and
$R^{01}_{y}(\pi/2)$ pulses. Two $R^{01}_{y}(\pi/2)$ pulses were used to fine-
tune $f_{01}$ using a Ramsey measurement. The $R^{01}_{y}(\pi)$ and
$R^{01}_{y}(\pi/2)$ pulses were then fine-tuned with repeated pulses. A
similar procedure was followed to calibrate for $f_{12}$ and the
$R^{12}_{y}(\pi)$ and $R^{12}_{y}(\pi/2)$ pulses.

After initial calibrations, we optimised the readout frequency of a single-
shot readout using the Josephson parametric amplifier. The CNN is then trained
for 50 cycles using 1024 measurements of the readout resonator after preparing
each of the three states, $|0\rangle$,$|1\rangle$ and $|2\rangle$ as described
in [42].

The procedure so far involved repeated measurements where the transmon was
reset to $|0\rangle$ state by waiting $35~{}\mu$s to reach thermal equilibrium
(at a decay rate of $250$ kHz). We used an active reset protocol described in
[39] to increase the experiment cycle time. This involved a reset pulse to
transfer the $|2\rangle$ state population to the readout resonator and let it
decay much faster (at a decay rate of $4$ MHz). An $R^{12}_{y}(\pi)$ pulse is
then used to transfer the unwanted $|1\rangle$ state population to the
$|2\rangle$ state, and the reset pulse was used again to transfer $|2\rangle$
state population to the readout resonator. The $R^{12}_{y}(\pi)$ ($40$ ns),
reset pulse ($370$ ns), and a wait time ($50$ ns) for the readout resonator to
decay were used four times in series to ensure the transmon is in the ground
state, taking $1.84$ us in total. The reset protocol was tested using standard
acquisition methods and the CNN to ensure the CNN was performing as intended.
The reset time, the preparation pulses for the protocol and the measurement
pulse time amounted to $3.2$ us, corresponding to a rate of $312.5$ kHz.

To ensure robust generation of $100$ Gbit of random numbers, the procedure
outlined in Algorithm 2 was followed, involving intermittent checks of the CNN
without reset, retraining the CNN if necessary and re-calibrating the transmon
as shown in Algorithm 1 if that fails.

Algorithm 1 Calibration

1:procedure Calibrate$\triangleright$ Calibrates the transmon preparation and
readout

2: $T_{\text{rep}}\leftarrow 40~{}\mu$s

3: set measurement frequency to $f_{r}$

4: set previously calibrated settings

5: Ramsey frequency calibration for $f_{01}$

6: Calibrate $R^{01}_{y}(\pi)$ and $R^{01}_{y}(\pi/2)$ pulses

7: Ramsey frequency calibration for $f_{12}$

8: Calibrate $R^{12}_{y}(\pi)$ and $R^{12}_{y}(\pi/2)$ pulses

9: Calibrate reset pulse frequency

10: set measurement frequency to $f_{r}-9$ MHz

11: Create convolutional neural network (CNN)

12: Train CNN for 50 training cycles

13:end procedure

Algorithm 2 Generation

1:procedure RunIndex

2: if files exist then

3: $r\leftarrow 1+$ last random_xxx.rbf file number

4: else

5: return $r\leftarrow 0$

6: end if

7: return $r$

8:end procedure

9:$T_{\text{rep}}\leftarrow 40~{}\mu$s

10:Prepare $|0\rangle$,$|1\rangle$ and $|2\rangle$ $\triangleright$ Cyclically
for each repetition

11:Create convolutional neural network (CNN)

12:Train CNN for 50 training cycles

13:$f\leftarrow$ measurement accuracy

14:$\triangleright$ Assignment fidelity as defined in [42]

15:$c\leftarrow 0$ $\triangleright$ Calibration counter used to terminate

16:$l\leftarrow 0$ $\triangleright$ Low $f$ counter used to calibrate

17:$r\leftarrow$RunIndex

18:while r < 750 do

19: while $f<0.86$ do

20: if $l>20$ then

21: if $c>5$ then

22: ERROR$\triangleright$ Calibrated 5 times already. Failed

23: end if

24: Calibrate

25: $c\leftarrow c+1$

26: $l\leftarrow 0$

27: end if

28: $l\leftarrow l+1$

29: Train CNN for 20 more training cycles

30: $f\leftarrow$ measurement accuracy

31: end while

32: $T_{\text{rep}}\leftarrow 3.2~{}\mu$s

33: Program protocol pulses

34: Measure $2^{26}$ repetitions

35: Store measurements in random_$r$.rbf

36: $T_{\text{rep}}\leftarrow 40~{}\mu$s

37:end while

38:On Error Log error and restart

The errors of our protocol consisted of the initialisation errors, the errors
of the control pulses, and the measurement errors. As the initialisation and
control errors were calibrated to be kept within $<1\%$, the measurement error
was the dominant error of our protocol due to the relaxation of the higher
excited states of the qutrit to the lower energy states during the readout
time. The typical assignment fidelities were $95\%$, $88\%$, and $78\%$ for
the ground, first and second excited states, respectively. All the fidelities
were continuously monitored during random number generation, and a drop in the
value of the average assignment fidelity was used to trigger the re-
calibration of the protocol (see Algorithm 2).

##  4 Testing

In this section, we present an empirical method to show the incomputability of
the outputs generated in Section 3.

###  4.1 Why do we need testing?

Why should we be interested in answering the above question? After all,
incomputability is established by mathematical proof, so why would we need
experimental corroboration, a weaker argument? An example is a random number
generator certified (by a mathematical proof) always to produce an
incomputable infinite sequence of random bits. Indeed, the mathematical proof
certifying incomputability is part of a mathematical model which uses certain
physical assumptions; its veracity rests on those assumptions. The fact that
each individual assumption is reasonable does not automatically guarantee that
globally, the set of assumptions is also reasonable. Experimental testing is
essential not only for corroborating the conclusion of the proof but also for
supporting the adequacy of the model. Furthermore, thorough testing allows one
to detect any issues with assumptions made in the theoretical analysis of a
device or its practical deployment.

Can we test incomputability with a statistical test, that is, with a method of
statistical inference to decide whether the data at hand sufficiently supports
a particular hypothesis? The answer is negative. Intuitively, this is a
consequence of the “asymptotic” nature of the notion of computability and its
negation: finite variations do not change them. For example, if the sequence
$x_{1}x_{2}\dots x_{n}\dots$ is computable (incomputable), then the sequences
$y_{1}y_{2}\dots y_{m}x_{1}x_{2}\dots x_{n}\dots$ and $x_{k}x_{k+1}\dots
x_{m}\dots$ are also computable (incomputable) for every string
$y_{1}y_{2}\dots y_{m}$ and positive integer $k$. For example, the
Champernowne binary sequence [15]

$0,1,00,01,10,11,000,\dots$

obtained by concatenating all binary strings in shortlex order.111Strings are
first sorted by increasing length, and strings of the same length are sorted
into lexicographical order: $0,1;00,01,10,11;000,001,\dots 111;\dots$ This
sequence is computable and normal, i.e. its digits are uniformly distributed:
all digits are equally likely, all pairs of digits are equally likely, all
triplets of digits are equally likely, and so on. Normality is a “symptom” of
randomness, and computability is a “symptom” of non-randomness. The
Champernown sequence shows that these symptoms can be compatible; no
statistical test can detect its computability, hence non-randomness.

Does this mean that incomputability cannot be “experimentally tested”? Of
course, no. In what follows, we will describe such a test used in assessing
the quality of outputs of quantum random generators, [12, 2].

###  4.2 Theory

We continue with a topic apparently unrelated to the question discussed in
this section: testing of primality of positive integers. Primality is
considered computationally easy because there exist polynomial algorithms in
the size of the input to solve it; the first such algorithm was proposed in
2004 [6]. However, every known primality polynomial algorithm is “practically
slow”, so probabilistic algorithms222Currently the best runs in time O$((\log\
n)^{6})$. are instead used [51].333In contrast, factorisation of positive
integers is “thought”, but not proved, to be a computationally difficult
problem. Currently, one cannot factorise a positive integer of 500 decimal
digits that is the product of two randomly chosen prime numbers. This fact is
exploited in the RSA cryptosystem implementing public-key cryptography [47].

The practical failure of polynomial primality tests motivated the search for
probabilistic algorithms for primality [40, 45, 48, 49, 51, 51]. To test the
primality of a positive integer $n$, the Solovay-Strassen primality test
generates the first $k$ natural numbers uniformly distributed between $1$ and
$n-1$, inclusive, and, for each $i\in\\{i_{1},\dots,i_{k}\\}$ checks “quickly”
the validity of a predicate $W(i,n)$ based on Euler’s criterion (called the
Solovay-Strassen predicate). If $W(i,n)$ is true then “$i$ is a witness of
$n$’s compositeness”; hence $n$ is certainly not prime. Otherwise, the test is
inconclusive. In this case, the probability that $n$ is prime is greater than
$1-2^{-k}$. This result is based on the fact that at least half the $i$’s
between $1$ and $n-1$ satisfy $W(i,n)$ if $n$ is composite, and _none_ of them
satisfy $W(i,n)$ if $n$ is prime [50].

In detail, we first define the Solovay-Strassen predicate $W(i,n)$ by

$\left(\frac{i}{n}\right)i^{(n-1)/2}\not\equiv 1\mod{n},$

where $\left(\frac{i}{n}\right)$ is the Jacobi symbol444If the prime
factorisation of the odd number $n$ is $p_{1}^{a_{1}}p_{2}^{a_{2}}\dots
p_{k}^{a_{k}}$, then
$\left(\frac{i}{n}\right)=\left(\frac{i}{p_{1}}\right)^{a_{1}}\left(\frac{i}{p_{2}}\right)^{a_{2}}\dots\left(\frac{i}{p_{k}}\right)^{a_{k}}$.
with $i\in\mathbb{N},i<n-1$.

If $i\geq 2$ and $W(i,n)$ is true, we say that $i$ is an _Euler witness
(E-witness)_. If $n>3$ is an odd composite, and $W(i,n)$ is false for $i\geq
1$, we say $n$ is an _Euler_ pseudo-prime for the base $i$ or that $i$ is an
_Euler liar (E-liar)_ for the Solovay-Strassen primality test. In particular,
the set $L_{ss}(n)$ of _E-liars_ has at most $\frac{\phi(n)}{2}$ elements.
Thus, the probability of sampling an _E-liar_ when performing the Solovay
Strassen test is given by $\beta_{n}=|L_{ss}(n)|/(n-1)$

The size of $L_{ss}(n)$ varies for different odd composite numbers. Consider
the Carmichael numbers, that is, composite positive integers $n$ satisfying
the congruence $b^{n-1}\equiv 1\pmod{n}$ for all integers $b$ relatively prime
to $n$. The largest $\beta_{n}$ is found in a subset of Carmichael numbers
with $\beta_{n}=\frac{1}{2}$. A Carmichael number passes a Fermat primality
test [18, Section 31.8] to every base relatively prime to the number, but few
of them pass the Solovay-Strassen test. Increasingly Carmichael numbers become
“rare”.555There are 1,401,644 Carmichael numbers in the interval
$[1,10^{18}]$.

Consider $s=s_{0}\dots s_{m-1}$ a binary string (of length $m$) and $n$ an
integer greater than 2. Let $k$ be the smallest integer such that
$(n-1)^{k+1}>2^{m}-1$; we can thus rewrite the number whose binary
representation is $s$ into base $n-1$ and obtain the unique string
$d_{k}d_{k-1}\dots d_{0}$ over the alphabet $\\{0,1,\dots,n-2\\}$, that is,

$\sum_{i=0}^{k}d_{i}(n-1)^{i}=\sum_{t=0}^{m-1}s_{t}2^{t}.$

The predicate $Z(s,n)$ is defined by

$Z(s,n)=\neg W(1+d_{0},n)\wedge\dots\wedge\neg W(1+d_{k-1},n),$ (4)

where $W$ is the Solovay-Strassen predicate.

The digits of $s$ (rewritten in base $n-1$) are used to define the Solovay
Strassen predicates. If $n$ is a pseudo-prime for all the bases from $s$ used
to construct these predicates, we say that $s$ is a $Z-liar$.

A string $s$ is $c$-random if $K(s)\geq|s|-c$; $|s|$ is the string length and
$K$ is the Kolmogorov complexity [11].

> Chaitin-Schwartz Theorem. [14] For all sufficiently large $c$, if $s$ is a
> $c$-random string of length $(l+2c)$ and $n$ is an integer whose binary
> representation is $l$ bits long, then $Z(s,n)$ is true if and only if $n$ is
> prime.

This result cannot be used to de-randomise666That is, to transform the
probabilistic algorithm into an equivalent deterministic algorithm. Solovay-
Strassen probabilistic algorithm because the set of $c$-random strings is
incomputable.777In fact, highly incomputable [11]: no infinite set of
$c$-random is computable.  However, the result can be used to model strings
from different random number generators to test the quality of long binary
strings by comparing their behaviour. In particular, we look at the number of
_Z-liars_ found by each generator.

###  4.3 Experimental analysis

Standard statistical tests of randomness focus on properties of the
distribution of bits or bit strings within sequences, failing to distinguish
between pseudo-random number generators and quantum random number generators.
To address this issue, in [2], the ability of random strings to de-randomise
the Solovay-Strassen probabilistic test of primality was used to compare the
algorithmic randomness of strings generated by a QRNG and those produced by
different PRNGs. Despite leading to mostly inconclusive results, the tests
conducted showed some advantages offered by a 3D-QRNG against PRNGs with
respect to the randomness of its outputs.

The following test, called the fourth Chaitin-Schwartz-Solovay-Strassen test
(CSS4) in [2], showed the highest potential for distinguishing between sources
of random strings. Recall that the crucial fact is that the set of $c$-random
strings is (highly) incomputable.

We construct the Chaitin-Schwartz predicate $Z(s,n)$ from (4) and generate a
pool of Solovay-Strassen predicates composed of the digits $s$ in base $n-1$.
Then, we fix $c=l-1$ where $l$ is the $l$-bit binary representation of $n$ and
sample $s$ from chunks of $l(l+2c)$ bits in order to look for _Z-liars_
generated by a set of bases for the predicates extracted from the string $s$.

In [2], Carmichael numbers were used in the majority of the tests. However,
despite Carmichael numbers having a larger $L_{ss}(n)$, it is difficult to
find _Z-liars_ due to the length of their binary representation. For example,
for the smallest Carmichael number more than $70\times 2^{32}$ bits would need
to be read to find a _Z-liar_ since the Solovay-Strassen test guarantees a
predicate is true with a probability of at least one-half when $n$ is a
composite number. For smaller numbers we expect see to a larger number of _Z-
liars_. Thus, for this test, only odd composite numbers less than 50 were used
for each round, and the process was repeatedly parsed through each string with
an incremental bit offset.

Recently in [30], a similar approach was taken by applying these tests to a
different set of PRNGs and two different QRNGs with a larger set of numbers;
each string tested had a length of $2^{26}$. Once again, the QRNGs showed no
clear advantage over the PRNGs. Moreover, the difficulty of finding _Z-liars_
led to a similar limitation in terms of numbers tested; _Z-liars_ were only
observed for composites $n\leq 25$. Still, an essential characteristic of this
test was confirmed: its sensitivity to the size of the pool of unique bases
extracted from the random strings. No _Z-liars_ were recorded when a
repetitive structure generated by their sampling process was present. For this
reason, we have a variation of this test was performed.

We tested two PRNGs and a QRNG: the Python3 Mersenne Twister-based generator,
the hashing function SHA3, considered a “cryptographically secure PRNG” and
the 3D-QRNG described in this paper.

Since the number of Solovay-Strassen tests increases with longer binary
representations, the probability of observing a _Z-liar_ becomes smaller, so a
large pool of unique bases was required to detect a significant number of _Z-
liars_ [2]. Thus, we prepared ten sets of strings of size $2^{32}$ for each
generator and applied the shifting process described in [2] for the test. The
average number of _Z-liars_ over the composite numbers less than 50 was taken
as the metric. Despite only detecting _Z-liars_ for composites up to 25, there
was a noticeable difference between sources for the numbers 9 and 15. For
these numbers, from our predicate construction, we have that a minimum of
$40\times 2^{13}$ bits and $40\times 2^{10}$ bits are needed for a $c$-random
string to have a chance of finding a _Z-liar_.

Composite number tested | 9 | 15 | 21 | 25 | 27 | 33 | 35 | 39 | 45 | 49
---|---|---|---|---|---|---|---|---|---|---
sha3 | 265.6 | 60.3 | 0 | 0.2 | 0 | 0 | 0 | 0 | 0 | 0
python3 | 260.1 | 58 | 0 | 0.3 | 0 | 0 | 0 | 0 | 0 | 0
qutrits | 536.4 | 131.9 | 0 | 0.2 | 0 | 0 | 0 | 0 | 0 | 0

Table 1: Average number of _Z-liars_ sampled by composite number tested (over
10 strings of length $2^{32}$) Figure 3: Fourth Chaitin-Schwartz-Solovay-
Strassen test: distribution of the average _Z-liar_ counts for all odd
composite numbers less than 50

The occurrence of patterns in long enough sequences of random events is
inevitable. Since a lower quality of randomness increases the rate at which
this occurs, the gap between the number of unique bases extractable between
RNGs with different qualities of randomness widens. Thus, given long enough
strings, we can observe this behaviour. Since many unique bases are required
to increase the likelihood of finding _Z-liars_ , from Figure 1, we see the
advantage offered by a 3D-QRNG generator over other alternative sources of
randomness.

In order to analyse the statistical significance of these results, we
conducted the non-parametric and distribution-free two-sample
Kolmogorov–Smirnov test. This test identifies if two datasets differ
significantly without any prior assumption about an underlying distribution.
To this end, we say that the difference between two datasets is statistically
significant if the $p$-value obtained through this test is less than 0.005.
This critical $p$-value is chosen to reduce the chance of false positives as
well as allow us to provide a direct comparison with results from [2].

| sha3 | qutrits
---|---|---
python3 | 0.9780 | 0.0047
sha3 |  | 0.0047
Table 2: Kolmogorov-Smirnov test $p$-values for the fourth Chaitin-Schwartz-
Solovay-Strassen test with the Z-liar count metric

We note that there is a significant difference between the 3D-QRNG qutrits and
the PRNGs. A similar behaviour was revealed in [2], where despite the non-
conclusive results of the fourth Chaitin-Schwartz-Solovay-Strassen test, the
Kolmogorov-Smirnoff test showed that the difference between a 3D-QRNG and the
other PRNGs is statistically relevant. The outcomes of the fourth Chaitin-
Schwartz-Solovay-Strassen test presented here show a stronger advantage of
3D-QRNGs over PRNGs.

##  5 Conclusions

This article uses a located form of the Kochen-Specker Theorem to derive a
physical realisation of a class of 3D-QRNGs by means of a superconducting
transmon. The sequences produced by these 3D-QRNGs are strongly incomputable,
a property that no other QRNG provides to date. Furthermore, we have used a
non-statistical randomness test to probe experimentally the incomputability of
its generated long strings: for the first time, a provable advantage over the
best PRNGs was found. This result has been achieved by using the Chaitin-
Schwartz Theorem to probe the “usefulness” of generated quantum random bits, a
form of Einstein’s justification.

These results highlight the real effects of incomputability in quantum systems
and complement the theoretical certification via value indefiniteness of the
class of QRNGs implemented. Furthermore, the experimental results confirm and
complement incomputability and, quite significantly, the choice of physical
assumptions in the theoretical part.

Finally, there is a strong motivation for developing alternative tests capable
of probing at algorithmic properties of randomness that better suit a wide
range of applications where the quality of randomness needs to be assessed
quickly or dynamically.

## References

  * [1] A. A. Abbott, C. S. Calude, J. Conder, and K. Svozil.  Strong Kochen-Specker theorem and incomputability of quantum randomness.  Physical Review A, 86(062109), Dec 2012.
  * [2] A. A. Abbott, C. S. Calude, M. J. Dinneen, and N. Huang.  Experimentally probing the algorithmic randomness and incomputability of quantum randomness.  Physica Scripta, 94:045103, 2019.
  * [3] A. A. Abbott, C. S. Calude, and K. Svozil.  Value-indefinite observables are almost everywhere.  Physical Review A, 89(032109), 2013.
  * [4] A. A. Abbott, C. S. Calude, and K. Svozil.  A quantum random number generator certified by value indefiniteness.  Mathematical Structures in Computer Science, 24:e240303, 6 2014\.
  * [5] A. A. Abbott, C. S. Calude, and K. Svozil.  A non-probabilistic model of relativised predictability in physics.  Information, 6(4):773–789, 2015.
  * [6] M. Agrawal, N. Kayal, and N. Saxena.  Primes is in P.  Annals of Mathematics, 160:781–793, 2004.
  * [7] J. M. Agüero Trejo and C. S. Calude.  A new quantum random number generator certified by value indefiniteness.  Theoretical Computer Science, 862:3–13, Mar. 2021.
  * [8] J. Bausch, T. S. Cubitt, A. Lucia, and D. Perez-Garcia.  Undecidability of the spectral gap in one dimension.  Phys. Rev. X, 10:031038, Aug 2020.
  * [9] L. Bienvenu, A. R. Day, and R. Hölzl.  From bi-immunity to absolute undecidability.  J. Symbolic Logic, 78(4):1218–1228, 12 2013.
  * [10] P. W. Bridgman.  A physicist’s second reaction to Mengenlehre.  Scripta Mathematica, 2:101–117, 224–234, 1934.
  * [11] C. Calude.  Information and Randomness—An Algorithmic Perspective.  Springer, Berlin, 2002 (2nd ed.).
  * [12] C. S. Calude, M. J. Dinneen, M. Dumitrescu, and K. Svozil.  Experimental evidence of quantum randomness incomputability.  Physical Review A, 82, 022102:1–8, 2010.
  * [13] C. S. Calude and K. Svozil.  Quantum randomness and value indefiniteness.  Advanced Science Letters, 1(2):165–168, 2008.  eprint arXiv:quant-ph/0611029.
  * [14] G. J. Chaitin and J. T. Schwartz.  A note on Monte Carlo primality tests and algorithmic information theory.  Communications on Pure and Applied Mathematics, 31(4):521–527, 1978\.
  * [15] D. G. Champernowne.  The construction of decimals normal in the scale of ten.  The Journal of London Mathematical Society, 8:254–260, 1933.
  * [16] W. R. Clements, P. C. Humphreys, B. J. Metcalf, W. S. Kolthammer, and I. A. Walmsley.  Optimal design for universal multiport interferometers.  Optica, 3(12):1460–1465, Dec 2016.
  * [17] B. S. Cooper and P. Odifreddi.  Incomputability in nature.  In S. B. Cooper and S. S. Goncharov, editors, Computability and Models: Perspectives East and West, pages 137–160. Plenum Press, New York, 2003\.
  * [18] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein.  Introduction to Algorithms.  The MIT Press, 3rd edition edition, 2009.
  * [19] J. F. Costa.  Incomputability at the foundations of physics (A study in the philosophy of science).  Journal of Logic and Computation, 23(6):1225–1248, 2013.
  * [20] T. S. Cubitt, D. Perez-Garcia, and M. M. Wolf.  Undecidability of the spectral gap.  Nature, 528(7581):207–211, 2015.
  * [21] N. C. A. da Costa and F. A. Doria.  Undecidability and incompleteness in classical mechanics.  International Journal of Theoretical Physics, 30:1041–1073, Aug. 1991.
  * [22] F. Diacu.  The solution of the n-body problem.  The Mathematical Intelligencer, 18(3):66–70, 1996.
  * [23] A. Einstein.  Physics and reality.  Journal of the Franklin Institute, 221(3):349–382, 1936.
  * [24] A. Einstein, B. Podolsky, and N. Rosen.  Can quantum-mechanical description of physical reality be considered complete?  Physical Review, 47(10):777–780, May 1935.
  * [25] P. Frank.  Das Kausalgesetz und seine Grenzen.  Springer, Vienna, 1932.
  * [26] P. Frank and R. S. Cohen (Editor).  The Law of Causality and its Limits (Vienna Circle Collection).  Springer, Vienna, 1997.
  * [27] N. Gisin.  Indeterminism in physics and intuitionistic mathematics.  Synthese, 199(13345–13371), 2021.
  * [28] H. Hertz.  The principles of mechanics presented in a new form.  MacMillan and Co., Ltd., London and New York, 1899.  with a foreword by H. von Helmholtz, translated by D. E. Jones and J. T. Walley.
  * [29] I. Kanter.  Undecidability principle and the uncertainty principle even for classical systems.  Physical Review Letters, 64:332–335, 1990.
  * [30] J. T. Kavulich, B. P. Van Deren, and M. Schlosshauer.  Searching for evidence of algorithmic randomness and incomputability in the output of quantum random number generators.  Physics Letters A, page 127032, 2020.
  * [31] J. Koch, T. M. Yu, J. Gambetta, A. A. Houck, D. I. Schuster, J. Majer, A. Blais, M. H. Devoret, S. M. Girvin, and R. J. Schoelkopf.  Charge-insensitive qubit design derived from the cooper pair box.  Phys. Rev. A, 76:042319, Oct 2007.
  * [32] S. B. Kochen and E. Specker.  The problem of hidden variables in quantum mechanics.  Journal of Mathematics and Mechanics, 17:59–87, 1967.  Reprinted in E. Specker. Selecta. Brikhäuser Verlag, Basel, 1990\.
  * [33] G. Kreisel.  A notion of mechanistic theory.  Synthese, 29:11–26, 1974.
  * [34] A. Kulikov, M. Jerger, A. Potočnik, A. Wallraff, and A. Fedorov.  Realization of a quantum random generator certified with the Kochen-Specker theorem.  Phys. Rev. Lett., 119:240501, Dec 2017.
  * [35] S. Lloyd.  Uncomputability and physical law.  In S. B. Cooper and M. I. Soskova, editors, The Incomputable: Journeys Beyond the Turing Barrier, Theory and Applications of Computability, pages 95–104. Springer International Publishing, 2017.
  * [36] F. London and E. Bauer.  La theorie de l’observation en mécanique quantique; No. 775 of Actualités scientifiques et industrielles: Exposés de physique générale, publiés sous la direction de Paul Langevin.  Hermann, Paris, 1939.  English translation in [37].
  * [37] F. London and E. Bauer.  The theory of observation in quantum mechanics.  In J. A. Wheeler and W. H. Zurek, editors, Quantum Theory and Measurement, pages 217–259. Princeton University Press, Princeton, NJ, 1983\.  consolidated translation of French original [36].
  * [38] G. Longo.  Incomputability in physics.  In F. Ferreira, B. Löwe, E. Mayordomo, and L. Mendes Gomes, editors, Programs, Proofs, Processes, pages 276–285, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg.
  * [39] P. Magnard, P. Kurpiers, B. Royer, T. Walter, J.-C. Besse, S. Gasparinetti, M. Pechal, J. Heinsoo, S. Storz, A. Blais, and A. Wallraff.  Fast and unconditional all-microwave reset of a superconducting qubit.  Phys. Rev. Lett., 121:060502, Aug 2018.
  * [40] G. Miller.  Riemann’s hypothesis and tests for primality.  J. Comp. Syst. Sci., 13:300–317, 1976.
  * [41] C. D. Moore.  Unpredictability and undecidability in dynamical systems.  Physical Review Letters, 64:2354–2357, 1990.  Cf. Ch. Bennett, Nature, 346, 606 (1990).
  * [42] R. Navarathna, T. Jones, T. Moghaddam, A. Kulikov, R. Beriwal, M. Jerger, P. Pakkiam, and A. Fedorov.  Neural networks for on-the-fly single-shot state classification.  Applied Physics Letters, 119(11):114003, Sept. 2021.
  * [43] H. Poincaré.  Wissenschaft und Hypothese.  Teubner, Leipzig, 1914.
  * [44] M. B. Pour-El and J. I. Richards.  Computability in Analysis and Physics.  Springer, Berlin, 1989.
  * [45] M. O. Rabin.  Probabilistic algorithm for testing primality.  J. Number Th., 12,:128–138, 1980.
  * [46] M. Reck, A. Zeilinger, H. J. Bernstein, and P. Bertani.  Experimental realization of any discrete unitary operator.  Physical Review Letters, 73:58–61, 1994.
  * [47] H. Riesel.  Prime Numbers and Computer Methods for Factorization, chapter Classical Methods of Factorization, pages 141–172.  Birkhäuser Boston, Boston, MA, 2012.
  * [48] R. Solovay and V. Strassen.  A fast Monte-Carlo test for primality.  SIAM Journal on Computing, 6(1):84–85, 1977.
  * [49] R. Solovay and V. Strassen.  Erratum: A fast Monte-Carlo test for primality.  SIAM Journal on Computing, 7(1):118, 1978.
  * [50] R. M. Solovay.  On random r.e. sets.  In A. I. Arruda, N. C. A. da Costa, and R. Chuaqui, editors, Non-Classical Logics, Model Theory, and Computability, pages 283–307. North-Holland, Amsterdam, 1977.
  * [51] A. Stiglic.  Encyclopedia of Cryptography and Security, chapter Probabilistic Primality Test, pages 980–980.  Springer US, Boston, MA, 2011.
  * [52] K. F. Sundman.  Memoire sur le problème de trois corps.  Acta Mathematica, 36:105–179, 1912.
  * [53] P. Suppes.  The transcendental character of determinism.  Midwest Studies In Philosophy, 18(1):242–257, 1993.
  * [54] K. Svozil.  The quantum coin toss – testing microphysical undecidability.  Physics Letters A, 143:433–437, 1990.
  * [55] K. Svozil.  Randomness & Undecidability in Physics.  World Scientific, Singapore, 1993.
  * [56] K. Svozil.  Omega and the time evolution of the n-body problem.  In C. S. Calude, editor, Randomness and Complexity, from Leibniz to Chaitin, pages 231–236, Singapore, 2007. World Scientific.  eprint arXiv:physics/0703031.
  * [57] K. Svozil.  Physical (A)Causality, volume 192 of Fundamental Theories of Physics.  Springer International Publishing, Cham, Heidelberg, New York, Dordrecht, London, 2018.
  * [58] Q. D. Wang.  The global solution of the $n$-body problem.  Celestial Mechanics, 50:73–88, 1991.
  * [59] Q. D. Wang.  Power series solutions and integral manifold of the n-body problem.  Regular & Chaotic Dynamics, 6(4):433–442, 2001.
  * [60] C. Weierstrass, C. Hermite, and G. Mittag-Leffler.  Mittheilung, einen von König Oscar II gestifteten mathematischen Preis betreffend. Communication sur un prix de mathématiques fondé par le roi Oscar II.  Acta Mathematica, 7(1):I–VI, 1885.
  * [61] S. Wolfram.  Undecidability and intractability in theoretical physics.  Physical Review Letters, 54(8):735–738, Feb 1985.
  * [62] B. Yurke, S. L. McCall, and J. R. Klauder.  SU(2) and SU(1,1) interferometers.  Physical Review A, 33:4033–4054, 1986.
  * [63] A. Zeilinger.  A foundational principle for quantum mechanics.  Foundations of Physics, 29(4):631–643, 1999.
  * [64] H. Zenil, editor.  Computable Universe: Understanding and Exploring Nature as Computation.  World Scientific, Singapore, 2013.