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 QUBO Formulations for Arithmetic Progression Graph Labeling Problems(Department of Computer Science, The University of Auckland, New Zealand, 2024) Calude, CS; Dinneen, MJ; Liu, YThe Arithmetic Progression Graph Labeling is an NP-complete problem with various applications, including optimizing scheduling problems. This paper presents Quadratic Unconstrained Boolean Optimization (QUBO) solutions for the version with fixed vertex labels of this problem, then the original general problem. We use and compare standard (D-Wave Advantage and Advantage 2 Prototype) and hybrid (D-Wave Leap Hybrid Solver Service) methods to solve these problems with D-Wave quantum machines. Our experiments suggest that the hybrid methods outperform the standard ones.Item Converting nonlocality into contextuality(Department of Computer Science, The University of Auckland, New Zealand, 2024) Svozil, KDiagonalization of matrix pencils provide a uniform technique to transcribe operator-valued violations of Boole’s ‘conditions of possible experience’ involving multipartite correlations into contextuality. They also provide structural analysis of the contexts involved, and thereby suggest compact forms of deviations of quantized systems from classical predictions.Item In Memory of Robert W. Doran(Department of Computer Science, The University of Auckland, New Zealand, 2024) Calude, CS; Carpenter, BE; Dinneen, MJ; Dobbie, GOur late friend and colleague Professor Robert W. Doran, usually known as “Bob”, would have been 80 years old in 2024. Apart from being a devoted teacher and, for many years, a highly respected Head of Department at the University of Auckland, he was an original and sometimes quirky thinker. Bob was one of the Computer Science pioneers in New Zealand (NZ), moving from the Mathematics Department to the newly formed Computer Science Department at Massey University in 1974. He was an inspiration to many young kiwis starting out in Computer Science over the years. After a second stint overseas he returned to NZ to the Department of Computer Science at the University of Auckland, where he is remembered by a number of staff for his kindness when they first arrived to take up a position in NZ. Bob would personally meet them and their families at the airport. Many of the people that arrived during that time, remained in NZ. This memorial starts with a summary of Bob’s professional life and publications, and then continues with various reminiscences and examples of his original approach to common questions, presented in alphabetical order of their contributors surnames.Item Randomness and One-way Functions(Department of Computer Science, The University of Auckland, New Zealand, 2024) Aguero, JM; Calude, CSThis paper proposes a method using high-quality randomness for inverting a class of one-way functions in a pre-given time. Experimental results suggest that the method is better than the lexicographic search.Item An Overseas Experience with Hypertext and Packet Switching(2024-02) Cashin, Peter; Carpenter, Brian EItem 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 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 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 ).