# Variational quantum state discriminator for supervised machine learning

Dongkeun Lee  Department of Chemistry, Sungkyunkwan University, Suwon, 16419,
Republic of Korea  Kyunghyun Baek  Electronics and Telecommunications Research
Institute, Daejeon, 34129, Republic of Korea  Joonsuk Huh
<EMAIL_ADDRESS>Department of Chemistry, Sungkyunkwan University, Suwon,
16419, Republic of Korea  Sungkyunkwan University Advanced Institute of
Nanotechnology, Suwon, 16419, Republic of Korea  Institute of Quantum
Biophysics, Sungkyunkwan University, Suwon, 16419, Republic of Korea  Daniel
K. Park<EMAIL_ADDRESS>Department of Applied Statistics, Yonsei
University, Seoul, 03722, Republic of Korea  Department of Statistics and Data
Science, Yonsei University, Seoul, 03722, Republic of Korea

###### Abstract

Quantum state discrimination (QSD) is a fundamental task in quantum
information processing with numerous applications. We present a variational
quantum algorithm that performs the minimum-error QSD, called the variational
quantum state discriminator (VQSD). The VQSD uses a parameterized quantum
circuit that is trained by minimizing a cost function derived from the QSD,
and finds the optimal positive-operator valued measure (POVM) for
distinguishing target quantum states. The VQSD is capable of discriminating
even unknown states, eliminating the need for expensive quantum state
tomography. Our numerical simulations and comparisons with semidefinite
programming demonstrate the effectiveness of the VQSD in finding optimal POVMs
for minimum-error QSD of both pure and mixed states. In addition, the VQSD can
be utilized as a supervised machine learning algorithm for multi-class
classification. The area under the receiver operating characteristic curve
obtained in numerical simulations with the Iris flower dataset ranges from
0.97 to 1 with an average of 0.985, demonstrating excellent performance of the
VQSD classifier.

##  I Introduction

Quantum measurement theory plays a crucial role in quantum information
processing (QIP), driving advancements in communication, computation, and
sensing [1, 2, 3, 4]. The theory states that non-orthogonal quantum states can
be distinguished with non-zero probability through quantum measurement, which
can generally be described by Positive Operator-Valued Measures (POVMs) [5,
6]. This arises from the geometric structure of quantum states defined on a
Hilbert space and the measurement postulate of quantum mechanics. Quantum
state discrimination (QSD) is a well-established field that provides a
theoretical ground for the distinguishability of quantum states and the
retrieval of classical information. Notably, the optimal strategy for
distinguishing two quantum states was proposed even prior to the advent of
quantum computing [7].

The ability to distinguish non-orthogonal states offers exciting prospects for
data science and machine learning as an arbitrary number of data can be
encoded in a single qubit. There is no classical analog to this since a
classical bit can only represent two orthogonal states. As a result, the
concept of QSD has emerged in various contexts within machine learning. One
area of research focuses on utilizing QSD for classical-quantum hybrid machine
learning. For instance, the optimal measurement theory for two-element POVMs
has been applied to determine the best quantum feature map for binary
classification tasks [8] and to learn a quantum circuit for quantum data
classification with a limited set of two-qubit states [9, 10]. Several
quantum-inspired algorithms 111Quantum-inspired algorithms refer to algorithms
executed on classical hardware but using the mathematical formalism of quantum
mechanics. based on the theory of QSD for constructing classifiers have also
been reported [12, 13, 14]. However, finding the optimal measurement for QSD
using a classical computer becomes computationally intractable for a large
number of qubits, as it necessitates complete information about the states,
often obtained through quantum state tomography. In addition, the two-state
QSD requires a spectral decomposition to construct the optimal POVM.
Furthermore, the optimization for more than two states is typically performed
through semidefinite programming (SDP), which involves a number of steps that
increase polynomially with the dimension of the Hilbert space and thus,
exponentially with the number of qubits [10]. Furthermore, converting the
optimal POVM found from classical methods to a corresponding quantum circuit
for implementation is generally a challenging task. Given these challenges, it
is natural to explore the possibility of directly finding the optimal POVM for
QSD on a quantum computer.

Motivated by the broad applications of QSD in various fields, including
machine learning, and the challenges of classical optimization, we present a
variational quantum algorithm (VQA) for performing minimum-error QSD. Our VQA
is a general solution capable of discriminating quantum systems of any
dimension, whether pure or mixed, in a systematic manner. Based on the
variational quantum state discriminator (VQSD) for mixed states, we also
propose a quantum multi-class classification algorithm. The training of the
quantum circuit corresponds to identifying non-linear decision boundaries
within the Hilbert space where the data is embedded, as the number of
distinguishable classes can exceed the dimension of the Hilbert space. While
this work primarily demonstrates the applicability of the VQSD in machine
learning, it can be applied to any application requiring minimum-error QSD.

The remainder of the paper is organized as follows. In Sec. II, we review
theoretical backgrounds for our work, such as the quantum circuit for POVMs
and the minimum-error QSD. Therein, we generalize a previous work that
reported the gate decomposition for four-element POVMs on two-qubit states to
an arbitrary number of qubits and POVM elements. Section III presents the
VQSD. It describes how to construct the cost function and the training
procedure in detail. The numerical simulation and results are also described
at the end of the section, demonstrating the success of VQSD in finding the
optimal POVM. Section IV describes the application of the VQSD in supervised
machine learning and show simulation results for multi-class classification
with the Iris flower dataset. Conclusions, discussion, and potential future
research directions are provided in Sec. V.

##  II Theoretical Framework

###  II.1 Quantum Circuit for POVMs

(a) ($n_{T}+n_{A}$)-qubit unitary circuit $\mathcal{U}$

(b) ($n_{T}+1$)-qubit gate $W_{a}$ (c) CSD binary tree

Figure 1: The circuit diagram for the unitary operation $\mathcal{U}$. It
describes performing POVMs on the arbitrary quantum states or target states
$|\psi\rangle_{T}$. Which POVM element is performed is determined by measuring
ancillary qubits and the bit string outcomes $z_{1}z_{2}\cdots z_{n_{A}}$
correspond to the POVM outcomes $m$. (a) A circuit $\mathcal{U}$ is factorized
into $n_{A}$ numbers of (uniformly controlled) $W_{a}$ gates and (b) a
($n_{T}+1$)-qubit gate $W_{a}$ consists of a general $n_{T}$-qubit $U$ and an
uniformly controlled $R_{y}$. The dotted lines drawn over $W_{a}$ gates
indicate that the corresponding qubits are not involved in the operation and
the half-filled circle stands for the uniform controls. (c) The CSD tree
describes binary decisions generated from ancillary qubits of the circuit
$\mathcal{U}$ at a glance.

A measurement in quantum mechanics is in general described by a set of
positive semi-definite operators $\\{E_{m}\\}$ satisfying
$\sum_{m=0}^{l-1}E_{m}=I$. Here, $m\in\\{0,\ldots,l\\}$ labels the possible
measurement outcomes, and the probability to obtain $m$ given a density matrix
$\rho$ that describes the quantum state is given by $p_{m}=\Tr(E_{m}\rho)$.
Note that the operators can be decomposed as $E_{m}=K_{m}^{\dagger}K_{m}$
where $\\{K_{m}\\}$ is known as a set of the Kraus operators. Upon obtaining
the outcome $m$, the quantum state evolves to $K_{m}\rho
K_{m}^{\dagger}/p_{m}$. We refer to such measurement procedure with the
collection of matrices $E_{m}$ as an $l$-element Positive Operator-Valued
Measure (POVM) [5].

According to Neumark’s theorem, an arbitrary POVM can be implemented with a
quantum circuit by applying a unitary operator on an extended system
consisting of the target quantum state and an ancillary system and then
measuring the latter [15, 16]. In this regard, ancillary qubits are introduced
and a multi-qubit unitary gate denoted by $\mathcal{U}$ acts on all qubits.
The unitary operation $\mathcal{U}$ on target and ancillary qubits can be
described in terms of a set of the Kraus operators $\\{K_{m}\\}$ as

$\mathcal{U}|\psi\rangle_{T}|\mathbf{0}\rangle_{A}=\sum^{l-1}_{m=0}\left(K_{m}|\psi\rangle_{T}\right)|m\rangle_{A},$
(1)

where $|\psi\rangle_{T}$ is the target quantum state consisting of $n_{T}$
qubits and $|\mathbf{0}\rangle_{A}$ denotes all ancillary qubits in the state
$|0\rangle$ (See Fig. 1(a)). Equation (1) signifies the implementation of the
quantum channel of Kraus rank $l$ [17, 18]. Performing a POVM on
$|\psi\rangle_{T}$ is then embodied by measuring ancillary qubits in the
computational basis (e.g. projective measurement in the $Z$ basis), which
yields the outcome $m$ with the probability
$p(m)={}_{T}\langle\psi|K^{\dagger}_{m}K_{m}|\psi\rangle_{T}$. Here, we call
the unitary operation $\mathcal{U}$ the POVM circuit.

Since an arbitrary unitary gate can be parameterized with real-valued
parameters, the POVM operator that produces the outcome $m$ can be written as

$\displaystyle\mathcal{E}_{m}(\Theta)$
$\displaystyle=E_{m}(\Theta)\otimes|\mathbf{0}\rangle_{A}\langle\mathbf{0}|$
$\displaystyle=\mathcal{U}^{\dagger}(\Theta)(I_{T}\otimes
M_{m})\,\mathcal{U}(\Theta),$ (2)

where $\Theta$ is the parameter vector, $I_{T}$ is the identity operator
acting on the target qubits, and $M_{m}=|m\rangle_{A}\langle m|$ represents
the projective measurement on the ancillary qubits in the computational basis.
Note that each bit string $z_{1}z_{2}\cdots z_{n_{A}}\in\\{0,1\\}^{n_{A}}$
produced by measuring $n_{A}$ ancillary qubits is converted into the decimal
value $m\in\\{0,\cdots,l-1\\}$, the outcome index of POVMs.

There are several ways to decompose the multi-qubit quantum circuits such as
the cosine-sine decomposition [19, 20], the decomposition introduced by Knill
[21], and the column-by-column decomposition [22]. For a better understanding
of the implementation of POVMs in the quantum circuit, we opt for a proper
unitary decomposition, the diagrams of which are illustrated in Fig. 1. The
decomposition of $\mathcal{U}$ for $n_{T}=n_{A}=2$ is discussed in Ref. [9].
We generalize the result therein for any $n_{T}$ and $n_{A}$ based on the
cosine-sine decomposition (CSD) and provide its rigorous development in
Appendix A. Specifically, an arbitrary quantum circuit $\mathcal{U}$ is first
decomposed into a set of ($n_{T}+1$)-qubit unitary operators $W_{a}$,
uniformly controlled by $a-1$ ancilla qubits as depicted in Fig. 1(a). A
unitary operator $W_{a}$ is then decomposed into a general $n_{T}$-qubit
unitary gate $U$ and an uniformly controlled single-qubit rotation around the
$y$-axis of the Bloch sphere, denoted by $R_{y}$, is applied to the $a$th
ancillary qubit controlled by all target qubits as shown in Fig. 1(b). The
dimension of the parameter vector $\Theta$ from all $U$ and $R_{y}$ gates is
$(l-1)(2^{2n_{T}}-1+2^{n_{T}})$.

Let us scrutinize the circuit structures of Fig. 1(a) and (b) from the
perspective of the Kraus operator. The action of the uniformly controlled
$R_{y}$ gate in Fig. 1(b) is equivalent to the multiplication of a diagonal
matrix by a state vector in the target system. Depending on the state of the
ancillary qubit, the diagonal matrix is either $C:=\cos(diag(\Theta_{R}))$ if
the ancilary qubit is in the state $|0\rangle_{A}$, or
$S:=\sin(diag(\Theta_{R}))$ for the state $|1\rangle_{A}$, where
$\Theta_{R}=(\theta_{1},\cdots,\theta_{2^{n_{T}}})$ is a parameter vector
involving $2^{n_{T}}$ angles of $R_{y}$ gates. Thus, a single gate $W_{a}$
implies the implementation of the Kraus operators of rank 2, $\\{CU,SU\\}$.

In order to generate the Kraus operator of rank $l>2$, an ancillary system of
$n_{A}=\lceil\log_{2}l\rceil$ qubits is required and $(a-1)$-fold uniformly
controlled $W_{a}$ gates are applied consecutively as the number of control
qubits are increased up to $n_{A}-1$, as shown in Fig. 1(a). Each uniformly
controlled $W_{a}$ gate builds up the binary rank Kraus operators that depend
on the previous results of the ancillary system. The whole procedure can be
figured out by introducing a CSD binary tree (see Fig. 1(c)) [19]. Then the
Kraus operator of rank $l$ can be formulated as

$K_{m}=\prod^{n_{A}}_{a=1}D_{j(a)}U_{j(a)},$ (3)

where a diagonal matrix $D_{j(a)}$ becomes either $C_{j(a)}$ if $z_{a}=0$, or
$S_{j(a)}$ if $z_{a}=1$. Here, the index
$j(a):=2^{a-1}+\sum^{a-1}_{i=1}z_{i}2^{a-1-i}$ is introduced to enumerate the
actions of the uniformly controlled $W_{a}$ gate because it is comprised of a
sequence of $(a-1)$-fold controlled gates with different angles (see Fig. 7 in
Appendix A). For example, a set of rank-4 Kraus operators,
$\\{C_{2}U_{2}C_{1}U_{1},S_{2}U_{2}C_{1}U_{1},C_{3}U_{3}S_{1}U_{1},S_{3}U_{3}S_{1}U_{1}\\}$,
can be carried by using $W_{1}$ and uniformly controlled $W_{2}$ gates and one
of its elements is determined by the measurement outcome $z_{1}z_{2}$.

The implementation of the control part of the uniformly controlled $W_{a}$
gates can be performed classically as it commutes with measurements, as
detailed in the appendix (Appendix A). As a result, the quantum gate
complexity is primarily determined by the implementation of the $W_{a}$ gate
depicted in Fig. 1(b). In the implementation of $W_{a}$, the complexity of the
required number of CNOT gates in an arbitrary $n_{T}$-qubit unitary $U$ is
$O(2^{2n_{T}})$ [20]. Additionally, the uniformly controlled $R_{y}$ operation
involves $2^{n_{T}}$ CNOT gates [23]. Thus the total number of CNOT gates in
the circuit $\mathcal{U}$ is $O(2^{2n_{T}}l)$ for a given value of $l$. In the
case of $n_{T}=2$, the total number of CNOT gates reduces to $3(l-1)$, where
three is considered the smallest number of CNOT gates for a universal two-
qubit gate [24, 25, 26]. To mitigate the exponential increase in the number of
two-qubit gates required for $\mathcal{U}$, it may be desirable to choose a
simpler structure for $\mathcal{U}$ such as the ansatz used in the Variational
Quantum Eigensolver (VQE) [10]. However, this simplification comes at the cost
of sacrificing global optimality.

###  II.2 Minimum-error quantum state discrimination

Quantum state discrimination is a protocol that aims to identify a quantum
state among a set of a priori completely known candidate states. The POVM
framework allows for the discrimination of non-orthogonal states with the
optimal success probability which depends on the distance between a priori
quantum states. This naturally motivates the minimum-error QSD whose goal is
to maximize the success probability for correctly guessing a state.

In preparation for minimum-error QSD, let us consider a set of $l$ different
quantum states $\\{\rho_{n}\\}^{l-1}_{n=0}$ with the corresponding a priori
probabilities $\\{q_{n}\\}_{n=0}^{l-1}$. When POVMs $\\{E_{m}\\}$ are
performed on quantum states $\rho_{n}$, the probability of the outcome $m$ is
$p(m|n)=\Tr[E_{m}\rho_{n}]$. If appropriate POVMs are taken, one can correctly
guess a state $\rho_{m}$ with a high probability $q_{m}p(m|m)$. In this
context, the minimum-error QSD aims to minimize the error probability

$p_{error}=1-\sum_{m=0}^{l-1}q_{m}\Tr[\rho_{m}E_{m}],$ (4)

where the last term denotes the success probability of the given POVM [27,
28].

If only two elements of POVMs ($l=2$) are implemented for discriminating two
different quantum states, one can analytically find the optimal POVMs and the
associated minimum probability of the error Eq.(4), known as the Helstrom
bound $\mathcal{B}_{H}$ in this special case [7]. Starting from Eq.(4), the
minimum error probability can be rewritten as

$\min p_{error}=\frac{1}{2}-\max_{E}\frac{1}{2}\Tr[E\Lambda]$ (5)

where $E=E_{0}-E_{1}$ and $\Lambda=q_{0}\rho_{0}-q_{1}\rho_{1}$. By applying
the spectral decomposition, one can get
$\Lambda=\lambda_{+}|\lambda_{+}\rangle\langle\lambda_{+}|+\lambda_{-}|\lambda_{-}\rangle\langle\lambda_{-}|$
where $\lambda_{+}$ and $\lambda_{-}$ denote positive and negative eigenvalues
of $\Lambda$, repsectively. The optimal POVMs can be obtained as
$E_{0}=|\lambda_{+}\rangle\langle\lambda_{+}|$ and
$E_{1}=|\lambda_{-}\rangle\langle\lambda_{-}|$. The Helstrom bound is then
given by $\mathcal{B}_{H}:=\frac{1}{2}-\frac{1}{2}\Tr|\Lambda|$.

When $l$ is larger than two, the set of POVMs that minimizes Eq.(4) usually
does not have an analytical solution. Instead, the necessary and sufficient
conditions are known to be satisfied by a set of the optimal POVMs and are
expressed as

$\displaystyle E_{m}\left(q_{m}\rho_{m}-q_{n}\rho_{n}\right)E_{n}=0$ (6)
$\displaystyle\sum^{l-1}_{m=0}q_{m}E_{m}\rho_{m}-q_{n}\rho_{n}\geq 0$ (7)

for any $m,n=0,\cdots,l-1$ [29, 7, 30]. It is noted that these conditions are
equivalent to each other and closely related to the duality relationship of
the semidefinite program [30]. The minimum-error QSD problem can be formulated
as the SDP. The classical solver for the SDP, however, requires the number of
iterations that grows exponentially with the number of target qubits and
polynomially with the number of the POVM elements as $O(2^{\omega
n_{T}}l^{\omega})$, where $\omega$ is the constant ranges from 2.37188 to 3
depending on the algorithm for matrix multiplication (see Appendix B). In
addition, the objective function involves computing the outcome probabilities
of POVM, and hence computing it classically requires exponential runtime. The
aforementioned procedure assumes that the target density matrices are fully
known. If not, quantum state tomography, which adds another layer of
exponential complexity, is also required. The intractability of minimum-error
QSD via classical means motivates the development of quantum algorithms for
it. Our method, which is described in the following section, is based on
training a parameterized quantum circuit, aiming to realize it on the noisy
intermediate-scale quantum (NISQ) devices [31]. Later, we will use the
classical solver for the SDP to compare its result with that of the VQSD [32].

##  III Variational Quantum State Discrimination

Training a parameterized quantum circuit with classical optimization
algorithms (e.g. gradient-based) have gained much attention recently,
especially as an effective means to utilize NISQ devices. Without loss of
generality, we refer to an algorithm based on such an approach variational
quantum algorithm (VQA) [33, 34]. Here, we develop a VQA that learns to
perform the minimum-error QSD in a supervised manner. In other words, the VQA
trains a quantum circuit to perform the optimal POVM for a given set of
labelled quantum states. We call this VQA the variational quantum state
discriminator (VQSD). While the labels for the quantum states need to be known
a priori, the quantum states themselves can be completely unknown, and this
distinguishes the proposed algorithm from the existing QSD methods.

###  III.1 Cost function

The first step towards utilizing the VQA for minimum-error QSD is establishing
an appropriate cost function that can discriminate different labeled sets
beyond individual quantum states. Let us consider that a set of $N$ quantum
states with $l$ labels,

$\mathcal{D}=\\{(|\Psi_{n}\rangle,y_{n})|\,y_{n}\in\\{0,\cdots,l-1\\},\;1\leq
n\leq N\\},$ (8)

is partitioned into $l$ disjoint subsets. A subset of quantum states with the
same label $m$ can be denoted by
$\mathcal{D}_{m}=\\{(|\Psi_{n}\rangle,y_{n})|y_{n}=m,\,\forall
n\in\mathcal{N}_{m}\\}$ with the index set
$\mathcal{N}_{m}=\\{n|y_{n}=m,\,\forall n\in\mathbb{N}\\}$.

To discriminate between different subsets $\mathcal{D}_{m}$ of input states
$\\{|\Psi_{n}\rangle_{I}\\}_{n}$, one can perform POVMs on either all $n_{I}$
input qubits or $n_{T}$ qubits out of $n_{I}$ qubits for each input state
$|\Psi_{n}\rangle_{I}$. The latter can be considered as measuring the reduced
density matrix of $|\Psi_{n}\rangle_{I}$ on the target subsystem consisting of
$n_{T}$ target qubits. This reduced density matrix can be written as
$\rho_{T,n}=\text{Tr}_{\bar{T}}|\Psi_{n}\rangle_{I}\langle\Psi_{n}|$, where
the complement of the target subsystem $\bar{T}$ is traced out.

For given $|\Psi_{n}\rangle_{I}$, a POVM $E_{m}$ may be performed on the
target subsystem, which yields the probability of the outcome
$p(m|n)=\text{Tr}[E_{m}\rho_{T,n}]=\,_{I}\langle\Psi_{n}|E_{m}|\Psi_{n}\rangle_{I}$.
For given $\mathcal{D}_{m}$, it is possible to perform a POVM with the outcome
$m$ on quantum states in the same class and obtain the probability of the
outcome $m$,
$p(m|\mathcal{D}_{m}):=\sum_{n\in\mathcal{N}_{m}}\,{}_{I}\langle\Psi_{n}|E_{m}|\Psi_{n}\rangle_{I}/|\mathcal{N}_{m}|$,
where $|\mathcal{N}_{m}|$ is the cardinality of $\mathcal{N}_{m}$. This
probability can also be viewed as performing $E_{m}$ on the target subsystem
of the mixed state

$\rho^{\prime}_{m}=\sum_{n\in\mathcal{N}_{m}}|\Psi_{n}\rangle\langle\Psi_{n}|/|\mathcal{N}_{m}|,$
(9)

which is the uniform mixture of all states in a subset $\mathcal{D}_{m}$.

As mentioned in the previous section, one can make POVMs on the input states
in the quantum circuit. From the MED Eq.(4), the cost function can then be
expressed in terms of the parameterized quantum circuit as

$\displaystyle C(\Theta)$
$\displaystyle=1-\sum_{m=0}^{l-1}q_{m}p(m|\mathcal{D}_{m})$
$\displaystyle=1-\sum^{l-1}_{m=0}\sum_{n\in\mathcal{N}_{m}}\frac{1}{|\mathcal{D}|}\langle\Psi^{0}_{n}|\mathcal{E}_{m}(\Theta)|\Psi^{0}_{n}\rangle,$
(10)

where $|\Psi^{0}_{n}\rangle=|\Psi_{n}\rangle_{I}|\mathbf{0}\rangle_{A}$ is a
quantum state of all qubits and $q_{m}=|\mathcal{N}_{m}|/|\mathcal{D}|$ is an
a priori probability for the subset $\mathcal{D}_{m}$. Minimizing this cost
function reduces the error of the label discrimination. This signifies that
the VQSD is well-trained from a set of the quantum states and can predict the
label of a new quantum state based on the measurement that optimally separates
the subsets $\mathcal{D}_{m}$ according to their label $m$. Note that the cost
function $C(\Theta)$ Eq.(10) is identical to the error probability $p_{error}$
in Eq.(4) when $|\mathcal{N}_{m}|=1$ for all $m$.

###  III.2 Algorithm

Figure 2: Illustration of the variational quantum state discriminator. The
input circuit prepares a set of arbitrary quantum states, either pure or
mixed, subject to POVM. In this example, the set of two-qubit states is
$\\{\mathcal{V}_{n}|00\rangle\\}_{n}$. A parameterized POVM circuit is then
performed on the target qubit of the input state ($n_{T}=1$ and $n_{I}=2$ in
this example) and trained by optimizing the cost function $C(\Theta)$ given in
Eq. (10)

The VQSD algorithm can be constructed as follows. First, a set of the input
states $\\{|\Psi_{n}\rangle\\}_{n\leq N}$ is given and ancillary qubits are
prepared in the state $|\mathbf{0}\rangle_{A}$. Note that the algorithm only
requires the label information and the input quantum states does not need to
be known. Hence it bypasses the quantum state tomography. Second, the
parameterized POVM circuit $\mathcal{U}(\Theta)$ acts on $n_{T}$ target qubits
out of $n_{I}$ input qubits, which implies that POVMs can be performed on the
reduced density matrix $\rho_{T,n}$ of an input state $|\Psi_{n}\rangle$. When
implementing on NISQ devices, small $n_{T}$ is desirable. Note that the number
of outcomes obtained from POVMs can be controlled by adjusting the number of
ancillary qubits. Third, the outcomes $m$ and the corresponding probabilities
$p(m|n)$ of POVMs are obtained from measuring ancillary qubits in the
computational basis. Fourth, a cost function Eq.(10) is constructed from the
outcomes $m$ and probabilities $p(m|n)$ and minimized using classical
optimizer. The parameter vector $\Theta$ in the POVM circuit is then optimized
toward synchronizing the outcome of POVMs with the label of the input states.
The trained POVM circuit $\mathcal{U}(\Theta_{opt})$ with the optimal
parameter vector $\Theta_{opt}$ serves as a quantum state discriminator. In
consequence, an unlabeled input state being inserted, the trained POVM circuit
and the measurement on ancillary qubits predicts a label with the highest
probability. The VQSD algorithm is illustrated in Fig. 2.

###  III.3 Simulation and Results

We demonstrate the performance of the VQSD via classical simulations. The
simulations are carried out using PennyLane [35], and the quantum circuit
parameters are updated via gradient descent optimization using adaptive moment
(ADAM) estimation [36].

The VQSD is tested with both pure and mixed states. The quantum circuit
creates a mixed state by tracing out a subsystem from an entangled state. More
specifically, the simulation uses the quantum circuit shown in Fig. 3, which
prepares an entangled state by applying $\mathcal{V}_{\rho_{\zeta}}$ to
$|00\rangle$. The reduced density matrix on the second qubit, denoted by
$\rho_{\zeta}$, is the mixed state inserted as the input to the POVM circuit.
The mathematical form of a single-qubit mixed state $\rho_{\zeta}$ is then
given by

$\displaystyle\rho_{\zeta}(\varphi)\equiv\cos^{2}\varphi|\zeta_{+}\rangle\langle\zeta_{+}|+\sin^{2}\varphi|\zeta_{-}\rangle\langle\zeta_{-}|,$
(11)

where $|\zeta_{\pm}\rangle$ denotes the eigenstates of the Pauli matrices
$\sigma_{\zeta}$ with $\zeta\in\\{x,y,z\\}$ and $\varphi$ parameterizes the
mixture weights. The Bloch vector of $\rho_{\zeta}(\varphi)$ lies along the
$\zeta$ axis of the Bloch sphere. In order to prepare a mixed state
$\rho_{\zeta}(\varphi)$ as an input in the quantum circuit, we make use of a
two-qubit unitary gate $\mathcal{V}_{\rho_{\zeta}}$ illustrated in Fig. 3 that
comprises $R_{y}$, CNOT, Hadamard, and phase shift gates. $R_{y}(\varphi)$ and
CNOT gates generate an entangled state
$\cos\varphi|00\rangle+\sin\varphi|11\rangle$. The $U_{\zeta}$ gate for each
qubit changes the $z$ basis into the $\zeta$ basis,
$\cos\varphi|\zeta_{+}\zeta_{+}\rangle+\sin\varphi|\zeta_{-}\zeta_{-}\rangle$,
where $U_{z}=I$, $U_{x}=H$, and $U_{y}=HS$. We then proceed with only one
qubit after the unitary operation $\mathcal{V}_{\rho_{\zeta}}$, which
signifies that the reduced density matrix of the second qubit,
$\rho_{2}=\text{Tr}_{1}[\mathcal{V}_{\rho_{\zeta}}|00\rangle\langle
00|\mathcal{V}^{\dagger}_{\rho_{\zeta}}]$, is subject to QSD.

Figure 3: Circuit diagrams for input-state preparations. (a) A mixed state
$\rho_{\zeta}$ is realized by exploiting one of two qubits in the state
$\mathcal{V}_{\rho_{\zeta}}|00\rangle$. The gate $U_{\zeta}$ corresponds to
one of three $U_{x}=H$, $U_{y}=HS$, and $U_{z}=I$.

Figure 4: Minimum-error QSD using the variational quantum algorithm. Sets of a
priori quantum states are given as (a)
$\\{\rho_{z}(\pi/5),\rho_{x}(\pi/6)\\}$, (b)
$\\{|0\rangle,|1\rangle,|+\rangle\\}$, (c)
$\\{\rho_{z}(\pi/5),\rho_{x}(\pi/6),\rho_{y}(\pi/8)\\}$, and (d)
$\\{|00\rangle,|{++}\rangle,\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle),\frac{1}{\sqrt{2}}(|01\rangle+|10\rangle)\\}$
and a priori probabilities are assumed to be equal. The two-state
discrimination task in (a) is compared with the Helstrom measurement, and the
three-state discrimination tasks in (b) to (d) are compared with the results
from the SDP solver and the PGM. Each plot shows that the cost function
converges to its minimum after approximately 100 to 150 iterations.

Together with the quantum circuit Fig. 3 of the mixed state Eq.(11), we
prepare four a priori sets of quantum states with equal probabilities:
$\\{\rho_{z}(\pi/5),\rho_{x}(\pi/6)\\}$,
$\\{|0\rangle,|1\rangle,|+\rangle\\}$,
$\\{\rho_{z}(\pi/5),\rho_{x}(\pi/6),\rho_{y}(\pi/8)\\}$, and
$\\{\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle),\frac{1}{\sqrt{2}}(|01\rangle+|10\rangle),|00\rangle,|{++}\rangle\\}$,
We then construct the parameterized POVM circuit Eq.(II.1) and the cost
function Eq.(10) with the condition $m=n$. By implementing the VQSD, we attain
the minimum value of the cost function with the convergence tolerance of
around $10^{-7}$. The minimum error of which is depicted in Fig. 4.

To verify the correctness of the solution obtained from the VQSD, we compare
the two-state discrimination task with the Helstrom measurement, and the
three-state discrimination tasks with the semidefinite programming (SDP)
solved by a convex optimization tool [32]. The difference between two minimum
errors from the classical SDP solver and the VQSD is around $10^{-6}$, which
confirms the validity of the VQSD. We also compare our method with the pretty-
good measurement (PGM) defined as
$\Pi_{m}:=q_{m}\rho^{-1/2}\rho_{m}\rho^{-1/2}$ with the ensemble
$\rho=\sum_{n=0}^{l-1}q_{n}\rho_{n}$, which is a suboptimal $l$-element POVM
when $l>2$ [37, 38, 39]. This measurement entirely depends on the state
preparation and is prescribed to gather the information of a quantum system in
a simple way with an analytical expression, although the global optimality is
not guaranteed. The error probability from performing the PGMs on each set of
quantum states is shown in Fig. 4(b)-(d), which corresponds to the fact that
the optimal POVM is generally not a PGM for the minimum-error QSD task [40].
Simulation results verify that the VQSD finds better measurements than the PGM
in all instances.

##  IV Application in Machine Learning

###  IV.1 Connection to classification

We now apply the VQSD to classification, a ubiquitous problem in data science
that can be solved via supervised learning. The training dataset for $l$-class
classification is the same as $\mathcal{D}$ in Eq. (8), except
$|\Psi_{n}\rangle$ represents the data embedded as the quantum state. With the
training dataset, the VQSD can be trained to perform minimum-error QSD to
distinguish $\rho^{\prime}_{m}$ in Eq. (9) with $m\in\\{0,\ldots,l-1\\}$. Once
training is completed, a test datum embedded as a quantum state is fed into
the VQSD circuit, and the resulting POVM element corresponds to the predicted
label.

###  IV.2 Simulation and Results

To demonstrate the ability of the VQSD for supervised classification, we
performed classical simulations using PennyLane. The simulation uses the Iris
flower dataset for ternary classification. The dataset consists of four
attributes (a four-dimensional data point $\mathbf{x}_{n}$) and species (a
class label $y_{n}$) of Iris flowers, and can be expressed as
$\mathcal{D}=\\{(\mathbf{x}_{n},y_{n})|\,\mathbf{x}_{n}\in\mathbb{R}^{4},y_{n}\in\\{0,1,2\\},n=1,\ldots,150\\}$.
Each class has the same number of data points (50 per class).

(a)

(b)

Figure 5: Circuit diagrams for quantum feature map and Visualization of Iris
flower dataset on Bloch sphere. (a) A quantum feature map $\mathcal{V}_{\Phi}$
consists of single-qubit rotations and the Ising coupling gates. The order of
gates in this map is determined by considering the commutation relation
between them. (b) The mixed states on the Bloch sphere are the reduced density
matrices of the data,
$\rho_{2}(\mathcal{D})=\text{Tr}_{1}[\mathcal{V}_{\Phi(\mathcal{D})}|00\rangle\langle
00|\mathcal{V}_{\Phi(\mathcal{D})}^{\dagger}]$ with an encoding function
Eq.(13). The blue square, red circle, and green triangle correspond to the
data label 0, 1, and 2, respectively.

(a)

(b)

Figure 6: Receiver operating characteristic (ROC) analysis for Iris flower
data classification by using VQSDs with different $n_{T}$, (a) the single-
qubit ($n_{T}=1$) POVM circuit and (b) the two-qubit ($n_{T}=2$) POVM circuit.
For each class, the mean ROC curves and mean AUCs averaged over the 5-fold
cross-validation are presented in both quantum state discriminators. In each
plot, the diagonal line corresponding to TPR=FPR is plotted as a guide to the
eyes.

Applying quantum machine learning to classical data requires an initial step
that encodes the classical data into a quantum state. For this, various
approaches exist, such as the amplitude encoding, angle encoding, Hamiltonian
encoding, and trainable quantum encoding [41, 8, 42, 43, 44, 45, 46, 47]. In
this simulation, we modify the Instantaneous quantum polynomial (IQP) encoding
that utilizes Ising Hamiltoinan, motivated by Havlíček et al. [46], to map a
four-dimensional data point into a two-qubit state. The feature-encoding
method suggested in Refs. [46, 48] maps classical data features to the
interaction terms of the Ising Hamiltonian. This leads to using the single-
qubit rotation gate $R_{Z}(\phi)=\exp(i\phi Z_{i})$ and the two-qubit coupling
gate $R_{ZZ}(\phi)=\exp(i\phi Z_{i}Z_{j})$ to embed a two-dimensional input
vector into two qubits. In addition to the $Z$ operators, we use $X$ operators
because we wish to encode four data features into a two-qubit state
$|\Psi_{n}\rangle=|\Phi(\mathbf{x}_{n})\rangle=\mathcal{V}_{\Phi(\mathbf{x}_{n})}|00\rangle$.
A quantum feature map is then defined as
$\mathcal{V}_{\Phi}=(V_{\Phi})^{l_{\Phi}}e^{i\phi_{1}P_{1}}$, where

$\displaystyle
V_{\Phi}=\prod^{4}_{\gamma=1}e^{\phi_{\gamma,\gamma+1}P_{\gamma}\cdot
P_{\gamma+1}}e^{i\phi_{\gamma}P_{\gamma}},$ (12)

$\phi$ is the coefficient that contains classical information, $l_{\Phi}$ is
the number of layers, and $P_{\gamma}$ is the $\gamma$-th element of the set
$\\{X{\small\otimes}I,I{\small\otimes}X,Z{\small\otimes}I,I{\small\otimes}Z\\}$.
We do not insert Hadamard gates between encoding layers because each layer
already contains non-commuting terms. The circuit diagram of
$\mathcal{V}_{\Phi}$ is illustrated in in Fig. 5(a). In the quantum circuit
for $\mathcal{V}_{\Phi}$, we encode data $\mathbf{x}_{n}$ into the
coefficients $\phi$ by using the encoding function $\phi(\mathbf{x})$. The
couplings in the quantum feature map $\mathcal{V}_{\Phi}$ necessitate the
information on correlations among the attributes of a data point. There are a
variety of approaches to encode a classical data point $\mathbf{x}$ into the
coefficients $\phi$. We tested all encoding functions suggested in Refs [46,
48], and found the following two types work the best for Iris data
classification.

$\displaystyle\phi_{j}(\mathbf{x})$
$\displaystyle=x_{j},\;\;\;\phi_{i,j}(\mathbf{x})=\frac{\pi}{3\cos(x_{i})\cos(x_{j})}$
(13) $\displaystyle\phi_{j}(\mathbf{x})$
$\displaystyle=x_{j},\;\;\;\phi_{i,j}(\mathbf{x})=\exp\left(\frac{|x_{i}-x_{j}|^{2}}{8/\ln(\pi)}\right)$
(14)

Thus, the simulation results in this section are of those carried out with the
above encoding functions.

Before encoding in the Hilbert space, let the Iris data set be preprocessed by
rescaling each attribute into the range $[-\pi/5,\pi/5]$. This rescaling is
empirically found to work well in combination with both encoding functions.
The rescaling mapping we use here is defined as

$x^{\prime}_{n,\alpha}=\frac{\pi}{5}\frac{2x_{n,\alpha}-(x_{\min,\alpha}+x_{\max,\alpha})}{x_{\max,\alpha}-x_{\min,\alpha}},$
(15)

where $x_{\min,\alpha}:=\min_{n}x_{n,\alpha}$ and
$x_{\max,\alpha}:=\max_{n}x_{n,\alpha}$ for each attribute
$\alpha\in\\{0,1,2,3\\}$. Next, the rescaled data point
$\mathbf{x}_{n}^{\prime}$ is embedded into the quantum state
$|\Psi_{n}\rangle=\mathcal{V}_{\Phi(\mathbf{x}^{\prime}_{n})}|00\rangle$ using
the quantum feature map $\mathcal{V}_{\Phi}$ and two encoding functions
Eq.(13) and Eq.(14). Here, the number of layers of the encoding circuit
$\mathcal{V}_{\Phi}$ is empirically chosen as $l_{\Phi}=2$.

In conjunction with this quantum data encoding, we facilitate two different
structures of the parameterized quantum circuit in the VQA: the single-qubit
POVM circuit ($n_{T}=1$) and the two-qubit POVM circuit ($n_{T}=2$) whose
diagrams are shown in Fig. 6(a) and (b), respectively. The encoding function
Eq.(13) is empirically selected for the former and Eq.(14) for the latter. In
both cases, measuring two ancilla qubits in the computational basis yields at
most four outcomes of POVMs.

To assess the classification performance of the VQSD, we use the stratified
5-fold cross-validation method. Namely, we shuffle the Iris data set, split
the data set in a 1:4 ratio of test to training data, and perform supervised
classification on all five splits. The classification performance of the VQSD
is quantified by the average test performance of the five classification
instances of the cross-validation process. Two metrics are used to determined
the test performance in each instance: the accuracy and the area under the
receiver operating characteristic (ROC) curve. The procedure for computing
theses metrics in our algorithm is described in the following.

First, when an unlabeled data point $\tilde{\mathbf{x}}$ is given, the quantum
state discriminator predicts the corresponding label
$\tilde{y}=\tilde{m}(\tilde{\mathbf{x}})$ according to a decision rule. The
decision rule chooses the label with the highest probability among all
possible outcomes of POVMs, which is given by

$\displaystyle\tilde{m}(\tilde{\mathbf{x}})$
$\displaystyle=\arg\max_{m}p(m|\tilde{\mathbf{x}}),$ (16)

where
$p(m|\tilde{\mathbf{x}})=\langle\Phi(\tilde{\mathbf{x}})|\mathcal{E}_{m}(\Theta_{opt})|\Phi(\tilde{\mathbf{x}})\rangle$
is the probability of obtaining the outcome $m$ from performing POVMs on
$|\Phi(\tilde{\mathbf{x}})\rangle$. For a test data set with known labels
$\tilde{\mathcal{D}}=\\{(\tilde{\mathbf{x}}_{n},\tilde{y}_{n})|\,\tilde{\mathbf{x}}_{n}\in\mathbb{R}^{4},\tilde{y}_{n}\in\\{0,1,2\\},\forall
n\in\mathbb{N}\\}$, one can examine how many labels matches the predictions of
the quantum model by evaluating the accuracy
$\sum_{n}\delta_{\tilde{m}(\tilde{\mathbf{x}}_{n}),\tilde{y}_{n}}/|\tilde{\mathcal{D}}|$.
In the 5-fold cross-validation, the mean accuracy is 0.893 for the single-
qubit POVM circuit and 0.920 for the two-qubit POVM circuit.

The second measure is the ROC curve and the area under the curve (AUC).
Although this measure is designed for binary classification, we can apply it
to multi-class classification through a one-vs-rest scheme. After formulating
the multi-class classification to the one-vs-rest binary classification, the
test data is assigned a label whose probability is higher than a predetermined
threshold value. Then the true-positive rate and the false-positive rate can
be evaluated at the threshold. The ROC curves are then drawn by shifting the
threshold value. The farther the ROC curve from the diagonal line the better
the performance of the classifier. Therefore, the performance of the
classifier can be quantified by the area under the ROC curve (AUC), which
ranges from 0.5 to 1, and the larger the AUC of ROC the better the performance
of the classifier. The mean ROC curves of the VQSD obtained from the 5-fold
cross-validation are shown in Fig. 6. There are three ROC curves in each plot
corresponding to three different combination of the one-vs-rest binary
classification. The VQSD classifiers with single-qubit and two-qubit POVM
circuits both show excellent classification performance as the mean AUC ranges
from 0.97 to 1 with an average of 0.985.

##  V Conclusions and Discussion

We proposed the VQSD, a variational quantum algorithm that performs the
minimum-error QSD. The proposed algorithm leverages the cosine-sine
decomposition to design a parameterized POVM circuit, and utilizes a cost
function derived from the theory of QSD to train the circuit.

The VQSD learns to solve the state discrimination tasks without prior
knowledge of the target states. Our results indicate that this method is as
effective as the semidefinite programming approach. We presented a multi-class
classification algorithm based on the VQSD and showcase its efficacy using the
Iris flower dataset. The numerical simulations conducted on this dataset
produced an area under the receiver operating characteristic curve that ranged
from 0.97 to 1, demonstrating its outstanding performance.

The VQSD offers several advantages over the classical solver for the SDP.
Unlike the classical algorithm for solving the SDP, the VQSD does not require
full information about the quantum states through quantum state tomography.
Besides, the VQSD has a computational complexity of $O(2^{2n_{T}}l)$ CNOT
gates, while the complexity of the classical SDP solver is $O(2^{\omega
n_{T}}l^{\omega})$, where $\omega$ depends on the matrix multiplication
algorithm and ranges from 2.37188 to 3. Additionally, classical optimization
procedures require an extra step of finding the corresponding quantum circuit
to implement QSD. These benefits make the VQSD more efficient than the
classical SDP solver for calculating the probabilities from POVMs on quantum
states and for discriminating multiple quantum states.

The VQSD can serve as a multi-class classifier in supervised machine learning
by discriminating mixed states that encode data subject to classification.
Since the quantum state can represent $O(2^{n_{T}})$ features [49, 42, 43, 45,
47], the VQSD circuit is efficient with respect to the number of data
features. The VQSD classifies multi-class data sets by synchronizing data
labels and measurement outcomes, requiring $\lceil\log_{2}l\rceil$ ancillary
qubits for $l$ data labels. Furthermore, existing quantum data compression
techniques, such as the quantum convolutional neural network (QCNN) [50, 51,
52] and the quantum autoencoder (QAE) [53, 54] can reduce number of target
qubits. This leads to a reduced size of the quantum circuit needed for multi-
class classification, making implementation on NISQ devices more feasible. The
use of the VQSD for multi-class classification in this manner represents a
promising approach for addressing the challenges associated with implementing
multi-class classification on quantum computing devices.

The performance of the VQSD can be improved by introducing an appropriate cost
function. A known issue with the minimum-error quantum state discrimination
strategy for more than two quantum states is that it can result in a zero-
valued POVM, as discussed in [28]. This problem can also occur in the
implementation of the VQSD, as demonstrated in Fig. 4(b). Here, the optimal
POVMs are given as $E_{0}=|0\rangle\langle 0|$, $E_{1}=|1\rangle\langle 1|$,
and $E_{2}=0$, making it challenging to discriminate the state $|+\rangle$. As
a result, the VQSD-based multi-class classifier may lose a data label. To
address this issue, further research is needed to investigate other QSD
strategies, such as maximum-confidence discrimination. Another avenue of
exploration is to integrate the VQSD as the classifier in existing quantum
machine learning algorithms, such as the QCNN, QAE, and the quantum generative
adversarial network [55, 56, 57]. As previously noted, the QCNN and the QAE
can complement the VQSD by reducing the number of target qubits required for
quantum state discrimination and, therefore, reducing the depth of the quantum
circuit. Furthermore, exploring the application of the VQSD for unsupervised
data clustering represents an intriguing direction for future research.

## Acknowledgment

This research was supported by the Yonsei University Research Fund of 2022
(2022-22-0124), by the National Research Foundation of Korea
(2021M3E4A1038308, 2021M3H3A1038085, 2022M3H3A106307411, and
2022M3E4A1074591), and by the KIST Institutional Program (2E32241-23-010). We
thank Israel Ferraz de Araujo for the insightful discussions on the subjects
of gate decomposition and quantum circuit complexity.

## References

  * [1] Charles H. Bennett.  Quantum cryptography using any two nonorthogonal states.  Phys. Rev. Lett., 68:3121–3124, May 1992.
  * [2] Lu-Ming Duan and Guang-Can Guo.  Probabilistic cloning and identification of linearly independent quantum states.  Phys. Rev. Lett., 80:4999–5002, Jun 1998.
  * [3] Anthony Chefles.  Quantum state discrimination.  Contemporary Physics, 41(6):401–424, 2000.
  * [4] Gael Sentís, Alex Monràs, Ramon Muñoz Tapia, John Calsamiglia, and Emilio Bagan.  Unsupervised classification of quantum data.  Phys. Rev. X, 9:041029, Nov 2019.
  * [5] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information: 10th Anniversary Edition.  Cambridge University Press, New York, NY, USA, 10th edition, 2011.
  * [6] John Watrous.  The Theory of Quantum Information.  Cambridge University Press, 2018.
  * [7] Carl W. Helstrom.  Quantum detection and estimation theory.  Journal of Statistical Physics, 1(2):231–252, Jun 1969.
  * [8] Seth Lloyd, Maria Schuld, Aroosa Ijaz, Josh Izaac, and Nathan Killoran.  Quantum embeddings for machine learning, 2020.
  * [9] H. Chen, L. Wossnig, S. Severini, H. Neven, and M. Mohseni.  Universal discriminative quantum neural networks.  Quantum Machine Intelligence, 3(1):1, 2020.
  * [10] Andrew Patterson, Hongxiang Chen, Leonard Wossnig, Simone Severini, Dan Browne, and Ivan Rungger.  Quantum state discrimination using noisy quantum neural networks.  Phys. Rev. Research, 3:013063, Jan 2021.
  * [11] Quantum-inspired algorithms refer to algorithms executed on classical hardware but using the mathematical formalism of quantum mechanics.
  * [12] Giuseppe Sergioli, Roberto Giuntini, and Hector Freytes.  A new quantum approach to binary classification.  PLOS ONE, 14(5):1–14, 05 2019.
  * [13] Roberto Giuntini, Hector Freytes, Daniel K Park, Carsten Blank, Federico Holik, Keng Loon Chow, and Giuseppe Sergioli.  Quantum state discrimination for supervised classification.  arXiv preprint arXiv:2104.00971, 2021.
  * [14] Roberto Giuntini, Federico Holik, Daniel K. Park, Hector Freytes, Carsten Blank, and Giuseppe Sergioli.  Quantum-inspired algorithm for direct multi-class classification.  Applied Soft Computing, 134:109956, 2023.
  * [15] M. A. Naimark, A. I. Loginov, and V. S. Shul’man.  Non-self-adjoint operator algebras in Hilbert space.  Journal of Soviet Mathematics, 5(2):250–278, 1976.
  * [16] Asher Peres.  Neumark’s theorem and quantum inseparability.  Foundations of Physics, 20(12):1441–1453, 1990.
  * [17] Raban Iten, Roger Colbeck, and Matthias Christandl.  Quantum circuits for quantum channels.  Physical Review A, 95(5):052316, 2017.
  * [18] Yordan S. Yordanov and Crispin H. W. Barnes.  Implementation of a general single-qubit positive operator-valued measure on a circuit-based quantum computer.  Phys. Rev. A, 100:062317, Dec 2019.
  * [19] Robert R Tucci.  A rudimentary quantum compiler (2cnd ed.).  arXiv preprint quant-ph/9902062, 1999.
  * [20] V. V. Shende, S. S. Bullock, and I. L. Markov.  Synthesis of quantum-logic circuits.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25(6):1000–1010, 2006.
  * [21] Emanuel Knill.  Approximation by quantum circuits.  arXiv preprint quant-ph/9508006, 1995.
  * [22] Raban Iten, Roger Colbeck, Ivan Kukuljan, Jonathan Home, and Matthias Christandl.  Quantum circuits for isometries.  Physical Review A, 93(3):032318, 2016.
  * [23] Mikko Möttönen, Juha J. Vartiainen, Ville Bergholm, and Martti M. Salomaa.  Quantum Circuits for General Multiqubit Gates.  Physical Review Letters, 93(13):130502, 2004.
  * [24] Vivek V. Shende, Igor L. Markov, and Stephen S. Bullock.  Minimal universal two-qubit controlled-NOT-based circuits.  Physical Review A, 69(6):062321, 2004.
  * [25] Farrokh Vatan and Colin Williams.  Optimal quantum circuits for general two-qubit gates.  Physical Review A, 69(3):032315, 2004.
  * [26] G. Vidal and C. M. Dawson.  Universal quantum circuit for two-qubit transformations with three controlled-NOT gates.  Physical Review A, 69(1):010301, 2004.
  * [27] Stephen M. Barnett and Sarah Croke.  Quantum state discrimination.  Adv. Opt. Photon., 1(2):238–278, Apr 2009.
  * [28] Joonwoo Bae and Leong-Chuan Kwek.  Quantum state discrimination and its applications.  Journal of Physics A: Mathematical and Theoretical, 48(8):083001, jan 2015.
  * [29] Alexander S Holevo.  Statistical decision theory for quantum systems.  Journal of multivariate analysis, 3(4):337–394, 1973.
  * [30] Horace Yuen, Robert Kennedy, and Melvin Lax.  Optimum testing of multiple hypotheses in quantum detection theory.  IEEE Transactions on Information Theory, 21(2):125–134, 1975.
  * [31] John Preskill.  Quantum Computing in the NISQ era and beyond.  Quantum, 2:79, August 2018.
  * [32] Steven Diamond and Stephen Boyd.  CVXPY: A Python-embedded modeling language for convex optimization.  Journal of Machine Learning Research, 17(83):1–5, 2016.
  * [33] M. Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C. Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R. McClean, Kosuke Mitarai, Xiao Yuan, Lukasz Cincio, and Patrick J. Coles.  Variational quantum algorithms.  Nature Reviews Physics, 3(9):625–644, 2021.
  * [34] Kishor Bharti, Alba Cervera-Lierta, Thi Ha Kyaw, Tobias Haug, Sumner Alperin-Lea, Abhinav Anand, Matthias Degroote, Hermanni Heimonen, Jakob S. Kottmann, Tim Menke, Wai-Keong Mok, Sukin Sim, Leong-Chuan Kwek, and Alán Aspuru-Guzik.  Noisy intermediate-scale quantum algorithms.  Rev. Mod. Phys., 94:015004, Feb 2022.
  * [35] Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, M Sohaib Alam, Shahnawaz Ahmed, Juan Miguel Arrazola, Carsten Blank, Alain Delgado, Soran Jahangiri, et al.  Pennylane: Automatic differentiation of hybrid quantum-classical computations.  arXiv preprint arXiv:1811.04968, 2018.
  * [36] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [37] Lane P. Hughston, Richard Jozsa, and William K. Wootters.  A complete classification of quantum ensembles having a given density matrix.  Physics Letters A, 183(1):14–18, 1993.
  * [38] Paul Hausladen and William K. Wootters.  A ‘Pretty Good’ Measurement for Distinguishing Quantum States.  Journal of Modern Optics, 41(12):2385–2390, 1994.
  * [39] Masashi Ban, Keiko Kurokawa, Rei Momose, and Osamu Hirota.  Optimum measurements for discrimination among symmetric quantum states and parameter estimation.  International Journal of Theoretical Physics, 36(6):1269–1288, 1997\.
  * [40] Erika Andersson, Stephen M. Barnett, Claire R. Gilson, and Kieran Hunter.  Minimum-error discrimination between three mirror-symmetric states.  Physical Review A, 65(5):052308, 2002.
  * [41] Maria Schuld and Francesco Petruccione.  Machine Learning with Quantum Computers.  Quantum Science and Technology. Springer International Publishing, 2 edition, 2021.
  * [42] Israel F. Araujo, Daniel K. Park, Francesco Petruccione, and Adenilton J. da Silva.  A divide-and-conquer algorithm for quantum state preparation.  Scientific Reports, 11(1):6329, March 2021.
  * [43] T. M. L. Veras, I. C. S. De Araujo, K. D. Park, and A. J. da Silva.  Circuit-based quantum memory for classical data with continuous amplitudes.  IEEE Transactions on Computers, pages 1–1, 2020.
  * [44] Ryan LaRose and Brian Coyle.  Robust data encodings for quantum classifiers.  Phys. Rev. A, 102:032420, Sep 2020.
  * [45] Israel F Araujo, Daniel K Park, Teresa B Ludermir, Wilson R Oliveira, Francesco Petruccione, and Adenilton J da Silva.  Configurable sublinear circuits for quantum state preparation.  Quantum Information Processing, 22(2):123, 2023.
  * [46] Vojtech Havlícek, Antonio D. Córcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow, and Jay M. Gambetta.  Supervised learning with quantum-enhanced feature spaces.  Nature, 567(7747):209–212, 2019.
  * [47] Carsten Blank, Adenilton J da Silva, Lucas P de Albuquerque, Francesco Petruccione, and Daniel K Park.  Compact quantum kernel-based binary classifier.  Quantum Science and Technology, 7(4):045007, jul 2022.
  * [48] Yudai Suzuki, Hiroshi Yano, Qi Gao, Shumpei Uno, Tomoki Tanaka, Manato Akiyama, and Naoki Yamamoto.  Analysis and synthesis of feature map for kernel-based quantum classifier.  Quantum Machine Intelligence, 2(1):9, 2020.
  * [49] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone.  Quantum random access memory.  Phys. Rev. Lett., 100:160501, Apr 2008.
  * [50] Iris Cong, Soonwon Choi, and Mikhail D. Lukin.  Quantum convolutional neural networks.  Nature Physics, 15(12):1273–1278, December 2019.
  * [51] Ian MacCormack, Conor Delaney, Alexey Galda, Nidhi Aggarwal, and Prineha Narang.  Branching quantum convolutional neural networks.  Phys. Rev. Research, 4:013117, Feb 2022.
  * [52] Tak Hur, Leeseok Kim, and Daniel K. Park.  Quantum convolutional neural network for classical data classification.  Quantum Machine Intelligence, 4(1):3, 2022.
  * [53] Jonathan Romero, Jonathan P Olson, and Alan Aspuru-Guzik.  Quantum autoencoders for efficient compression of quantum data.  Quantum Science and Technology, 2(4):045001, Aug 2017.
  * [54] Dmytro Bondarenko and Polina Feldmann.  Quantum autoencoders to denoise quantum data.  Phys. Rev. Lett., 124:130502, Mar 2020.
  * [55] Seth Lloyd and Christian Weedbrook.  Quantum generative adversarial learning.  Phys. Rev. Lett., 121:040502, Jul 2018.
  * [56] Pierre-Luc Dallaire-Demers and Nathan Killoran.  Quantum generative adversarial networks.  Phys. Rev. A, 98:012324, Jul 2018.
  * [57] He-Liang Huang, Yuxuan Du, Ming Gong, Youwei Zhao, Yulin Wu, Chaoyue Wang, Shaowei Li, Futian Liang, Jin Lin, Yu Xu, Rui Yang, Tongliang Liu, Min-Hsiu Hsieh, Hui Deng, Hao Rong, Cheng-Zhi Peng, Chao-Yang Lu, Yu-Ao Chen, Dacheng Tao, Xiaobo Zhu, and Jian-Wei Pan.  Experimental quantum generative adversarial networks for image generation.  Phys. Rev. Appl., 16:024051, Aug 2021.
  * [58] Ville Bergholm, Juha J. Vartiainen, Mikko Möttönen, and Martti M. Salomaa.  Quantum circuits with uniformly controlled one-qubit gates.  Physical Review A, 71(5):052330, 2005.
  * [59] Erika Andersson and Daniel K. L. Oi.  Binary search trees for generalized measurements.  Physical Review A, 77(5):052104, 2008.
  * [60] Eric Chitambar and Gilad Gour.  Quantum resource theories.  Rev. Mod. Phys., 91:025001, Apr 2019.
  * [61] A. C. Doherty, Pablo A. Parrilo, and Federico M. Spedalieri.  Distinguishing separable and entangled states.  Phys. Rev. Lett., 88:187904, Apr 2002.
  * [62] D Cavalcanti and P Skrzypczyk.  Quantum steering: a review with focus on semidefinite programming.  Reports on Progress in Physics, 80(2):024001, dec 2016.
  * [63] Alexander Streltsov, Gerardo Adesso, and Martin B. Plenio.  Colloquium: Quantum coherence as a resource.  Rev. Mod. Phys., 89:041003, Oct 2017.
  * [64] Alexei Gilchrist, Nathan K. Langford, and Michael A. Nielsen.  Distance measures to compare real and ideal quantum processes.  Phys. Rev. A, 71:062310, Jun 2005.
  * [65] Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong.  A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization.  2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 1049–1065, 2015.

##  Appendix A Decomposition of the POVM circuit.

Figure 7: The uniform controlled gate [23, 58]. It is two-fold uniformly
controlled gate $U(\boldsymbol{\theta})$ composed of four two-fold controlled
$U$ gates, each with different angles $\theta_{i}$. The parameter vector
$\boldsymbol{\theta}$ contains the angles $\theta_{i}$ for all $i$. The white
control qubit represents that the unitary operation $R$ is applied only when
the control qubit is the state $|0\rangle$.

We demonstrate the derivation of the circuit structure $\mathcal{U}$ in Fig. 1
based on the cosine-sine decomposition (CSD). The CSD is closely related to
the singular value decomposition (SVD) of a unitary operator. Let us consider
an arbitrary $2^{n}$-by-$2^{n}$ unitary operator $V_{n}\in\text{U}(n)$ is
divided into four blocks as depicted in the form of a 2-by-2 matrix. The SVD
is applied to each block, leading to the CSD and the circuit diagram of a
unitary operator $V_{n}$ can be described as

$\displaystyle V_{n}=\begin{pmatrix}B^{(0)}_{n-1}&\vline&\\\
\hline\cr&\vline&B^{(1)}_{n-1}\end{pmatrix}\begin{pmatrix}C&\vline&-S\\\
\hline\cr S&\vline&C\end{pmatrix}\begin{pmatrix}A^{(0)}_{n-1}&\vline&\\\
\hline\cr&\vline&A^{(1)}_{n-1}\end{pmatrix}.$ (17)

The two-fold uniformly controlled $A_{n-1}$ ($B_{n-1}$) gate corresponds to
the first (third) decomposed matrix in (17) where
$A^{(0)}_{n-1},A^{(1)}_{n-1}$ ($B^{(0)}_{n-1},B^{(1)}_{n-1}$) are left (right)
unitary operators with dimensions of $2^{n-1}\times 2^{n-1}$ from the SVDs.
The $(n-1)$-fold uniformly controlled $R_{y}$ gate matches the second
decomposed matrix in Eq.(17) involving two different singular value matrices
$C=diag(\cos{\varphi}_{1},\cdots,\cos{\varphi}_{2^{n-1}})$ and
$S=diag(\sin{\varphi}_{1},\cdots,\sin{\varphi}_{2^{n-1}})$ for rotational
angles $\varphi_{i}$ in $R_{y}$ gates. When one ancillary qubit is initially
in the state $|0\rangle$, the CSD of $V_{n}$ can be simplified as

$\displaystyle V_{n}$ $\displaystyle=\begin{pmatrix}B^{(0)}_{n-1}&\vline&\\\
\hline\cr&\vline&B^{(1)}_{n-1}\end{pmatrix}\begin{pmatrix}C&\vline&-S\\\
\hline\cr S&\vline&C\end{pmatrix}\begin{pmatrix}A^{(0)}_{n-1}\\\
\hline\cr\,\end{pmatrix}$
$\displaystyle=\begin{pmatrix}B^{(0)}_{n-1}&\vline&\\\
\hline\cr&\vline&B^{(1)}_{n-1}\end{pmatrix}\begin{pmatrix}C\\\ \hline\cr
S\end{pmatrix}A^{(0)}_{n-1},$ (18)

which contains $(n-1)$-qubit unitary operations $R_{n-1}$ without controls
[22].

Based on (18), we here demonstrate the circuit decomposition of
$\mathcal{U}=V_{n}$ in Fig. 1. When $n_{A}$ ancillary qubits initially set in
the state $|\mathbf{0}\rangle_{A}$ are considered, one can decompose an
arbitrary unitary operator $V_{n}$,

$\displaystyle V_{n}=\begin{pmatrix}V_{n-1}^{(0)}&\vline&\\\
\hline\cr&\vline&V_{n-1}^{(1)}\end{pmatrix}\begin{pmatrix}C\\\ \\\ \hline\cr
S\\\ \\\ \end{pmatrix}U,$ (19)

where $U$ is a $2^{n_{T}}$-by-$2^{n_{T}}$ unitary operator corresponding to
the right unitary matrix from performing the SVD on $V_{n}$, $C$ (or $S$) is
the $2^{n_{T}}$-by-$2^{n_{T}}$ diagonal matrix satisfying
$C_{ii}=\cos\varphi_{i}$ (or $S_{ii}=\sin\varphi_{i}$), and
$V^{(z_{1})}_{n-1}$ for any $z_{1}\in\\{0,1\\}$ is a unitary operator of size
$2^{n-1}\times 2^{n-1}$ with $n=n_{T}+n_{A}$. $V^{(z_{1})}_{n-1}$ specifically
consists of $2^{n_{T}}$ columns determined by the left-singular vectors of
$V_{n}$ and arbitrary $2^{n_{A}-1}$ columns. Each block in the second
decomposed matrix of (19) contains $2^{n_{A}-1}-1$ zero matrices of dimension
$2^{n_{T}}$ [17]. By using (19) recursively, a unitary operator $V_{n}$ can be
decomposed until $V_{n_{T}}$ is obtained,

Thus, this circuit structures are exactly the same as the ones in Fig. 1. when
the $n_{A}$-fold uniformly controlled $V_{n_{T}}$ gate at the end is omitted,
which does not lose the generality of performing POVMs on $n_{T}$-qubit
states. Moreover, the circuit can be more simplified by commuting the control
and the measurement, thereby reducing the number of the CNOT gate and
considering it only for the gate $U$ [59, 17, 9].

##  Appendix B Semidefinite programming for minimum-error QSD

Semidefinite programming (SDP) provides numerical solutions in numerous
applications of quantum information theory [6]. For instance, SDP is used to
compute monotones quantifying quantum resources in convex quantum resource
theories [60] such as entanglement[61], steering[62] and coherence[63], and
also to calculate the minimum error discrimination in discrimination tasks
[28, 64].

The (primal) SDP is formulated as follows:

Minimize $\displaystyle\text{Tr}[\mathcal{C}X],$ (20) subject to
$\displaystyle\text{Tr}[\mathcal{A}_{j}X]\leq b_{j}\text{ for }j=0,...,k-1,$
$\displaystyle X\geq 0,$

where $h\times h$ Hermitian matrices $\mathcal{C},\mathcal{A}_{j}$ and real
number $b_{j}$ are given for all integer $j$. The objective function is
minimized over the positive semidefinite matrix $X$ of dimension $h\times h$.
The recent method for solving SPD has been known as runtime
$O(k(k^{2}+h^{\omega}+ks)\log(1/\epsilon))$ where the constant $\omega$ is the
exponent of a matrix multiplication algorithm, $s$ is the sparsity of given
matrices $(\mathcal{C},\mathcal{A}_{0},\cdots,\mathcal{A}_{k-1}$), and
$\epsilon$ is the accuracy of the solution [65].

The minimum-error discrimination task in Section II.2 can be viewed in the
framework of SDP. The error probability Eq.(4) is equivalent to the objective
function of SDP by considering
$\mathcal{C}:=\bigoplus_{j=0}^{l-1}-q_{j}\rho_{j}$ and
$X=\bigoplus_{j=0}^{l-1}E_{j}$. Also, the completeness of the POVM can be
assigned to an equality constraint $\text{Tr}[X]=h/l$ in (20). If the quantum
system is defined on the $d$-dimensional Hilbert space, the dimension $h$ is
given as the multiplication of $d$ and $l$. It is remarkable that computing
SDP has polynomial time complexity with the dimension of the Hilbert space $d$
but exponential one with the number of target qubits $n_{T}$ in this work.
Moreover, in order to construct SDPs, the exact form of states should be
specified. Namely, quantum state tomography (QST) is required. On the other
hand, QST is not involved in our framework because parameter optimization is
performed without state information. As a result, this property allows us to
apply our VQAs to find the optimal POVMs in machine learning
straightforwardly.