8: Also at University of Chinese Academy of Sciences, Beijing, China
9: Also at Institute for Theoretical and Experimental Physics named by A.I.
Alikhanov of NRC ‘Kurchatov Institute’, Moscow, Russia
10: Also at Joint Institute for Nuclear Research, Dubna, Russia
11: Also at Suez University, Suez, Egypt
12: Now at British University in Egypt, Cairo, Egypt
13: Also at Purdue University, West Lafayette, USA
14: Also at Université de Haute Alsace, Mulhouse, France
15: Also at Erzincan Binali Yildirim University, Erzincan, Turkey
16: Also at CERN, European Organization for Nuclear Research, Geneva,
Switzerland
17: Also at RWTH Aachen University, III. Physikalisches Institut A, Aachen,
Germany
18: Also at University of Hamburg, Hamburg, Germany
19: Also at Brandenburg University of Technology, Cottbus, Germany
20: Also at Institute of Physics, University of Debrecen, Debrecen, Hungary,
Debrecen, Hungary
21: Also at Institute of Nuclear Research ATOMKI, Debrecen, Hungary
22: Also at MTA-ELTE Lendület CMS Particle and Nuclear Physics Group, Eötvös
Loránd University, Budapest, Hungary, Budapest, Hungary
23: Also at IIT Bhubaneswar, Bhubaneswar, India, Bhubaneswar, India
24: Also at Institute of Physics, Bhubaneswar, India
25: Also at G.H.G. Khalsa College, Punjab, India
26: Also at Shoolini University, Solan, India
27: Also at University of Hyderabad, Hyderabad, India
28: Also at University of Visva-Bharati, Santiniketan, India
29: Now at INFN Sezione di Bari a, Università di Bari b, Politecnico di Bari
c, Bari, Italy
30: Also at Italian National Agency for New Technologies, Energy and
Sustainable Economic Development, Bologna, Italy
31: Also at Centro Siciliano di Fisica Nucleare e di Struttura Della Materia,
Catania, Italy
32: Also at Riga Technical University, Riga, Latvia, Riga, Latvia
33: Also at Malaysian Nuclear Agency, MOSTI, Kajang, Malaysia
34: Also at Consejo Nacional de Ciencia y Tecnología, Mexico City, Mexico
35: Also at Warsaw University of Technology, Institute of Electronic Systems,
Warsaw, Poland
36: Also at Institute for Nuclear Research, Moscow, Russia
37: Now at National Research Nuclear University ’Moscow Engineering Physics
Institute’ (MEPhI), Moscow, Russia
38: Also at St. Petersburg State Polytechnical University, St. Petersburg,
Russia
39: Also at University of Florida, Gainesville, USA
40: Also at Imperial College, London, United Kingdom
41: Also at P.N. Lebedev Physical Institute, Moscow, Russia
42: Also at California Institute of Technology, Pasadena, USA
43: Also at Budker Institute of Nuclear Physics, Novosibirsk, Russia
44: Also at Faculty of Physics, University of Belgrade, Belgrade, Serbia
45: Also at Università degli Studi di Siena, Siena, Italy
46: Also at INFN Sezione di Pavia a, Università di Pavia b, Pavia, Italy,
Pavia, Italy
47: Also at National and Kapodistrian University of Athens, Athens, Greece
48: Also at Universität Zürich, Zurich, Switzerland
49: Also at Stefan Meyer Institute for Subatomic Physics, Vienna, Austria,
Vienna, Austria
50: Also at Burdur Mehmet Akif Ersoy University, BURDUR, Turkey
51: Also at Şırnak University, Sirnak, Turkey
52: Also at Department of Physics, Tsinghua University, Beijing, China,
Beijing, China
53: Also at Near East University, Research Center of Experimental Health
Science, Nicosia, Turkey
54: Also at Beykent University, Istanbul, Turkey, Istanbul, Turkey
55: Also at Istanbul Aydin University, Application and Research Center for
Advanced Studies (App. & Res. Cent. for Advanced Studies), Istanbul, Turkey
56: Also at Mersin University, Mersin, Turkey
57: Also at Piri Reis University, Istanbul, Turkey
58: Also at Gaziosmanpasa University, Tokat, Turkey
59: Also at Ozyegin University, Istanbul, Turkey
60: Also at Izmir Institute of Technology, Izmir, Turkey
61: Also at Bozok Universitetesi Rektörlügü, Yozgat, Turkey
62: Also at Marmara University, Istanbul, Turkey
63: Also at Milli Savunma University, Istanbul, Turkey
64: Also at Kafkas University, Kars, Turkey
65: Also at Istanbul Bilgi University, Istanbul, Turkey
66: Also at Hacettepe University, Ankara, Turkey
67: Also at Adiyaman University, Adiyaman, Turkey
68: Also at Vrije Universiteit Brussel, Brussel, Belgium
69: Also at School of Physics and Astronomy, University of Southampton,
Southampton, United Kingdom
70: Also at IPPP Durham University, Durham, United Kingdom
71: Also at Monash University, Faculty of Science, Clayton, Australia
72: Also at Bethel University, St. Paul, Minneapolis, USA, St. Paul, USA
73: Also at Karamanoğlu Mehmetbey University, Karaman, Turkey
74: Also at Bingol University, Bingol, Turkey
75: Also at Georgian Technical University, Tbilisi, Georgia
76: Also at Sinop University, Sinop, Turkey
77: Also at Mimar Sinan University, Istanbul, Istanbul, Turkey
78: Also at Nanjing Normal University Department of Physics, Nanjing, China
79: Also at Texas A&M University at Qatar, Doha, Qatar
80: Also at Kyungpook National University, Daegu, Korea, Daegu, Korea


# Ground and excited state energy calculations of the H2 molecule using a
variational quantum eigensolver algorithm on an NMR quantum simulator

Dileep Singh<EMAIL_ADDRESS>Department of Physical Sciences,
Indian Institute of Science Education & Research Mohali, Sector 81 SAS Nagar,
Manauli PO 140306 Punjab, India.  Shashank Mehendale
<EMAIL_ADDRESS>Department of Chemistry, University of
Toronto, Toronto, ON M5S 1A1, Canada  Arvind<EMAIL_ADDRESS>Department of Physical Sciences, Indian Institute of Science Education &
Research Mohali, Sector 81 SAS Nagar, Manauli PO 140306 Punjab, India.  Kavita
Dorai<EMAIL_ADDRESS>Department of Physical Sciences, Indian
Institute of Science Education & Research Mohali, Sector 81 SAS Nagar, Manauli
PO 140306 Punjab, India.

###### Abstract

Variational quantum algorithms are emerging as promising candidates for near-
term practical applications of quantum information processors, in the field of
quantum chemistry. We implement the variational quantum eigensolver algorithm
to calculate the molecular ground-state energy of the H2 molecule and
experimentally demonstrated it on an NMR quantum processor. Further, we
simulate the excited states of the H2 molecule using the variational quantum
deflation algorithm and experimentally demonstrate it on the same NMR quantum
processor. We also develop the first simulation of the energy calculation of
the H2 molecule using only a single qubit, and verify the results on an NMR
quantum computer. Our experimental results demonstrate that only a single NMR
qubit suffices to calculate the molecular energies of the H2 molecule to the
desired accuracy.

##  I Introduction

The current century is witnessing what is termed as the “second quantum
revolution” and quantum computing is at its forefront MacFarlane  _et al._
(2003). In recent years, it has been shown that there are a number of problems
that a quantum algorithm would solve much more efficiently as compared to its
classical counterpart Nielsen and Chuang (2010). One such class of problems is
‘quantum simulation’, wherein the goal is to simulate a quantum system
efficiently and gain the maximum amount of information about the system
Feynman (1982).

A major class of problems coming under the umbrella of quantum simulationLloyd
(1996) is the problem of finding the eigenstates of the Hamiltonian of a given
system, which has been a prime focus in the field of quantum chemistry Cao
_et al._ (2019). Finding the ground and excited state energies of a molecule
gives enormous information about its properties, such as its stability, rate
of reactions and the molecular orbitals involved Aspuru-Guzik  _et al._
(2005). The calculation of ground and excited state energies of molecules is
of great importance in chemistry, but this becomes a challenging task for a
classical computer as the complexity of the molecules grows. These problems
are extremely difficult to solve analytically and hence the only way out is a
numerical approach. However, even this becomes a daunting task for molecules
with a large number of atoms and electrons, due to the large number of degrees
of freedom involved. This is where quantum algorithms demonstrate their
supremacy over their classical counterparts, and various quantum algorithms
have been developed to efficiently calculate the energies of molecules on a
quantum computer Whitfield  _et al._ (2011); Kassal  _et al._ (2011); Jones
_et al._ (2012).

Quantum algorithms are prone to a lot of errors and require quantum error
correction which limits their usefulness. Taking into consideration that we
are in the NISQ era Preskill (2018), a new class of algorithms has been
developed, which are partly classical and partly quantum, which can reduce the
required gate depth and mitigate errors to a certain extent. Variational
Quantum Eigensolver (VQE) is one such algorithm that has been developed to
calculate the ground state of Hamiltonians on a quantum computer McClean  _et
al._ (2016); Moll  _et al._ (2018); Jones  _et al._ (2019); Wang  _et al._
(2019). The VQE algorithm may enable near-term quantum-enhanced computation
Peruzzo  _et al._ (2014) due to its low circuit depth.

In addition to ground state energy calculation of molecules, the excited state
energies have several important applications. There have been a few proposals
to develop an algorithm for the detection of excited states of a molecular
Hamiltonian: a method that minimizes the von Neumann entropy Santagati  _et
al._ (2018) and the quantum subspace expansion method Colless  _et al._
(2018). Recently, an algorithm which is an extension of the VQE algorithm was
proposed, namely the Variational Quantum Deflation (VQD) algorithm, to
calculate the excited state energies of molecules Higgott  _et al._ (2019).
The VQD algorithm systematically finds excited states at almost no extra cost
as compared to the other two methods. Using the VQD algorithm, the excited
states are obtained by applying the VQE algorithm to a modified Hamiltonian
which has the excited states as its ground state. Several experiments has been
performed to demonstrate the energy spectra of molecules using VQE algorithms
on different quantum platforms such as photonic quantum processors, trapped
ions and using superconducting qubits O’Malley  _et al._ (2016); Hempel  _et
al._ (2018); Motta  _et al._ (2023); Jones  _et al._ (2024); Misiewicz and
Evangelista (2024).

In this paper, we have simulated the ground state energy and excited state
energies of the H2 molecule using the VQE and VQD algorithms, respectively.
The simulated results are then verified on an NMR quantum processor. To use
the variational principle, we varied the states in the qubit space so as to
find the state which minimizes the energy expectation value. This is done by
using the technique of Unitary Coupled Cluster Singles and Doubles (UCCSD) Xia
and Kais (2020). The experimental verification is done by calculating the
expectation values terms involved in the H2 molecule Hamiltonian by using two
NMR qubits. The experimental verification involves the calculation of
expectation values of the state, and this is achieved by measuring the single-
qubit Pauli $Z$ operator of the experimentally prepared states. We also
simulated the energies of the H2 molecule on a single qubit system and
verified the results on an NMR quantum computer. This is the first
experimental demonstration of energy calculations of the H2 molecule which
requires only one qubit and uses fewer experimental resources as compared to
similar work.

The material of the paper is arranged as follows: Section II describes the
theoretical background of the variational quantum eigensolver algorithm, the
variational quantum deflation algorithm, the electronic structure of H2
molecule and the solution of the H2 molecular Hamiltonian using one and two
qubits. Section III describes the NMR implementation of the ground and excited
state energies of the H2 molecule using a two-qubit and a single-qubit system,
respectively. Section IV contains a few concluding remarks.

##  II Theoretical background

###  II.1 Quantum variational methods for energy calculations

Given that quantum systems are described by Hamiltonians, finding their
eigenvalues and eigenvectors is of paramount importance and becomes
increasingly difficult with increase in system dimensionality. For a
Hamiltonian $H$, an ansatz state $\ket{\psi(\theta)}$ is chosen with at least
one free parameter $\theta$. The expectation value of energy
$\epsilon_{\theta}=\langle\psi(\theta)|H|\psi(\theta)\rangle$ is minimized
over the parameter $\theta$ to obtain the minimum possible energy. The lowest
expectation value that can be obtained in this way is the ground state energy
of the Hamiltonian itself. In that case, the state $\ket{\psi(\theta)}$ will
be the ground state of the given Hamiltonian. However, this may not work as
the family of states $\ket{\psi(\theta)}$ may not contain the ground state!
Therefore, a good choice of ansatz is important. On a quantum computer, there
is an additional possibility of storing the quantum state in the quantum
memory and carrying out the entire optimization process as a quantum computing
process. The above variational VQE algorithm is a hybrid one, because a
classical computer is used to update the value of the parameter $\theta$
McClean  _et al._ (2016).

A variation of the above method can be used to calculate the excited states of
the Hamiltonian and the procedure is called the VQD method Higgott  _et al._
(2019). If $\ket{\phi_{0}}$ is the ground state of the original Hamiltonian
$H$, the VQD Hamiltonian for the first excited state is given by:

$H_{1}=H+\beta_{0}|\phi_{0}\rangle\langle\phi_{0}|$ (1)

where $\beta_{0}$ is a parameter and is chosen such that the variational
calculation applied on $H_{1}$ gives its minimum energy (such that it is equal
to the first excited state of of the original Hamiltonian $H$). The VQD method
can be easily extended to find the other excited states of $H$ by
appropriately constructing the new Hamiltonian for the variational purpose.

###  II.2 Solving for energies of the H2 molecule

The Hamiltonian of the H2 molecule in atomic units is given by Colless  _et
al._ (2018); O’Malley  _et al._ (2016):

$\displaystyle
H=-\sum_{i}\dfrac{\nabla_{R_{i}}}{2M_{i}}-\sum_{i}\dfrac{\nabla_{r_{i}}}{2}+\sum_{i,j>i}\dfrac{Z_{i}Z_{j}}{|R_{i}-R_{j}|}$
(2)
$\displaystyle-\sum_{i,j>i}\dfrac{Z_{i}}{|R_{i}-r_{j}|}+\sum_{i,j>i}\dfrac{1}{|r_{i}-r_{j}|}$

where $R_{i},M_{i},Z_{i}$ denote the position, mass and charge of the
$i^{\text{th}}$ nuclei respectively, and $r_{i}$ denotes the position of the
$i^{\text{th}}$ electron.

The above Hamiltonian is first solved in the Born-Oppenheimer approximation
and then cast into the second quantized form using a specific choice of
$N$-particle basis functions O’Malley  _et al._ (2016). Since quantum many-
body problems are described in the language of second quantization, one needs
a formalism to translate the language of second quantization to a language
that a quantum computer can read. This can be achieved in various ways,
including the Jordan-Wigner transformation, the Bravyi-Kitaev transformation,
and the Parity transformation O’Malley  _et al._ (2016). In this work, we use
the Parity transformation. The quantum many-body Hamiltonian can be written in
second quantization as O’Malley  _et al._ (2016):

$\displaystyle
H=\sum_{\mu,\nu}t_{\mu,\nu}c^{\dagger}_{\mu}c_{\nu}+\sum_{\mu,\nu,\mu^{\prime}\nu^{\prime}}V_{\mu,\nu,\mu^{\prime}\nu^{\prime}}c^{\dagger}_{\mu}c^{\dagger}_{\nu}c_{\nu^{\prime}}c_{\mu^{\prime}}$
where, $\displaystyle t_{\mu,\nu}=\int
d\sigma\phi^{*}_{\mu}(\sigma)\left(-\dfrac{\nabla_{r}}{2}-\sum_{i}\dfrac{Z_{i}}{|R_{i}-r|}\right)\phi_{\mu}(\sigma)$
$\displaystyle V_{\mu,\nu,\mu^{\prime}\nu^{\prime}}=\int
d\sigma_{1}d\sigma_{2}\dfrac{\phi^{*}_{\mu}(\sigma_{1})\phi^{*}_{\nu}(\sigma_{2})\phi_{\mu^{\prime}}(\sigma_{1})\phi_{\nu^{\prime}}(\sigma_{2})}{|r_{1}-r_{2}|}$

where $\sigma_{i}=(r_{i},s_{i})$ with $r_{i},s_{i}$ are the position and spin
indices, respectively. The operators $c_{\mu},c_{\mu}^{\dagger}$ are the
lowering and raising operators for electron occupation in orbitals.

To solve the above Hamiltonian on a quantum computer using the VQD algorithm,
all the second quantized operators have to be mapped to the Pauli operators,
and the orbitals have to be mapped to qubits. Using the Parity transformation,
the many-body H2 Hamiltonian is mapped to the qubit Hamiltonian acting in a
two-qubit state space Seeley  _et al._ (2012); Ganzhorn  _et al._ (2019):

$H=a_{0}II+a_{1}ZI+a_{2}IZ+a_{3}ZZ+a_{4}XX$ (3)

The coefficients $a_{i}$ encode the information of molecular integrals
pertaining to a specific basis set. We have chosen the STO-3G basis in our
calculations. The Qiskit.Chemistry module Javadi-Abhari  _et al._ (2024) was
used to generate the Hamiltonian in the STO-3G basis, which was then converted
to a qubit Hamiltonian using the Parity map. The values of the $a_{i}$
coefficients corresponding to each Pauli operator were extracted as a function
of different internuclear distances.

In order to use the variational principle for the minimum energy calculation,
we use the Unitary Coupled Cluster Singles and Doubles (UCCSD) ansatz:

$\ket{\psi(\theta)}=U(\theta)\ket{\psi_{0}}$ (4)

where $\ket{\psi_{0}}$ is an initial reference state and $U(\theta)$ is the
UCCSD evolution operator. The choice of the reference state is the Hartree-
Fock (HF) state, which definitely has a support on the ground state of the
Hamiltonian. After writing the HF state in the Parity basis, the symmetry in
the action of UCCSD operator and the HF state can be exploited to give a two-
qubit UCCSD operator:

$U(\theta)=\exp(i\theta XY)$ (5)

with the HF state given by $\ket{01}$ O’Malley  _et al._ (2016). The action of
$U(\theta)$ on $\ket{01}$ can be computed from:

$U(\theta)\ket{01}=\exp(i\theta
XY)\ket{01}=\cos{\theta}\ket{01}+\sin{\theta}\ket{10}$ (6)

The action of $U(\theta)$ on $\ket{01}$, and then minimization of the energy
expectation leads to the ground state of the Hamiltonian. The classical
minimization process is done using the Nelder-Mead method given by the
minimize function of the scipy.optimize module Olsson and Nelson (1975);
community (2024). The VQD modified Hamiltonian and the same ansatz leads to an
excited state of the H2 molecule.

Given that we obtained two energy eigenstates of the Hamiltonian in the space
spanned by the vectors $\ket{01},\ket{10}$, the other two eigenstates belong
to the space spanned by the other two computational basis vectors, namely
$|00\rangle$ and $|11\rangle$. In order to find the other two eigen states, we
take the initial state to be $\ket{00}$, and apply the ansatz circuit which
performs the evolution $U(\theta)$ (as in the previous case) given by:

$U(\theta)=\exp(i\theta XY)\\\
U(\theta)\ket{00}=\cos{\theta}\ket{00}-\sin{\theta}\ket{11}$ (7)

Since the H2 Hamiltonian of Eqn. (3) is real in the computational basis, there
has to exist a real eigenbasis for the Hamiltonian with real coefficients of
expansion in the computational basis. Thus, we do not have to explore the
space where the relative phase between the two computational basis vectors is
complex. Hence the problem essentially gets divided into two problems, each of
two dimensions.

###  II.3 Solving for the energies of the H2 molecule using a single qubit

As is clear from Equation 6 in the previous section, the UCCSD ansatz only
explores a two-dimensional subspace of the entire four-dimensional space. This
creates a possibility of mapping the two-dimensional subspace to a single-
qubit space. If we map the state to involved to a single-qubit state as:

$\ket{01}\rightarrow\ket{0},\mbox{and}\quad\ket{10}\rightarrow\ket{1}$ (8)

the UCCSD operator gets mapped to $\exp(-i\theta Y)$, where $Y$ acts on the
single-qubit space.

In order to map the Hamiltonian, we first evaluate how different terms of the
Hamiltonian act on the basis vectors spanning the subspace (Table 1).

Table 1:  The action of the individual terms of the Hamiltonian on the states $\ket{01}$ and $\ket{10}$. $II\ket{01}$ | = | $\ket{01}$ | $II\ket{10}$ | = | $\ket{10}$
---|---|---|---|---|---
$ZI\ket{01}$ | = | $\ket{01}$ | $ZI\ket{10}$ | = | $-\ket{10}$
$IZ\ket{01}$ | = | $-\ket{01}$ | $IZ\ket{10}$ | = | $\ket{10}$
$ZZ\ket{01}$ | = | $-\ket{01}$ | $ZZ\ket{10}$ | = | $-\ket{10}$
$XX\ket{01}$ | = | $\ket{10}$ | $XX\ket{10}$ | = | $\ket{01}$

It is evidence from Table 1, that:

$\displaystyle II\longrightarrow I\ \ $ $\displaystyle\&\ \
ZZ\longrightarrow-I$ $\displaystyle ZI\longrightarrow Z\ \ $ $\displaystyle\&\
\ IZ\longrightarrow-Z$ $\displaystyle XX$ $\displaystyle\longrightarrow X$ (9)

Thus, the diagonalization of the Hamiltonian in the two-dimensional subspace
of the two-qubit space reduces to the diagonalization of a single-qubit
Hamiltonian given by:

$H=(a_{0}-a_{3})I+(a_{1}-a_{2})Z+a_{4}X$ (10)

with the UCCSD ansatz $\exp(-i\theta Y)$ and the initial state $\ket{0}$.

For the remaining two eigenstates, we follow an analogous procedure to obtain:

$H=(a_{0}+a_{3})I+(a_{1}+a_{2})Z+a_{4}X$ (11)

with the UCCSD ansatz $\exp(i\theta Y)$ and the initial state $\ket{0}$.

Diagonalizing these two Hamiltonians will give all the four excited states of
the original two-qubit H2 Hamiltonian. The reduction of the problem to a
single qubit is resource efficient from the point of view of its experimental
implementation. Further, since there are only three terms in the Hamiltonian,
the calculation of energy expectation values becomes simpler. Additionally,
the UCCSD ansatz, unlike in the two-qubit qubit case, is now a simple rotation
about the $Y$-axis, which is easier to implement experimentally on any quantum
platform. Last but not the least, the initial state can be directly taken to
be the pseudopure state on an NMR quantum computer, without any additional
requirement to prepare a reference state. With all these advantages, we have
shown that the entire problem of diagonalization of the two-qubit H2 molecule
can be easily recast as a problem of diagonalization in a single-qubit space.

##  III Experimental Implementation

###  III.1 Calculating energies of the H2 molecule using two NMR qubits

Figure 1: (a) Molecular structure of ${}^{13}\rm C$-labeled chloroform used as
a two-qubit quantum system. (b) NMR pulse sequence for the PPS $|00\rangle$
state where the value of the flip angle $\alpha$ is kept fixed at
$59.69^{\circ}$, while $\rm J$ represents the coupling between the ${}^{1}\rm
H$ and ${}^{13}\rm C$; the total time evolution is given by $\frac{1}{2\rm
J}$. (c) Quantum circuit for the required state, generated with an optimized
value of $\theta$ for different intermolecular distances. The unfilled
rectangles denote $\pi$ pulses, while the filled rectangle represents a
$\frac{\pi}{2}$ pulse. The flip angles and phases of the other pulses are
written below each pulse, and a bar over the phase denotes negative phase.

To experimentally calculate the energies simulated by VQE algorithms of the H2
molecule on a four-dimensional quantum system, the molecule of ${}^{13}\rm C$
enriched chloroform dissolved in acetone-D6 was used, with the ${}^{13}\rm C$
and ${}^{1}\rm H$ spins being labeled as qubit $1$ and qubit $2$, respectively
(Fig. 1(a)). NMR experiments are sensitive only to the deviation density
matrix and the initial state is typically prepared from thermal equilibrium as
a pseudopure state (PPS), which mimics the evolution of true pure states
Oliveira  _et al._ (2007):

$\rho_{00}=\frac{1-\epsilon}{2^{3}}I_{4}+\epsilon|00\rangle\langle 00|$ (12)

where spin polarization $\epsilon\approx 10^{-6}$ and $I_{4}$ is the $4\times
4$ identity operator. We initialized the system in the PPS $|00\rangle$ using
the spatial averaging technique Oliveira  _et al._ (2007), via a combination
of RF pulses and pulsed magnetic gradients. The NMR pulse sequence for the PPS
is given in Fig. 1(b).

Table 2: Hamiltonian coefficients $a_{i},i=0,1,2,3,4$ for different internuclear separations (R). R (Å) |  $a_{0}$ |  $a_{1}$ |  $a_{2}$ |  $a_{3}$ |  $a_{4}$
---|---|---|---|---|---
0.30 |  -0.75374 |  0.80864 |  -0.80864 |  -0.01328 |  0.16081
0.40 |  -0.86257 |  0.68881 |  -0.68881 |  -0.01291 |  0.16451
0.50 |  -0.94770 |  0.58307 |  -0.58307 |  -0.01251 |  0.16887
0.60 |  -1.00712 |  0.49401 |  -0.49401 |  -0.01206 |  0.17373
0.70 |  -1.04391 |  0.42045 |  -0.42045 |  -0.01150 |  0.179005
0.80 |  -1.06321 |  0.35995 |  -0.35995 |  -0.01080 |  0.18462
0.90 |  -1.07028 |  0.30978 |  -0.30978 |  -0.00996 |  0.19057
1.00 |  -1.06924 |  0.26752 |  -0.26752 |  -0.00901 |  0.19679
1.10 |  -1.06281 |  0.23139 |  -0.23139 |  -0.00799 |  0.20322
1.20 |  -1.05267 |  0.20018 |  -0.20018 |  -0.00696 |  0.20979
1.30 |  -1.03991 |  0.17310 |  -0.17310 |  -0.00596 |  0.21641
1.40 |  -1.02535 |  0.14956 |  -0.14956 |  -0.00503 |  0.22302
1.50 |  -1.00964 |  0.12910 |  -0.12910 |  -0.00418 |  0.22953
1.60 |  -0.99329 |  0.11130 |  -0.11130 |  -0.00344 |  0.23590
1.70 |  -0.97673 |  0.09584 |  -0.09584 |  -0.00280 |  0.24207
1.80 |  -0.96028 |  0.08240 |  -0.08240 |  -0.00226 |  0.24801
Figure 2: (a) Details of the mapping performed for the measurement of the
expectation values $\langle ZI\rangle$, $\langle IZ\rangle$, $\langle
ZZ\rangle$, $\langle XX\rangle$. The Identity operator $I$ denotes ‘no
operation’. (b) NMR spectra of 1H and 13C, displaying the experimentally
measured expectation values of $\langle ZI\rangle$ and $\langle IZ\rangle$,
$\langle ZZ\rangle$, $\langle XX\rangle$, respectively, for the ground state
energy calculation, at an intermolecular distance $R=0.70$ Å.

Experiments were performed on a Bruker Avance III 600-MHz FT-NMR spectrometer
equipped with a TXI probe. Quantum gates, required for the NMR implementation,
were achieved by using specially crafted RF pulses of suitable amplitude,
phase, and duration and nonlocal unitary operations were achieved by free
evolution under the system Hamiltonian. The T1 and T2 relaxation times of the
1H spin-1/2 nuclei were $\approx 8$ sec and $\approx 3$ sec, respectively. The
T1 and T2 relaxation times of the 13C spin-1/2 nuclei were $\approx 17$ sec
and $\approx 0.5$ sec, respectively. The duration of the $\frac{\pi}{2}$
pulses for ${}^{1}\rm H$ and ${}^{13}\rm C$ nuclei were $7.14$ $\mu$s at a
power level of $19.9$ W, and $12.4$ $\mu$s at a power level of $237.3$ W,
respectively.

In order to experimentally calculate the energies of the H2 molecule, we need
to calculate the expectation values of $\langle ZI\rangle$, $\langle
IZ\rangle$, $\langle ZZ\rangle$, $\langle XX\rangle$. In an NMR experiment
these expectation values can be calculated by mapping them onto the single-
qubit Pauli $Z$ operator. This mapping is easily performed in the context of
an NMR experimental measurement as the observed $z$ magnetization of a nuclear
spin in a particular quantum state is proportional to the expectation value of
the Pauli $Z$ operator of the spin in that state Gaikwad  _et al._ (2018);
Singh  _et al._ (2019). For instance, in order to determine the expectation
value $\langle ZZ\rangle$ for the state $\rho=|\psi\rangle\langle\psi|$, we
map the state $\rho$ to $\rho_{1}=U_{1}\rho U_{1}^{\dagger}$, where
$U_{1}=$CNOT12 followed by observing $\langle Z_{2}\rangle$ for the state
$\rho_{1}$. The expectation value of $\langle Z_{2}\rangle$ for the state
$\rho_{1}$ is equivalent to observing the expectation value of $\langle
ZZ\rangle$ for the state $\rho$.

Figure 3: Ground and excited state energies of the H2 molecule calculated
using the VQE and VQD algorithms, respectively, over a range of internuclear
separations. The simulated results are represented by joined lines, while the
experimentally calculated values (obtained using two NMR qubits) are
represented by distinct points with accompanying error bars.

The quantum circuit and corresponding NMR pulse sequence for the experimental
calculation of required expectation values is given in Fig. 1(c). The circuit
comprises three parts (delineated by dashed red lines in Fig. 1(c)): the first
part corresponds to initializing the state to the HF state $|01\rangle$, which
is achieved by applying a single-qubit rotation on the $|00\rangle$ state. The
second part of the circuit applies the parameterized ansatz $U(\theta)$ on the
initial state, which is achieved by optimizing the value of $\theta$ (using
the Nelder-Mead method and the scipy.optimize module). The third part of the
circuit calculates the expectation values $\langle ZI\rangle$, $\langle
IZ\rangle$, $\langle ZZ\rangle$, $\langle XX\rangle$ for the parameterized
ansatz, which is achieved by mapping these expectation values onto the single-
qubit Pauli $Z$ operator. The experimentally calculated energies are obtained
by adding these expectation values to their respective electronic constants
($a_{i},i=0,1,2,3,4$). The numerical values of the electronic constants are
tabulated in Table 2, for different values of the internuclear separation (R)
of the H2 molecule.

Figure 4: (a) Molecular structure of chloroform, used as a one-qubit quantum
system. (b) Mapping details for the measurement of the expectation values
$\langle Z\rangle$ and $\langle X\rangle$. The identity operator $I$ denotes
‘no operation’. (c) NMR spectra of 1H, depicting the experimentally measured
expectation values of $\langle Z\rangle$ and $\langle X\rangle$.

The ground state and the excited state energies of the H2 molecule were
experimentally calculated using VQE and VQD algorithms, respectively, for
sixteen different internuclear distances in the range $0.30-1.80$ Å. For each
of these internuclear separations, there are five associated electronic
constants $a_{0},a_{1},a_{2},a_{3},a_{4}$ (as given in the H2 molecular
Hamiltonian in Eqn. (3)). Fig. 2(a) contains the details of mapping that we
have used in the NMR experiment to calculate the expectation values required
for the experimentally prepared states. Fig. 2(b) depicts the NMR spectra of
the expectation values $\langle ZI\rangle$, $\langle IZ\rangle$, $\langle
ZZ\rangle$, $\langle XX\rangle$ for the ground state energy at an internuclear
separation of R$=0.70$ Å.. The ground and excited state energies of the H2
molecule have been experimentally calculated using a similar method, for the
thirteen other internuclear separations. The ground and excited state energies
have been plotted as a function of the internuclear distances in Fig. 3. As
evident from the plot in Fig. 3, the simulated and experimentally measured
values agree well, to within experimental errors.

###  III.2 Calculating energies of the H2 molecule using one NMR qubit

To experimentally calculate the energies of the H2 molecule via variational
quantum algorithms implemented on a two-dimensional quantum system, the
molecule of chloroform dissolved in acetone-D6 was used, with the 1H spin
realizing a single qubit (Fig. 4(a)). In order to perform the energy
calculation, we need to calculate only two expectation values, namely $\langle
Z\rangle$ and $\langle X\rangle$. The details of the mapping used for the
experimental calculation are given in Fig. 4(b). Fig. 4(c), depicts the NMR
spectra of the expectation values of $\langle Z\rangle$, $\langle X\rangle$
for the ground state energy of the H2 molecule at the internuclear separation
R$=0.70$ Å.

Figure 5: Simulations and experimental calculations of the ground and excited
state energies of the H2 molecule, for a range of internuclear separations.
The simulated results are represented by joined lines, while the
experimentally calculated values (obtained using a single NMR qubit) are
represented by distinct points with accompanying error bars.

The ground and excited state energies for the H2 molecule have been calculated
experimentally for sixteen different internuclear separations. The ground and
excited state energies have been plotted as a function of the internuclear
separation in Fig. 5. The red dashed curve represents the energy calculation
corresponding to the reduced single-qubit Hamiltonian given in Eqn. (10). The
green curve represents the energy calculation corresponding to the reduced
single-qubit Hamiltonian given in Eqn. (11). As is evident from the plot in
Fig. 5, the simulated and experimentally measured values agree well to within
experimental errors. Furthermore, it is remarkable that the simulated and
experimentally measured values of the molecular energies in Fig. 5, are very
close to the values obtained in Fig. 3, validating the efficiency of the VQD
algorithm using only a single qubit.

The experimental complexity is reduced due to the reduction of two-qubit
system to a one-qubit system. We were hence able to calculate the energy
spectra of the H2 molecule by measuring only two expectation values, namely,
$\langle Z\rangle$ and $\langle X\rangle$. In the corresponding NMR
experiments, these expectation values can be obtained by applying a single RF
pulse on the experimentally prepared state. This is the first experimental
demonstration on an NMR quantum simulator of the calculation of energies of
the H2 molecule which requires only a single qubit for its implementation.

##  IV Conclusions

The ground and excited states of the H2 Hamiltonian were obtained in the
Parity basis using VQE and VQD algorithms, and the results of the calculations
were verified on an NMR quantum simulator. Further, the problem of calculation
of the H2 ground state energy was reduced to a single-qubit problem which was
also verified on the NMR quantum simulator. Two NMR qubits were used for the
simulation of the single-qubit problem and the expectation values involved in
the Hamiltonian were obtained by measuring the single-qubit Pauli $Z$ operator
of the experimentally prepared state. The experimental implementation of
variational quantum algorithms to calculate the ground and excited state
energies of molecules is important for the field of quantum chemistry, and our
results are a step forward in this direction.

###### Acknowledgements.

All the experiments were performed on a Bruker Avance-III 600 MHz FT-NMR
spectrometer at the NMR Research Facility of IISER Mohali. A. acknowledges
financial support from DST/ICPS/QuST/Theme-1/2019/Q-68. K .D. acknowledges
financial support from DST/ICPS/QuST/Theme-2/2019/Q-74.

## References

  * MacFarlane  _et al._ (2003) A. G. J. MacFarlane, J. P. Dowling, and G. J. Milburn, Philos. Trans. R. Soc. London. Ser. A 361, 1655 (2003).
  * Nielsen and Chuang (2010) M. A. Nielsen and I. L. Chuang,  _Quantum Computation and Quantum Information_ (Cambridge University Press, Cambridge UK, 2010).
  * Feynman (1982) R. P. Feynman, Int. J. Theor. Phys. 21, 467 (1982).
  * Lloyd (1996) S. Lloyd, Science 273, 1073 (1996).
  * Cao  _et al._ (2019) Y. Cao, J. Romero, J. P. Olson, M. Degroote, P. D. Johnson, M. Kieferová, I. D. Kivlichan, T. Menke, B. Peropadre, N. P. D. Sawaya, S. Sim, L. Veis, and A. Aspuru-Guzik, Chem. Rev. 119, 10856 (2019), pMID: 31469277, https://doi.org/10.1021/acs.chemrev.8b00803 .
  * Aspuru-Guzik  _et al._ (2005) A. Aspuru-Guzik, A. D. Dutoi, P. J. Love, and M. Head-Gordon, Science 309, 1704 (2005).
  * Whitfield  _et al._ (2011) J. D. Whitfield, J. Biamonte, and A. Aspuru-Guzik, Mol. Phys. 109, 735 (2011), https://doi.org/10.1080/00268976.2011.552441 .
  * Kassal  _et al._ (2011) I. Kassal, J. D. Whitfield, A. Perdomo-Ortiz, M.-H. Yung, and A. Aspuru-Guzik, Annu. Rev. Phys. Chem. 62, 185 (2011), pMID: 21166541, https://doi.org/10.1146/annurev-physchem-032210-103512 .
  * Jones  _et al._ (2012) N. C. Jones, J. D. Whitfield, P. L. McMahon, M.-H. Yung, R. V. Meter, A. Aspuru-Guzik, and Y. Yamamoto, New J. Phys. 14, 115023 (2012).
  * Preskill (2018) J. Preskill, Quantum 2, 79 (2018).
  * McClean  _et al._ (2016) J. R. McClean, J. Romero, R. Babbush, and A. Aspuru-Guzik, New J. Phys. 18, 023023 (2016).
  * Moll  _et al._ (2018) N. Moll, P. Barkoutsos, L. S. Bishop, J. M. Chow, A. Cross, D. J. Egger, S. Filipp, A. Fuhrer, J. M. Gambetta, M. Ganzhorn, A. Kandala, A. Mezzacapo, P. Müller, W. Riess, G. Salis, J. Smolin, I. Tavernelli, and K. Temme, Quantum Sci. Technol. 3, 030503 (2018).
  * Jones  _et al._ (2019) T. Jones, S. Endo, S. McArdle, X. Yuan, and S. C. Benjamin, Phys. Rev. A 99, 062304 (2019).
  * Wang  _et al._ (2019) D. Wang, O. Higgott, and S. Brierley, Phys. Rev. Lett. 122, 140504 (2019).
  * Peruzzo  _et al._ (2014) A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, Nat. Commun. 5, 4213 (2014).
  * Santagati  _et al._ (2018) R. Santagati, J. Wang, A. A. Gentile, S. Paesani, N. Wiebe, J. R. McClean, S. Morley-Short, P. J. Shadbolt, D. Bonneau, J. W. Silverstone, D. P. Tew, X. Zhou, J. L. O’Brien, and M. G. Thompson, Sci. Adv. 4, eaap9646 (2018).
  * Colless  _et al._ (2018) J. I. Colless, V. V. Ramasesh, D. Dahlen, M. S. Blok, M. E. Kimchi-Schwartz, J. R. McClean, J. Carter, W. A. de Jong, and I. Siddiqi, Phys. Rev. X 8, 011021 (2018).
  * Higgott  _et al._ (2019) O. Higgott, D. Wang, and S. Brierley, Quantum 3, 156 (2019).
  * O’Malley  _et al._ (2016) P. J. J. O’Malley, R. Babbush, I. D. Kivlichan, J. Romero, J. R. McClean, R. Barends, J. Kelly, P. Roushan, A. Tranter, N. Ding, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, A. G. Fowler, E. Jeffrey, E. Lucero, A. Megrant, J. Y. Mutus, M. Neeley, C. Neill, C. Quintana, D. Sank, A. Vainsencher, J. Wenner, T. C. White, P. V. Coveney, P. J. Love, H. Neven, A. Aspuru-Guzik, and J. M. Martinis, Phys. Rev. X 6, 031007 (2016).
  * Hempel  _et al._ (2018) C. Hempel, C. Maier, J. Romero, J. McClean, T. Monz, H. Shen, P. Jurcevic, B. P. Lanyon, P. Love, R. Babbush, A. Aspuru-Guzik, R. Blatt, and C. F. Roos, Phys. Rev. X 8, 031022 (2018).
  * Motta  _et al._ (2023) M. Motta, G. O. Jones, J. E. Rice, T. P. Gujarati, R. Sakuma, I. Liepuoniute, J. M. Garcia, and Y.-y. Ohnishi, Chem. Sci. 14, 2915 (2023).
  * Jones  _et al._ (2024) M. A. Jones, H. J. Vallury, and L. C. Hollenberg, Phys. Rev. Appl. 21, 064017 (2024).
  * Misiewicz and Evangelista (2024) J. P. Misiewicz and F. A. Evangelista, J. Phys. Chem. A 128, 2220 (2024).
  * Xia and Kais (2020) R. Xia and S. Kais, Quantum Sci. Technol. 6, 015001 (2020).
  * Seeley  _et al._ (2012) J. T. Seeley, M. J. Richard, and P. J. Love, J. Chem. Phys. 137, 224109 (2012), https://doi.org/10.1063/1.4768229 .
  * Ganzhorn  _et al._ (2019) M. Ganzhorn, D. Egger, P. Barkoutsos, P. Ollitrault, G. Salis, N. Moll, M. Roth, A. Fuhrer, P. Mueller, S. Woerner, I. Tavernelli, and S. Filipp, Phys. Rev. Applied 11, 044092 (2019).
  * Javadi-Abhari  _et al._ (2024) A. Javadi-Abhari, M. Treinish, K. Krsulich, C. J. Wood, J. Lishman, J. Gacon, S. Martiel, P. D. Nation, L. S. Bishop, A. W. Cross, B. R. Johnson, and J. M. Gambetta, “Quantum computing with Qiskit,”  (2024), arXiv:2405.08810 [quant-ph] .
  * Olsson and Nelson (1975) D. M. Olsson and L. S. Nelson, Technometrics 17, 45 (1975).
  * community (2024) T. S. community, “scipy.optimize,”  (2008-2024).
  * Oliveira  _et al._ (2007) I. S. Oliveira, T. J. Bonagamba, R. S. Sarthour, J. C. C. Freitas, and E. R. deAzevedo,  _NMR Quantum Information Processing_ (Elsevier, Linacre House, Jordan Hill, Oxford OX2 8DP, UK, 2007).
  * Gaikwad  _et al._ (2018) A. Gaikwad, D. Rehal, A. Singh, Arvind, and K. Dorai, Phys. Rev. A 97, 022311 (2018).
  * Singh  _et al._ (2019) D. Singh, J. Singh, K. Dorai, and Arvind, Phys. Rev. A 100, 022109 (2019).


# Matching variables to equations in infinite linear equation systems

J. Pascal Gollin  J. Pascal Gollin, Discrete Mathematics Group, Institute for
Basic Science (IBS), 55 Expo-ro, Yuseong-gu, Daejeon, Korea, 34126
<EMAIL_ADDRESS>and  Attila Joó  Attila Joó, Department of Mathematics,
University of Hamburg, Bundesstraße 55 (Geomatikum), 20146 Hamburg, Germany
and Set theory and general topology research division, Alfréd Rényi Institute
of Mathematics, 13-15 Reáltanoda St., Budapest, Hungary  attila.joo@uni-
hamburg.de

(Date: November 23)

###### Abstract.

A fundamental result in linear algebra states that if a homogenous linear
equation system has only the trivial solution, then there are at most as many
variables as equations. We prove the following generalisation of this
phenomenon. If a possibly infinite homogenous linear equation system with
finitely many variables in each equation has only the trivial solution, then
there exists an injection from the variables to the equations that maps each
variable to an equation in which it appears.

###### Key words and phrases:

linear equation system, matching, thin sum

###### 2020 Mathematics Subject Classification:

Primary: 15A06, 05C50 Secondary: 05C63

The first author was supported by the Institute for Basic Science
(IBS-R029-Y3).

Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research
Foundation)-513023562 and partially by NKFIH OTKA-129211

##  1\. Introduction

Infinite linear equation systems appear in the most diverse areas of
mathematics. They have a key role in boundary value problems for linear
partial differential equations. Banach devoted them in his book [5] a whole
section entitled “Systems of linear equations in infinitely many unknowns”. In
this setting, there are countably many variables and infinite sums are defined
via convergence. Another possible approach deals with sums that are “thin”,
i.e. that there are only finitely many non-zero summands in each. Such sums
appear for example in horizon planning programs (see [11]). More recently,
these sums turned out to be fruitful in the representation theory of infinite
matroids. For a set $I$ and field $\mathbb{F}$, a family
${\mathcal{F}=(f_{j}\in\mathbb{F}^{I}\,\colon\,j\in J)}$ is called _thin_ if
for each ${i\in I}$ there are only finitely many ${j\in J}$ with
${f_{j}(i)\neq 0}$. Infinite linear combinations of the functions $f_{j}$ can
be defined in a natural way. Indeed, if ${\lambda_{j}\in\mathbb{F}}$ for
${j\in J}$, then for each ${i\in I}$ the sum ${\sum_{j\in
J}\lambda_{j}f_{j}(x)}$ is a well-defined element of ${\mathbb{F}}$, therefore
${\sum_{j\in J}\lambda_{j}f_{j}}$ can be considered as an element of
$\mathbb{F}^{I}$. If the constant $0$ function on $I$ is obtained only if
${\lambda_{j}=0}$ for every ${j\in J}$, then $\mathcal{F}$ is said to be
_thinly independent_. In other words, $\mathcal{F}$ is thinly independent if
the (possibly infinite) homogenous linear equation system ${\sum_{j\in
J}f_{j}(i)x_{j}=0\ (i\in I)}$ has only the trivial solution. Investigation of
the concept of thin dependence in the context of matroid theory was initiated
by Bruhn and Diestel [6] and became a relatively well-understood subject after
the discoveries of Afzali and Bowler [2].

Our main result states that for a thinly independent $\mathcal{F}$, there is
always a system of distinct representatives for the family
${\\{\mathsf{supp}(f_{j})\,\colon\,j\in J\\}}$ where ${\mathsf{supp}(f_{j})}$
denotes the _support_ of $f_{j}$, that is the set of those elements of $X$ on
which $f_{j}$ is non-zero. Note that by considering arbitrary families with
the the usual linear independence in $\mathbb{F}^{I}$, the analogous statement
fails. Indeed, for example the dimension of the vector space
${\mathsf{GF}(2)^{\mathbb{N}}}$ is continuum and therefore no base of it can
be injectively mapped into $\mathbb{N}$. Considering thin families but still
the usual independence does not fix this issue. To demonstrate this, let us
take in $\mathsf{GF}(2)^{\mathbb{N}}$ the unit vectors together with their
thin sum, the constant $1$ vector. Then, no desired injection exists, although
this family is linearly independent.

Let us rephrase our main result in a more elementary way. A basic fact in
linear algebra states that if a finite homogeneous linear equation system has
only the trivial solution, then there are at most as many variables as
equations. Naively lifting observations such as this to an infinite setting
often loses some interesting structural information about the problem, since a
pure comparison between cardinalities of sets is a rough measure. Instead, let
us strengthen the fact to include more structural information. If a finite
homogeneous linear equation system has only the trivial solution, then it is
not too hard to show (using standard techniques from matching theory) that
there exists an injection from the variables to the equations where each
variable is mapped to an equation in which it has non-zero coefficient. Our
main result states that this remains true for every homogeneous thin linear
equation system.

######  Theorem 1.

Let $I$ and $J$ be sets, let $\mathbb{F}$ be a field, and let
${a_{i,j}\in\mathbb{F}}$ for ${i\in I}$ and ${j\in J}$ such that for each
${i\in I}$ there are only finitely many ${j\in J}$ with ${a_{i,j}\neq 0}$.
Suppose that the (possibly infinite) homogeneous linear equation system

$\sum_{j\in J}a_{i,j}x_{j}=0\quad(i\in I)$ ($\ast$)

has only the trivial solution. Then there is an injection ${\varphi\colon J\to
I}$ such that ${a_{\varphi(j),j}\neq 0}$ for every ${j\in J}$.

In a regular matrix, one can rearrange its rows to obtain a matrix in which
every entry of the diagonal is non-zero. Using the terminology of thinly
independent families as before and using the Cantor-Bernstein Theorem (see
Theorem 2.3), we obtain the following generalisation of this fact as a
corollary of Theorem 1.

######  Corollary 2.

Let $I$ and $J$ be sets, let $\mathbb{F}$ be a field, and let
${a_{i,j}\in\mathbb{F}}$ for ${i\in I}$ and ${j\in J}$ such that the families
${((i\mapsto a_{i,j})\in\mathbb{F}^{I}\,\colon\,j\in J)}$ and ${((j\mapsto
a_{i,j})\in\mathbb{F}^{J}\,\colon\,i\in I)}$ are both thinly independent. Then
there is a bijection ${\psi\colon J\to I}$ such that ${a_{\psi(j),j}\neq 0}$
for every ${j\in J}$.

##  2\. Notation and Preliminaries

For the domain and range of a function $f$ we write ${\mathsf{dom}(f)}$ and
${\mathsf{ran}(f)}$ respectively. We write ${\mathsf{ran}_{I}(f)}$ as an
abbreviation of ${\mathsf{ran}(f)}\cap I$. For a subset
${S\subseteq\mathsf{dom}(f)}$, we denote by $f{\upharpoonright}S$ the
_restriction_ of $f$ to $S$.

A _bipartite graph_ $G$ is a triple $(S,T,E)$, where $S$ and $T$ are disjoint
sets and ${E\subseteq\\{\\{s,t\\}\,\colon\,s\in S\textnormal{ and }t\in
T\\}}$. The elements of ${S\cup T}$ are the _vertices_ of $G$ and the elements
of $E$ are the _edges_ of $G$. The set containing all ${w\in S\cup T}$ for
which ${\\{v,w\\}\in E}$ is the _neighbourhood_ ${N_{G}(v)}$ of $v$, and the
cardinal ${\lvert{N_{G}(v)}\rvert}$ is the _degree_ of $v$. A _matching_ $M$
in $G$ is a set of edges no two of which share a vertex. We say a matching $M$
_covers_ a set ${X\subseteq S\cup T}$ if each vertex in $X$ is contained in
some edge in $M$. A matching is _perfect_ if it covers ${S\cup T}$.

Let $I$ and $J$ be sets and let $\mathbb{F}$ be a field. We denote by
$\mathbb{F}^{I}$ the vector space of functions from $I$ to $\mathbb{F}$. Given
an element ${b\in\mathbb{F}^{I}}$ and ${i\in I}$ we write $b_{i}$ instead of
${b(i)}$. A _matrix_ in this paper is a function ${A\colon I\times
J\to\mathbb{F}}$. For ${i\in I}$ and ${j\in J}$, we write $a_{i,j}$ instead of
${A(i,j)}$. For a fixed ${i\in I}$, the map ${j\mapsto a_{i,j}}$ is the _row_
of $A$ corresponding to $i$ while columns are defined analogously. The _rank_
${r(A)}$ of a finite matrix $A$ is the dimension of the subspace of
${\mathbb{F}^{J}}$ spanned by its rows (equivalently the dimension of the
subspace of ${\mathbb{F}^{I}}$ spanned by its columns).

Let ${A\colon I\times J\to\mathbb{F}}$ be a matrix, and let
${b\in\mathbb{F}^{I}}$. We say that $A$ is _row-thin_ if the support of each
row of $A$ is finite. If $A$ is row-thin, then we denote by

$\sum_{j\in J}a_{i,j}x_{j}=b_{i}\quad(i\in I)$

a _thin system of linear equations_ with _variables_ ${x_{j}\ (j\in J)}$. We
may also denote this system by ${Ax=b}$. If ${b_{i}=0}$ for all ${i\in I}$, we
call the system _homogeneous_. Note that given an element
${s\in\mathbb{F}^{J}}$, the sum $\sum_{j\in J}a_{i,j}s_{j}$ is a well-defined
element of $\mathbb{F}$. A _solution_ for ${Ax=b}$ is an element
${\lambda\in\mathbb{F}^{J}}$ such that $\sum_{j\in J}a_{i,j}\lambda_{j}=b_{i}$
for each ${i\in I}$. We say that ${Ax=b}$ is _solvable_ if it has a solution.

If the field $\mathbb{F}$ is finite, then standard compactness arguments show
that the solvability of a thin linear equation system is equivalent with the
solvability of all its finite subsystems. Maybe surprisingly, this remains
true without any restriction on $\mathbb{F}$.

######  Theorem 2.1 (Compactness of thin linear equation systems, Cowen and
Emerson [9]***This theorem was rediscovered independently by Bruhn and
Georgakopoulos [7]. Their proof was later simplified by Afzali and Bowler [1,
Lemma 4.2].).

If every finite subset of the equations of a thin linear equation system is
solvable, then the whole system is solvable.

To prove our main theorem, we also need a tool from infinite matching theory
developed by Wojciechowski [12]. Let ${G=(S,T,E)}$ be a bipartite graph. A
_string_ corresponding to $G$ is an injective function $f$ defined on an
ordinal number with range ${\mathsf{ran}(f)\subseteq S\cup T}$. A string $f$
is called _saturated_ if whenever $f(\alpha)=v\in S$, then
${N_{G}(v)\subseteq\mathsf{ran}(f{\upharpoonright}\alpha})$. In other words, a
vertex ${v\in S}$ can only appear in the transfinite sequence $f$ after all of
its neighbours already appeared. For a saturated string $f$ with
${\mathsf{dom}(f)=\alpha}$, the quantity
${\mu_{G}(f)\in\mathbb{Z}\cup\\{-\infty,+\infty\\}}$ is defined by transfinite
recursion on $\alpha$ as follows.

$\mu_{G}(f):=\begin{cases}0&\mbox{if }\alpha=0,\\\
\liminf\\{\mu_{G}(f{\upharpoonright}\beta)\,\colon\,\beta<\alpha\\}&\mbox{if
}\alpha\text{ is a limit ordinal},\\\
\mu_{G}(f{\upharpoonright}\beta)-1&\mbox{if }\alpha=\beta+1\text{ and
}f(\beta)\in S,\\\ \mu_{G}(f{\upharpoonright}\beta)+1&\mbox{if
}\alpha=\beta+1\text{ and }f(\beta)\in T,\end{cases}$

where we use the convention that ${\pm\infty+k=\pm\infty}$ for
${k\in\mathbb{Z}}$. It is not too hard to prove that if $G$ admits a matching
that covers $S$, then we must have ${\mu_{G}(f)\geq 0}$ for every saturated
string $f$. Under some assumption the reverse is also true.

######  Theorem 2.2 (Wojciechowski [12, Theorem 1]†††The criterion given in
Theorem 2.2 is called $\mu$-admissibility and was inspired by the
$q$-admissibility criterion of Nash-Williams (see [10]). A characterisation of
matchability for arbitrary bipartite graphs was discovered by Aharoni, Nash-
Williams and Shelah [4]. For a survey on infinite matching theory (including
the non-bipartite case) we refer to [3].).

Let ${G=(S,T,E)}$ be a bipartite graph in which each vertex in $T$ has
countable degree. Then there is a matching in $G$ covering $S$ if and only if
${\mu_{G}(f)\geq 0}$ for every saturated string $f$ corresponding to $G$

To obtain Corollary 2, we now state the well-known theorem of Cantor and
Bernstein in a stronger, graph-theoretic form.

######  Theorem 2.3 (Cantor-Bernstein [8]).

If ${G=(S,T,E)}$ is a bipartite graph and there exist a matching $M_{S}$ that
covers $S$ as well as a matching $M_{T}$ that covers $T$, then $G$ admits a
perfect matching.

##  3\. Proof of the main results

Let us fix a homogeneous thin linear equation system ${Ax=0}$, where ${A\colon
I\times J\to\mathbb{F}}$, that admits only the trivial solution. Without loss
of generality, we may assume that $I$ and $J$ are disjoint. We define a
bipartite graph $G_{A}=(J,I,E)$ where ${\\{i,j\\}\in E}$ for ${i\in I}$ and
${j\in J}$ if and only if $a_{i,j}$ is non-zero. We will simply write $\mu$
instead of $\mu_{G_{A}}$. Moreover, when we refer to a saturated string we
will always mean a saturated string with respect to $G_{A}$.

######  Observation 3.1.

If a string $f$ is saturated, then for ${i\in
I\smallsetminus(\mathsf{ran}_{I}(f)})$ and ${j\in\mathsf{ran}_{J}(f)}$, we
have ${a_{i,j}=0}$. In other words, the matrix
${A{\upharpoonright}(I\times(\mathsf{ran}_{J}(f)))}$ is obtained from the
matrix
${A{\upharpoonright}((\mathsf{ran}_{I}(f))\times(\mathsf{ran}_{J}(f)))}$ by
extending the columns by zeroes.

######  Lemma 3.2.

If $f$ is a saturated string such that $\mu$ takes non-negative finite values
on all proper initial segments of $f$, then for every finite
${I_{0}\subseteq\mathsf{ran}_{I}(f)}$, there is a finite
${I^{\prime}\subseteq\mathsf{ran}_{I}(f)}$ extending ${I_{0}}$ and a finite
${J^{\prime}\subseteq\mathsf{ran}_{J}(f)}$ such that
${\mu(f)={\lvert{I^{\prime}}\rvert}-r(A{\upharpoonright}(I^{\prime}\times
J^{\prime}))}$.

###### Proof.

We apply transfinite induction on ${\mathsf{dom}(f)=:\alpha}$.

If ${\alpha=0}$, we must have ${I_{0}=\varnothing}$ and we can only take
${I^{\prime}:=J^{\prime}:=\varnothing}$. This is appropriate because
${\mu(\varnothing)={\lvert{\varnothing}\rvert}=r(\varnothing)=0}$.

If $\alpha$ is a limit ordinal, then
${U:=\\{\beta<\alpha\,\colon\,\mu(f{\upharpoonright}\beta)=\mu(f)\\}}$ is
unbounded in $\alpha$ by the definition of $\mu$. Let a finite set
${I_{0}\subseteq\mathsf{ran}_{I}(f)}$ be given and let ${\beta\in U}$ large
enough to satisfy ${I_{0}\subseteq\mathsf{ran}(f{\upharpoonright}\beta)}$. By
induction, we obtain a finite set
${I^{\prime}\subseteq\mathsf{ran}_{I}(f{\upharpoonright}\beta)}$ extending
$I_{0}$ and a finite set
${J^{\prime}\subseteq\mathsf{ran}_{J}(f{\upharpoonright}\beta)}$ such that
${\mu(f{\upharpoonright}\beta)={\lvert{I^{\prime}}\rvert}-r(A{\upharpoonright}(I^{\prime}\times
J^{\prime}))}$. Since
${\mathsf{ran}(f{\upharpoonright}\beta)\subseteq\mathsf{ran}(f)}$, these
$I^{\prime}$ and $J^{\prime}$ are as desired.

Finally, assume that ${\alpha=\beta+1}$ and let a finite
${I_{0}\subseteq\mathsf{ran}_{I}(f)}$ be given. Suppose first that
${i:=f(\beta)\in I}$. We may assume without loss of generality that ${i\in
I_{0}}$. By applying the induction hypotheses for ${f{\upharpoonright}\beta}$
and ${I_{0}\smallsetminus\\{i\\}}$, we can pick finite sets
${I^{*}\subseteq\mathsf{ran}_{I}(f{\upharpoonright}\beta)}$ and
${J^{*}\subseteq\mathsf{ran}_{J}(f{\upharpoonright}\beta)}$ with
${I^{*}\supseteq I_{0}\smallsetminus\\{i\\}}$ and
${\mu(f{\upharpoonright}\beta)={\lvert{I^{*}}\rvert}-r(A{\upharpoonright}(I^{*}\times
J^{*}))}$. On the one hand,
${{\lvert{I^{*}\cup\\{i\\}}\rvert}={\lvert{I^{*}}\rvert}+1}$ since ${i\notin
I^{*}}$ and ${\mu(f)=\mu(f{\upharpoonright}\beta)+1}$ since ${f(\beta)=i\in
I}$. On the other hand, ${r(A{\upharpoonright}(I^{*}\times
J^{*}))=r(A{\upharpoonright}((I^{*}\cup\\{i\\})\times J^{*}))}$ because
Observation 3.1 ensures that each column is extended only by a new $0$
coordinate. By combining these, we conclude that
${\mu(f)={\lvert{I^{*}\cup\\{i\\}}\rvert}-r(A{\upharpoonright}((I^{*}\cup\\{i\\})\times
J^{*}))}$, thus ${I^{\prime}:=I^{*}\cup\\{i\\}}$ and ${J^{\prime}:=J^{*}}$ are
appropriate. Now we suppose that ${j_{0}:=f(\beta)\in J}$. The thin linear
equation system

$\sum_{j\in\mathsf{ran}_{J}(f{\upharpoonright}\beta)}a_{i,j}x_{j}=a_{i,j_{0}}\quad(i\in
I)$

has no solution since a solution would yield a non-trivial solution of ($\ast$
‣ 1). Note that for ${i\in
I\smallsetminus\mathsf{ran}(f{\upharpoonright}\beta)}$, the equations above
are trivial (i.e. all coefficients and the right side are zeroes) by
Observation 3.1. Therefore the subsystem of the equations corresponding the
indices in ${\mathsf{ran}_{I}(f{\upharpoonright}\beta)}$ is unsolvable. By
Theorem 2.1, there is already a finite
${I_{1}\subseteq\mathsf{ran}_{I}(f{\upharpoonright}\beta)}$ such that the
corresponding subsystem is unsolvable. Now we apply the induction hypothesis
for ${f{\upharpoonright}\beta}$ and ${I_{0}\cup I_{1}}$ to pick finite sets
${I^{*}\subseteq\mathsf{ran}_{I}(f{\upharpoonright}\beta)}$ and
${J^{*}\subseteq\mathsf{ran}_{J}(f{\upharpoonright}\beta)}$ with
${I^{*}\supseteq I_{0}\cup I_{1}}$ and
${\mu(f{\upharpoonright}\beta)={\lvert{I^{*}}\rvert}-r(A{\upharpoonright}(I^{*}\times
J^{*}))}$. On one hand, ${\mu(f)=\mu(f{\upharpoonright}\beta)-1}$ since
${f(\beta)=j_{0}\in J}$. On the other hand,
${r(A{\upharpoonright}(I^{*}\times(J^{*}\cup\\{j_{0}\\})))=r(A{\upharpoonright}(I^{*}\times
J^{*}))+1}$ because the new column is not spanned by the old ones because
${I_{1}\subseteq I^{*}}$. By combining these, we conclude that
${\mu(f)={\lvert{I^{*}}\rvert}-r(A{\upharpoonright}(I^{*}\times(J^{*}\cup\\{j_{0}\\})))}$,
thus ${I^{\prime}:=I^{*}}$ and ${J^{\prime}:=J^{*}\cup\\{j_{0}\\}}$ are
appropriate, which completes the proof. ∎

Let us restate our main theorem using the notation from Section 2.

######  Theorem 1.

Let $I$ and $J$ be sets, let $\mathbb{F}$ be a field, and let $A\colon I\times
J\to\mathbb{F}$ be a row-thin matrix. If the homogeneous thin linear equation
system ${Ax=0}$ has only the trivial solution, then there is an injection
${\varphi\colon J\to I}$ such that ${a_{\varphi(j),j}\neq 0}$ for every ${j\in
J}$.

###### Proof.

Suppose for a contradiction that the desired injection does not exist, i.e.
there is no matching in $G_{A}$ that covers $J$. By Theorem 2.2, we can pick a
saturated string $f$ with ${\mu(f)<0}$. By replacing $f$ with an initial
segment of itself if necessary, we can assume that $\mu$ takes only non-
negative finite values on the proper initial segments of $f$. According to
Lemma 3.2, we have
${\mu(f)={\lvert{I^{\prime}}\rvert}-r(A{\upharpoonright}(I^{\prime}\times
J^{\prime}))}$ for some finite ${I^{\prime}\subseteq I}$ and
${J^{\prime}\subseteq J}$. Since the rank of a matrix is at most the number of
rows this leads to ${\mu(f)\geq 0}$, contradicting the choice of $f$. ∎

Let us now prove Corollary 2, which we restate using the terminology from
Section 2.

######  Corollary 2.

Let $I$ and $J$ be sets, let $\mathbb{F}$ be a field, and let ${A\colon
I\times J\to\mathbb{F}}$ such that the family of rows and the family of
columns are both thinly independent. Then there is a bijection ${\psi\colon
J\to I}$ such that ${a_{\psi(j),j}\neq 0}$ for every ${j\in J}$.

###### Proof.

Consider the graph $G_{A}$ as above. By Theorem 1, since the family of rows is
thinly independent there is matching that covers $I$, and since the family of
columns is thinly independent, there is a matching that covers $J$. By Theorem
2.3, $G_{A}$ admits a perfect matching $M$. Setting $\psi(j)$ to be the unique
${i\in I}$ for which ${\\{i,j\\}\in M}$ completes the proof. ∎

## References

  * [1] Seyed Hadi Afzali Borujeni and Nathan Bowler  “Thin sums matroids and duality”  In _Advances in Mathematics_ 271 Elsevier, 2015, pp. 1–29  DOI: 10.1016/j.aim.2014.10.010
  * [2] Seyed Hadi Afzali Borujeni, Hiu-Fai Law and Malte Müller  “Finitary and cofinitary gammoids”  In _Discrete Applied Mathematics_ 209 Elsevier, 2016, pp. 2–10
  * [3] Ron Aharoni  “Infinite matching theory”  In _Discrete mathematics_ 95.1-3 Elsevier, 1991, pp. 5–22  DOI: 10.1016/0012-365x(91)90327-x
  * [4] Ron Aharoni, Crispin Nash-Williams and Saharon Shelah  “A general criterion for the existence of transversals”  In _Proceedings of the London Mathematical Society_ 3.1 Narnia, 1983, pp. 43–68  DOI: 10.1112/plms/s3-47.1.43
  * [5] S. Banach  “Theory of linear operations” Translated from the French by F. Jellett, With comments by A. Pełczyński and Cz. Bessaga 38, North-Holland Mathematical Library  North-Holland Publishing Co., Amsterdam, 1987, pp. x+237
  * [6] Henning Bruhn and Reinhard Diestel  “Infinite matroids in graphs”  In _Discrete Mathematics_ 311.15, 2011, pp. 1461–1471  DOI: https://doi.org/10.1016/j.disc.2010.12.015
  * [7] Henning Bruhn and Agelos Georgakopoulos  “Bases and closures under infinite sums”  In _Linear Algebra and its Applications_ 435.8 Elsevier BV, 2011, pp. 2007–2018  DOI: 10.1016/j.laa.2011.03.029
  * [8] Georg Cantor  “Mitteilungen zur Lehre vom Transfiniten”  In _Zeitschrift für Philosophie und philosophische Kritik_ 91, 1987, pp. 81–125
  * [9] Robert Cowen and William Emerson  “A compactness theorem for linear equations”  In _Studia Logica_ 57.2-3 Springer ScienceBusiness Media LLC, 1996, pp. 355–357  DOI: 10.1007/bf00370839
  * [10] C…. Nash-Williams  “Another criterion for marriage in denumerable societies”  In _Annals of Discrete Mathematics_ 3 Elsevier, 1978, pp. 165–179  DOI: 10.1016/s0167-5060(08)70505-3
  * [11] H. Romeijn and Robert L. Smith  “Shadow Prices in Infinite-Dimensional Linear Programming”  In _Mathematics of Operations Research_ 23.1 Institute for Operations Researchthe Management Sciences (INFORMS), 1998, pp. 239–256  DOI: 10.1287/moor.23.1.239
  * [12] Jerzy Wojciechowski  “A Criterion for the Existence of Transversals of Set Systems”  In _Journal of the London Mathematical Society_ 56.3 Wiley, 1997, pp. 491–503  DOI: 10.1112/s0024610797005528