Quantum technology and its application in quantum computing has been gaining relevance and making incredible strides in the achievement of practical implementations of this new form of hardware acceleration. However, in order to really succeed as a computational choice in the many application fields — from science to economy—, the devices need to be programmable and within reach to non-quantum users. There are multiple approaches to solve the quantum computing riddle. This paper looks at two of them, Boson sampling and qubit gate-based quantum accelerators, and compares their implementation and programmability of a common problem: the maximum clique problem.
Quantum technology and its application in quantum computing has been gaining relevance and making incredible strides in the achievement of practical implementations of this new form of hardware acceleration. However, in order to really succeed as a computational choice in the many application fields — from science to economy—, the devices need to be programmable and within reach to non-quantum users. There are multiple approaches to solve the quantum computing riddle. This paper looks at two of them, Boson sampling and qubit gate-based quantum accelerators, and compares their implementation and programmability of a common problem: the maximum clique problem.
Two of the most promising computational models for quantum computing are the qubit-based model and the continuous variable model, which result in two different computational approaches, namely the qubit gate model and boson sampling. The qubit gate model is a universal form of quantum computation that relies heavily on the principles of superposition and entanglement to solve problems using qubits based on technologies ranging from magnetic fields created from superconducting materials to the spins of valence electrons in atoms. Boson sampling is a non-universal form of quantum computation that uses bosons as continuous-variable values for its computation. Both models show promising prospects for useful quantum advantages over classical computers, but these models are fundamentally different, not only on their technologies but on their applications. Each model excels in different sets of applications.\nA direct comparison for solving a problem using qubit gate models and boson sampling allows one to better understand not only the individual technologies, but how to decide which model is better suited to solving a given problem and how to start development on solving the given problem. This thesis uses the maximum clique problem to examine the application development process in the qubit gate model and boson sampling as well as a comparison of other known algorithms to the maximum clique problem. The maximum clique problem is an NP-Hard problem concerned with finding the largest fully-connected subgraph. The qubit gate model algorithm to the maximum clique problem is a novel algorithm.
Abstract Quantum computing is gaining popularity across a wide range of scientific disciplines due to its potential to solve long-standing computational problems that are considered intractable with classical computers. One promising area where quantum computing has potential is in the speed-up of NP -hard optimisation problems that are common in industrial areas such as logistics and finance. Newcomers to the field of quantum computing who are interested in using this technology to solve optimisation problems do not have an easily accessible source of information on the current capabilities of quantum computers and algorithms. This paper aims to provide a comprehensive overview of the theory of quantum optimisation techniques and their practical application, focusing on their near-term potential for noisy intermediate scale quantum devices. The paper starts by drawing parallels between classical and quantum optimisation problems, highlighting their conceptual similarities and differences. Two main paradigms for quantum hardware are then discussed: analogue and gate-based quantum computers. While analog devices such as quantum annealers are effective for some optimisation problems, they have limitations and cannot be used for universal quantum computation. In contrast, gate-based quantum computers offer the potential for universal quantum computation, but they face challenges with hardware limitations and accurate gate implementation. The paper provides a detailed mathematical discussion with references to key works in the field, as well as a more practical discussion with relevant examples. The most popular techniques for quantum optimisation on gate-based quantum computers, the quantum approximate optimisation algorithm and the quantum alternating operator ansatz framework, are discussed in detail. However, it is still unclear whether these techniques will yield quantum advantage, even with advancements in hardware and noise reduction. The paper concludes with a discussion of the challenges facing quantum optimisation techniques and the need for further research and development to identify new, effective methods for achieving quantum advantage.
Boson sampling is a computational problem that has recently been proposed as a candidate to obtain an unequivocal quantum computational advantage. The problem consists in sampling from the output distribution of indistinguishable bosons in a linear interferometer. There is strong evidence that such an experiment is hard to classically simulate, but it is naturally solved by dedicated photonic quantum hardware, comprising single photons, linear evolution, and photodetection. This prospect has stimulated much effort resulting in the experimental implementation of progressively larger devices. We review recent advances in photonic boson sampling, describing both the technological improvements achieved and the future challenges. We also discuss recent proposals and implementations of variants of the original problem, theoretical issues occurring when imperfections are considered, and advances in the development of suitable techniques for validation of boson sampling experiments. We conclude by discussing the future application of photonic boson sampling devices beyond the original theoretical scope.
As this century unfolds we will witness the rise of the quantum computer. A quantum computer is a device that utilizes the laws of one of the most fundamental theories of physics— quantum mechanics. By utilizing properties of quantum mechanics a quantum computer is able to perform certain information processing tasks much more effciently than an ordinary classical computer. The last century of modern society was revolutionized by some of the simplest ideas in quantum mechanics like energy quantization and quantum tunnelling, which led to technologies like the laser and the transistor. We can expect to see additional technological revolutions occur in this century since we are beginning to build technologies with some of the more complex properties of quantum mechanics such as quantum entanglement and quantum superposition. These quantum effects make more radical technologies like the quantum computer possible. This thesis is based upon the work I have done during my PhD candidature at Macquarie University. In this work we develop quantum technologies that are directed towards realising a quantum computer. Specifically, we have made many theoretical advancements in a type of quantum information processing protocol called Boson Sampling. This device effciently simulates the interaction of quantum particles called bosons, which no classical computer can effciently simulate. In this thesis we explore quantum random walks, which are the basis of how the bosons in Boson Sampling interfere with each other. We explore implementing BosonSampling using the most readily available photon source technology. We invented a completely new architecture which can implement Boson Sampling in time rather than space and has since been used to make the worlds largest Boson Sampling experiment ever performed. We look at variations to the traditional Boson Sampling architecture by considering other quantum states of light. We show a worlds first application inspired by Boson Sampling in quantum metrology where measurements may be made more accurately than with any classical method. Lastly, dealing with Boson Sampling, we look at reformulating the formalism of Boson Sampling using a quantum optics approach. In addition, but not related to BosonSampling, we show a protocol for effciently generating large-photon Fock states, which are a type of quantum state of light, that are useful for quantum computation. Also, we show a method for generating a specific quantum state of light that is useful for quantum error correction — an essential component of realising a quantum computer — by coupling together light and atoms.
Abstract Boson Sampling is a task that is conjectured to be computationally hard for a classical computer, but which can be efficiently solved by linear-optical interferometers with Fock state inputs. Significant advances have been reported in the last few years, with demonstrations of small- and medium-scale devices, as well as implementations of variants such as Gaussian Boson Sampling. Besides the relevance of this class of computational models in the quest for unambiguous experimental demonstrations of quantum advantage, recent results have also proposed the first applications for hybrid quantum computing. Here, we introduce the adoption of non-linear photon–photon interactions in the Boson Sampling framework, and analyze the enhancement in complexity via an explicit linear-optical simulation scheme. By extending the computational expressivity of Boson Sampling, the introduction of non-linearities promises to disclose novel functionalities for this class of quantum devices. Hence, our results are expected to lead to new applications of near-term, restricted photonic quantum computers.
This paper is devoted to the evaluation of the hardware resources of computer systems for solving a computationally expensive problem such as the calculation of the probability distributions of statistics by the second multiplicity method based on ∆-exact approximations of samples with a size of 320-1280 characters and an alphabet power of 128-256 characters.The accuracy is ∆ = 10 -5 and the total solution time should not exceed 30 days or 2.592 × 10 6 seconds for 24/7 computing.Owing to the use of the properties of the second multiplicity method, the computational complexity of the calculations can be brought within the range of 9.68 × 10 22 -1.60 × 10 52 operations with the number of tested vectors at 6.50 × 10 23 -1.39 × 10 50 .The solution of this problem for the specified parameters of samples during the given time requires hardware resources which cannot be provided by modern computer technology such as processors, graphics accelerators and programmable logic integrated circuits.Therefore, in this paper, we analyze the possibilities of promising quantum and photon technologies for solving the problem with the given parameters.The main advantage of quantum computer systems is the high speed of calculations for all possible parameter values.However, quantum acceleration will not be achieved to calculate the probability distributions of statistics due to the need to check all the obtained solutions.Here, the number of obtained solutions corresponds to the dimension of the problem.In addition, due to the current development level of quantum hardware components, it is impossible to create and use 120 qubit quantum computers for the solution of the considered problem.Photon computers can provide high computation speeds at low power consumptions and require the smallest number of nodes to solve the considered problem.However, unsolved problems with the physical implementation of efficient memory elements and the lack of available hardware components make the use of photon computer technologies impossible for calculating the probability distributions of statistics in the near future (5-7 years).Therefore, it is most reasonable to use hybrid computer systems containing nodes of different architectures.To solve the problem on various hardware platforms (general purpose processors, GPUs and FPGAs) and configurations of hybrid computer systems, we suggest to use the architecture-independent high-level programming language SET@L.The language combines the representation of calculations as sets and collections (based on the alternative set theory of P. Vopenka), the absolutely parallel form of the problem represented as an information graph and the paradigm of aspect-oriented programming.