Alastair Abbott
Office: Room 576, Building 303S
Science Building
Department of Computer Science
38 Princes Street
The University of Auckland
Office Hour: Friday 11am
Phone: +64 9 373 7599 ext 87595
Email: aabb009 [at] aucklanduni.ac.nz
Position: Joint Doctoral Candidate in the Department of Computer Science at the University of Auckland and in the laboratoire CREA at the École Polytechnique, Paris.
Supervised by Prof. Cristian S. Calude (UoA) and Prof. Giuseppe Longo (ÉP).
 Photo of me
Personal Details
Curriculum Vitae is available here.
Education
  • 2010: MSc with First Class Honours, Computer Science, University of Auckland.
  • 2009: BSc(Hons) First Class, Computer Science, University of Auckland.
  • 2006-2008: BSc in Computer Science and Physics, University of Auckland.
    • Awards and Scholarships
    • University of Auckland Doctorial Scholarship, 2011-2014
    • Department of Computer Science Poster Competition, 2nd place, 2011.
    • University of Auckland Masters Scholarship, 2010.
    • Montgomery Memorial Prize in Logic, 2009.
    • New Zealand Computer Society Cup and Shield, 2009.
    • Faculty of Science Summer Scholarship, 2008 (Computer Science), 2008 (Physics), 2009 (Computer Science).
    • J. C. Butcher Prize in Theoretical Computer Science, 2008.
    • Senior Prize in Computer Science, 2008.
    Research
    Research Interests
    My current research is primarily based around the interface between algorithmic information theory (AIT) and randomness in quantum mechanics. AIT is a strong tool for analysing the randomness and complexity of finite and infinite bit-strings. Bit-strings produced by two-valued quantum experiments (for example, reflection at a beamsplitter) are generally considered intrinsically random, but this is postulated and largely glossed over by physicists. We are looking at analysing such strings in the infinite limit, in order to understand in what sense these quantum bit-strings are random.

    Quantum bit-strings have attracted interest in recent times as a stronger alternative to common pseudo-random generators because of the importance of random numbers in cryptography and Monte-Carlo algorithms, and the fact that "anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin" (J. von Neumann). We are looking at how experiments to produce such strings should be performed to ensure they are theoretically as random as possible.

    Some further reading on this topic:

    • C. S. Calude and K. Svozil. Quantum Randomness and Value Indefiniteness. Advanced Science Letters 1 (2008), pp. 165-168. [full text].
    • K. Svozil. Three Criteria for Quantum Random-number Generators Based on Beam Splitters. Phys. Rev. A. 79, 054306 (2009). [DOI: 10.1103/PhysRevA.79.054306].

    I also have an interest in quantum computation, from both a practical and theoretical viewpoint. Some of my previous and ongoing research is focused on de-quantisation of quantum algorithms, the ability to find and prove results about the ability to find efficient classical simulations for quantum algorithms. Some important quantum algorithms have strong classical features, and exploring what enables/forbids equivalent classical algorithms.

    Publications
    1. A. A. Abbott, C. S. Calude and K. Svozil. On Demons and Oracles. Asia Pacific Mathematics Newsletter, 2(1), 2012, pp. 25-31.
    2. A. A. Abbott, M. Bechmann, C. S. Calude and A. Sebald. A nuclear magnetic resonance implementation of a classical Deutsch-Jozsa algorithm. International Journal of Unconventional Computing, in press (2011).
    3. A. A. Abbott and I. Watson. Ontology-aided product classification: A nearest neighbour approach. Case-Based Reasoning Research and Development, LNCS 6880 (2011), pp. 348-362.
    4. A. A. Abbott and C. S. Calude. Von Neumann normalisation and symptoms of randomness: An application to sequences of quantum random bits. In C. S. Calude, J. Kari and I. Petre (eds.), Unconventional Computation, LNCS 6714 (2011), pp. 40-51. [DOI: 10.1007/978-3-642-21341-0_10]
    5. A. A. Abbott, C. S. Calude and K. Svozil. A quantum random number generator certified by value indefiniteness. CDMTCS Research Report 396, 2010.
    6. A. A. Abbott and C. S. Calude. Von Neumann normalisation of a quantum random number generator. Computability - The Journal of the Association CiE, accepted (2011).
    7. A. A. Abbott and C. S. Calude. Understanding the quantum computational speed-up via de-quantisation. Electronic Proceedings in Theoretical Computer Science 26 (2010), pp. 1-12. [DOI: 10.4204/EPTCS.26.1].
    8. A. A. Abbott. De-quantisation of the quantum Fourier transform. Applied Mathematics and Computation, in press (2011). [DOI: 10.1016/j.amc.2011.06.057].
    9. A. A. Abbott. The Deutsch-Jozsa problem: De-quantisation and entanglement. Natural Computing, in press (2011). [DOI: 10.1007/s11047-011-9276-7]
    10. A. A. Abbott and M. J. Dinneen. An investigation of algorithms to aesthetically draw Cayley graphs. CDMTCS Research Report 318, 2008
    Conference Presentations
    1. A. A. Abbott. Von Neumann normalisation and symptoms of randomness: An application to sequences of quantum random bits. Unconventional Computation, Turku, Finland, 2011.
    2. A. A. Abbott. Ontology-aided product classification: A nearest neighbour approach. New Zealand Computer Science Research Student Conference, Palmerston North, New Zealand, 2011.
    3. A. A. Abbott. De-quantisation of the quantum Fourier transform. 3rd International Workshop on Physics and Computation, the Nile, Luxor-Aswan, Egypt, 2010.
    4. A. A. Abbott. The Deutsch-Jozsa Problem: De-quantisation and entanglement. Workshop on Physics and Computation, Ponta Delgada, Portugal, 2009.
    5. A. A. Abbott. De-quantisation in quantum computing: An overview and an application to the quantum Fourier transform. New Zealand Computer Science Research Student Conference, Wellington, New Zealand, 2010.
    Masters Thesis
    Quantum Random Numbers: Certification and Generation. Supervised by Prof. Cristian S. Calude.

    In this thesis we study the generation of randomness from quantum mechanical sources: quantum random number generators (QRNGs). Such devices are thought to provide a better quality of randomness than is possible with classical devices, but the issue is in need of more rigorous study.
    We present and extend some recent results providing a more theoretical grounding for the indeterminism in quantum mechanics. In particular, we show that sequences of quantum random bits are incomputable in the strongest sense: no bit can be provably computed in advance.
    We study in detail the use of von Neumann normalisation for QRNGs producing both finite strings and infinite sequences of bits; such normalisation methods are necessary in order to counter for experimental imperfections. We show that, in the case of a constantly biased source, this normalisation gives the desired uniform distribution. The effect of this normalisation on the (in)computability of the generated sequences is studied, and it is shown that algorithmic randomness and Borel normality are preserved, but ε-randomness (and thus incomputability) is, in general, not. Experimental bounds for the extent of departure from the uniform distribution in the non-ideal case of a slowly drifting bias are derived.
    We further propose a new QRNG which uses entangled photon pairs and is certified to produce incomputable bits by value indefiniteness; this is the first QRNG with explicit certification by a physical principle. The effects of various experimental imperfections are discussed in detail, and care is taken to make the proposed QRNG as robust as is possible to these. A robust method based on XORing the produced bit- strings together is proposed to further improve the quality of the distribution produced by the QRNG. Various improvements and optimisations to this scheme are discussed.
    Honours Thesis
    De-quantisation in Quantum Computation. Supervised by Prof. Cristian S. Calude.

    This dissertation is original work, and explores the use of de-quantisation of quantum algorithms as a tool to better understand the limitations of quantum computing. De-quantisation can help to develop both better classical and quantum algorithms, and provides insight into what provides the supposed 'quantum speed-up'. In this thesis we explore extending an existing de-quantisation of the Deutsch-Jozsa problem, and present initial results on the de-quantisation of the quantum Fourier transform (which were extended in a subsequent paper, in preparation and accepted into the conference Physics and Computation, 2010, Egypt).
    Teaching
    In Semester 1, 2012 I am tutoring CompSci 350 (Mathematical Foundations of Computer Science) and am demonstrating in the Advanced Physics Labs.