-
Advantages of multistage quantum walks over QAOA
Authors:
Lasse Gerblich,
Tamanna Dasanjh,
Horatio Q. X. Wong,
David Ross,
Leonardo Novo,
Nicholas Chancellor,
Viv Kendon
Abstract:
Methods to find the solution state for optimization problems encoded into Ising Hamiltonians are a very active area of current research. In this work we compare the quantum approximate optimization algorithm (QAOA) with multi-stage quantum walks (MSQW). Both can be used as variational quantum algorithms, where the control parameters are optimized classically. A fair comparison requires both quantu…
▽ More
Methods to find the solution state for optimization problems encoded into Ising Hamiltonians are a very active area of current research. In this work we compare the quantum approximate optimization algorithm (QAOA) with multi-stage quantum walks (MSQW). Both can be used as variational quantum algorithms, where the control parameters are optimized classically. A fair comparison requires both quantum and classical resources to be assessed. Alternatively, parameters can be chosen heuristically, as we do in this work, providing a simpler setting for comparisons. Using both numerical and analytical methods, we obtain evidence that MSQW outperforms QAOA, using equivalent resources. We also show numerically for random spin glass ground state problems that MSQW performs well even for few stages and heuristic parameters, with no classical optimization.
△ Less
Submitted 16 July, 2024; v1 submitted 9 July, 2024;
originally announced July 2024.
-
Entropy Computing: A Paradigm for Optimization in an Open Quantum System
Authors:
Lac Nguyen,
Mohammad-Ali Miri,
R. Joseph Rupert,
Wesley Dyk,
Sam Wu,
Nick Vrahoretis,
Irwin Huang,
Milan Begliarbekov,
Nicholas Chancellor,
Uchenna Chukwu,
Pranav Mahamuni,
Cesar Martinez-Delgado,
David Haycraft,
Carrie Spear,
Mark Campanelli,
Russell Huffman,
Yong Meng Sua,
Yuping Huang
Abstract:
Modern quantum technologies using matter are designed as closed quantum systems to isolate them from interactions with the environment. This design paradigm greatly constrains the scalability and limits practical implementation of such systems. Here, we introduce a novel computing paradigm, entropy computing, that works by conditioning a quantum reservoir thereby enabling the stabilization of a gr…
▽ More
Modern quantum technologies using matter are designed as closed quantum systems to isolate them from interactions with the environment. This design paradigm greatly constrains the scalability and limits practical implementation of such systems. Here, we introduce a novel computing paradigm, entropy computing, that works by conditioning a quantum reservoir thereby enabling the stabilization of a ground state. In this work, we experimentally demonstrate the feasibility of entropy computing by building a hybrid photonic-electronic computer that uses measurement-based feedback to solve non-convex optimization problems. The system functions by using temporal photonic modes to create qudits in order to encode probability amplitudes in the time-frequency degree of freedom of a photon. This scheme, when coupled with electronic interconnects, allows us to encode an arbitrary Hamiltonian into the system and solve non-convex continuous variables and combinatorial optimization problems. We show that the proposed entropy computing paradigm can act as a scalable and versatile platform for tackling a large range of NP-hard optimization problems.
△ Less
Submitted 5 July, 2024;
originally announced July 2024.
-
Integrating Quantum Algorithms Into Classical Frameworks: A Predictor-corrector Approach Using HHL
Authors:
Omer Rathore,
Alastair Basden,
Nicholas Chancellor,
Halim Kusumaatmaja
Abstract:
The application of quantum algorithms to classical problems is generally accompanied by significant bottlenecks when transferring data between quantum and classical states, often negating any intrinsic quantum advantage. Here we address this challenge for a well-known algorithm for linear systems of equations, originally proposed by Harrow, Hassidim and Lloyd (HHL), by adapting it into a predictor…
▽ More
The application of quantum algorithms to classical problems is generally accompanied by significant bottlenecks when transferring data between quantum and classical states, often negating any intrinsic quantum advantage. Here we address this challenge for a well-known algorithm for linear systems of equations, originally proposed by Harrow, Hassidim and Lloyd (HHL), by adapting it into a predictor-corrector instead of a direct solver. Rather than seeking the solution at the next time step, the goal now becomes determining the change between time steps. This strategy enables the intelligent omission of computationally costly steps commonly found in many classical algorithms, while simultaneously mitigating the notorious readout problems associated with extracting solutions from a quantum state. Random or regularly performed skips instead lead to simulation failure. We demonstrate that our methodology secures a useful polynomial advantage over a conventional application of the HHL algorithm. The practicality and versatility of the approach are illustrated through applications in various fields such as smoothed particle hydrodynamics, plasma simulations, and reactive flow configurations. Moreover, the proposed algorithm is well suited to run asynchronously on future heterogeneous hardware infrastructures and can effectively leverage the synergistic strengths of classical as well as quantum compute resources.
△ Less
Submitted 28 June, 2024;
originally announced June 2024.
-
Experimental demonstration of improved quantum optimization with linear Ising penalties
Authors:
Puya Mirkarimi,
David C. Hoyle,
Ross Williams,
Nicholas Chancellor
Abstract:
The standard approach to encoding constraints in quantum optimization is the quadratic penalty method. Quadratic penalties introduce additional couplings and energy scales, which can be detrimental to the performance of a quantum optimizer. In quantum annealing experiments performed on a D-Wave Advantage, we explore an alternative penalty method that only involves linear Ising terms and apply it t…
▽ More
The standard approach to encoding constraints in quantum optimization is the quadratic penalty method. Quadratic penalties introduce additional couplings and energy scales, which can be detrimental to the performance of a quantum optimizer. In quantum annealing experiments performed on a D-Wave Advantage, we explore an alternative penalty method that only involves linear Ising terms and apply it to a customer data science problem. Our findings support our hypothesis that the linear Ising penalty method should improve the performance of quantum optimization compared to using the quadratic penalty method due to its more efficient use of physical resources. Although the linear Ising penalty method is not guaranteed to exactly implement the desired constraint in all cases, it is able to do so for the majority of problem instances we consider. For problems with many constraints, where making all penalties linear is unlikely to be feasible, we investigate strategies for combining linear Ising penalties with quadratic penalties to satisfy constraints for which the linear method is not well-suited. We find that this strategy is most effective when the penalties that contribute most to limiting the dynamic range are removed.
△ Less
Submitted 8 April, 2024;
originally announced April 2024.
-
Quantum optimization with linear Ising penalty functions for customer data science
Authors:
Puya Mirkarimi,
Ishaan Shukla,
David C. Hoyle,
Ross Williams,
Nicholas Chancellor
Abstract:
Constrained combinatorial optimization problems, which are ubiquitous in industry, can be solved by quantum algorithms such as quantum annealing (QA) and the quantum approximate optimization algorithm (QAOA). In these quantum algorithms, constraints are typically implemented with quadratic penalty functions. This penalty method can introduce large energy scales and make interaction graphs much mor…
▽ More
Constrained combinatorial optimization problems, which are ubiquitous in industry, can be solved by quantum algorithms such as quantum annealing (QA) and the quantum approximate optimization algorithm (QAOA). In these quantum algorithms, constraints are typically implemented with quadratic penalty functions. This penalty method can introduce large energy scales and make interaction graphs much more dense. These effects can result in worse performance of quantum optimization, particularly on near-term devices that have sparse hardware graphs and other physical limitations. In this work, we consider linear Ising penalty functions, which are applied with local fields in the Ising model, as an alternative method for implementing constraints that makes more efficient use of physical resources. We study the behaviour of the penalty method in the context of quantum optimization for customer data science problems. Our theoretical analysis and numerical simulations of QA and the QAOA indicate that this penalty method can lead to better performance in quantum optimization than the quadratic method. However, the linear Ising penalty method is not suitable for all problems as it cannot always exactly implement the desired constraint. In cases where the linear method is not successful in implementing all constraints, we propose that schemes involving both quadratic and linear Ising penalties can be effective.
△ Less
Submitted 8 April, 2024;
originally announced April 2024.
-
Load Balancing For High Performance Computing Using Quantum Annealing
Authors:
Omer Rathore,
Alastair Basden,
Nicholas Chancellor,
Halim Kusumaatmaja
Abstract:
With the advent of exascale computing, effective load balancing in massively parallel software applications is critically important for leveraging the full potential of high performance computing systems. Load balancing is the distribution of computational work between available processors. Here, we investigate the application of quantum annealing to load balance two paradigmatic algorithms in hig…
▽ More
With the advent of exascale computing, effective load balancing in massively parallel software applications is critically important for leveraging the full potential of high performance computing systems. Load balancing is the distribution of computational work between available processors. Here, we investigate the application of quantum annealing to load balance two paradigmatic algorithms in high performance computing. Namely, adaptive mesh refinement and smoothed particle hydrodynamics are chosen as representative grid and off-grid target applications. While the methodology for obtaining real simulation data to partition is application specific, the proposed balancing protocol itself remains completely general. In a grid based context, quantum annealing is found to outperform classical methods such as the round robin protocol but lacks a decisive advantage over more advanced methods such as steepest descent or simulated annealing despite remaining competitive. The primary obstacle to scalability is found to be limited coupling on current quantum annealing hardware. However, for the more complex particle formulation, approached as a multi-objective optimization, quantum annealing solutions are demonstrably Pareto dominant to state of the art classical methods across both objectives. This signals a noteworthy advancement in solution quality which can have a large impact on effective CPU usage.
△ Less
Submitted 8 March, 2024;
originally announced March 2024.
-
Zeno-effect Computation: Opportunities and Challenges
Authors:
Jesse Berwald,
Nicholas Chancellor,
Raouf Dridi
Abstract:
Adiabatic quantum computing has demonstrated how quantum Zeno can be used to construct quantum optimisers. However, much less work has been done to understand how more general Zeno effects could be used in a similar setting. We use a construction based on three state systems rather than directly in qubits, so that a qubit can remain after projecting out one of the states. We find that our model of…
▽ More
Adiabatic quantum computing has demonstrated how quantum Zeno can be used to construct quantum optimisers. However, much less work has been done to understand how more general Zeno effects could be used in a similar setting. We use a construction based on three state systems rather than directly in qubits, so that a qubit can remain after projecting out one of the states. We find that our model of computing is able to recover the dynamics of a transverse field Ising model, several generalisations are possible, but our methods allow for constraints to be implemented non-perturbatively and does not need tunable couplers, unlike simple transverse field implementations. We further discuss how to implement the protocol physically using methods building on STIRAP protocols for state transfer. We find a substantial challenge, that settings defined exclusively by measurement or dissipative Zeno effects do not allow for frustration, and in these settings pathological spectral features arise leading to unfavorable runtime scaling. We discuss methods to overcome this challenge for example including gain as well as loss as is often done in optical Ising machines.
△ Less
Submitted 13 November, 2023;
originally announced November 2023.
-
Cycle discrete-time quantum walks on a noisy quantum computer
Authors:
Vivek Wadhia,
Nicholas Chancellor,
Viv Kendon
Abstract:
The rapid development of quantum computing has led to increasing interest in quantum algorithms for a variety of different applications. Quantum walks have also experienced a surge in interest due to their potential use in quantum algorithms. Using the qiskit software package, we test how accurately the current generation of quantum computers provided by IBM can simulate a cycle discrete-time quan…
▽ More
The rapid development of quantum computing has led to increasing interest in quantum algorithms for a variety of different applications. Quantum walks have also experienced a surge in interest due to their potential use in quantum algorithms. Using the qiskit software package, we test how accurately the current generation of quantum computers provided by IBM can simulate a cycle discrete-time quantum walk. Implementing an 8-node, 8-step walk and a simpler 4-node, 4-step discrete-time quantum walk on an IBM quantum device known as ibmq_quito, the results for each step of the respective walks are presented. A custom noise model is developed in order to estimate that noise levels in the ibmq_santiago quantum device would need to be reduced by at least 94% in order to execute a 16-node, 16-step cycle discrete-time quantum walk to a reasonable level of fidelity.
△ Less
Submitted 7 December, 2023; v1 submitted 20 July, 2023;
originally announced July 2023.
-
Grover Speedup from Many Forms of the Zeno Effect
Authors:
Jesse Berwald,
Nick Chancellor,
Raouf Dridi
Abstract:
It has previously been established that adiabatic quantum computation, operating based on a continuous Zeno effect due to dynamical phases between eigenstates, is able to realise an optimal Grover-like quantum speedup. In other words is able to solve an unstructured search problem with the same $\sqrt{N}$ scaling as Grover's original algorithm. A natural question is whether other manifestations of…
▽ More
It has previously been established that adiabatic quantum computation, operating based on a continuous Zeno effect due to dynamical phases between eigenstates, is able to realise an optimal Grover-like quantum speedup. In other words is able to solve an unstructured search problem with the same $\sqrt{N}$ scaling as Grover's original algorithm. A natural question is whether other manifestations of the Zeno effect can also support an optimal speedup in a physically realistic model (through direct analog application rather than indirectly by supporting a universal gateset). In this paper we show that they can support such a speedup, whether due to measurement, decoherence, or even decay of the excited state into a computationally useless state. Our results also suggest a wide variety of methods to realise speedup which do not rely on Zeno behaviour. We group these algorithms into three families to facilitate a structured understanding of how speedups can be obtained: one based on phase kicks, containing adiabatic computation and continuous-time quantum walks; one based on dephasing and measurement; and finally one based on destruction of the amplitude within the excited state, for which we are not aware of any previous results. These results suggest that there may be exciting opportunities for new paradigms of analog quantum computing based on these effects.
△ Less
Submitted 30 May, 2023; v1 submitted 18 May, 2023;
originally announced May 2023.
-
A thermodynamic approach to optimization in complex quantum systems
Authors:
Alberto Imparato,
Nicholas Chancellor,
Gabriele De Chiara
Abstract:
We consider the problem of finding the energy minimum of a complex quantum Hamiltonian by employing a non-Markovian bath prepared in a low energy state. The energy minimization problem is thus turned into a thermodynamic cooling protocol in which we repeatedly put the system of interest in contact with a colder auxiliary system. By tuning the internal parameters of the bath, we show that the optim…
▽ More
We consider the problem of finding the energy minimum of a complex quantum Hamiltonian by employing a non-Markovian bath prepared in a low energy state. The energy minimization problem is thus turned into a thermodynamic cooling protocol in which we repeatedly put the system of interest in contact with a colder auxiliary system. By tuning the internal parameters of the bath, we show that the optimal cooling is obtained in a regime where the bath exhibits a quantum phase transition in the thermodynamic limit. This result highlights the importance of collective effects in thermodynamic devices. We furthermore introduce a two-step protocol that combines the interaction with the bath with a measure of its energy. While this protocol does not destroy coherence in the system of interest, we show that it can further enhance the cooling effect.
△ Less
Submitted 28 March, 2024; v1 submitted 10 May, 2023;
originally announced May 2023.
-
NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
Authors:
Rhonda Au-Yeung,
Nicholas Chancellor,
Pascal Halffmann
Abstract:
In the last decade, public and industrial research funding has moved quantum computing from the early promises of Shor's algorithm through experiments to the era of noisy intermediate scale quantum devices (NISQ) for solving real-world problems. It is likely that quantum methods can efficiently solve certain (NP-)hard optimization problems where classical approaches fail. In our perspective, we ex…
▽ More
In the last decade, public and industrial research funding has moved quantum computing from the early promises of Shor's algorithm through experiments to the era of noisy intermediate scale quantum devices (NISQ) for solving real-world problems. It is likely that quantum methods can efficiently solve certain (NP-)hard optimization problems where classical approaches fail. In our perspective, we examine the field of quantum optimization where we solve optimisation problems using quantum computers. We demonstrate this through a proper use case and discuss the current quality of quantum computers, their solver capabilities, and benchmarking difficulties. Although we show a proof-of-concept rather than a full benchmark, we use the results to emphasize the importance of using appropriate metrics when comparing quantum and classical methods. We conclude with discussion on some recent quantum optimization breakthroughs and the current status and future directions.
△ Less
Submitted 21 December, 2022;
originally announced December 2022.
-
Suppressing unwanted fluctuations in QAOA and approximate quantum annealing
Authors:
Touheed Anwar Atif,
Catherine Potts,
David Haycraft,
Raouf Dridi,
Nicholas Chancellor
Abstract:
The quantum approximate optimisation algorithm (QAOA) was partially inspired by digitising quantum annealing. Based on this inspiration, we develop techniques to use the additional flexibility of a universal gate-model quantum computer to mitigate fluctuation effects which are known to distort the search space within quantum annealing and lead to false minima. We find that even just the added abil…
▽ More
The quantum approximate optimisation algorithm (QAOA) was partially inspired by digitising quantum annealing. Based on this inspiration, we develop techniques to use the additional flexibility of a universal gate-model quantum computer to mitigate fluctuation effects which are known to distort the search space within quantum annealing and lead to false minima. We find that even just the added ability to take Pauli X measurements allows us to modify the mixer angles to counteract these effects by scaling mixer terms in a way proportional to the diagonal elements of the Fubini-Study metric. We find that mitigating these effects can lead to higher success probabilities in cases where the energy landscape is distorted and that we can use the same Pauli X measurements to target which variables are likely to be susceptible to strong fluctuations. The effects of the methods we introduce are relevant even at relatively low depth of $p=10-20$, suggesting that the techniques we are developing are likely to be relevant in the near term. Furthermore, since these methods rely on controlling a degree of freedom which is not typically modified in QAOA, our methods will be compatible with a wide range of other QAOA innovations. We further verify that these fluctuation effects can be observed on an IonQ Harmony QPU.
△ Less
Submitted 1 December, 2022;
originally announced December 2022.
-
Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond
Authors:
Adam Callison,
Nicholas Chancellor
Abstract:
Hybrid quantum-classical algorithms are central to much of the current research in quantum computing, particularly when considering the noisy intermediate-scale quantum (NISQ) era, with a number of experimental demonstrations having already been performed. In this perspective, we discuss in a very broad sense what it means for an algorithm to be hybrid quantum-classical. We first explore this conc…
▽ More
Hybrid quantum-classical algorithms are central to much of the current research in quantum computing, particularly when considering the noisy intermediate-scale quantum (NISQ) era, with a number of experimental demonstrations having already been performed. In this perspective, we discuss in a very broad sense what it means for an algorithm to be hybrid quantum-classical. We first explore this concept very directly, by building a definition based on previous work in abstraction/representation theory, arguing that what makes an algorithm hybrid is not directly how it is run (or how many classical resources it consumes), but whether classical components are crucial to an underlying model of the computation. We then take a broader view of this question, reviewing a number of hybrid algorithms and discussing what makes them hybrid, as well as the history of how they emerged, and considerations related to hardware. This leads into a natural discussion of what the future holds for these algorithms. To answer this question, we turn to the use of specialized processors in classical computing.The classical trend is not for new technology to completely replace the old, but to augment it. We argue that the evolution of quantum computing is unlikely to be different: hybrid algorithms are likely here to stay well past the NISQ era and even into full fault-tolerance, with the quantum processors augmenting the already powerful classical processors which exist by performing specialized tasks.
△ Less
Submitted 14 July, 2022;
originally announced July 2022.
-
Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms
Authors:
Puya Mirkarimi,
Adam Callison,
Lewis Light,
Nicholas Chancellor,
Viv Kendon
Abstract:
An algorithm for a particular problem may find some instances of the problem easier and others harder to solve, even for a fixed input size. We numerically analyse the relative hardness of MAX 2-SAT problem instances for various continuous-time quantum algorithms and a comparable classical algorithm. This has two motivations: to investigate whether small-sized problem instances, which are commonly…
▽ More
An algorithm for a particular problem may find some instances of the problem easier and others harder to solve, even for a fixed input size. We numerically analyse the relative hardness of MAX 2-SAT problem instances for various continuous-time quantum algorithms and a comparable classical algorithm. This has two motivations: to investigate whether small-sized problem instances, which are commonly used in numerical simulations of quantum algorithms for benchmarking purposes, are a good representation of larger instances in terms of their hardness to solve, and to determine the applicability of continuous-time quantum algorithms in a portfolio approach, where we take advantage of the variation in the hardness of instances between different algorithms by running them in parallel. We find that, while there are correlations in instance hardness between all of the algorithms considered, they appear weak enough that a portfolio approach would likely be desirable in practice. Our results also show a widening range of hardness of randomly generated instances as the problem size is increased, which demonstrates both the difference in the distribution of hardness at small sizes and the value of a portfolio approach that can reduce the number of extremely hard instances. We identify specific weaknesses of these quantum algorithms that can be overcome with a portfolio approach, such their inability to efficiently solve satisfiable instances (which is easy classically).
△ Less
Submitted 21 July, 2023; v1 submitted 14 June, 2022;
originally announced June 2022.
-
Using copies to improve precision in continuous-time quantum computing
Authors:
Jemma Bennett,
Adam Callison,
Tom O'Leary,
Mia West,
Nicholas Chancellor,
Viv Kendon
Abstract:
In the quantum optimisation setting, we build on a scheme introduced by Young et al [PRA 88, 062314, 2013], where physical qubits in multiple copies of a problem encoded into an Ising spin Hamiltonian are linked together to increase the logical system's robustness to error. We introduce several innovations that improve this scheme significantly. First, we note that only one copy needs to be correc…
▽ More
In the quantum optimisation setting, we build on a scheme introduced by Young et al [PRA 88, 062314, 2013], where physical qubits in multiple copies of a problem encoded into an Ising spin Hamiltonian are linked together to increase the logical system's robustness to error. We introduce several innovations that improve this scheme significantly. First, we note that only one copy needs to be correct by the end of the computation, since solution quality can be checked efficiently. Second, we find that ferromagnetic links do not generally help in this "one correct copy" setting, but anti-ferromagnetic links do help on average, by suppressing the chance of the same error being present on all of the copies. Third, we find that minimum-strength anti-ferromagnetic links perform best, by counteracting the spin-flips induced by the errors. We have numerically tested our innovations on small instances of spin glasses from Callison et al [NJP 21, 123022, 2019], and we find improved error tolerance for three or more copies in configurations that include frustration. Interpreted as an effective precision increase, we obtain several extra bits of precision for three copies connected in a triangle. This provides proof-of-concept of a method for scaling quantum annealing beyond the precision limits of hardware, a step towards fault tolerance in this setting.
△ Less
Submitted 30 August, 2022; v1 submitted 6 June, 2022;
originally announced June 2022.
-
Controller-based Energy-Aware Wireless Sensor Network Routing using Quantum Algorithms
Authors:
Jie Chen,
Prasanna Date,
Nicholas Chancellor,
Mohammed Atiquzzaman,
Cormac Sreenan
Abstract:
Energy efficient routing in wireless sensor networks has attracted attention from researchers in both academia and industry, most recently motivated by the opportunity to use SDN (software defined network)-inspired approaches. These problems are NP-hard, with algorithms needing computation time which scales faster than polynomial in the problem size. Consequently, heuristic algorithms are used in…
▽ More
Energy efficient routing in wireless sensor networks has attracted attention from researchers in both academia and industry, most recently motivated by the opportunity to use SDN (software defined network)-inspired approaches. These problems are NP-hard, with algorithms needing computation time which scales faster than polynomial in the problem size. Consequently, heuristic algorithms are used in practice, which are unable to guarantee optimally. In this short paper, we show proof-of-principle for the use of a quantum annealing processor instead of a classical processor, to find optimal or near-optimal solutions very quickly. Our preliminary results for small networks show that this approach using quantum computing has great promise and may open the door for other significant improvements in the efficacy of network algorithms.
△ Less
Submitted 12 October, 2021;
originally announced October 2021.
-
Understanding domain-wall encoding theoretically and experimentally
Authors:
Jesse Berwald,
Nicholas Chancellor,
Raouf Dridi
Abstract:
We analyze the method of encoding pairwise interactions of higher-than-binary discrete variables (these models are sometimes referred to as discrete quadratic models) into binary variables based on domain walls on one dimensional Ising chains. We discuss how this is relevant to quantum annealing, but also many gate model algorithms such as VQE and QAOA. We theoretically show that for problems of p…
▽ More
We analyze the method of encoding pairwise interactions of higher-than-binary discrete variables (these models are sometimes referred to as discrete quadratic models) into binary variables based on domain walls on one dimensional Ising chains. We discuss how this is relevant to quantum annealing, but also many gate model algorithms such as VQE and QAOA. We theoretically show that for problems of practical interest for quantum computing and assuming only quadratic interactions are available between the binary variables, it is not possible to have a more efficient general encoding in terms of number of binary variables per discrete variable. We furthermore use a D-Wave Advantage 1.1 flux qubit quantum annealing computer to show that the dynamics effectively freeze later for a domain-wall encoding compared to a traditional one-hot encoding. This second result could help explain the dramatic performance improvement of domain wall over one hot which has been seen in a recent experiment on D-Wave hardware. This is an important result because usually problem encoding and the underlying physics are considered separately, our work suggests that considering them together may be a more useful paradigm. We argue that this experimental result is also likely to carry over to a number of other settings, we discuss how this has implications for gate-model and quantum-inspired algorithms.
△ Less
Submitted 14 September, 2022; v1 submitted 26 August, 2021;
originally announced August 2021.
-
Inclusive learning for quantum computing: supporting the aims of quantum literacy using the puzzle game Quantum Odyssey
Authors:
Laurentiu Nita,
Nicholas Chancellor,
Laura Mazzoli Smith,
Helen Cramman,
Gulsah Dost
Abstract:
With a vast domain of applications and now having quantum computing hardware available for commercial use, an education challenge arises in getting people of various background to become quantum literate. Quantum Odyssey is a new piece of computer software that promises to be a medium where people can learn quantum computing without any previous requirements. It aims to achieve this through visual…
▽ More
With a vast domain of applications and now having quantum computing hardware available for commercial use, an education challenge arises in getting people of various background to become quantum literate. Quantum Odyssey is a new piece of computer software that promises to be a medium where people can learn quantum computing without any previous requirements. It aims to achieve this through visual cues and puzzle play, without requiring the user to possess a background in computer coding or even linear algebra, which are traditionally a must to work on quantum algorithms. In this paper we report our findings on an UKRI Citizen Science grant that involves using Quantum Odyssey to teach how to construct quantum computing algorithms. Sessions involved 30 minutes of play, with 10 groups of 5 students, ranging between 11 to 18 years old, in two schools in the UK. Results show the Quantum Odyssey visual methods are efficient in portraying counterintuitive quantum computational logic in a visual and interactive form. This enabled untrained participants to quickly grasp difficult concepts in an intuitive way and solve problems that are traditionally given today in Masters level courses in a mathematical form. The results also show an increased interest in quantum physics after play, a higher openness and curiosity to learn the mathematics behind computing on quantum systems. Participants developed a visual, rather than mathematical intuition, that enabled them to understand and correctly answer entry level technical quantum information science.
△ Less
Submitted 13 June, 2021;
originally announced June 2021.
-
Performance of Domain-Wall Encoding for Quantum Annealing
Authors:
Jie Chen,
Tobias Stollenwerk,
Nicholas Chancellor
Abstract:
In this paper we experimentally test the performance of the recently proposed domain-wall encoding of discrete variables from [Chancellor Quantum Sci. Technol. 4 045004] on Ising model flux qubit quantum annealers. We compare this encoding with the traditional one-hot methods and find that they outperform the one-hot encoding for three different problems at different sizes both of the problem and…
▽ More
In this paper we experimentally test the performance of the recently proposed domain-wall encoding of discrete variables from [Chancellor Quantum Sci. Technol. 4 045004] on Ising model flux qubit quantum annealers. We compare this encoding with the traditional one-hot methods and find that they outperform the one-hot encoding for three different problems at different sizes both of the problem and of the variables. From these results we conclude that the domain-wall encoding yields superior performance against a variety of metrics furthermore, we do not find a single metric by which one hot performs better. We even find that a 2000Q quantum annealer with a drastically less connected hardware graph but using the domain-wall encoding can outperform the next generation Advantage processor if that processor uses one-hot encoding.
△ Less
Submitted 12 June, 2021; v1 submitted 24 February, 2021;
originally announced February 2021.
-
AKLT-states as ZX-diagrams: diagrammatic reasoning for quantum states
Authors:
Richard D. P. East,
John van de Wetering,
Nicholas Chancellor,
Adolfo G. Grushin
Abstract:
From Feynman diagrams to tensor networks, diagrammatic representations of computations in quantum mechanics have catalysed progress in physics. These diagrams represent the underlying mathematical operations and aid physical interpretation, but cannot generally be computed with directly. In this paper we introduce the ZXH-calculus, a graphical language based on the ZX-calculus, that we use to repr…
▽ More
From Feynman diagrams to tensor networks, diagrammatic representations of computations in quantum mechanics have catalysed progress in physics. These diagrams represent the underlying mathematical operations and aid physical interpretation, but cannot generally be computed with directly. In this paper we introduce the ZXH-calculus, a graphical language based on the ZX-calculus, that we use to represent and reason about many-body states entirely graphically. As a demonstration, we express the 1D AKLT state, a symmetry protected topological state, in the ZXH-calculus by developing a representation of spins higher than 1/2 within the calculus. By exploiting the simplifying power of the ZXH-calculus rules we show how this representation straightforwardly recovers the AKLT matrix-product state representation, the existence of topologically protected edge states, and the non-vanishing of a string order parameter. Extending beyond these known properties, our diagrammatic approach also allows us to analytically derive that the Berry phase of any finite-length 1D AKLT chain is $π$. In addition, we provide an alternative proof that the 2D AKLT state on a hexagonal lattice can be reduced to a graph state, demonstrating that it is a universal quantum computing resource. Lastly, we build 2D higher-order topological phases diagrammatically, which we use to illustrate a symmetry-breaking phase transition. Our results show that the ZXH-calculus is a powerful language for representing and computing with physical states entirely graphically, paving the way to develop more efficient many-body algorithms and giving a novel diagrammatic perspective on quantum phase transitions.
△ Less
Submitted 8 December, 2021; v1 submitted 2 December, 2020;
originally announced December 2020.
-
Fluctuation guided search in quantum annealing
Authors:
Nicholas Chancellor
Abstract:
Quantum annealing has great promise in leveraging quantum mechanics to solve combinatorial optimisation problems. However, to realize this promise to it's fullest extent we must appropriately leverage the underlying physics. In this spirit, I examine how the well known tendency of quantum annealers to seek solutions where more quantum fluctuations are allowed can be used to trade off optimality of…
▽ More
Quantum annealing has great promise in leveraging quantum mechanics to solve combinatorial optimisation problems. However, to realize this promise to it's fullest extent we must appropriately leverage the underlying physics. In this spirit, I examine how the well known tendency of quantum annealers to seek solutions where more quantum fluctuations are allowed can be used to trade off optimality of the solution to a synthetic problem for the ability to have a more flexible solution, where some variables can be changed at little or no cost. I demonstrate this tradeoff experimentally using the reverse annealing feature a D-Wave Systems QPU for both problems composed of all binary variables, and those containing some higher-than-binary discrete variables. I further demonstrate how local controls on the qubits can be used to control the levels of fluctuations and guide the search. I discuss places where leveraging this tradeoff could be practically important, namely in hybrid algorithms where some penalties cannot be directly implemented on the annealer and provide some proof-of-concept evidence of how these algorithms could work.
△ Less
Submitted 9 November, 2020; v1 submitted 14 September, 2020;
originally announced September 2020.
-
Search range in experimental quantum annealing
Authors:
Nicholas Chancellor,
Viv Kendon
Abstract:
We construct an Ising Hamiltonian with an engineered energy landscape such that it has a local energy minimum which is near to the true global minimum solution, and further away from a false minimum. Using a technique established in previous experiments, we design our experiment such that (at least on timescales relevant to our study) the false minimum is reached preferentially in forward annealin…
▽ More
We construct an Ising Hamiltonian with an engineered energy landscape such that it has a local energy minimum which is near to the true global minimum solution, and further away from a false minimum. Using a technique established in previous experiments, we design our experiment such that (at least on timescales relevant to our study) the false minimum is reached preferentially in forward annealing due to high levels of quantum fluctuations. This allows us to demonstrate the key principle of reverse annealing, that the solution space can be searched locally, preferentially finding nearby solutions, even in the presence of a false minimum. The techniques used here are, to the best of our knowledge, distinct from previously used experimental techniques, and allow us to probe the fundamental search range of the device in a way which has not been previously explored. We perform these experiments on two flux qubit quantum annealers, one with higher noise levels than the other. We find evidence that the lower noise device is more likely to find the more distant energy minimum (the false minimum in this case), suggesting that reducing noise fundamentally increases the range over which flux qubit quantum annealers are able to search. Our work explains why reducing the noise leads to improved performance on these quantum annealers. This supports the idea that these devices may be able to search over broad regions of the solution space quickly, one of the core reasons why quantum annealers are viewed as a potential avenue for a quantum computational advantage.
△ Less
Submitted 15 July, 2021; v1 submitted 25 August, 2020;
originally announced August 2020.
-
An energetic perspective on rapid quenches in quantum annealing
Authors:
Adam Callison,
Max Festenstein,
Jie Chen,
Laurentiu Nita,
Viv Kendon,
Nicholas Chancellor
Abstract:
There are well developed theoretical tools to analyse how quantum dynamics can solve computational problems by varying Hamiltonian parameters slowly, near the adiabatic limit. On the other hand, there are relatively few tools to understand the opposite limit of rapid quenches, as used in quantum annealing and (in the limit of infinitely rapid quenches) in quantum walks. In this paper, we develop s…
▽ More
There are well developed theoretical tools to analyse how quantum dynamics can solve computational problems by varying Hamiltonian parameters slowly, near the adiabatic limit. On the other hand, there are relatively few tools to understand the opposite limit of rapid quenches, as used in quantum annealing and (in the limit of infinitely rapid quenches) in quantum walks. In this paper, we develop several tools which are applicable in the rapid quench regime. Firstly, we analyse the energy expectation value of different elements of the Hamiltonian. From this, we show that monotonic quenches, where the strength of the problem Hamiltonian is consistently increased relative to fluctuation (driver) terms, will yield a better result on average than random guessing. Secondly, we develop methods to determine whether dynamics will occur locally under rapid quench Hamiltonians, and identify cases where a rapid quench will lead to a substantially improved solution. In particular, we find that a technique we refer to as "pre-annealing" can significantly improve the performance of quantum walks. We also show how these tools can provide efficient heuristic estimates for Hamiltonian parameters, a key requirement for practical application of quantum annealing.
△ Less
Submitted 5 March, 2021; v1 submitted 22 July, 2020;
originally announced July 2020.
-
Error measurements for a quantum annealer using the one-dimensional Ising model with twisted boundaries
Authors:
Nicholas Chancellor,
Philip J. D. Crowley,
Tanja Đurić,
Walter Vinci,
Mohammad H. Amin,
Andrew G. Green,
Paul A. Warburton,
Gabriel Aeppli
Abstract:
A finite length ferromagnetic chain with opposite spin polarisation imposed at its two ends is one of the simplest frustrated spin models. In the clean classical limit the domain wall inserted on account of the boundary conditions resides with equal probability on any one of the bonds, and the degeneracy is precisely equal to the number of bonds. If quantum mechanics is introduced via a transverse…
▽ More
A finite length ferromagnetic chain with opposite spin polarisation imposed at its two ends is one of the simplest frustrated spin models. In the clean classical limit the domain wall inserted on account of the boundary conditions resides with equal probability on any one of the bonds, and the degeneracy is precisely equal to the number of bonds. If quantum mechanics is introduced via a transverse field, the domain wall will behave as a particle in a box, and prefer to be nearer the middle of the chain rather than the ends. A simple characteristic of a real quantum annealer is therefore which of these limits obtains in practice. Here we have used the ferromagnetic chain with antiparallel boundary spins to test a real flux qubit quantum annealer and discover that contrary to both expectations, the domain walls found are non-uniformly distributed on account of effective random longitudinal fields present notwithstanding tuning carried out to zero out such fields when the couplings between qubits are nominally zero. We present a simple derivation of the form of the distribution function for the domain walls, and show also how the effect we have discovered can be used to determine the strength of the effective random fields (noise) characterising the annealer. The noise measured in this fashion is smaller than what is seen during the single qubit tuning process, but nonetheless qualitatively affects the outcome of the simulation performed by the annealer.
△ Less
Submitted 11 April, 2022; v1 submitted 13 June, 2020;
originally announced June 2020.
-
Toward a standardized methodology for constructing quantum computing use cases
Authors:
Nicholas Chancellor,
Robert Cumming,
Tim Thomas
Abstract:
We propose a standardized methodology for developing and evaluating use cases for quantum computers and quantum inspired methods. This methodology consists of a standardized set of questions which should be asked to determine how and indeed if, near term quantum computing can play a role in a given application. Developing such a set of questions is important because it allows different use cases t…
▽ More
We propose a standardized methodology for developing and evaluating use cases for quantum computers and quantum inspired methods. This methodology consists of a standardized set of questions which should be asked to determine how and indeed if, near term quantum computing can play a role in a given application. Developing such a set of questions is important because it allows different use cases to be evaluated in a fair and objective way, rather than considering each case on an ad hoc basis which could lead to an evaluation which focuses on positives of a use case, while ignoring weaknesses. To demonstrate our methodology we apply it to a concrete use case, ambulance dispatch, and find that there are some ways in which near term quantum computing could be deployed sensibly, but also demonstrate some cases ways in which its use would not be advised. The purpose of this paper is to initiate a dialogue within the community of quantum computing scientists and potential end users on what questions should be asked when developing real world use cases.
△ Less
Submitted 10 June, 2020;
originally announced June 2020.
-
The challenge and opportunities of quantum literacy for future education and transdisciplinary problem-solving
Authors:
Laurentiu Nita,
Laura Mazzoli Smith,
Nicholas Chancellor,
Helen Cramman
Abstract:
Resulting from cross-disciplinary dialogue between physicists, computer scientists, educationalists, and industrial end users, we propose the concept of quantum literacy as one means of addressing the transdisciplinary nature of the complex problems that we see at the heart of issues around global sustainability. In this way, quantum literacy can contribute to UN Sustainable Development Goal 4, Qu…
▽ More
Resulting from cross-disciplinary dialogue between physicists, computer scientists, educationalists, and industrial end users, we propose the concept of quantum literacy as one means of addressing the transdisciplinary nature of the complex problems that we see at the heart of issues around global sustainability. In this way, quantum literacy can contribute to UN Sustainable Development Goal 4, Quality Education. We argue that quantum literacy, as defined here, addresses the challenges of learning and skills acquisition within a highly bounded discipline and of access to the kind of powerful knowledge that should be more accessible to a wide group of learners throughout the life course, both students and professionals. It is increasingly important that the knowledge of quantum technologies is accessible to those who work with real world applications in a more inclusive way. We therefore argue for the importance of addressing pedagogic issues when powerful knowledge consists of dense concepts, as well as complex and hierarchical relations between concepts, in addition to presenting a strong barrier to entry in the form of mathematics. We introduce a specific puzzle visualization learning tool through which to achieve these pedagogic ends with respect to quantum computation. Visualization through puzzles can enable non-specialists to develop an intuitive, but still rigorous, understanding of universal quantum computation and provide a facility for non-specialists to discover increasingly complex and new quantum algorithms. Using the Hong-Ou-Mandel optical effect from quantum mechanics, we demonstrate how visual methods such as those made possible through the puzzle visualization tool, can be very useful for understanding underlying complex processes in quantum physics and beyond and therefore support the aims of quantum literacy.
△ Less
Submitted 17 May, 2020; v1 submitted 14 April, 2020;
originally announced April 2020.
-
Quantum Computing for Quantum Tunnelling
Authors:
Steven Abel,
Nicholas Chancellor,
Michael Spannowsky
Abstract:
We demonstrate how quantum field theory problems can be embedded on quantum annealers. The general method we use is a discretisation of the field theory problem into a general Ising model, with the continuous field values being encoded into Ising spin chains. To illustrate the method, and as a simple proof of principle, we use a (hybrid) quantum annealer to recover the correct profile of the thin-…
▽ More
We demonstrate how quantum field theory problems can be embedded on quantum annealers. The general method we use is a discretisation of the field theory problem into a general Ising model, with the continuous field values being encoded into Ising spin chains. To illustrate the method, and as a simple proof of principle, we use a (hybrid) quantum annealer to recover the correct profile of the thin-wall tunnelling solution. This method is applicable to many nonperturbative problems.
△ Less
Submitted 16 March, 2020;
originally announced March 2020.
-
Decoding quantum error correction with Ising model hardware
Authors:
Joschka Roffe,
Stefan Zohren,
Dominic Horsman,
Nicholas Chancellor
Abstract:
Fault tolerant quantum computers will require efficient co-processors for real-time decoding of their adopted quantum error correction protocols. In this work we examine the possibility of using specialised Ising model hardware to perform this decoding task. Examples of Ising model hardware include quantum annealers such as those produced by D-Wave Systems Inc., as well as classical devices such a…
▽ More
Fault tolerant quantum computers will require efficient co-processors for real-time decoding of their adopted quantum error correction protocols. In this work we examine the possibility of using specialised Ising model hardware to perform this decoding task. Examples of Ising model hardware include quantum annealers such as those produced by D-Wave Systems Inc., as well as classical devices such as those produced by Hitatchi and Fujitsu and optical devices known as coherent Ising machines. We use the coherent parity check (CPC) framework to derive an Ising model mapping of the quantum error correction decoding problem for an uncorrelated quantum error model. A specific advantage of our Ising model mapping is that it is compatible with maximum entropy inference techniques which can outperform maximum likelihood decoding in some circumstances. We use numerical calculations within our framework to demonstrate that maximum entropy decoding can not only lead to improved error suppression, but can also shift threshold values for simple codes. As a high value problem for which a small advantage can lead to major gains, we argue that decoding quantum codes is an ideal use case for quantum annealers. In addition, the structure of quantum error correction codes allows application specific integrated circuit (ASIC) annealing hardware to reduce embedding costs, a major bottleneck in quantum annealing. Finally, we also propose a way in which a quantum annealer could be optimally used as part of a hybrid quantum-classical decoding scheme.
△ Less
Submitted 25 March, 2019;
originally announced March 2019.
-
Domain wall encoding of discrete variables for quantum annealing and QAOA
Authors:
Nicholas Chancellor
Abstract:
In this paper I propose a new method of encoding discrete variables into Ising model qubits for quantum optimization. The new method is based on the physics of domain walls in one dimensional Ising spin chains. I find that these encodings and the encoding of arbitrary two variable interactions is possible with only two body Ising terms. Following on from similar results for the `one hot' method of…
▽ More
In this paper I propose a new method of encoding discrete variables into Ising model qubits for quantum optimization. The new method is based on the physics of domain walls in one dimensional Ising spin chains. I find that these encodings and the encoding of arbitrary two variable interactions is possible with only two body Ising terms. Following on from similar results for the `one hot' method of encoding discrete variables [Hadfield et. al. Algorithms 12.2 (2019): 34] I also demonstrate that it is possible to construct two body mixer terms which do not leave the logical subspace, an important consideration for optimising using the quantum alternating operator ansatz (QAOA). I additionally discuss how, since the couplings in the domain wall encoding only need to be ferromagnetic and therefore could in principle be much stronger than anti-ferromagnetic couplers, application specific quantum annealers for discrete problems based on this construction may be beneficial. Finally, I compare embedding for synthetic scheduling and colouring problems with the domain wall and one hot encodings on two graphs which are relevant for quantum annealing, the chimera graph and the Pegasus graph. For every case I examine I find a similar or better performance from the domain wall encoding as compared to one hot, but this advantage is highly dependent on the structure of the problem. For encoding some problems, I find an advantage similar to the one found by embedding in a Pegasus graph compared to embedding in a chimera graph.
△ Less
Submitted 20 July, 2019; v1 submitted 12 March, 2019;
originally announced March 2019.
-
Finding spin-glass ground states using quantum walks
Authors:
Adam Callison,
Nicholas Chancellor,
Florian Mintert,
Viv Kendon
Abstract:
Quantum computation using continuous-time evolution under a natural hardware Hamiltonian is a promising near- and mid-term direction toward powerful quantum computing hardware. We investigate the performance of continuous-time quantum walks as a tool for finding spin glass ground states, a problem that serves as a useful model for realistic optimization problems. By performing detailed numerics, w…
▽ More
Quantum computation using continuous-time evolution under a natural hardware Hamiltonian is a promising near- and mid-term direction toward powerful quantum computing hardware. We investigate the performance of continuous-time quantum walks as a tool for finding spin glass ground states, a problem that serves as a useful model for realistic optimization problems. By performing detailed numerics, we uncover significant ways in which solving spin glass problems differs from applying quantum walks to the search problem. Importantly, unlike for the search problem, parameters such as the hopping rate of the quantum walk do not need to be set precisely for the spin glass ground state problem. Heuristic values of the hopping rate determined from the energy scales in the problem Hamiltonian are sufficient for obtaining a better than square-root scaling. This makes it practical to use quantum walks for solving such problems, and opens the door for a range of applications on suitable quantum hardware.
△ Less
Submitted 20 December, 2019; v1 submitted 12 March, 2019;
originally announced March 2019.
-
Embedding quadratization gadgets on Chimera and Pegasus graphs
Authors:
Nike Dattani,
Nick Chancellor
Abstract:
We group all known quadratizations of cubic and quartic terms in binary optimization problems into six and seven unique graphs respectively. We then perform a minor embedding of these graphs onto the well-known Chimera graph, and the brand new Pegasus graph. We conclude with recommendations for which gadgets are best to use when aiming to reduce the total number of qubits required to embed a probl…
▽ More
We group all known quadratizations of cubic and quartic terms in binary optimization problems into six and seven unique graphs respectively. We then perform a minor embedding of these graphs onto the well-known Chimera graph, and the brand new Pegasus graph. We conclude with recommendations for which gadgets are best to use when aiming to reduce the total number of qubits required to embed a problem.
△ Less
Submitted 22 January, 2019;
originally announced January 2019.
-
Pegasus: The second connectivity graph for large-scale quantum annealing hardware
Authors:
Nike Dattani,
Szilard Szalay,
Nick Chancellor
Abstract:
Pegasus is a graph which offers substantially increased connectivity between the qubits of quantum annealing hardware compared to the graph Chimera. It is the first fundamental change in the connectivity graph of quantum annealers built by D-Wave since Chimera was introduced in 2009 and then used in 2011 for D-Wave's first commercial quantum annealer. In this article we describe an algorithm which…
▽ More
Pegasus is a graph which offers substantially increased connectivity between the qubits of quantum annealing hardware compared to the graph Chimera. It is the first fundamental change in the connectivity graph of quantum annealers built by D-Wave since Chimera was introduced in 2009 and then used in 2011 for D-Wave's first commercial quantum annealer. In this article we describe an algorithm which defines the connectivity of Pegasus and we provide what we believe to be the best way to graphically visualize Pegasus in order to see which qubits couple to each other. As supplemental material, we provide a wide variety of different visualizations of Pegasus which expose different properties of the graph in different ways. We provide an open source code for generating the many depictions of Pegasus that we show.
△ Less
Submitted 22 January, 2019;
originally announced January 2019.
-
Practical designs for permutation symmetric problem Hamiltonians on hypercubes
Authors:
Ben Dodds,
Viv Kendon,
Charles S. Adams,
Nicholas Chancellor
Abstract:
We present a method to experimentally realize large-scale permutation-symmetric Hamiltonians for continuous-time quantum protocols such as quantum walk and adiabatic quantum computation. In particular, the method can be used to perform an encoded continuous-time quantum search on a hypercube graph with 2^n vertices encoded into 2n qubits. We provide details for a realistically achievable implement…
▽ More
We present a method to experimentally realize large-scale permutation-symmetric Hamiltonians for continuous-time quantum protocols such as quantum walk and adiabatic quantum computation. In particular, the method can be used to perform an encoded continuous-time quantum search on a hypercube graph with 2^n vertices encoded into 2n qubits. We provide details for a realistically achievable implementation in Rydberg atomic systems. Although the method is perturbative, the realization is always achieved at second order in perturbation theory, regardless of the size of the mapped system. This highly efficient mapping provides a natural set of problems which are tractable both numerically and analytically, thereby providing a powerful tool for benchmarking quantum hardware and experimentally investigating the physics of continuous-time quantum protocols.
△ Less
Submitted 21 August, 2019; v1 submitted 19 December, 2018;
originally announced December 2018.
-
Quantum codes from classical graphical models
Authors:
Joschka Roffe,
Stefan Zohren,
Dominic Horsman,
Nicholas Chancellor
Abstract:
We introduce a new graphical framework for designing quantum error correction codes based on classical principles. A key feature of this graphical language, over previous approaches, is that it is closely related to that of factor graphs or graphical models in classical information theory and machine learning. It enables us to formulate the description of the recently-introduced `coherent parity c…
▽ More
We introduce a new graphical framework for designing quantum error correction codes based on classical principles. A key feature of this graphical language, over previous approaches, is that it is closely related to that of factor graphs or graphical models in classical information theory and machine learning. It enables us to formulate the description of the recently-introduced `coherent parity check' quantum error correction codes entirely within the language of classical information theory. This makes our construction accessible without requiring background in quantum error correction or even quantum mechanics in general. More importantly, this allows for a collaborative interplay where one can design new quantum error correction codes derived from classical codes.
△ Less
Submitted 28 August, 2019; v1 submitted 20 April, 2018;
originally announced April 2018.
-
Protecting quantum memories using coherent parity check codes
Authors:
Joschka Roffe,
David Headley,
Nicholas Chancellor,
Dominic Horsman,
Viv Kendon
Abstract:
Coherent parity check (CPC) codes are a new framework for the construction of quantum error correction codes that encode multiple qubits per logical block. CPC codes have a canonical structure involving successive rounds of bit and phase parity checks, supplemented by cross-checks to fix the code distance. In this paper, we provide a detailed introduction to CPC codes using conventional quantum ci…
▽ More
Coherent parity check (CPC) codes are a new framework for the construction of quantum error correction codes that encode multiple qubits per logical block. CPC codes have a canonical structure involving successive rounds of bit and phase parity checks, supplemented by cross-checks to fix the code distance. In this paper, we provide a detailed introduction to CPC codes using conventional quantum circuit notation. We demonstrate the implementation of a CPC code on real hardware, by designing a [[4,2,2]] detection code for the IBM 5Q superconducting qubit device. Whilst the individual gate-error rates on the IBM device are too high to realise a fault tolerant quantum detection code, our results show that the syndrome information from a full encode-decode cycle of the [[4,2,2]] CPC code can be used to increase the output state fidelity by post-selection. Following this, we generalise CPC codes to other quantum technologies by showing that their structure allows them to be efficiently compiled using any experimentally realistic native two-qubit gate. We introduce a three-stage CPC design process for the construction of hardware-optimised quantum memories. As a proof-of-concept example, we apply our design process to an idealised linear seven-qubit ion trap. In the first stage of the process, we use exhaustive search methods to find a large set of [[7,3,3]] codes that saturate the quantum Hamming bound for seven qubits. We then optimise over the discovered set of codes to meet the hardware and layout demands of the ion trap device. We also discuss how the CPC design process will generalise to larger-scale codes and other qubit technologies.
△ Less
Submitted 22 May, 2018; v1 submitted 6 September, 2017;
originally announced September 2017.
-
Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
Authors:
James G. Morley,
Nicholas Chancellor,
Sougato Bose,
Viv Kendon
Abstract:
Computing using a continuous-time evolution, based on the natural interaction Hamiltonian of the quantum computer hardware, is a promising route to building useful quantum computers in the near-term. Adiabatic quantum computing, quantum annealing, computation by continuous-time quantum walk, and special purpose quantum simulators all use this strategy. In this work, we carry out a detailed examina…
▽ More
Computing using a continuous-time evolution, based on the natural interaction Hamiltonian of the quantum computer hardware, is a promising route to building useful quantum computers in the near-term. Adiabatic quantum computing, quantum annealing, computation by continuous-time quantum walk, and special purpose quantum simulators all use this strategy. In this work, we carry out a detailed examination of adiabatic and quantum walk implementation of the quantum search algorithm, using the more physically realistic hypercube connectivity, rather than the complete graph, for our base Hamiltonian. We calculate the optimal adiabatic schedule for the hypercube, and then interpolate between adiabatic and quantum walk searching, obtaining a family of hybrid algorithms. We show that all of these hybrid algorithms provide the quadratic quantum speed up when run with optimal parameter settings, which we determine and discuss in detail. We incorporate the effects of multiple runs of the same algorithm, noise applied to the qubits, and two types of problem misspecification, determining the optimal hybrid algorithm for each case. Our results reveal a rich structure of how these different computational mechanisms operate and should be balanced in different scenarios. For large systems with low noise and good control, quantum walk is the best choice, while hybrid strategies can mitigate the effects of many shortcomings in hardware and problem misspecification.
△ Less
Submitted 9 January, 2019; v1 submitted 1 September, 2017;
originally announced September 2017.
-
Graphical Structures for Design and Verification of Quantum Error Correction
Authors:
Nicholas Chancellor,
Aleks Kissinger,
Joschka Roffe,
Stefan Zohren,
Dominic Horsman
Abstract:
We introduce a high-level graphical framework for designing and analysing quantum error correcting codes, centred on what we term the coherent parity check (CPC). The graphical formulation is based on the diagrammatic tools of the zx-calculus of quantum observables. The resulting framework leads to a construction for stabilizer codes that allows us to design and verify a broad range of quantum cod…
▽ More
We introduce a high-level graphical framework for designing and analysing quantum error correcting codes, centred on what we term the coherent parity check (CPC). The graphical formulation is based on the diagrammatic tools of the zx-calculus of quantum observables. The resulting framework leads to a construction for stabilizer codes that allows us to design and verify a broad range of quantum codes based on classical ones, and that gives a means of discovering large classes of codes using both analytical and numerical methods. We focus in particular on the smaller codes that will be the first used by near-term devices. We show how CSS codes form a subset of CPC codes and, more generally, how to compute stabilizers for a CPC code. As an explicit example of this framework, we give a method for turning almost any pair of classical [n,k,3] codes into a [[2n - k + 2, k, 3]] CPC code. Further, we give a simple technique for machine search which yields thousands of potential codes, and demonstrate its operation for distance 3 and 5 codes. Finally, we use the graphical tools to demonstrate how Clifford computation can be performed within CPC codes. As our framework gives a new tool for constructing small- to medium-sized codes with relatively high code rates, it provides a new source for codes that could be suitable for emerging devices, while its zx-calculus foundations enable natural integration of error correction with graphical compiler toolchains. It also provides a powerful framework for reasoning about all stabilizer quantum error correction codes of any size.
△ Less
Submitted 23 June, 2023; v1 submitted 23 November, 2016;
originally announced November 2016.
-
Quantum walk transport properties on graphene structures
Authors:
Hamza Bougroura,
Habib Aissaoui,
Nicholas Chancellor,
Viv Kendon
Abstract:
We present numerical studies of quantum walks on \C60 and related graphene structures, to investigate their transport properties. Also known as a \emph{honeycomb lattice}, the lattice formed by carbon atoms in the graphene phase can be rolled up to form nanotubes of various dimensions. Graphene nanotubes have many important applications, some of which rely on their unusual electrical conductivity…
▽ More
We present numerical studies of quantum walks on \C60 and related graphene structures, to investigate their transport properties. Also known as a \emph{honeycomb lattice}, the lattice formed by carbon atoms in the graphene phase can be rolled up to form nanotubes of various dimensions. Graphene nanotubes have many important applications, some of which rely on their unusual electrical conductivity and related properties. Quantum walks on graphs provide an abstract setting in which to study such transport properties independent of the other chemical and physical properties of a physical substance. They can thus be used to further the understanding of mechanisms behind such properties. We find that nanotube structures are significantly more efficient in transporting a quantum walk than cycles of equivalent size, provided the symmetry of the structure is respected in how they are used. We find faster transport on zig-zag nanotubes compared to armchair nanotubes, which is unexpected given that for the actual materials the armchair nanotube is metallic, while the zig-zag is semiconducting.
△ Less
Submitted 8 January, 2018; v1 submitted 9 November, 2016;
originally announced November 2016.
-
Modernizing Quantum Annealing II: Genetic algorithms with the Inference Primitive Formalism
Authors:
Nicholas Chancellor
Abstract:
Quantum annealing allows for quantum fluctuations to be used used to assist in finding the solution to some of the worlds most challenging computational problems. Recently, this field has attracted much interest because of the construction of large-scale flux-qubit based quantum annealing devices. There has been recent work on [Chancellor NJP 19(2):023024, 2017] how the control protocols of these…
▽ More
Quantum annealing allows for quantum fluctuations to be used used to assist in finding the solution to some of the worlds most challenging computational problems. Recently, this field has attracted much interest because of the construction of large-scale flux-qubit based quantum annealing devices. There has been recent work on [Chancellor NJP 19(2):023024, 2017] how the control protocols of these devices can be modified so that individual annealer calls on real devices can take initial conditions. Development is being undertaken to implement such protocols in the quantum annealing devices designed by D-Wave Systems Inc. and these features will be available to customers soon. In this paper, I develop a formalism for algorithmic design in quantum annealers, which I call the `inference primitive' formalism. This formalism allows for a natural description of calls to quantum annealers with a general control structure. This more generalized control structure includes not only the ability to include initial conditions in an annealer run, but also to control the annealing schedules of qubits or clusters of qubits independently, thereby representing relative certainty values of different parts of a candidate solution. I discuss the compatability of such controls with a wide variety of other current efforts to improve the performance of annealers, such as non-stoquatic drivers, synchronizing freeze times for the qubits, and belief propagation techniques. To demonstrate the power of the formalism I present here, I discuss how this new formalism can be used to represent annealer implementations of genetic algorithms, and can represent the addition of genetic components to currently used algorithms. The new tools I develop will allow a more complete understanding of the algorithmic space available to quantum annealers, and thereby make the field more competitive.
△ Less
Submitted 28 November, 2017; v1 submitted 19 September, 2016;
originally announced September 2016.
-
Modernizing Quantum Annealing using Local Searches
Authors:
Nicholas Chancellor
Abstract:
I describe how real quantum annealers may be used to perform local (in state space) searches around specified states, rather than the global searches traditionally implemented in the quantum annealing algorithm. Such protocols will have numerous advantages over simple quantum annealing. By using such searches the effect of problem mis-specification can be reduced, as only energy differences betwee…
▽ More
I describe how real quantum annealers may be used to perform local (in state space) searches around specified states, rather than the global searches traditionally implemented in the quantum annealing algorithm. Such protocols will have numerous advantages over simple quantum annealing. By using such searches the effect of problem mis-specification can be reduced, as only energy differences between the searched states will be relevant. The quantum annealing algorithm is an analogue of simulated annealing, a classical numerical technique which has now been superseded. Hence, I explore two strategies to use an annealer in a way which takes advantage of modern classical optimization algorithms. Specifically, I show how sequential calls to quantum annealers can be used to construct analogues of population annealing and parallel tempering which use quantum searches as subroutines. The techniques given here can be applied not only to optimization, but also to sampling. I examine the feasibility of these protocols on real devices and note that implementing such protocols should require minimal if any change to the current design of the flux qubit-based annealers by D-Wave Systems Inc. I further provide proof-of-principle numerical experiments based on quantum Monte Carlo that demonstrate simple examples of the discussed techniques.
△ Less
Submitted 22 June, 2017; v1 submitted 22 June, 2016;
originally announced June 2016.
-
An Overview of Approaches to Modernize Quantum Annealing Using Local Searches
Authors:
Nicholas Chancellor
Abstract:
I describe how real quantum annealers may be used to perform local (in state space) searches around specified states, rather than the global searches traditionally implemented in the quantum annealing algorithm. The quantum annealing algorithm is an analogue of simulated annealing, a classical numerical technique which is now obsolete. Hence, I explore strategies to use an annealer in a way which…
▽ More
I describe how real quantum annealers may be used to perform local (in state space) searches around specified states, rather than the global searches traditionally implemented in the quantum annealing algorithm. The quantum annealing algorithm is an analogue of simulated annealing, a classical numerical technique which is now obsolete. Hence, I explore strategies to use an annealer in a way which takes advantage of modern classical optimization algorithms, and additionally should be less sensitive to problem mis-specification then the traditional quantum annealing algorithm.
△ Less
Submitted 21 June, 2016;
originally announced June 2016.
-
Experimental Freezing of mid-Evolution Fluctuations with a Programmable Annealer
Authors:
Nicholas Chancellor,
Gabriel Aeppli,
Paul A. Warburton
Abstract:
For randomly selected couplers and fields, the D-Wave device typically yields a highly Boltzmann like distribution [ indicating equilibration. These equilibrated data however do not contain much useful information about the dynamics which lead to equilibration. To illuminate the dynamics, special Hamiltonians can be chosen which contain large energy barriers. In this paper we generalize this appro…
▽ More
For randomly selected couplers and fields, the D-Wave device typically yields a highly Boltzmann like distribution [ indicating equilibration. These equilibrated data however do not contain much useful information about the dynamics which lead to equilibration. To illuminate the dynamics, special Hamiltonians can be chosen which contain large energy barriers. In this paper we generalize this approach by considering a class of Hamiltonians which map clusters of spin-like qubits into 'superspins', thereby creating an energy landscape where local minima are separated by large energy barriers. These large energy barriers allow us to observe signatures of the transverse field frozen. To study these systems, we assume that the these frozen spins are describes by the Kibble-Zurek mechanism which was originally developed to describe formation of topological defects in the early universe. It was soon realized that it also has applications in analogous superconductor systems and later realized to also be important for the transverse field Ising model . We demonstrate that these barriers block equilibration and yield a non-trivial distribution of qubit states in a regime where quantum effects are expected to be strong, suggesting that these data should contain signatures of whether the dynamics are fundamentally classical or quantum. We exhaustively study a class of 3x3 square lattice superspin Hamiltonians and compare the experimental results with those obtained by exact diagonalisation. We find that the best fit to the data occurs at finite transverse field. We further demonstrate that under the right conditions, the superspins can be relaxed to equilibrium, erasing the signature of the transverse field. These results are interesting for a number of reasons. They suggest a route to detect signatures of quantum mechanics on the device on a statistical level.
△ Less
Submitted 24 May, 2016;
originally announced May 2016.
-
A Direct Mapping of Max k-SAT and High Order Parity Checks to a Chimera Graph
Authors:
Nicholas Chancellor,
Stefan Zohren,
Paul A. Warburton,
Simon C. Benjamin,
Stephen Roberts
Abstract:
We demonstrate a direct mapping of max k-SAT problems (and weighted max k-SAT) to a Chimera graph, which is the non-planar hardware graph of the devices built by D-Wave Systems Inc. We further show that this mapping can be used to map a similar class of maximum satisfiability problems where the clauses are replaced by parity checks over potentially large numbers of bits. The latter is of specific…
▽ More
We demonstrate a direct mapping of max k-SAT problems (and weighted max k-SAT) to a Chimera graph, which is the non-planar hardware graph of the devices built by D-Wave Systems Inc. We further show that this mapping can be used to map a similar class of maximum satisfiability problems where the clauses are replaced by parity checks over potentially large numbers of bits. The latter is of specific interest for applications in decoding for communication. We discuss an example in which the decoding of a turbo code, which has been demonstrated to perform near the Shannon limit, can be mapped to a Chimera graph. The weighted max k-SAT problem is the most general class of satisfiability problems, so our result effectively demonstrates how any satisfiability problem may be directly mapped to a Chimera graph. Our methods faithfully reproduce the low energy spectrum of the target problems, so therefore may also be used for maximum entropy inference.
△ Less
Submitted 1 November, 2016; v1 submitted 3 April, 2016;
originally announced April 2016.
-
Circuit design for multi-body interactions in superconducting quantum annealing system with applications to a scalable architecture
Authors:
Nicholas Chancellor,
Stefan Zohren,
Paul A. Warburton
Abstract:
Quantum annealing provides a way of solving optimization problems by encoding them as Ising spin models which are implemented using physical qubits. The solution of the optimization problem then corresponds to the ground state of the system. Quantum tunnelling is harnessed to enable the system to move to the ground state in a potentially highly non-convex energy landscape. A major difficulty in en…
▽ More
Quantum annealing provides a way of solving optimization problems by encoding them as Ising spin models which are implemented using physical qubits. The solution of the optimization problem then corresponds to the ground state of the system. Quantum tunnelling is harnessed to enable the system to move to the ground state in a potentially highly non-convex energy landscape. A major difficulty in encoding optimization problems in physical quantum annealing devices is the fact that many real world optimization problems require interactions of higher connectivity as well as multi-body terms beyond the limitations of the physical hardware. In this work we address the question of how to implement multi-body interactions using hardware which natively only provides two-body interactions. The main result is an efficient circuit design of such multi-body terms using superconducting flux qubits in which effective N-body interactions are implemented using N ancilla qubits and only two inductive couplers. It is then shown how this circuit can be used as the unit cell of a scalable architecture by applying it to a recently proposed embedding technique for constructing an architecture of logical qubits with arbitrary connectivity using physical qubits which have nearest-neighbor four-body interactions. It is further shown that this design is robust to non-linear effects in the coupling loops as well as mismatches in some of the circuit parameters.
△ Less
Submitted 13 October, 2017; v1 submitted 31 March, 2016;
originally announced March 2016.
-
Maximum-Entropy Inference with a Programmable Annealer
Authors:
Nicholas Chancellor,
Szilard Szoke,
Walter Vinci,
Gabriel Aeppli,
Paul A. Warburton
Abstract:
Optimisation problems in science and engineering typically involve finding the ground state (i.e. the minimum energy configuration) of a cost function with respect to many variables. If the variables are corrupted by noise then this approach maximises the likelihood that the solution found is correct. An alternative approach is to make use of prior statistical information about the noise in conjun…
▽ More
Optimisation problems in science and engineering typically involve finding the ground state (i.e. the minimum energy configuration) of a cost function with respect to many variables. If the variables are corrupted by noise then this approach maximises the likelihood that the solution found is correct. An alternative approach is to make use of prior statistical information about the noise in conjunction with Bayes's theorem. The maximum entropy solution to the problem then takes the form of a Boltzmann distribution over the ground and excited states of the cost function. Here we use a programmable Josephson junction array for the information decoding problem which we simulate as a random Ising model in a field. We show experimentally that maximum entropy decoding at finite temperature can in certain cases give competitive and even slightly better bit-error-rates than the maximum likelihood approach at zero temperature, confirming that useful information can be extracted from the excited states of the annealing device. Furthermore we introduce a microscopic bit-by-bit analytical method which is agnostic to the specific application and use it to show that the annealing device samples from a highly Boltzmann-like distribution. Machines of this kind are therefore candidates for use in a wide variety of machine learning applications which exploit maximum entropy inference, including natural language processing and image recognition. We further show that the limiting factor for performance in our experiments is likely to be control errors rather than failure to reach equilibrium. Our work also provides a method for determining if a system is in equilibrium which can be easily generalized. We discuss possible applications of this method to spin glasses and probing the performance of the quantum annealing algorithm.
△ Less
Submitted 1 March, 2016; v1 submitted 26 June, 2015;
originally announced June 2015.
-
Pfaffian-like ground states for bosonic atoms and molecules in one-dimensional optical lattices
Authors:
Tanja Duric,
Nicholas Chancellor,
Philip J. D. Crowley,
Pierfrancesco Di Cintio,
Andrew G. Green
Abstract:
We study ground states and elementary excitations of a system of bosonic atoms and diatomic Feshbach molecules trapped in a one-dimensional optical lattice using exact diagonalization and variational Monte Carlo methods. We primarily study the case of an average filling of one boson per site. In agreement with bosonization theory, we show that the ground state of the system in the thermodynamic li…
▽ More
We study ground states and elementary excitations of a system of bosonic atoms and diatomic Feshbach molecules trapped in a one-dimensional optical lattice using exact diagonalization and variational Monte Carlo methods. We primarily study the case of an average filling of one boson per site. In agreement with bosonization theory, we show that the ground state of the system in the thermodynamic limit corresponds to the Pfaffian-like state when the system is tuned towards the superfluid-to-Mott insulator quantum phase transition. Our study clarifies the possibility of the creation of exotic Pfaffian-like states in realistic one-dimensional systems. We also present preliminary evidence that such states support non-Abelian anyonic excitations that have potential application for fault-tolerant topological quantum computation.
△ Less
Submitted 3 March, 2016; v1 submitted 17 March, 2015;
originally announced March 2015.
-
Interaction-induced anomalous quantum Hall state on the honeycomb lattice
Authors:
Tanja Duric,
Nicholas Chancellor,
Igor F. Herbut
Abstract:
We examine the existence of the interaction-generated quantum anomalous Hall phase on the honeycomb lattice. For the spinless model at half filling, the existence of a quantum anomalous Hall phase (Chern insulator phase) has been predicted using mean-field methods. However, recent exact diagonalization studies for small clusters with periodic boundary condition have not found a clear sign of an in…
▽ More
We examine the existence of the interaction-generated quantum anomalous Hall phase on the honeycomb lattice. For the spinless model at half filling, the existence of a quantum anomalous Hall phase (Chern insulator phase) has been predicted using mean-field methods. However, recent exact diagonalization studies for small clusters with periodic boundary condition have not found a clear sign of an interaction-driven Chern insulator phase. We use exact diagonalization method to study properties of small clusters with open boundary condition and, contrary to previous studies, we find clear signatures of the topological phase transition for finite size clusters. We also examine applicability of the entangled-plaquette state (correlator-product state) ansatz to describe the ground states of the system. Within this approach the lattice is covered with plaquettes and the ground state wave-function is written in terms of the plaquette coefficients. Configurational weights can then be optimized using a variational Monte Carlo algorithm. Using the entangled-plaquette state ansatz we study the ground state properties of the system for larger system sizes and show that the results agree with the exact diagonalization results for small clusters. This confirms validity of the entangled-plaquette state ansatz to describe the ground states of the system and provides further confirmation of the existence of the quantum anomalous Hall phase in the thermodynamic limit, as predicted by the mean-field theory calculations.
△ Less
Submitted 3 April, 2014; v1 submitted 22 January, 2014;
originally announced January 2014.
-
Quantification and Control of non-Markovian Evolution in Finite Quantum Systems via Feedback
Authors:
Nicholas Chancellor,
Christoph Petri,
Lorenzo Campos Venuti,
Anthony F. J. Levi,
Stephan Haas
Abstract:
We consider the unitary time evolution of continuous quantum mechanical systems confined to a cavity in contact with a finite bath of variable size. Measures for Markovianity for such finite system-bath configurations are developed in terms of Hilbert-Schmidt distances of time evolving wave packets. The relevant time scales are identified, which characterize pseudo-Markovian transient behavior, bo…
▽ More
We consider the unitary time evolution of continuous quantum mechanical systems confined to a cavity in contact with a finite bath of variable size. Measures for Markovianity for such finite system-bath configurations are developed in terms of Hilbert-Schmidt distances of time evolving wave packets. The relevant time scales are identified, which characterize pseudo-Markovian transient behavior, boundary scattering induced non-Markovian oscillations at intermediate times, and non-Markovian rephasing events at long time scales. It is shown how these time scales can be controlled by tunable parameters such as the bath size and the strength of the system-bath coupling.
△ Less
Submitted 21 May, 2014; v1 submitted 2 December, 2013;
originally announced December 2013.
-
Scalable universal holonomic quantum computation realized with an adiabatic quantum data bus and potential implementation using superconducting flux qubits
Authors:
Nicholas Chancellor,
Stephan Haas
Abstract:
In this paper we examine the use of an adiabatic quantum data transfer protocol to build a universal quantum computer. Single qubit gates are realized by using a bus protocol to transfer qubits of information down a spin chain with a unitary twist. This twist arises from altered couplings on the chain corresponding to unitary rotations performed on one region of the chain. We show how a controlled…
▽ More
In this paper we examine the use of an adiabatic quantum data transfer protocol to build a universal quantum computer. Single qubit gates are realized by using a bus protocol to transfer qubits of information down a spin chain with a unitary twist. This twist arises from altered couplings on the chain corresponding to unitary rotations performed on one region of the chain. We show how a controlled NOT gate can be realized by using a control qubit with Ising type coupling. The method discussed here can be extended to non-adiabatic quantum bus protocols. We also examine the potential of realizing such a quantum computer by using superconducting flux qubits.
△ Less
Submitted 21 March, 2013; v1 submitted 29 January, 2013;
originally announced January 2013.
-
Non-Markovian Equilibration Controlled by Symmetry Breaking
Authors:
Nicholas Chancellor,
Christoph Petri,
Stephan Haas
Abstract:
We study the effects of symmetry breaking on non-Markovian dynamics in various system-bath arrangements. It is shown that by breaking certain symmetries features signaling non-Markovian time evolution disappear within a finite time t_{g}. We demonstrate numerically that the scaling of t_{g} with the symmetry breaking strength is different for various types of symmetry. We provide a mathematical ex…
▽ More
We study the effects of symmetry breaking on non-Markovian dynamics in various system-bath arrangements. It is shown that by breaking certain symmetries features signaling non-Markovian time evolution disappear within a finite time t_{g}. We demonstrate numerically that the scaling of t_{g} with the symmetry breaking strength is different for various types of symmetry. We provide a mathematical explanation for these differences related to the spectrum of the total system-bath Hamiltonian and provide arguments that the scaling properties of t_{g} should be universal.
△ Less
Submitted 17 April, 2013; v1 submitted 23 January, 2013;
originally announced January 2013.