7 results for Abbott, A.A.

  • On Demons and Oracles

    Abbott, A.A.; Calude, C.S.; Svozil, K. (2011)

    Report
    The University of Auckland Library

    This paper presents a personal, subjective overview of Church-Turing Thesis and some attempts to trespass the Turing barrier.

    View record details
  • A Quantum Random Number Generator Certified by Value Indefiniteness

    Abbott, A.A.; Calude, C.S.; Svozil, K. (2010)

    Report
    The University of Auckland Library

    In this paper we propose a quantum random number generator (QRNG) which utilises 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 utilising 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.

    View record details
  • The Deutsch-Jozsa Problem: De-quantization and Entanglement

    Abbott, A.A. (2009)

    Report
    The University of Auckland Library

    The Deustch-Jozsa problem is one of the most basic ways to demonstrate the power of quantum computation. Consider a Boolean function f : {0, 1}n → {0, 1} and suppose we have a black-box to compute f. The Deutsch-Jozsa problem is to determine if f is constant (i.e. f(x) = const, ∀x ∈ {0, 1}n) or if f is balanced (i.e. f(x) = 0 for exactly half the possible input strings x ∈ {0, 1}n) using as few calls to the black-box computing f as is possible, assuming f is guaranteed to be constant or balanced. Classically it appears that this requires at least 2n−1 + 1 black-box calls in the worst case, but the well known quantum solution solves the problem with probability one in exactly one black-box call. It has been found that in some cases the algorithm can be de-quantised into an equivalent classical, deterministic solution. We explore the ability to extend this de-quantisation to further cases, and examine with more detail when de-quantisation is possible, both with respect to the Deutsch-Jozsa problem, as well as in more general black-box algorithms.

    View record details
  • A Nuclear Magnetic Resonance Implementation of a Classical Deutsch-Jozsa Algorithm

    Abbott, A.A.; Bechmann, M.; Calude, C.S.; Sebald, a. (2011)

    Report
    The University of Auckland Library

    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.

    View record details
  • De-quantisation of the Quantum Fourier Transform

    Abbott, A.A. (2010)

    Report
    The University of Auckland Library

    The quantum Fourier transform (QFT) plays an important role in many known quantum algorithms such as Shor’s algorithm for prime factorisation. In this paper we show that the QFT algorithm can, on a restricted set of input states, be de-quantised into a classical algorithm which is both more efficient and simpler than the quantum algorithm. By working directly with the algorithm instead of the circuit, we develop a simple classical version of the quantum basis-state algorithm. We formulate conditions for a separable state to remain separable after the QFT is performed, and use these conditions to extend the de-quantised algorithm to work on all such states without loss of efficiency. Our technique highlights the linearity of quantum mechanics as the fundamental feature accounting for the difference between quantum and de-quantised algorithms, and that it is this linearity which makes the QFT such a useful tool in quantum computation.

    View record details
  • Von Neumann Normalisation of a Quantum Random Number Generator

    Abbott, A.A.; Calude, C.S. (2010)

    Report
    The University of Auckland Library

    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.

    View record details
  • Understanding the Quantum Computational Speed-up via De-quantisation

    Abbott, A.A.; Calude, C.S. (2010)

    Report
    The University of Auckland Library

    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) and 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 and limits of the different methods are discussed, and the importance of utilising a range of techniques is emphasised. We further discuss some features of quantum algorithms which current de-quantisation methods do not cover and highlight several important open questions in the area.

    View record details