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

ACM SIGPLAN Fortran Forum

Quantum computing in Fortran

Adriaan Albert Markus

Published Aug 1, 2004• 2 citations
Publisher

Abstract

Quantum computing is the delicate art of using a quantum-mechanical system to perform some kind of computation. Such a system differs in a number of significant ways from ordinary computers:• A quantum computer actually does a lot of computations at the same time, each solution is represented by a particular possible state. This is inherent to the physical properties of such a system.• Unless you are sure that you have reached the final (unique) solution, you can not "look" at the "values" of the variables in the computer program that is being run: since all solutions are possible at the same time, observing the values will influence the system and put it into one particular, but otherwise arbitrary, state.• All computations must be reversible, that is, a statement like "a = 5" can only appear in the initialization phase of a program, because the previous value will be lost. On the other hand, a statement like "a = a + 5" is reversible, since you can retrieve the original value.The properties of such a quantum computer make it possible to devise very efficient algorithms. One such algorithm, described by L. Grover (see the references), is searching in an unsorted array of items. With ordinary computers this can not be done more efficiently than in O (N) steps (an exhaustive search: each item is examined in the worst case), with this quantum algorithm, however, the number of steps needed is O (N 1/2 ).Devising quantum algorithms requires a thorough understanding of quantum mechanics, there is no doubt about that. Another question is: do we need quantum computers and special programming languages to program (or perhaps emulate) these algorithms? This article tries to show that, at least for the quantum search algorithm, a classical programming language like Fortran is quite fit (yes, the pun is fortunate).

DOI
10.1145/1024334.1024335

Related papers

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

Quantum Computing: State-of-Art and Challenges

Juliana Kaizer Vizzotto

In this article we review the concept of quantum computing and briefly discuss the state-of-art and some actual challenges in the field of software (i.e. programming languages and algorithms) for quantum computing.

Workshop-School on Theoretical Computer Science•Oct 1, 2013•7 citations

Some quantum search algorithms for arbitrary initial amplitude distribution

Hiromi Miyajima, Noritaka Shigei, Keisuke Arima

For searching any item in an unsorted database with N items, Grover's quantum searching algorithm takes only O(√N) steps, which is much faster than O(N) steps required for a classical computer. However, it is known that Grover's algorithm is effective only in the case where the initial amplitude distribution of dataset is uniform. On the other hand, Ventura has also proposed a quantum searching algorithm. The algorithm is effective only in the special case for the initial amplitude distribution. Therefore, we have proposed an effective quantum searching algorithm in another case in the previous paper. In this paper, we generalize the previous algorithm and propose several effective algorithms in several cases where initial amplitude distributions of dataset are non-uniform. Further, in order to show the effectiveness of the algorithms, we analyze their dynamics.

International Conference on Natural Computation (ICNC)•Aug 1, 2010•4 citations

Quantum algorithms: an overview

Ashley Montanaro

Abstract Quantum computers are designed to outperform standard computers by running quantum algorithms. Areas in which quantum algorithms can be applied include cryptography, search and optimisation, simulation of quantum systems and solving large systems of linear equations. Here we briefly survey some known quantum algorithms, with an emphasis on a broad overview of their applications rather than their technical details. We include a discussion of recent developments and near-term applications of quantum algorithms.

arXiv:1511.04206•npj Quantum Information•Jan 12, 2016•1,217 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•4 citations

5 Four myths about quantum computing

Koen Groenland

Four myths about quantum computingThis chapter relies on a bit of quantum physics jargon.See the chapter 'An introduction to the quantum world' for a quick introduction. Myth 1: Quantum computers find all solutions at onceThis myth is likely the most technical, and builds on a misinterpretation of the concept of superposition.A single qubit can be in two states at the same time (0 and 1), two qubits can represent four states (00, 01, 10, 11), and three qubits are potentially in eight unique configurations simultaneously.As we increase the number of qubits, this number of coexisting states scales exponentially!This means that a mere 1000 qubits can effectively 'store' 2 1000 unique values, all at the same time.That's an incomprehensibly large number, much more than there are atoms in the visible universe.Even the fastest computers in the world couldn't loop through all these states in a lifetime.Each of these states can be interpreted like a file on a computer, be it an Excel spreadsheet, a web page, a CAD drawing, or whatever kind of data we choose to work with.A smart computer scientist can also devise a way to make 1000 bits represent 'solutions' to a problem.For example, imagine that we want to find an optimal aeroplane wing that generates incredible lift while requiring as few materials as possible.Using quantum superposition, we might represent 2 1000 such wings simultaneously.We picked the example of aeroplane wings because simulating their aerodynamic properties requires a pretty hefty computation.Let's assume that we have written such a computer program that accurately simulates any wing.Let's call that program f .It will output 1 if the wing works well (according to whatever metric), and 0 otherwise.Surely, the program takes a very large number of computation steps, which we'll call T. The program will need some input, denoted by x , which is a 1000-bit description of all the relevant properties of a hypothetical aeroplane wing.In other words, the computer program computes f (x) = 1 if x is a fantastic wing, and f (x) = 0 if it's rubbish.Now, a quantum computer should be able to execute any classical function, right?We should be able to run f on a quantum computer, but now we have the unique feature that the 1000-qubit input can represent a humongous number of potential aeroplane wings at the same time.By doing a mere T computational steps, we can check the properties of 2 1000 solutions!

Amsterdam University Press eBooks•Mar 9, 2025•0 citations
Quantum computing is the delicate art of using a quantum-mechanical system to perform some kind of computation. Such a system differs in a number of significant ways from ordinary computers:• A quantum computer actually does a lot of computations at the same time, each solution is represented by a particular possible state. This is inherent to the physical properties of such a system.• Unless you are sure that you have reached the final (unique) solution, you can not "look" at the "values" of the variables in the computer program that is being run: since all solutions are possible at the same time, observing the values will influence the system and put it into one particular, but otherwise arbitrary, state.• All computations must be reversible, that is, a statement like "a = 5" can only appear in the initialization phase of a program, because the previous value will be lost. On the other hand, a statement like "a = a + 5" is reversible, since you can retrieve the original value.The properties of such a quantum computer make it possible to devise very efficient algorithms. One such algorithm, described by L. Grover (see the references), is searching in an unsorted array of items. With ordinary computers this can not be done more efficiently than in O (N) steps (an exhaustive search: each item is examined in the worst case), with this quantum algorithm, however, the number of steps needed is O (N 1/2 ).Devising quantum algorithms requires a thorough understanding of quantum mechanics, there is no doubt about that. Another question is: do we need quantum computers and special programming languages to program (or perhaps emulate) these algorithms? This article tries to show that, at least for the quantum search algorithm, a classical programming language like Fortran is quite fit (yes, the pun is fortunate).
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.
For searching any item in an unsorted database with N items, Grover's quantum searching algorithm takes only O(√N) steps, which is much faster than O(N) steps required for a classical computer. However, it is known that Grover's algorithm is effective only in the case where the initial amplitude distribution of dataset is uniform. On the other hand, Ventura has also proposed a quantum searching algorithm. The algorithm is effective only in the special case for the initial amplitude distribution. Therefore, we have proposed an effective quantum searching algorithm in another case in the previous paper. In this paper, we generalize the previous algorithm and propose several effective algorithms in several cases where initial amplitude distributions of dataset are non-uniform. Further, in order to show the effectiveness of the algorithms, we analyze their dynamics.
Abstract Quantum computers are designed to outperform standard computers by running quantum algorithms. Areas in which quantum algorithms can be applied include cryptography, search and optimisation, simulation of quantum systems and solving large systems of linear equations. Here we briefly survey some known quantum algorithms, with an emphasis on a broad overview of their applications rather than their technical details. We include a discussion of recent developments and near-term applications of quantum algorithms.
Four myths about quantum computingThis chapter relies on a bit of quantum physics jargon.See the chapter 'An introduction to the quantum world' for a quick introduction. Myth 1: Quantum computers find all solutions at onceThis myth is likely the most technical, and builds on a misinterpretation of the concept of superposition.A single qubit can be in two states at the same time (0 and 1), two qubits can represent four states (00, 01, 10, 11), and three qubits are potentially in eight unique configurations simultaneously.As we increase the number of qubits, this number of coexisting states scales exponentially!This means that a mere 1000 qubits can effectively 'store' 2 1000 unique values, all at the same time.That's an incomprehensibly large number, much more than there are atoms in the visible universe.Even the fastest computers in the world couldn't loop through all these states in a lifetime.Each of these states can be interpreted like a file on a computer, be it an Excel spreadsheet, a web page, a CAD drawing, or whatever kind of data we choose to work with.A smart computer scientist can also devise a way to make 1000 bits represent 'solutions' to a problem.For example, imagine that we want to find an optimal aeroplane wing that generates incredible lift while requiring as few materials as possible.Using quantum superposition, we might represent 2 1000 such wings simultaneously.We picked the example of aeroplane wings because simulating their aerodynamic properties requires a pretty hefty computation.Let's assume that we have written such a computer program that accurately simulates any wing.Let's call that program f .It will output 1 if the wing works well (according to whatever metric), and 0 otherwise.Surely, the program takes a very large number of computation steps, which we'll call T. The program will need some input, denoted by x , which is a 1000-bit description of all the relevant properties of a hypothetical aeroplane wing.In other words, the computer program computes f (x) = 1 if x is a fantastic wing, and f (x) = 0 if it's rubbish.Now, a quantum computer should be able to execute any classical function, right?We should be able to run f on a quantum computer, but now we have the unique feature that the 1000-qubit input can represent a humongous number of potential aeroplane wings at the same time.By doing a mere T computational steps, we can check the properties of 2 1000 solutions!