MITSUBISHI-B Project
Title:
Achievable precision with heuristic solvers: quantum algorithms and quantum supremacy
Industrial Partner: Information Technology R&D Center, Mitsubishi Electric Corp.
Mitsubishi Electric is a world leader in manufacturing and sales of electrical andelectronic products and systems used in a broad range of fields and applications. As aglobal leader among green companies, our technologies are being applied to contributeto and support society and daily life around the world. The Information Technology R&D
Center is actively creating new businesses through basic research and development in
the fields of information technology, media intelligence, electro-optics microwaves, andcommunication technologies. We are also seeking technologies that reinforce ourposition on the leading edge of progress, with work to renew existing businesses throughthe fruits of our R&D in the field of IT.
Industry Mentors
Aruto Hosaka, Ph.D., Researcher, Photonics Platform Group, Advanced Basic Research
Dept.
Tsuyoshi Yoshida, Ph.D., Senior Manager, Photonics Platform Group, Advanced Basic
Research Dept.
Background:
New computing schemes such as quantum computing have emerged in parallel with thesteady evolution of deployable classic computing toward solving various problems much
more efficiently. To address the huge problems that arise when one scales to larger
problems, heuristic algorithms (and hardware for implementing the algorithms) often are
employed. Herein, we have two issues:
1)

The superiority and inferiority can depend on the problem characteristics or even on
random numbers frequently used in the examination.

2)

The true distance between the obtained and the exact solutions is generally
unknown.

While there have been many proposals for new algorithms based on quantum computing,their general performance over a wide range of problems cannot easily be comparedbecause of these issues.

Expectation:
Because of the issues described above, we would like to do the following in this project:1)

define a metric to describe how good potentially obtainable solutions are in various(or general) problems, and2)give some mathematical guarantee to the algorithm that are being tested, where wecall this “achievable precision,” e.g., upper and/or lower bound(s) of residuals fromthe exact solution if it can be quantified by any means.

In this approach, quantum algorithms, quantum-inspired algorithms, and/or somethingaround those will be treated as heuristic algorithms.
The current state of quantum computing is referred to as the “noisy intermediate-scalequantum (NISQ)” era. Algorithms with variational approaches, including a linear
equations solver, have been proposed for exploiting NISQ machines. In such a variational
quantum linear solver, the convergence of the solution strongly depends on its initialvalue given.
Ref. [1] introduced the use of classic preconditioning for helping the convergence
performance in a variational quantum linear solver. Fig. 1 illustrates the idea. Fig. 1(a) is
a typical schematic of quantum circuit called “ansatz,” and Figs. 1(b) and 1(c) show theinfluence of the preconditioning. In a variational quantum linear solver, the parameters
shown in Fig. 1(a) are iteratively updated to solve linear equations 𝐴𝒙 = 𝒃, where thepresetting initial values is a key to good convergence. Then preconditioning is expected
to improve the convergence performance in a variational quantum linear solver (Fig. 1(b))
as well as ones used in classic computing such as Krylov subspace methods (Fig. 1(c)).

(a)

(b)

(c)
Fig. 1: Ideas of a variational quantum linear solver with preconditioning: (a) ansatz
and (b) preconditioning for variational algorithms with NISQ machines, and (c) Krylov
subspace methods in classic computing [1, Fig. 1].
Several problems of linear equations were examined by numerical simulations
assuming an ideal NISQ machine (i.e., excluding the noise). The results show that thepreconditioning with irregular LU decomposition can reduce the residuals (as shown inFigs. 2 and 3). Note that the number of quantum bits (“qubits”), one of the measures in
the quantum computing scale, was limited to 7 for problems with 27×27 matrices because
we emulated quantum computing by a usual classic computer and the emulation
required large computational resources. While the exact solution is easily obtained byclassic computing in this small problem, quantum computing is expected to have thescalability toward solving huge scale problems because the required number of qubits
can potentially be reduced to log scale with maintaining another measure of the “depth.”
The depth should be large in terms of giving a high resolution of solution candidates but
be small in terms of the noise in quantum computing.

Fig. 2: An example of variational quantum linear solver simulation in cases with(“ILU”) and without preconditioning (“Direct”); (a) dependence on the iteration, (b) thedistance between the obtained and the exact solutions shown in (c), respectively. [1,Fig. 2].

Fig. 3: An example of variational quantum linear solver simulation; dependence on
the depth [1, Fig. 3(a)].
A possible conclusion of this g-RIPS project could be that there is no metric as definedin (1) (above) and/or that it is impossible to find a guarantee as defined in (2) (above).
On the other hand, it would be a significant scientific achievement (potentially including
a guarantee of quantum supremacy from mathematical viewpoints) to be reported in an
academic conference or journal when we find something meaningful, even if it is valid
only under limited conditions.
Requirements:-Mandatory: undergraduate-level knowledge in linear algebra.

-Preferable: programming skills. Python codes for [1], which work in usual classic
computers, are available.

References:
Fundamentals of variational quantum linear solvers can be found in [2] and [3]. Krylov
subspace methods are described in various textbooks such as [4]. For an introduction,
we also have access to [5] online. If you need a textbook for quantum computing [6] orones shown in the website [7] might be useful. For more information regarding thisproject, please see references shown in our recent work [1].
[1] A. Hosaka et al., “Preconditioning for a variational quantum linear solver,” arXiv:
2312.15657 [quant-ph], December 2023.
Available: www.arxiv.org/abs/2312.15657[2] C. Bravo-Prieto et al., “Variational quantum linear solver,” Quantum, vol. 7, p. 1188,

November 2023. Available: www.quantum-journal.org/papers/q-2023-11-22-1188[3] M. Cerezo et al. "Variational quantum algorithms," Nature Reviews Physics, vol. 3, no.
9, pp. 625–644, September 2021.
Available: www.nature.com/articles/s42254-021-00348-9[4] Y. Saad, Iterative methods for sparse linear systems, Society for Industrial andApplied Mathematics, 2003.
[5] S. Fan, “An introduction to Krylov subspace methods,” arXiv: 1811.09025 [math.OC],
November 2018. Available: www.arxiv.org/abs/1811.09025[6] M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information:
10th Anniversary Edition, Cambridge University Press, 2010.
[7] The Quantum insider, “7 Quantum Computing Books To Read In 2022 [Ranked &Reviewed],”[Online].

Available:

www.thequantuminsider.com/2020/05/15/7-

quantum-computing-books-for-the-uninitiated