ACM SIGACT News

Guest Column

Cristian S. Calude, Elena Calude, Michael J. Dinneen

Published Mar 9, 2015• 25 citations

Abstract

The paper presents a brief introduction to quantum computing with focus on the adiabatic model which is illustrated with the commercial D-Wave computer. We also include new theory and experimental work done on the D-Wave computer. Finally we discuss a hybrid method of combining classical and quantum computing and a few open problems.

DOI: 10.1145/2744447.2744459

Related papers

Notes on Adiabatic Quantum Computers

Boaz Tamir, Eliahu Cohen

We discuss in this chapter the basics of adiabatic computation, as well as some physical implementations. After a short introduction of the quantum circuit model, we describe quantum adiabatic computation, quantum annealing, and the strong relations between the three. We conclude with a brief presentation of the D-Wave computer and some future challenges.

arXiv:1512.07617Dec 23, 20150 citations

Guest Column

Carlo Mereghetti, Beatrice Palano

Quantum computing is a prolific research area, halfway between physics and computer science [27, 29, 52]. Most likely, its origins may be dated back to 70's, when some works on quantum information began to appear (see, e.g., [34, 37]). In early 80's, R.P. Feynman suggested that the computational power of quantum mechanical processes might be beyond that of traditional computation models [25]. Almost at the same time, P. Benioff already proved that such processes are at least as powerful as Turing machines [9]. In 1985, D. Deutsch [22] proposed the notion of a quantum Turing machine as a physically realizable model for a quantum computer. From the point of view of structural complexity, E. Bernstein and U. Vazirani introduced in [20] the class BQP of problems solvable in polynomial time on quantum Turing machines, focusing attention on relations with the corresponding deterministic and probabilistic classes P and BPP, respectively. Several works in the literature explored classical issues in complexity theory from the quantum paradigm perspective (see, e.g., [7, 60, 61]).

ACM SIGACT NewsOct 17, 20214 citations

The Promise and Challenges of Quantum Computing

Mark B. Ritter

This brief overview of quantum computing gives an intuitive, albeit incomplete view of why it shows promise over any known classical approach to computing. The difficulty of making a qubit which allows us to protect and control quantum information will be illustrated in an overview of existing quantum technologies, including ions, superconducting qubits, spins and defects in solids. Finally, I will review a few of the problems which may benefit most from quantum computing and why many in industry are excited by the prospects.

International Symposium on VLSI Technology, Systems and Applications (VLSI-TSA)Aug 1, 20204 citations

Adiabatic Quantum Computing

Sebastian D. Pinski

Adiabatic Quantum Computing (AQC) is a relatively new subject in the world of quantum computing, let alone Physics. Inspiration for this project has come from recent controversy around D-Wave Systems in British Columbia, Canada, who claim to have built a working AQC which is now commercially available and hope to be distributing a 1024 qubit chip by the end of 2008. Their 16 qubit chip was demonstrated online for the Supercomputing 2007 conference within which a few small problems were solved; although the explanations that journalists and critics received were minimal and very little was divulged in the question and answer session. This 'unconvincing' demonstration has caused physicists and computer scientists to hit back at D-Wave. The aim of this project is to give an introduction to the historic advances in classical and quantum computing and to explore the methods of AQC. Through numerical simulations an algorithm for the Max Independent Set problem is empirically obtained.

arXiv:1108.0560Aug 2, 20111 citation

Quantum Computing: Predictions and Challenges

S. P. Kulik

Abstract A brief overview of the state of the art in the field of quantum computing is presented and the main problems in the construction of full-scale quantum computers, as well as ways to solve them, are discussed.

Bulletin of the Lebedev Physics InstituteDec 1, 20232 citations

Nonperturbative Methods in Quantum Field Theory

Dorota M. Grabowska

There are many fundamental questions in particle and nuclear physics that cannot be addressed via classical computing techniques. These include the equation of state for finite density nuclear matter, real-time dynamics of quantum field theories from first-principles and non-perturbative aspects of chiral gauge theories. In recent years quantum computing hardware has seen dramatic advancements, which have brought with them the possibility to apply quantum computing to these and other open problems in high energy physics. In this talk, after a brief introduction to quantum computing, I will discuss my recent work towards the quantum simulation of lower-dimensional lattice gauge theories, focusing on the interplay between Gauss’ law, gauge redundancies and (un)favourable resource scaling.

Jan 1, 20220 citations