※The painter ChatGPT “A visually striking image representing a quantum computer.”
Quantum Computing and Quantum Mechanical Time
In my previous post:
I explained that quantum mechanical time (relativistic time) is expressed by complex function
\[ \small \zeta = te^{i\omega t}, \]
and that the path length can be calculated to approximate
\[ \small T(t) = \int_0^t \sqrt{1+\omega^2u^2} du \approx \frac{1}{2}\omega t^2. \]
In other words, the length of time that flows in quantum motion is calculated as a value proportional to \(\small t^2\), relative to the time we perceive \(\small t\). By utilizing quantum motion, it may be possible to perform numerical calculations or process information as if the time taken is \(\small t^2\) while the time taken is \(\small t\).
The theory of quantum computing is what has driven this idea forward, and the attempt to realize it as a physical medium is what is known as a quantum computer. The theory of quantum computing is extremely complex, and its essence is unclear, but here is my personal view: If we wanted to make it possible to perform the same calculations as a quantum computer by admitting just one cheat in classical computer calculations, what kind of cheating would be possible? Here is my answer to this question:
- Assume that multiplying a \(\small N \times N\) matrix by a vector with \(\small N\) elements can be calculated in \(\small O(N)\), i.e. a computational complexity on the order of \(\small N\) (on a classical computer it would take \(\small O(N^2)\)).
The mechanism behind quantum computers is to make this type of cheating possible by using quantum mechanical phenomena.
I wrote this as multiplying a \(\small N \times N\) matrix by a \(\small N\) element vector, but this can also be replaced with a Fourier transform (inverse Fourier transform). This means that calculations that would require \(\small O(N^2)\) or \(\small O(N)\) computational complexity on a classical computer can be completed in \(\small O(N)\) or \(\small O(\sqrt{N})\), and is sometimes referred to as a quadratic speed up. At first glance, this may not seem like much of a benefit, but for example, a calculation that requires operations of around \(\small 10^{20}\) will have the number of orders of magnitude halved to \(\small 10^{10}\). This means that calculations that once required an astronomical amount of calculations may now be reduced to a more realistic amount of calculations. Below is a brief summary of how this is thought to work.
Quantum Computation Procedure
Current computers, known as classical computers, store information in a logical model called bits, which have a state of 0 or 1. This is expressed by the ON/OFF state of a collection of numerous power switches called an integrated circuit. When represented as \(\small a_i\in\{0,1\}\), a number \(\small x\) can be represented as a combination of \(\small n\) bits \(\small x=a_1a_2\cdots a_n\), which can represent one of \(\small 2^n\) possible values. The current mechanism of computers is to perform calculations by repeatedly applying functions (devices) that perform simple conversion processes on the value of this collection of bits to information called logic circuits.
In contrast, the logical model used in quantum computers is called the quantum bit (qubit), which also represents information using \(\small n\) quantum bits \(\small x=q_1q_2\cdots q_n\). However, this model simultaneously represents all combinations and stores information in the form of a coefficient that indicates the probability that the target information will be sampled among those combinations. Specifically, if the probability that \(\small n\) quantum bits are simultaneously detected with the value \(\small x\) is represented as:
\[ \small P(x) = \psi(x)\psi^\ast(x) = \left\{\begin{array}{ll} p_{00\cdots0} & x=00\cdots0 \\ p_{00\cdots1} & x=00\cdots1 \\ \quad\vdots \\ p_{11\cdots1} & x=11\cdots1 \end{array} \right., \]
then the wave function:
\[ \small \psi(x) = \left\{ \begin{array}{ll} c_{00\cdots0} & x=00\cdots0 \\
c_{00\cdots1} & x=00\cdots1 \\ \quad\vdots \\ c_{11\cdots1} & x=11\cdots1 \end{array} \right. \]
becomes a model that represents information. For example, when a quantum bit is in a state where it can take on either 0 or 1 with a probability of \(\small 1/2\), it is represented as:
\[ \small \psi(x) = \frac{1}{\sqrt{2}} |0\rangle+\frac{i}{\sqrt{2}} |1\rangle＝c_0 |0\rangle+c_1 |1\rangle, \]
and the information represented in this case is \(\small (c_0,c_1)=(1/\sqrt{2},i/\sqrt{2})\). In other words, the information stored in the quantum state here is the coefficient \(\small c_{q_1q_2\cdots q_n}\). In a quantum computer, the \(\small n\) quantum bits do not hold definite information, but rather the information held is a probability distribution (with \(\small 2^n\) parameters) over the values these quantum bits can take. A quantum computer performs calculations by repeatedly applying operators (quantum gates) that perform simple transformation processes to this wave function.
I wrote that the device that performs the transformation process is an operator (quantum gate), which is a function that receives a function as an argument and returns a function as a return value. In the term of linear algebra, functions are vectors and operators are matrices. A quantum gate is a function that takes a wave function \(\small \psi(c_{q_1q_2\cdots q_n})\) as an argument and returns the transformed wave function \(\small \psi(c’_{q_1q_2\cdots q_n})\). Since wave functions must sum to 1 (probability distribution) when multiplied by their complex conjugates and squared, matrices known as quantum gates are limited to unitary matrices \(\small U\) that have the following properties:
\[ \small U(U^\ast)^T=I. \]
In linear algebra, applying a quantum gate is the process of multiplying a vector by a matrix to return another vector,
\[ \small U\psi(c_{q_1q_2\cdots q_n}) = \psi(c’_{q_1q_2\cdots q_n}). \]
This corresponds to a process that requires a computational complexity of \(\small O\left(N^2=(2^n)^2\right)\) on a classical computer. In a quantum computer, the algorithm is designed on the assumption that it would be ideal if this could be achieved in \(\small n\) operations, i.e. \(\small O(n)\), by passing quantum bits through a quantum gate.
Since the computational complexity of \(\small 2^n\) and \(\small n\) seems to be significantly different, one might think that quantum supremacy would be a piece of cake. However, even in classical computers, algorithms that perform brute force calculations (calculations that take exponential time) are rare, and even in quantum computers, it is unrealistic to prepare unitary matrices (up to \(\small (2^n)^2\) in number) that can arbitrarily manipulate wave functions. In reality, the process would require the repeated operation of a small number of quantum gates that perform simple transformations, and the cost of this algorithm would depend on the computational tasks involved.
The computational processes are:
- The probability distribution is manipulated in advance to make it easier to sample the target solution.
- Sampling is repeated until a satisfactory solution is calculated.
and appears to be basically similar to searching for a solution using Monte Carlo simulation. If one is willing to sacrifice some accuracy in the solution, there are likely many algorithms available for searching for solutions through simulation even on classical computers. Therefore, it can be inferred that this difference in computational complexity is an algorithmic issue, that there is a high probability that an equivalent algorithm exists for classical computers, and that the range of mathematical problems in which quantum computers have an advantage is extremely limited.
Therefore, the essential difference between the computational complexity of classical computers and quantum computers lies in the degree of freedom available to the operation of applying quantum gates to quantum bits. Since quantum gates are matrices, they should have \(\small n^2\) degrees of freedom, which may mean that they can process a square-number of pieces of information compared to the number of observable values \(\small n\). For this reason, it seems that typical quantum algorithms are often claimed to be theoretically capable of being calculated in the order of \(\small O(N),O(\sqrt{N})\), whereas what took \(\small O(N^2)\) or \(\small O(N)\) on a classical computer can be calculated in the order of \(\small O(N),O(\sqrt{N})\). This probably means that the amount of calculations that can be expected to be sped up in general numerical calculations, excluding special problems, is on the order of magnitude.
Can We Bring It Off?
Can we bring it off? You idiot, just do it.
A black joke about the NHK educational program for kindergarteners “Dekirukana” (“Can you bring it off?”)
No scientist or engineer actually working on developing quantum computers would be allowed to ask this question or give any answer other than “Yes, we can.” Whether it is public spending by the government or investment by private capital, investing in technology that is not viable is an investor’s worst nightmare, and it is an unforgivable outrage for the researchers themselves to say so. If they said that, it would mean investors would have to fire all their researchers and engineers and cut their losses. There are often dubious venture companies that continue to say “we can do it!” when it seems completely impossible to achieve, but this is probably because as long as investors tell them to do it, they have no choice but to keep saying they can do it. Therefore, this is a question that only an outsider can ask and answer. Inevitably, outsiders do not have detailed knowledge of the technology in question, and so end up not really understanding it. However, it is easy to point out the questionable points, so I will just point out what seems difficult.
The workings of quantum computers follow the principles of quantum mechanics, and it is said that they are theoretically possible if the principles of quantum mechanics are correct. However, you will notice from the above explanation that there are some questionable technical points that deviate from our common sense. Specifically, the following two assertions seem to contradict each other:
- Each quantum bit can be treated so that the probability of detection is correlated with the others (multiple quantum bits can be treated as if they were a single concatenated number).
- Each quantum bit can be manipulated with a quantum gate so that they do not affect each other’s detection probability (multiple quantum bits can be treated as if they were a single independent logical bit).
The ability to treat the detection probabilities of multiple quantum bits as correlated is justified by a phenomenon known as quantum entanglement. It seems that some quantum physical quantities (often momentum and spin) can be manipulated in a way that correlates with each other, and by utilizing this, it is possible to superimpose the states of multiple quantum bits in a correlated manner. This needs to be true for \(\small n\) quantum bits to be able to represent \(\small 2^n\) possible values.
On the other hand, in order to manipulate the probability of detection of quantum bits, it is necessary to repeatedly apply simple quantum operations using quantum gates. The combination of quantum gates required to realize any calculation is called a universal quantum gate, and the simple quantum gates included in this combination manipulate the probabilities related to 1 to 3 quantum bits. Note that we will always need a quantum gate that can operate on at least two bits simultaneously. In order to realize this operation, it is necessary to satisfy the condition that the result of manipulating the probability of the target quantum bit does not affect the detection probability of other quantum bits; this is condition 2 above.
Quantum computing algorithms are presented under the assumption that these two things are compatible, but in reality, isn’t it possible that these two things are not compatible? The reason is that the \(\small n\) qubits are correlated, so it is unlikely that one could manipulate a small number of qubits independently without affecting the other qubits. In other words, an additional operation is required that does not change (bind) the detection probability of other quantum bits, and in order to realize operation 2, the quantum gate is required to have \(\small N^2\) (the number of matrix elements) degrees of freedom in the first place. However, if the number of timings in which we can observe or manipulate quantum motion is only proportional to \(\small t\), then there are only \(\small N\) degrees of freedom (the number of eigenvalues), making this manipulation impossible.
Typically, this manifests itself as a phenomenon in which the correlation (quantum entanglement) that existed between quantum bits is broken down as a result of applying a quantum gate to quantum bits. This is called noise, and it is thought that quantum computing may be possible by performing additional error correction processing to correct this.One hypothesis would be that it is not noise at all, but rather the inability to perform the correct calculations. In summary, in gate-based quantum computers, the concept of a quantum gate may be the Holy Grail (a fictional entity that can grant any wish). It may be a good idea to keep in mind that gate-based quantum computers may not be feasible as a calculation mechanism for calculating fewer computational complexity than classical computers.
Conclusion
Although I claim to be an expert in financial engineering, I have avoided the topic of financial engineering in this blog (thinking that if I were to write about it, I would write a book or a paper), but I would like to end by briefly explaining what is expected of quantum computers in the field of financial engineering. Quantum finance is a field that attempts to describe the theory of financial engineering using the theory of quantum mechanics. One major motivation for this is whether quantum computers can be used to speed up the calculation of the market value of complex financial products such as derivatives in financial engineering, and the risk calculations of financial portfolios. To achieve this, it will be necessary to replace the mark-to-market algorithms used in financial engineering with those used in quantum computing.
The present value of complex financial instruments such as derivatives is calculated using Monte Carlo simulation, but this calculation has the property that the computational cost is roughly proportional to the number of simulations \(\small N\) (i.e., \(\small O(N)\)). However, in order to improve the numerical convergence by one order of magnitude, the number of simulations must be increased by a factor of ten. Therefore, in order to obtain sufficient convergence, a considerable number of simulations must be performed, but in reality, it is common to cut off the simulation after a compromise due to computation time and resources. By replacing this with quantum computing, it would be nice if the calculations could be completed in about \(\small O(\sqrt{N})\), which is what is expected of quantum computers in financial engineering.
It is not yet clear whether quantum computers can perform calculations faster than classical computers. This may be because the notion of computational complexity in computational theory is merely proportional to the amount of data or some other simple calculation, and it is not possible to compare computational costs in the true sense of the word. In this sense, it may not be possible to theoretically prove whether quantum computers can perform calculations faster than classical computers, and we may have to try them out on a trial-and-error basis. Even if some noise is introduced or the processing is approximate, if calculations equivalent to matrix calculations of \(\small N \times N\) can be achieved using quantum bits and quantum gates on the order of \(\small O(N)\), it would mean that quantum computers have the potential to achieve faster calculations than classical computers.
Of course, if the fact that quantum motion appears to move proportionally to \(\small t^2\) over \(\small t\) only applies to noise and such phenomena cannot be used to control quantum motion, then this may turn out to be nothing more than a pipe dream. If quantum motion can only be controlled to a degree proportional to \(\small t\), then the degrees of freedom that can be expressed by quantum motion are limited to \(\small N\), which is the same as the amount of computation required in classical mechanics. Another possibility is that, even if it is theoretically impossible, some efficient calculation may be possible using practical techniques. In this case, these techniques would be more of an art (craftsmanship) research than a science (theory).
Reference
[1] Nielsen, M. A., & Chuang, I. L. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge: Cambridge University Press.
[2] Rebentrost, P., Gupt, B., & Bromley, T.R. (2018). Quantum computational finance: Monte Carlo pricing of financial derivatives. Physical Review A.
Comments