CDMTCS Research Reports (1995+)
https://hdl.handle.net/2292/3508
2022-05-29T11:25:18ZAn Improved Quantum Solution for the Stereo Matching Problem
https://hdl.handle.net/2292/58020
An Improved Quantum Solution for the Stereo Matching Problem
Heidari, S; Rogers, M; Delmas, P
As the most computationally intensive part of a
stereo vision system, stereo matching has been the focus of intense
research activities for the last four decades. We present the first
attempts to compare a quantum stereo matching solution with
state-of-the-art approaches on the Middlebury stereo datasets.
We first looked at quantum annealing computation as a way to
interact with the D-Wave quantum computer and then improved
the quantum solution to the stereo matching problem found in
the literature. Using a line-by-line approach, we traded accuracy
off for the qubits availability in the QPU (Quantum Processor
Unit). Our findings show that it is possible to obtain results from
real-sized images despite the scarcity of physical qubits in the
quantum hardware. While the current quantum solution solves a
class P stereo matching problem, its real advantage over classical
stereo matching algorithms will arise with NP-hard problems
which will be the focus of our future research.
2021-01-01T00:00:00ZWhat Neural Networks Are (Not) Good For?
https://hdl.handle.net/2292/58018
What Neural Networks Are (Not) Good For?
Calude, CS; Heidari, S; Sifakis, J
Perceptron Neural Networks (PNNs) are essential components of intelligent systems because they produce efficient solutions to problems of overwhelming complexity for conventional computing methods.
There are lots of papers showing that PNNs can approximate a wide variety of
functions, but comparatively very few discuss their limitations, the scope of this
paper. To this aim we define two classes of Boolean functions – sensitive and robust
–, and prove that an exponentially large set of sensitive functions are exponentially
difficult to compute by multi-layer PNNs (hence incomputable by single-layer PNNs)
and a comparatively large set of functions in the second one, but not all, are computable by single-layer PNNs.
Finally we used polynomial threshold PNNs to compute all Boolean functions
with quantum annealing and present in detail a QUBO computation on the D-Wave
Advantage.
These results confirm that the successes of PNNs, or lack of them, are in part
determined by properties of the learned data sets and suggest that sensitive functions
may not be (efficiently) computed by PNNs.
2021-01-01T00:00:00ZBuilding the World out of Information and Computation
https://hdl.handle.net/2292/58019
Building the World out of Information and Computation
Chaitin, G
According to Pythagoras: All is Number, God is a Mathematician. Modern physics is in fact based on continuous mathematics, dierential and partial
dierential equations, validating Pythagoras’ vision.
In this essay we shall instead discuss a neo-Pythagorean ontology: All is
Algorithm, God is a Programmer. In other words, can there be discrete
computational models of the physical world? This is sometimes referred to as
digital philosophy.
There are in fact two books on digital philosophy, both in Italian:
• Ugo Pagallo, Introduction to Digital Philosophy, from Leibniz to Chaitin
• Andrea Vaccaro and Giuseppe Longo, Bit Bang: The Birth of Digital
Philosophy
Let’s review the development of digital philosophy. We’ll start, as is often the
case, with Leibniz.
2021-01-01T00:00:00ZA Life in Mathematics
https://hdl.handle.net/2292/58017
A Life in Mathematics
Chaitin, G
Gregory Chaitin’s life in mathematics punctuated by some photographs taken during crucial episodes in his career.
2021-01-01T00:00:00Z