CDMTCS Research Reports (1995+)
Permanent URI for this collectionhttps://hdl.handle.net/2292/3508
Centre for Discrete Mathematics and Theoretical Computer Science
Copyright Statement: The digital copies of reports in this collection are protected by the Copyright Act 1994 (New Zealand). They may be consulted by you, provided you comply with the provisions of the Act.
Browse
Recent Submissions
Item Binary Quantum Random Number Generator Based on Value Indefinite Observables(Department of Computer Science, The University of Auckland, New Zealand, 2023) Calude, CS; Svozil, KAll quantum random number generators based on measuring value indefinite observables are at least three-dimensional because the Kochen-Specker Theorem and the Located Kochen-Specker Theorem are false in dimension two. In this article, we construct a quantum random number generator based on measuring a three-dimensional value indefinite observable that generates binary quantum random outputs with the same randomness qualities as the ternary ones: its outputs are maximally unpredictable.Item Philosophical Mathematics. Infinity, Incompleteness, Irreducibility(Department of Computer Science, The University of Auckland, New Zealand, 2023) Chaitin, GItem Quantum Annealing for Computer Vision Minimization Problems(Department of Computer Science, The University of Auckland, New Zealand, 2023) Heidari, S; Dinneen, MJ; Delmas, PComputer Vision (CV) labeling problems play a pivotal role in low-level vision. For decades, it has been known that these problems can be elegantly formulated as discrete energy-minimization problems derived from probabilistic graphical models such as Markov Random Fields (MRFs). Despite recent advances in MRF inference algorithms (such as graph-cut and message-passing methods), the resulting energy-minimization problems are generally viewed as intractable. The emergence of quantum computations, which offer the potential for faster solutions to certain problems than classical methods, has led to an increased interest in utilizing quantum properties to overcome intractable problems. Recently, there has also been a growing interest in Quantum Computer Vision (QCV), hoping to provide a credible alternative/assistant to deep learning solutions. This study investigates a new Quantum Annealing-based inference algorithm for CV discrete energy minimization problems. Our contribution is focused on Stereo Matching as a significant CV labeling problem. As a proof of concept, we also use a hybrid quantum-classical solver provided by D-Wave System to compare our results with the best classical inference algorithms in the literature. Our results show that Quantum Annealing can yield promising results for Stereo Matching problems, with improved accuracy on certain stereo images and competitive performance on others.Item How Real is Incomputability in Physics?(Department of Computer Science, The University of Auckland, New Zealand, 2023) Aguero, JM; Calude, CS; Dinneen, MJ; Fedorov, A; Kulikov, A; Navarathna, R; Svozil, KA 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 law 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.Item There are Forty Nine KURATOWSKI Lattices in CANTOR Space(Department of Computer Science, The University of Auckland, New Zealand, 2023) Staiger, L; Wagner, KWKuratowski observed that, starting from a subset M of a topological space and applying the closure operator and the interior operator arbitrarily often, one can generate at most seven different sets. We show that there are forty nine different types of sets w.r.t. the inclusion relations between the seven generated sets. All these types really occur in Cantor space, even for subsets defined by finite automata. For a given type, it is NL-complete to decide whether a set M, accepted by a given finite automaton, is of this type. In the topological space of real numbers only 39 of the 49 types really occur.Item Does a Computer Think if No One Is Around to See It?(Department of Computer Science, The University of Auckland, New Zealand, 2023) Stoica, OCI show that a computer cannot have unambiguous thoughts, not even about a number. What we believe computers do is our own convention. It may seem objective because we anchor it in the user interface. But many other conventions are possible, and they yield different computations, equally valid according to the principles of Computer Science. I prove that the alternative computations equally happen when a single computation is carried out, and in principle they can be accessed. I exemplify this with a program that computes the result for a given input, and then decodes it into the results for all other possible inputs. If thinking would be a computation, a computer would have different, possibly opposite thoughts, corresponding to many alternative computations it implements at the same time. I show probabilistically that the human mind does not have this ambiguity. Therefore, even if the human mind can be simulated by a computer, it cannot be reduced to computation.Item Construire l'univers a partir de l'information et du calcul(Department of Computer Science, The University of Auckland, New Zealand, 2023) Chaitin, GJWeaving together mathematics, epistemology and autobiography, this book begins with a tribute to Leibniz and a guide to Greg’s favorite books, then presents Greg’s three favorite lecture transcripts, and last but not least tells the story of Greg’s unconventional life and research trajectory and ponders the mystery of creativity. Seventy pages, mostly in English, with a foreword and a brief introduction in French intended for a Moroccan audience. The material in French was kindly provided by Réda Benkirane, a professor at UM6P, and author of the book La Complexité, vertiges et promesses. Cover illustration by Sophie Lenormand based on Greg’s talk at UM6P in Chapter 3.Item ChatGPT, Randomness and the Infinity(Department of Computer Science, The University of Auckland, New Zealand, 2023) Calude, CSChatGPT, an application first released in November 2022 by Abacus. AI, has become very popular instantaneously and still dominates AI discussions in media and technical circles. In this paper, we briefly discuss the merits and shortcomings of ChatGPT, the role of randomness in its capacity for diversification and a “dialogue” about infinity. We end with a few questions.Item Efficient Clique Embedding with Faulty Hardware Components(Department of Computer Science, The University of Auckland, New Zealand, 2022) Dinneen, MJ; Hua, RIn this paper, we investigate graph embeddings of large cliques into the existing D-Wave quantum architectures (Chimera, Pegasus) when physical qubits or couplers have faults. The motivation for pre-computing large clique embeddings allows for easier embeddings (without extensive classical computation) of arbitrary logical qubit interaction graphs (e.g. QUBO graphs) when performing quantum annealing on the restricted topologies of the existing D-Wave quantum architectures. To investigate the performance and scalability of existing hardware topology (Pegasus graph), we propose a method for simulating large hardware graphs with random faulty compo- nents and compare the performance of di erent embedding techniques on these graphs.Item An Equivalent QUBO Model to the Minimum Multi-Way Cut Problem(Department of Computer Science, The University of Auckland, New Zealand, 2022) Heidari, S; Dinneen, MJ; Delmas, PMotivated by an application in Computer Vision, we present an e cient QUBO solution for the minimum multi-way cut problem. For an edge-weighted input graph G = (V;E) and a set of terminals T = ft1; t2; : : : ; tkg V we want to nd a subset of edges Ec of minimum total cost such that G0 = G n Ec separates T. QUBO rep- resentations are useful for solving problems on an adiabatic quantum computer like those produced by D-Wave Systems. Our reduction from the multi-way cut problem requires only O(kjV j) binary variables/qubits. The main result of this paper is a proof of correctness of this model. Furthermore, our reduction is small enough to be able to empirically test it with an existing D-Wave hybrid quantum-classical solver, which is illustrated at the end of this paper.Item Topologies for Finite Words: Compatibility with the CANTOR Topology(Department of Computer Science, The University of Auckland, New Zealand, 2022) Staiger, LInfinite words are often considered as limits of finite words. As topological methods have been proved to be useful in the theory of !-languages it seems to be providing to include finite and infinite words into one (topological) space. In most cases this results in a poor topological structure induced on the subspace of finite words. In the present paper we investigate the possibility to link topologies in the space of finite words with a topology in the space of infinite words via a natural mapping. A requirement in this linking of topologies consists in the compatibility of the topological properties (openness, closedness etc) of images with preimages and vice versa. Here we show that choosing for infinite words the natural topology of the CANTOR space and the -limit as linking mapping there are several natural topologies on the space of finite words compatible with the topology of the CANTOR space. It is interesting to observe that besides the well-known prefix topology there are at least two more whose origin is fromlanguage theory—centers and supercenters of languages. We show that several of these topologies on the space of finite words fit into a class of L-topologies and exhibit their special properties w.r.t. to the compatibility with the CANTOR topology.Item Liber Amicorum Cristian S. Calude 70(Department of Computer Science, The University of Auckland, New Zealand, 2022) Campeanu, C; Dinneen, MJ; Svozil, KItem Sublinear P system solutions to NP-complete problems(Department of Computer Science, The University of Auckland, New Zealand, 2022) Henderson, A; Nicolescu, R; Dinneen, MJcP systems have been shown to very e ciently solve many NP-complete problems, i.e. in linear time. However, these solutions have been independent of each other and have not utilised the theory of reductions. This work presents a sublinear solution to k-SAT and demonstrates that k-colouring can be reduced to k-SAT in constant time. This work demonstrates that traditional reductions are e cient in cP systems and that they can sometimes produce more e cient solutions than the previous problem-speci c solutions.Item Photonic Ternary Quantum Number Generators(Department of Computer Science, The University of Auckland, New Zealand, 2022) Aguero, JM; Calude, CSWe construct a class of 3-dimensional photonic quantum random number generators and prove that each generates maximally unpredictable digits via measurements that are robust to errors. In particular, every sequence generated is strongly incomputable; hence its quality is provable better than that of every pseudo-random sequence. We also briefly contrast 2-dimensional and 3-dimensional quantum random number generators, discuss photonic implementations and show the superiority of the latter ones. These results suggest that incomputability in physics is real and practically useful.Item A QUBO Formulation for the Tree Containment Problem(Department of Computer Science, The University of Auckland, New Zealand, 2022) Dinneen, MJ; Ghodla, PS; Linz, Sto represent the evolutionary relationships between entities such as species, languages, cancer cells, and viruses. To reconstruct and analyze phylogenetic networks, the problem of deciding whether or not a given rooted phylogenetic network embeds a given rooted phylogenetic tree is of recurring interest. This problem, formally know as Tree Containment, is NP-complete in general and polynomial-time solvable for certain classes of phylogenetic networks. In this paper, we connect ideas from quantum computing and phylogenetics to present an efficient Quadratic Unconstrained Binary Optimization formulation for Tree Containment in the general setting. For an instance (N, T ) of Tree Containment, where N is a phylogenetic network with nN vertices and T is a phylogenetic tree with nT vertices, the number of logical qubits that are required for our formulation is O(nNnT ).Item Long and Short Proofs(Department of Computer Science, The University of Auckland, New Zealand, 2022) Calude, CS; Staiger, LWe study the “gap" between the length of a theorem and the smallest length of its proof in a given formal system T. To this aim, we define and study f-short and f-long proofs in T, where f is a computable function. The results show that formalisation comes with a price tag, and a long proof does not guarantee a theorem’s non-triviality or importance. Applications to proof-assistants are briefly discussed.Item An Algorithmic Heat Engine(Department of Computer Science, The University of Auckland, New Zealand, 2022) Stay, MWe construct an algorithmic heat engine and use it to increase the average runtime of programs in a distribution.Item T is Inaccessible(Department of Computer Science, The University of Auckland, New Zealand, 2022-05) Carpenter, BEThis note advances an entirely materialistic and deterministic view of the limits of physical theories. The following sections cover: a) A demonstration that any physical theory that is accessible to human intelligence is necessarily an approximation; b) Recognition that physical theories based on probability and randomness are therefore approximations; c) A conjecture as to how the randomness and unpredictability that we observe arises from an underlying and inaccessible theory; d) A conjecture about the origin of unpredictable spontaneous quantum events such as unstable isotope decay.Item Building the World out of Information and Computation(Department of Computer Science, The University of Auckland, New Zealand, 2021) Chaitin, GAccording 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.Item What Neural Networks Are (Not) Good For?(Department of Computer Science, The University of Auckland, New Zealand, 2021) Calude, CS; Heidari, S; Sifakis, JPerceptron 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.