Source author record

Cristian S. Calude

Cristian S. Calude appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

17works
9topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

17 published item(s)

preprint2020arXiv

A New Quantum Random Number Generator Certified by Value Indefiniteness

In this paper we propose a new ternary QRNG based on measuring located value indefinite observables with probabilities $1/4, 1/2,1/4$ and prove that every sequence generated is maximally unpredictable, 3-bi-immune (a stronger form of bi-immunity), and its prefixes are Borel normal. The ternary quantum random digits produced by the QRNG are algorithmically transformed into quantum random bits using an alphabetic morphism which preserves all the above properties.

preprint2020arXiv

Von Neumann Normalisation of a Quantum Random Number Generator

In this paper we study von Neumann un-biasing normalisation for ideal and real quantum random number generators, operating on finite strings or infinite bit sequences. In the ideal cases one can obtain the desired un-biasing. This relies critically on the independence of the source, a notion we rigorously define for our model. In real cases, affected by imperfections in measurement and hardware, one cannot achieve a true un-biasing, but, if the bias "drifts sufficiently slowly", the result can be arbitrarily close to un-biasing. For infinite sequences, normalisation can both increase or decrease the (algorithmic) randomness of the generated sequences. A successful application of von Neumann normalisation---in fact, any un-biasing transformation---does exactly what it promises, un-biasing, one (among infinitely many) symptoms of randomness; it will not produce "true" randomness.

preprint2019arXiv

A Hybrid Quantum-Classical Paradigm to Mitigate Embedding Costs in Quantum Annealing

Despite rapid recent progress towards the development of quantum computers capable of providing computational advantages over classical computers, it seems likely that such computers will, initially at least, be required to run in a hybrid quantum-classical regime. This realisation has led to interest in hybrid quantum-classical algorithms allowing, for example, quantum computers to solve large problems despite having very limited numbers of qubits. Here we propose a hybrid paradigm for quantum annealers with the goal of mitigating a different limitation of such devices: the need to embed problem instances within the (often highly restricted) connectivity graph of the annealer. This embedding process can be costly to perform and may destroy any computational speedup. In order to solve many practical problems, it is moreover necessary to perform many, often related, such embeddings. We will show how, for such problems, a raw speedup that is negated by the embedding time can nonetheless be exploited to give a real speedup. As a proof-of-concept example we present an in-depth case study of a simple problem based on the maximum weight independent set problem. Although we do not observe a quantum speedup experimentally, the advantage of the hybrid approach is robustly verified, showing how a potential quantum speedup may be exploited and encouraging further efforts to apply the approach to problems of more practical interest.

preprint2015arXiv

A Non-Probabilistic Model of Relativised Predictability in Physics

Little effort has been devoted to studying generalised notions or models of (un)predictability, yet is an important concept throughout physics and plays a central role in quantum information theory, where key results rely on the supposed inherent unpredictability of measurement outcomes. In this paper we continue the programme started in [1] developing a general, non-probabilistic model of (un)predictability in physics. We present a more refined model that is capable of studying different degrees of "relativised" unpredictability. This model is based on the ability for an agent, acting via uniform, effective means, to predict correctly and reproducibly the outcome of an experiment using finite information extracted from the environment. We use this model to study further the degree of unpredictability certified by different quantum phenomena, showing that quantum complementarity guarantees a form of relativised unpredictability that is weaker than that guaranteed by Kochen-Specker-type value indefiniteness. We exemplify further the difference between certification by complementarity and value indefiniteness by showing that, unlike value indefiniteness, complementarity is compatible with the production of computable sequences of bits.

preprint2015arXiv

A variant of the Kochen-Specker theorem localising value indefiniteness

The Kochen-Specker theorem proves the inability to assign, simultaneously, noncontextual definite values to all (of a finite set of) quantum mechanical observables in a consistent manner. If one assumes that any definite values behave noncontextually, one can nonetheless only conclude that some observables (in this set) are value indefinite. In this paper we prove a variant of the Kochen-Specker theorem showing that, under the same assumption of noncontextuality, if a single one-dimensional projection observable is assigned the definite value 1, then no one-dimensional projection observable that is incompatible (i.e., non-commuting) with this one can be assigned consistently a definite value. Unlike standard proofs of the Kochen-Specker theorem, in order to localise and show the extent of value indefiniteness this result requires a constructive method of reduction between Kochen-Specker sets. If a system is prepared in a pure state $|ψ\rangle$, then it is reasonable to assume that any value assignment (i.e., hidden variable model) for this system assigns the value 1 to the observable projecting onto the one-dimensional linear subspace spanned by $|ψ\rangle$, and the value 0 to those projecting onto linear subspaces orthogonal to it. Our result can be interpreted, under this assumption, as showing that the outcome of a measurement of any other incompatible one-dimensional projection observable cannot be determined in advance, thus formalising a notion of quantum randomness.

preprint2015arXiv

On the unpredictability of individual quantum measurement outcomes

We develop a general, non-probabilistic model of prediction which is suitable for assessing the (un)predictability of individual physical events. We use this model to provide, for the first time, a rigorous proof of the unpredictability of a class of individual quantum measurement outcomes, a well-known quantum attribute postulated or claimed for a long time. We prove that quantum indeterminism - formally modelled as value indefiniteness - is incompatible with the supposition of predictability: measurements of value indefinite observables are unpredictable. The proof makes essential use of a strengthened form of the Kochen-Specker theorem proven previously to identify value indefinite observables. This form of quantum unpredictability, like the Kochen-Specker theorem, relies on three assumptions: compatibility with quantum mechanical predictions, non-contextuality, and the value definiteness of observables corresponding to the preparation basis of a quantum state. We explore the relation between unpredictability and incomputability and show that the unpredictability of individual measurements of a value indefinite quantum observable complements, and is independent of, the global strong incomputability of any sequence of outcomes of this particular quantum experiment. Finally, we discuss a real model of hypercomputation whose computational power has yet to be determined, as well as further open problems.

preprint2015arXiv

Universality and Almost Decidability

We present and study new definitions of universal and programmable universal unary functions and consider a new simplicity criterion: almost decidability of the halting set. A set of positive integers S is almost decidable if there exists a decidable and generic (i.e. a set of natural density one) set whose intersection with S is decidable. Every decidable set is almost decidable, but the converse implication is false. We prove the existence of infinitely many universal functions whose halting sets are generic (negligible, i.e. have density zero) and (not) almost decidable. One result - namely, the existence of infinitely many universal functions whose halting sets are generic (negligible) and not almost decidable - solves an open problem in [9]. We conclude with some open problems.

preprint2014arXiv

Embedding Quantum Universes into Classical Ones

Do the partial order and ortholattice operations of a quantum logic correspond to the logical implication and connectives of classical logic? Re-phrased, how far might a classical understanding of quantum mechanics be, in principle, possible? A celebrated result by Kochen and Specker answers the above question in the negative. However, this answer is just one among different possible ones, not all negative. It is our aim to discuss the above question in terms of mappings of quantum worlds into classical ones, more specifically, in terms of embeddings of quantum logics into classical logics; depending upon the type of restrictions imposed on embeddings the question may get negative or positive answers.

preprint2014arXiv

Value-indefinite observables are almost everywhere

Kochen-Specker theorems assure the breakdown of certain types of non-contextual hidden variable theories through the non-existence of global, holistic frame functions; alas they do not allow us to identify where this breakdown occurs, nor the extent of it. It was recently shown [Phys. Rev. A 86, 062109 (2012)] that this breakdown does not occur everywhere; here we show that it is maximal in that it occurs almost everywhere, and thus prove that quantum indeterminacy--often referred to as contextuality or value indefiniteness--is a global property as is often assumed. In contrast to the Kochen-Specker theorem, we only assume the weaker non-contextuality condition that any potential value assignments that may exist are locally non-contextual. Under this assumption, we prove that once a single arbitrary observable is fixed to occur with certainty, almost (i.e. with Lebesgue measure one) all remaining observables are indeterminate.

preprint2012arXiv

Is Feasibility in Physics Limited by Fantasy Alone?

Although various limits on the predicability of physical phenomena as well as on physical knowables are commonly established and accepted, we challenge their ultimate validity. More precisely, we claim that fundamental limits arise only from our limited imagination and fantasy. To illustrate this thesis we give evidence that the well-known Turing incomputability barrier can be trespassed via quantum indeterminacy. From this algorithmic viewpoint, the "fine tuning" of physical phenomena amounts to a "(re)programming" of the universe.

preprint2012arXiv

Strong Kochen-Specker theorem and incomputability of quantum randomness

The Kochen-Specker theorem shows the impossibility for a hidden variable theory to consistently assign values to certain (finite) sets of observables in a way that is non-contextual and consistent with quantum mechanics. If we require non-contextuality, the consequence is that many observables must not have pre-existing definite values. However, the Kochen-Specker theorem does not allow one to determine which observables must be value indefinite. In this paper we present an improvement on the Kochen-Specker theorem which allows one to actually locate observables which are provably value indefinite. Various technical and subtle aspects relating to this formal proof and its connection to quantum mechanics are discussed. This result is then utilized for the proposal and certification of a dichotomic quantum random number generator operating in a three-dimensional Hilbert space.

preprint2011arXiv

A Nuclear Magnetic Resonance Implementation of a Classical Deutsch-Jozsa Algorithm

Nuclear magnetic resonance (NMR) has been widely used as a demonstrative medium for showcasing the ability for quantum computations to outperform classical ones. A large number of such experiments performed have been implementations of the Deutsch-Jozsa algorithm. It is known, however, that in some cases the Deutsch-Jozsa problem can be solved classically using as many queries to the black-box as in the quantum solution. In this paper we describe experiments in which we take the contrasting approach of using NMR as a classical computing medium, treating the nuclear spin vectors classically and utilising an alternative embedding of bits into the physical medium. This allows us to determine the actual Boolean function computed by the black-box for the n=1,2 cases, as opposed to only the nature (balanced or constant) as conventional quantum algorithms do. Discussion of these experiments leads to some clarification of the complications surrounding the comparison of different quantum algorithms, particularly black-box type algorithms.

preprint2010arXiv

A Quantum Random Number Generator Certified by Value Indefiniteness

In this paper we propose a quantum random number generator (QRNG) which utilizes an entangled photon pair in a Bell singlet state, and is certified explicitly by value indefiniteness. While "true randomness" is a mathematical impossibility, the certification by value indefiniteness ensures the quantum random bits are incomputable in the strongest sense. This is the first QRNG setup in which a physical principle (Kochen-Specker value indefiniteness) guarantees that no single quantum bit produced can be classically computed (reproduced and validated), the mathematical form of bitwise physical unpredictability. The effects of various experimental imperfections are discussed in detail, particularly those related to detector efficiencies, context alignment and temporal correlations between bits. The analysis is to a large extent relevant for the construction of any QRNG based on beam-splitters. By measuring the two entangled photons in maximally misaligned contexts and utilizing the fact that two rather than one bitstring are obtained, more efficient and robust unbiasing techniques can be applied. A robust and efficient procedure based on XORing the bitstrings together---essentially using one as a one-time-pad for the other---is proposed to extract random bits in the presence of experimental imperfections, as well as a more efficient modification of the von Neumann procedure for the same task. Some open problems are also discussed.

preprint2010arXiv

Understanding the Quantum Computational Speed-up via De-quantisation

While it seems possible that quantum computers may allow for algorithms offering a computational speed-up over classical algorithms for some problems, the issue is poorly understood. We explore this computational speed-up by investigating the ability to de-quantise quantum algorithms into classical simulations of the algorithms which are as efficient in both time and space as the original quantum algorithms. The process of de-quantisation helps formulate conditions to determine if a quantum algorithm provides a real speed-up over classical algorithms. These conditions can be used to develop new quantum algorithms more effectively (by avoiding features that could allow the algorithm to be efficiently classically simulated), as well as providing the potential to create new classical algorithms (by using features which have proved valuable for quantum algorithms). Results on many different methods of de-quantisations are presented, as well as a general formal definition of de-quantisation. De-quantisations employing higher-dimensional classical bits, as well as those using matrix-simulations, put emphasis on entanglement in quantum algorithms; a key result is that any algorithm in which the entanglement is bounded is de-quantisable. These methods are contrasted with the stabiliser formalism de-quantisations due to the Gottesman-Knill Theorem, as well as those which take advantage of the topology of the circuit for a quantum algorithm. The benefits of the different methods are contrasted, and the importance of a range of techniques is emphasised. We further discuss some features of quantum algorithms which current de-quantisation methods do not cover.