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

arXiv:quant-ph/9805086

Quantum Effects in Algorithms

Richard Jozsa

Published May 29, 1998• 15 citations
arXivHTMLPDF

Abstract

We discuss some seemingly paradoxical yet valid effects of quantum physics in information processing. Firstly, we argue that the act of ``doing nothing'' on part of an entangled quantum system is a highly non-trivial operation and that it is the essential ingredient underlying the computational speedup in the known quantum algorithms. Secondly, we show that the watched pot effect of quantum measurement theory gives the following novel computational possibility: suppose that we have a quantum computer with an on/off switch, programmed ready to solve a decision problem. Then (in certain circumstances) the mere fact that the computer would have given the answer if it were run, is enough for us to learn the answer, even though the computer is in fact not run.

DOI
10.48550/arxiv.quant-ph/9805086

Related papers

Reflections on the Role of Entanglement in the Explanation of Quantum Computational Speedup

Michael E. Cuffaro

Of the many and varied applications of quantum information theory, perhaps the most fascinating is the sub-field of quantum computation. In this sub-field, computational algorithms are designed which utilise the resources available in quantum systems in order to compute solutions to computational problems with, in some cases, exponentially fewer resources than any known classical algorithm. While the fact of quantum computational speedup is almost beyond doubt, the source of quantum speedup is still a matter of debate. In this paper I argue that entanglement is a necessary component for any explanation of quantum speedup and I address some purported counter-examples that some claim show that the contrary is true. In particular, I address Biham et al.'s mixed-state version of the Deutsch-Jozsa algorithm, and Knill \& Laflamme's deterministic quantum computation with one qubit (DQC1) model of quantum computation. I argue that these examples do not demonstrate that entanglement is unnecessary for the explanation of quantum speedup, but that they rather illuminate and clarify the role that entanglement does play.

•Dec 6, 2011•0 citations

WHAT IS QUANTUM COMPUTATION?

ARTUR K. EKERT, Patrick M. Hayden, Hitoshi Inamori +1 more

"Information is physical and any processing of information is always performed by physical means," an innocent-sounding statement, but its consequences are profound. When quantum effects become important, for example, at the level of single atoms and photons, the classical theory of computation becomes fundamentally inadequate. Entirely new modes of computation and information processing become possible. In the last few years there has been an explosion of theoretical and experimental research in quantum computation. In this brief review we describe some of these developments.

•May 1, 2001•16 citations

Counterfactual computation

Graeme Mitchison, Richard Jozsa

Suppose that we are given a quantum computer programmed ready to perform a computation if it is switched on. Counterfactual computation is a process by which the result of the computation may be learnt without actually running the computer. Such processes are possible within quantum physics and to achieve this effect a computer embodying the possibility of running the computation must be available, even though the computation is, in fact, not run. We study the possibilities and limitations of protocols for the counterfactual computation of decision problems (where the result r is either 0 or 1). If p⊂r denotes the probability of learning the result r 'for free' in a protocol, then one might hope to design a protocol which simultaneously has large p⊂0 and p⊂1. However, we prove that p⊂0 + p⊂1 ≤ 1 in any protocol of this type and derive further constraints on p⊂0 and p⊂1 in terms of N, the number of times that the computer is not run. In particular, we show that any protocol with p⊂0 + p⊂1 = 1 – ∈ must have N tending to infinity as ∈ tends to 0. We show that ‘interaction–free’ measurements can be regarded as counterfactual computations, and our results then imply that N must be large if the probability of interaction is to be close to zero. Finally, we consider some ways in which our formulation of counterfactual computation can be generalized.

arXiv:quant-ph/9907007•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•May 8, 2001•77 citations

A quantum view on convex optimization

Joran van Apeldoorn

Every day we need to make many decisions: what we should have for dinner, what to vote for, or whether to kiss that special person for the first time. There are also many decisions that need to be made at a larger scale, for example, groups, governments, and corporations have to make decisions in order to use their resources wisely. Every decision asks us to consider many possibilities and to try to get the optimal outcome (or more often than not, to simply avoid disaster). Making these decisions is further complicated by the constraints that are put on us. Even though people have become quite good at making decisions, the increasing complexity of the world around us means that `going with our guts' is often an ill-advised optimization strategy. The field of mathematics allows us to formulate an abstract version of some of the more complex problems we encounter, and allows us to quantify what the objectives and constraints are. For some problems mathematics even gives us a simple closed-form solution, e.g. many of us have learned in school how find the extreme points on a parabola. However, for many problems there is no such simple closed-form solution, the best we can do is to use a method, or algorithm, to construct a solution. This puts us in the realm of computer science. Computer science considers how to solve problems systematically, and more importantly how many steps the decision-making process has to take. Most optimization problems can be solved by simply listing all possible combinations of decisions and then searching for the best option, but as the number of decisions increases, so does the number of combinations. In fact, for many situations the number of possible combinations increases exponentially, making the process of writing down all the options impractical. Instead we often look for a smarter, more efficient algorithm, one that scales better with the problem size. It is not always easy (or even possible) to find an efficient algorithm. Consider the problem of finding the lowest place in the Swiss Alps. We may walk down into what seems the deepest valley, only to learn later that a farmer three valleys over has dug a really deep well. One of the problems in such a scenario is that we may find a local minimum, but due to a lack of structure in the problem we have no clear way of finding a global minimum. Some problems do have more structure, an important class of these is the class of convex optimization problems. Convex optimization problems have the useful property that local minima are also global minima. For our example about the Alps this means that, as long as we keep going down, we will always reach the lowest point. However, as anyone who ever went snowboarding can tell you, how you go down matters a lot for how fast you will get there. Apart from considering the structure of the problem we are trying to solve we should also consider what steps we can take to solve it. We may want to use pen and paper, use our laptop, or use a supercomputer, all of which function differently. However, these methods are not inherently different, with enough time we could perform the same computation as a supercomputer with nothing more than a pen and a piece of paper. Although this would be significantly slower, the scaling with the problem size would stay the same since the basic steps we can use are the same, only slower. What basic steps we may perform is ultimately dictated by the laws of physics: we can only change the state of our piece of paper, or our computer, in ways that are allowed by physics. Specifically, our piece of paper and our computers both follow the laws of classical physics, the physics that we see around us every day. During the 20th century our understanding of physics has changed and we now know that classical physics does not give a full description of the natural world. One of the places where classical physics breaks down is at the scale of atoms and elementary particles, at this small scale the universe is governed by the laws of quantum physics. Quantum physics predicts behavior that is not possible in classical physics. Particles might be in a superposition of many different classical states, only becoming a specific one of those states at random when interacting with our classical world via a measurement. Miraculously, and contrary to classical randomness, this quantum randomness does not stem from our inherent lack of knowledge about the particle, the different parts of the superposition are all present until we measure and can interfere with each other. A natural question to ask is whether these phenomena can be used to our benefit when performing computations. A computer that works according to the rules of quantum physics is called a Quantum computer, such devices have a wider range of basic operations that they can perform than classical computers do. This thesis asks the following central question can quantum computers solve convex optimization problems faster? In order to answer this question we consider a few different types of problem that we may encounter in convex optimization. If we have some black-box procedure to evaluate how good a proposed solution to a convex optimization problem is, for example a way of estimating the height of a point in the Alps or a method of estimating our profits given a business strategy, then a classical computer would have to try a lot of small changes in order to find the change that improves our objective the most. However, we show that a quantum computer can find the optimal direction for improvement exponentially faster. We then consider specific categories of convex optimization problems, mainly linear programming and semidefinite programming. These problem categories include many natural problems and have been widely used both for theoretical and practical purposes. For example, linear programming can be used for finding the optimal strategies of zero-sum games, coming up with a diet plan, or planning resources. Semidefinite programming is a generalization of linear programming and can additionally be useful for designing optimal experiments, approximately solving hard problems, or optimize processes involving quantum mechanics. Our quantum algorithms for these problems use a natural connection between quantum physics and semidefinite programming: the solutions to a semidefinite programming problem correspond to the states of a quantum system. We show that quantum computers can solve semidefinite programming problems and linear programming problems quadratically faster than a classical computer can. In fact, our algorithms take less time to solve the problem than that it would take to read through the whole input. We also take a more negative view and discuss the limitations of quantum computers. We show that, even though quantum computers can find the optimal direction of improvement exponentially faster, there is no general exponential speedup for finding the optimal value. We also show that in many ways our methods for solving linear and semidefinite programming problems are optimal: faster methods would not be able to read enough of the input to still get a good solution. To conclude, we showed that in a few different settings the answer to our central question is yes. The results in this dissertation show that quantum computers can solve some convex optimization problems faster, but there are also limits to this. There are still many open questions regarding convex optimization on quantum computers and we regard this topic as an important direction of future research.

•Feb 6, 2020•4 citations

WHAT IS QUANTUM COMPUTATION?

ARTUR K. EKERT, Patrick M. Hayden, Hitoshi Inamori +1 more

"Information is physical and any processing of information is always performed by physical means," an innocent-sounding statement, but its consequences are profound. When quantum effects become important, for example, at the level of single atoms and photons, the classical theory of computation becomes fundamentally inadequate. Entirely new modes of computation and information processing become possible. In the last few years there has been an explosion of theoretical and experimental research in quantum computation. In this brief review we describe some of these developments.

International Journal of Modern Physics A•Aug 10, 2001•13 citations

Variety of Effects of Decoherence in Quantum Algorithms

Jun HASEGAWA

Quantum computations have so far proved to be more powerful than classical computations, but quantum computers still have not been put into practical use due to several technical issues. One of the most serious problems for realizing quantum computers is decoherence that occurs inevitably since our apparatus are surrounded with environment and open systems. In this paper, we give some surveys on a variety of effects of decoherence in quantum algorithms such as Grover's database search and quantum walks, and we show how quantum algorithms work under decoherence, how sensitive they are against decoherence, and how to implement a robust quantum circuit.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2009•1 citation
We discuss some seemingly paradoxical yet valid effects of quantum physics in information processing. Firstly, we argue that the act of ``doing nothing'' on part of an entangled quantum system is a highly non-trivial operation and that it is the essential ingredient underlying the computational speedup in the known quantum algorithms. Secondly, we show that the watched pot effect of quantum measurement theory gives the following novel computational possibility: suppose that we have a quantum computer with an on/off switch, programmed ready to solve a decision problem. Then (in certain circumstances) the mere fact that the computer would have given the answer if it were run, is enough for us to learn the answer, even though the computer is in fact not run.
Of the many and varied applications of quantum information theory, perhaps the most fascinating is the sub-field of quantum computation. In this sub-field, computational algorithms are designed which utilise the resources available in quantum systems in order to compute solutions to computational problems with, in some cases, exponentially fewer resources than any known classical algorithm. While the fact of quantum computational speedup is almost beyond doubt, the source of quantum speedup is still a matter of debate. In this paper I argue that entanglement is a necessary component for any explanation of quantum speedup and I address some purported counter-examples that some claim show that the contrary is true. In particular, I address Biham et al.'s mixed-state version of the Deutsch-Jozsa algorithm, and Knill \& Laflamme's deterministic quantum computation with one qubit (DQC1) model of quantum computation. I argue that these examples do not demonstrate that entanglement is unnecessary for the explanation of quantum speedup, but that they rather illuminate and clarify the role that entanglement does play.
"Information is physical and any processing of information is always performed by physical means," an innocent-sounding statement, but its consequences are profound. When quantum effects become important, for example, at the level of single atoms and photons, the classical theory of computation becomes fundamentally inadequate. Entirely new modes of computation and information processing become possible. In the last few years there has been an explosion of theoretical and experimental research in quantum computation. In this brief review we describe some of these developments.
Suppose that we are given a quantum computer programmed ready to perform a computation if it is switched on. Counterfactual computation is a process by which the result of the computation may be learnt without actually running the computer. Such processes are possible within quantum physics and to achieve this effect a computer embodying the possibility of running the computation must be available, even though the computation is, in fact, not run. We study the possibilities and limitations of protocols for the counterfactual computation of decision problems (where the result r is either 0 or 1). If p⊂r denotes the probability of learning the result r 'for free' in a protocol, then one might hope to design a protocol which simultaneously has large p⊂0 and p⊂1. However, we prove that p⊂0 + p⊂1 ≤ 1 in any protocol of this type and derive further constraints on p⊂0 and p⊂1 in terms of N, the number of times that the computer is not run. In particular, we show that any protocol with p⊂0 + p⊂1 = 1 – ∈ must have N tending to infinity as ∈ tends to 0. We show that ‘interaction–free’ measurements can be regarded as counterfactual computations, and our results then imply that N must be large if the probability of interaction is to be close to zero. Finally, we consider some ways in which our formulation of counterfactual computation can be generalized.
Every day we need to make many decisions: what we should have for dinner, what to vote for, or whether to kiss that special person for the first time. There are also many decisions that need to be made at a larger scale, for example, groups, governments, and corporations have to make decisions in order to use their resources wisely. Every decision asks us to consider many possibilities and to try to get the optimal outcome (or more often than not, to simply avoid disaster). Making these decisions is further complicated by the constraints that are put on us. Even though people have become quite good at making decisions, the increasing complexity of the world around us means that `going with our guts' is often an ill-advised optimization strategy. The field of mathematics allows us to formulate an abstract version of some of the more complex problems we encounter, and allows us to quantify what the objectives and constraints are. For some problems mathematics even gives us a simple closed-form solution, e.g. many of us have learned in school how find the extreme points on a parabola. However, for many problems there is no such simple closed-form solution, the best we can do is to use a method, or algorithm, to construct a solution. This puts us in the realm of computer science. Computer science considers how to solve problems systematically, and more importantly how many steps the decision-making process has to take. Most optimization problems can be solved by simply listing all possible combinations of decisions and then searching for the best option, but as the number of decisions increases, so does the number of combinations. In fact, for many situations the number of possible combinations increases exponentially, making the process of writing down all the options impractical. Instead we often look for a smarter, more efficient algorithm, one that scales better with the problem size. It is not always easy (or even possible) to find an efficient algorithm. Consider the problem of finding the lowest place in the Swiss Alps. We may walk down into what seems the deepest valley, only to learn later that a farmer three valleys over has dug a really deep well. One of the problems in such a scenario is that we may find a local minimum, but due to a lack of structure in the problem we have no clear way of finding a global minimum. Some problems do have more structure, an important class of these is the class of convex optimization problems. Convex optimization problems have the useful property that local minima are also global minima. For our example about the Alps this means that, as long as we keep going down, we will always reach the lowest point. However, as anyone who ever went snowboarding can tell you, how you go down matters a lot for how fast you will get there. Apart from considering the structure of the problem we are trying to solve we should also consider what steps we can take to solve it. We may want to use pen and paper, use our laptop, or use a supercomputer, all of which function differently. However, these methods are not inherently different, with enough time we could perform the same computation as a supercomputer with nothing more than a pen and a piece of paper. Although this would be significantly slower, the scaling with the problem size would stay the same since the basic steps we can use are the same, only slower. What basic steps we may perform is ultimately dictated by the laws of physics: we can only change the state of our piece of paper, or our computer, in ways that are allowed by physics. Specifically, our piece of paper and our computers both follow the laws of classical physics, the physics that we see around us every day. During the 20th century our understanding of physics has changed and we now know that classical physics does not give a full description of the natural world. One of the places where classical physics breaks down is at the scale of atoms and elementary particles, at this small scale the universe is governed by the laws of quantum physics. Quantum physics predicts behavior that is not possible in classical physics. Particles might be in a superposition of many different classical states, only becoming a specific one of those states at random when interacting with our classical world via a measurement. Miraculously, and contrary to classical randomness, this quantum randomness does not stem from our inherent lack of knowledge about the particle, the different parts of the superposition are all present until we measure and can interfere with each other. A natural question to ask is whether these phenomena can be used to our benefit when performing computations. A computer that works according to the rules of quantum physics is called a Quantum computer, such devices have a wider range of basic operations that they can perform than classical computers do. This thesis asks the following central question can quantum computers solve convex optimization problems faster? In order to answer this question we consider a few different types of problem that we may encounter in convex optimization. If we have some black-box procedure to evaluate how good a proposed solution to a convex optimization problem is, for example a way of estimating the height of a point in the Alps or a method of estimating our profits given a business strategy, then a classical computer would have to try a lot of small changes in order to find the change that improves our objective the most. However, we show that a quantum computer can find the optimal direction for improvement exponentially faster. We then consider specific categories of convex optimization problems, mainly linear programming and semidefinite programming. These problem categories include many natural problems and have been widely used both for theoretical and practical purposes. For example, linear programming can be used for finding the optimal strategies of zero-sum games, coming up with a diet plan, or planning resources. Semidefinite programming is a generalization of linear programming and can additionally be useful for designing optimal experiments, approximately solving hard problems, or optimize processes involving quantum mechanics. Our quantum algorithms for these problems use a natural connection between quantum physics and semidefinite programming: the solutions to a semidefinite programming problem correspond to the states of a quantum system. We show that quantum computers can solve semidefinite programming problems and linear programming problems quadratically faster than a classical computer can. In fact, our algorithms take less time to solve the problem than that it would take to read through the whole input. We also take a more negative view and discuss the limitations of quantum computers. We show that, even though quantum computers can find the optimal direction of improvement exponentially faster, there is no general exponential speedup for finding the optimal value. We also show that in many ways our methods for solving linear and semidefinite programming problems are optimal: faster methods would not be able to read enough of the input to still get a good solution. To conclude, we showed that in a few different settings the answer to our central question is yes. The results in this dissertation show that quantum computers can solve some convex optimization problems faster, but there are also limits to this. There are still many open questions regarding convex optimization on quantum computers and we regard this topic as an important direction of future research.
"Information is physical and any processing of information is always performed by physical means," an innocent-sounding statement, but its consequences are profound. When quantum effects become important, for example, at the level of single atoms and photons, the classical theory of computation becomes fundamentally inadequate. Entirely new modes of computation and information processing become possible. In the last few years there has been an explosion of theoretical and experimental research in quantum computation. In this brief review we describe some of these developments.
Quantum computations have so far proved to be more powerful than classical computations, but quantum computers still have not been put into practical use due to several technical issues. One of the most serious problems for realizing quantum computers is decoherence that occurs inevitably since our apparatus are surrounded with environment and open systems. In this paper, we give some surveys on a variety of effects of decoherence in quantum algorithms such as Grover's database search and quantum walks, and we show how quantum algorithms work under decoherence, how sensitive they are against decoherence, and how to implement a robust quantum circuit.