Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

University of Chicago Press eBooks

Perspectives in Computation

Robert Geroch

Published Jan 1, 2009• 2 citations
Publisher

Abstract

Computation is the process of applying a procedure or algorithm to the solution of a mathematical problem. Mathematicians and physicists have been occupied for many decades pondering which problems can be solved by which procedures, and, for those that can be solved, how this can most efficiently be done. In recent years, quantum mechanics has augmented our understanding of the process of computation and of its limitations. Perspectives in Computation covers three broad topics: the computation process and its limitations, the search for computational efficiency, and the role of quantum mechani

DOI
10.7208/chicago/9780226288567.001.0001

Related papers

An algebraic approach for quantum computation

Quôc-Nam Trân, Jennifer R. Daniel, Valentin V. Andreev

Quantum computation is one of the very promising new fields of the new millennium for basic research in theoretical computer science and computational mathematics. Quantum computers have stimulated great interests due to their promise of being able to solve problems considered infeasible on current computers. From a computer scientist's and mathematician's point of view, the growth in the capacities of the underlying hardware is vital since an inefficient algorithm can solve the problem with the faster new hardware. For decades, this attitude was irrelevant but the deadline to change it is near. That is why quantum computation has led to rapid developments in physics, mathematics and computer science.This tutorial paper summarizes our year long series of multidisciplinary seminars on the topics of using computational algebra in quantum computation for finding new theoretical models for the upcoming generation of computers together with finding the models' computational abilities.

Journal of computing sciences in colleges•Oct 1, 2006•0 citations

What is Quantum Computation?

Apoorva D. Patel

Quantum computation is a rapidly progressing field today. What are its principles? In what sense is it distinct from conventional computation? What are its advantages and disadvantages? What type of problems can it address? How practical is it to make a quantum computer? I summarise some of the important concepts of quantum computation, in an attempt to answer these questions. A deeper understanding of them would pave the way for future development.

arXiv:quant-ph/9909082•Sep 27, 1999•0 citations

Quantum algorithms from the near to future term

Gregory Boyd

Many important physical and mathematical problems are difficult to solve on classical computers, resulting in difficulty in finding new advanced materials, simulating quantum field theories and solving large combinatorial optimisation tasks. Quantum computers have shown great promise in being able to solve these (and many other) problems faster than their classical counterparts, and therefore should be thoroughly investigated as a significant tool for enabling the acceleration of scientific progress. This work develops methods to tackle several problems across the spectrum of quantum algorithms, providing methods suitable for the near-term hardware, to the future where large fault-tolerant quantum computers exist. Therefore, the works in this thesis range from efficiently making use of limited quantum hardware to taking advantage of hardware benefits (e.g. excess qubits) as quantum computation advances. Covered topics include: an alternative paradigm for the optimisation of variational circuits and quantum neural networks; techniques for improving energy estimation of quantum states through the collection and processing of large amounts of randomised measurement data; the use of entanglement in guiding the automatic discovery of quantum circuits; investigating the role of symmetries in adiabatic state preparation of molecules and the large scale parallelisation of a common fault-tolerant subroutine, potentially producing large runtime speed-ups for the simulation of chemistry on quantum computers. Although there are many challenges remaining from both hardware and algorithms perspectives before the large-scale utility of quantum computers can be demonstrated, the contributions of this work make steps towards the efficient utilisation of quantum hardware that will be available in the coming years.

•Jan 1, 2025•0 citations

Classically-Boosted Quantum Optimization Algorithm

Guoming Wang

Considerable effort has been made recently in the development of heuristic quantum algorithms for solving combinatorial optimization problems. Meanwhile, these problems have been studied extensively in classical computing for decades. In this paper, we explore a natural approach to leveraging existing classical techniques to enhance quantum optimization. Specifically, we run a classical algorithm to find an approximate solution and then use a quantum circuit to search its "neighborhood" for higher-quality solutions. We propose the Classically-Boosted Quantum Optimization Algorithm (CBQOA) that is based on this idea and can solve a wide range of combinatorial optimization problems, including all unconstrained problems and many important constrained problems such as Max Bisection, Maximum Independent Set, Minimum Vertex Cover, Portfolio Optimization, Traveling Salesperson and so on. A crucial component of this algorithm is an efficiently-implementable continuous-time quantum walk (CTQW) on a properly-constructed graph that connects the feasible solutions. CBQOA utilizes this CTQW and the output of an efficient classical procedure to create a suitable superposition of the feasible solutions which is then processed in certain way. This algorithm has the merits that it solves constrained problems without modifying their cost functions, confines the evolution of the quantum state to the feasible subspace, and does not rely on efficient indexing of the feasible solutions. We demonstrate the applications of CBQOA to Max 3SAT and Max Bisection, and provide empirical evidence that it outperforms previous approaches on these problems.

arXiv:2203.13936•Mar 25, 2022•3 citations

The limits of computation

Mingji Xia, Zhengfeng Ji

The powerful idea of computation has accompanied the development of human civilization, has deeply changed the way we live and work, and has accelerated the advancement of many areas of sciences. In this article, we explore the power and limits of computation from several different perspectives. We will discuss topics from the models of computation and Church-Turing thesis, to the impact of the P versus NP problem and quantum computing on our understanding of the limits of computation. More concretely, we will explore the computability and the halting problem, the efficiency problem of computation, the P versus NP problem. We then move on to the discussion of quantum computation, quantum algorithm for factoring and its implications, quantum simulation and the relation between quantum and classical computations.

Chinese Science Bulletin (Chinese Version)•Jan 25, 2016•1 citation

Quantum computation

Jiannis K. Pachos

Computation is a process of performing a large number of simple operations. The main building blocks of classical computers are bits. Each of them can take either the value 0 or 1. A series of gates can change these values by acting on them selectively. This process is structured to fulfil a purpose. For example, if we are interested in adding two numbers, the numbers are encoded into bits and gates are performed such that the final state of the bits reveals the desired answer: a number which is the sum of the initial ones. While it is possible to build algorithms that can perform almost any computation, it is also desirable to find the answer within a reasonable length of time or with a reasonable amount of resources. There is an ever-growing demand in computational power for both scientific and commercial purposes. Indeed, it is surprisingly easy to find an application that can jam even the fastest computer. This fuels a vast effort in the research of information science to increase the speed and processing power of computers. Modern computational models are based on the universal Turing machine (Turing, 1937). This is a theoretical information processing model that employs the elementary gate processes described above. It can efficiently simulate any other device capable of performing an algorithmic process. Since the introduction of the Turing machine, physics has influenced computation in many ways.

Cambridge University Press eBooks•Apr 12, 2012•0 citations
Computation is the process of applying a procedure or algorithm to the solution of a mathematical problem. Mathematicians and physicists have been occupied for many decades pondering which problems can be solved by which procedures, and, for those that can be solved, how this can most efficiently be done. In recent years, quantum mechanics has augmented our understanding of the process of computation and of its limitations. Perspectives in Computation covers three broad topics: the computation process and its limitations, the search for computational efficiency, and the role of quantum mechani
Quantum computation is one of the very promising new fields of the new millennium for basic research in theoretical computer science and computational mathematics. Quantum computers have stimulated great interests due to their promise of being able to solve problems considered infeasible on current computers. From a computer scientist's and mathematician's point of view, the growth in the capacities of the underlying hardware is vital since an inefficient algorithm can solve the problem with the faster new hardware. For decades, this attitude was irrelevant but the deadline to change it is near. That is why quantum computation has led to rapid developments in physics, mathematics and computer science.This tutorial paper summarizes our year long series of multidisciplinary seminars on the topics of using computational algebra in quantum computation for finding new theoretical models for the upcoming generation of computers together with finding the models' computational abilities.
Many important physical and mathematical problems are difficult to solve on classical computers, resulting in difficulty in finding new advanced materials, simulating quantum field theories and solving large combinatorial optimisation tasks. Quantum computers have shown great promise in being able to solve these (and many other) problems faster than their classical counterparts, and therefore should be thoroughly investigated as a significant tool for enabling the acceleration of scientific progress. This work develops methods to tackle several problems across the spectrum of quantum algorithms, providing methods suitable for the near-term hardware, to the future where large fault-tolerant quantum computers exist. Therefore, the works in this thesis range from efficiently making use of limited quantum hardware to taking advantage of hardware benefits (e.g. excess qubits) as quantum computation advances. Covered topics include: an alternative paradigm for the optimisation of variational circuits and quantum neural networks; techniques for improving energy estimation of quantum states through the collection and processing of large amounts of randomised measurement data; the use of entanglement in guiding the automatic discovery of quantum circuits; investigating the role of symmetries in adiabatic state preparation of molecules and the large scale parallelisation of a common fault-tolerant subroutine, potentially producing large runtime speed-ups for the simulation of chemistry on quantum computers. Although there are many challenges remaining from both hardware and algorithms perspectives before the large-scale utility of quantum computers can be demonstrated, the contributions of this work make steps towards the efficient utilisation of quantum hardware that will be available in the coming years.
Considerable effort has been made recently in the development of heuristic quantum algorithms for solving combinatorial optimization problems. Meanwhile, these problems have been studied extensively in classical computing for decades. In this paper, we explore a natural approach to leveraging existing classical techniques to enhance quantum optimization. Specifically, we run a classical algorithm to find an approximate solution and then use a quantum circuit to search its "neighborhood" for higher-quality solutions. We propose the Classically-Boosted Quantum Optimization Algorithm (CBQOA) that is based on this idea and can solve a wide range of combinatorial optimization problems, including all unconstrained problems and many important constrained problems such as Max Bisection, Maximum Independent Set, Minimum Vertex Cover, Portfolio Optimization, Traveling Salesperson and so on. A crucial component of this algorithm is an efficiently-implementable continuous-time quantum walk (CTQW) on a properly-constructed graph that connects the feasible solutions. CBQOA utilizes this CTQW and the output of an efficient classical procedure to create a suitable superposition of the feasible solutions which is then processed in certain way. This algorithm has the merits that it solves constrained problems without modifying their cost functions, confines the evolution of the quantum state to the feasible subspace, and does not rely on efficient indexing of the feasible solutions. We demonstrate the applications of CBQOA to Max 3SAT and Max Bisection, and provide empirical evidence that it outperforms previous approaches on these problems.
The powerful idea of computation has accompanied the development of human civilization, has deeply changed the way we live and work, and has accelerated the advancement of many areas of sciences. In this article, we explore the power and limits of computation from several different perspectives. We will discuss topics from the models of computation and Church-Turing thesis, to the impact of the P versus NP problem and quantum computing on our understanding of the limits of computation. More concretely, we will explore the computability and the halting problem, the efficiency problem of computation, the P versus NP problem. We then move on to the discussion of quantum computation, quantum algorithm for factoring and its implications, quantum simulation and the relation between quantum and classical computations.
Computation is a process of performing a large number of simple operations. The main building blocks of classical computers are bits. Each of them can take either the value 0 or 1. A series of gates can change these values by acting on them selectively. This process is structured to fulfil a purpose. For example, if we are interested in adding two numbers, the numbers are encoded into bits and gates are performed such that the final state of the bits reveals the desired answer: a number which is the sum of the initial ones. While it is possible to build algorithms that can perform almost any computation, it is also desirable to find the answer within a reasonable length of time or with a reasonable amount of resources. There is an ever-growing demand in computational power for both scientific and commercial purposes. Indeed, it is surprisingly easy to find an application that can jam even the fastest computer. This fuels a vast effort in the research of information science to increase the speed and processing power of computers. Modern computational models are based on the universal Turing machine (Turing, 1937). This is a theoretical information processing model that employs the elementary gate processes described above. It can efficiently simulate any other device capable of performing an algorithmic process. Since the introduction of the Turing machine, physics has influenced computation in many ways.