Practical Quantum K-Means Clustering: Performance Analysis and Applications in Energy Grid Classification

Stephen DiAdamo^1,2, Corey O'Meara^1, Giorgio Cortiana^1, and Juan Bernabé-Moreno^1

^1E.ON Digital Technology GmbH

^2Technische Universität München

Author contact<EMAIL_ADDRESS><EMAIL_ADDRESS>
In this work, we aim to solve a practical use-case of unsupervised clustering which has applications in predictive maintenance in the energy operations sector using quantum computers. Using only cloud access to quantum computers, we complete a thorough performance analysis of what some current quantum computing systems are capable of for practical applications involving non-trivial mid-to-high dimensional datasets. We first benchmark how well distance estimation can be performed using two different metrics based on the swap-test, using both angle and amplitude data embedding. Next, for the clustering performance analysis, we generate sets of synthetic data with varying cluster variance and compare simulation to physical hardware using the two metrics. From the results of this performance analysis, we propose a general, competitive, and parallelized version of quantum $k$-means clustering to avoid some pitfalls discovered due to noisy hardware and apply the approach to a real energy grid clustering scenario. Using real-world German electricity grid data, we show that the new approach improves the balanced accuracy of the standard quantum $k$-means clustering by $67.8\%$ with respect to the labeling of the classical algorithm.

Quantum clustering, quantum distance estimation, quantum computing, cloud quantum computing.

§ INTRODUCTION

Given the challenging engineering requirements for building and maintaining quantum computers, it is likely that quantum computers will only be accessible through cloud services for the majority of users. Quantum computers, depending on the qubit technology, can require a complex construction and maintenance schedule that make it impractical for the average user to own [1]. Rather than building quantum computers as a hardware product to sell to consumers, large companies like Amazon, Microsoft, and IBM are rather developing cloud-based platforms for online access to their quantum devices. Although these quantum cloud services are currently accessible, the question of how useable are they for practical, industrial use-cases arises. Can these quantum computers produce accurate enough distance estimates for clustering? Can we achieve any speedup with them currently? The focus of this work is therefore to benchmark a simple, common use-case using IBM's Quantum cloud services [2].

Clustering algorithms can be used on unlabeled data to find relationships between the data's various features. To perform clustering, an algorithm introduced by Lloyd in 1982 called $k$-means clustering [3] can be used. The $k$-means algorithm takes as input a collection of unlabeled data points, or feature vectors, and outputs a list of labels, one for each data point. The data points are labeled based on the minimal distance to a particular centroid. During execution, the algorithm improves the centroid locations by running iteratively, updating the location to be the mean of the data points that are determined nearest to them based on a distance metric.

Classically, the usual method for measuring the distance between centroids and data points is to simply compute the Euclidean distance. For feature vectors of $N$ features, computing the Euclidean distance requires $O(N)$ computational steps. With a quantum approach, using quantum amplitude encoding (see
[4] for details), one can encode length-$N$ vectors into $O(\log_2 N)$ qubits, an exponential decrease in resources for encoding, assuming one can load quantum states into a quantum random access memory [5]. With this encoding, one can perform what is known as a swap-test using a quantum computer, as described in [6, 5], to compute an estimate for the Euclidean distance between two vectors. Because the swap-test requires a number of operations proportional to the number of qubits used for encoding—needed for swapping two multi-qubit states—in theory this would result in an exponential speedup in runtime complexity. Moreover, the minimum distance to a centroid for each point can be found using a Grover's search [7] for an additional quadratic speedup. Using a simpler data embedding approach like angle embedding, the theoretical advantage provided by an amplitude embedding is lost, as angle embedding requires a number of qubits directly proportional to the data dimension. However, the benefit of using this alternative embedding is that the depth of the state preparation circuit is constant, whereas with amplitude encoding, the state preparation circuit uses exponentially more non-local gates as the data dimension grows [8], leading to vastly deeper circuits using current approaches.

This result makes quantum clustering and nearest-neighbor classification appear as very attractive use cases for quantum computing, since they both use distance estimation and therefore can benefit by a theoretical speedup. When put into practice though, there are various challenges to overcome before one can effectively perform distance estimation on a quantum computer. Moreover, a strong assumption of efficient state preparation needs to be made in order to have an exponential speedup using the quantum approach over the classical approach [9]. Nonetheless, with this article, we aim to expand the results related to clustering on real, gate based, quantum hardware, and in particular, to explore how this type of algorithm can be executed on IBM's quantum cloud computing service. In this work, we use only the software libraries and services available to us with no direct hardware access, aiming to demonstrate how well one can expect quantum clustering to perform using generally available resources.

We begin in Section <ref> by reviewing how we perform data encoding and how we calculate the distance estimation in our quantum algorithm using the cloud service. In Section <ref>, we benchmark how well distance estimation can be performed, testing for various Euclidean distances and dimensions in simulation and on hardware. In Section <ref> we analyze various clustering experiments using synthetic data with two and four dimensions with several datasets. Given the results of the performance analysis in the prior sections, we then apply the findings to a non-trivial clustering problem which is relevant in the energy sector in Section <ref>. In particular, we show that decomposing high-dimensional vectors into 2-dimensional subspace projections, we are able to compute the overall distance in a more parallel fashion which significantly reduces the error induced by existing quantum hardware, simultaneously reducing the total number of circuits.

§.§ Related Work

Performing clustering and nearest-neighbor type algorithms using quantum computers has been studied in various contexts. Improving the encoding strategy to work better with IBM's quantum computers was studied by Khan et al. in [10]. In the article, they describe an encoding mechanism for feature vectors and benchmark the approach on IBM's quantum computer. Feature vectors, after PCA is performed, of dimension two are considered and benchmarked with the MNIST dataset using quantum hardware. Using the IonQ quantum hardware, Johri et al. perform data classification using clustering on their trapped ion quantum computer [11]. In their work, they define an optimized method for encoding 8-dimensional classical data into the quantum computer and use PCA to benchmark against MNIST data for ten different labels and perform their quantum algorithm for nearest-neighbor classification. In these works, an explicit benchmarking of distance estimation accuracy is not demonstrated. Moreover, the only experiments tested on the IBM quantum system were of two dimensions.  In a quantum annealing setting, clustering has also been considered. The authors of [12] and [13] map a clustering problem to a quadratic unconstrained binary optimization (QUBO) problem for an adiabatic quantum computer and use hardware to test their approach. Quantum annealing uses a different approach to quantum computing versus the gate based model, indeed no swap-test is involved, and the results from annealing experiments do not paint a clear picture for performance using a universal quantum computing approach.

In [14], Benlamine, et al. review three methods for distance estimation using a quantum approach and benchmark the approaches using nearest-neighbor classification in simulation. Further modified quantum clustering approaches were proposed in [15, 16]. These works did not perform tests on real physical hardware. In [17], Nguyen et al. run experiments to test the accuracy of the swap-test using their trapped ion system in a continuous variable setting, but do not perform any experiments of clustering.

§ PROGRAM SETUP AND CONFIGURATION

In this section, we review the setup and configuration used to perform clustering algorithms. In the first subsection, we review how the synthetic data is generated. Next, we review how the quantum algorithm works as well as the two methods used for classical data embedding in quantum states. Finally, we review the software approach used to execute the algorithms on the quantum cloud hardware.

§.§ Generating Synthetic Data and Quantum Data Loading

In the experiments conducted, we used synthetic data generated with varying dimension, number of clusters, cluster variance, and minimal distance between the centers.

At a high level, the cluster generation algorithm used works by firstly selecting $k$ center points to then generate cluster data around them. Using the center points as the multi-dimensional mean of a multi-variate normal distribution, a set number of cluster points are generated surrounding the center. Input to this algorithm is a cluster-variance parameter which we use to set the variance level of the respective dimension to control the “tightness"—how we measure difficultly of clustering—of the cluster. To avoid the randomly initialized center points being too close to each other, an additional step that resets a center point if it is within some $\epsilon$ distance from the already initialized center points is added. The synthetic data generated can be seen in Figure <ref>.

(a) at (0, 0)

tick pos=left,
x grid style=white!69.0196078431373!black,
xtick style=color=black,
y grid style=white!69.0196078431373!black,
ytick style=color=black,
[draw=black, fill=black, mark=*, only marks, mark options=scale=0.55]
x  y
0.394167052778071 1.60619624297316
0.346022831941382 1.67346807020386
0.519257642464963 1.65471749922932
0.265300370968658 1.71460246665098
0.363168493442897 1.64705984248653
0.589175912125789 1.92491602915451
0.474263267496367 1.76259639365014
0.278138267304768 1.8095636564899
0.290010189925745 1.68174885791758
0.48768129750344 1.63730364090829
0.261191568494348 1.69703010375387
0.50816739928847 1.49449185813907
0.409474487180394 1.81215465913765
0.602224381763763 1.82269072129287
0.480413059814191 1.7336326124919
4.31085380503874 0.737385025796865
4.16808501615574 0.542751641177875
4.35985697584545 0.555594462992495
4.16296738182533 0.543471789577743
4.3115907471386 0.44325370343536
4.26199550107372 0.561377769315049
4.22885614544874 0.554846458025495
4.49111063813783 0.420417965542819
4.28140261280451 0.683854121261776
4.20135906060479 0.444876784033371
4.32048707363585 0.490970802997064
4.43827415226364 0.540281803089652
4.39023437920535 0.377114168196779
4.05959855414032 0.6477008506086
4.2345638791642 0.397670743066214
2.28138913608308 4.33499193468541
2.04719284772349 4.24406462084837
2.21847230647349 4.22362159363952
2.11210436939069 4.67729023087227
2.25260563023125 4.4798880281257
2.34092042707846 4.26700631898674
2.05765624258414 4.43489657715846
2.08048586063901 4.6515709912111
2.46526616507966 4.38772760389163
2.12370952453507 4.40773453772753
2.4207295547953 4.57027701550005
2.39879639921274 4.47395917755514
2.22591424676106 4.39551675335551
2.15631872544511 4.4221526103357
2.09545338790163 4.3013728322635
4.01861106562655 3.5159079352129
4.10777449726994 3.42370252418762
3.97993469168294 3.3889061870844
4.0181802922123 3.33800384540655
4.02561640888086 3.58971532365957
4.12514977770654 3.52830910328117
3.91957968146256 3.46712337216159
4.03265747043598 3.32865965723785
4.04529836333352 3.38252070504349
4.11574757358903 3.5191908291639
4.04251358813811 3.5654390903013
4.15488877505889 3.43196824038289
4.25270148669297 3.50056555794238
4.20263617827531 3.36977494923703
4.16520456954503 3.6082268246087

(b) at (4, 0)

tick pos=left,
x grid style=white!69.0196078431373!black,
xtick style=color=black,
y grid style=white!69.0196078431373!black,
ytick style=color=black,
[draw=black, fill=black, mark=*, only marks,  mark options=scale=0.55]
x  y
0.315246643490534 1.40888298672282
0.112224147619282 1.6925659299472
0.842749286318353 1.61349542777469
-0.228179647784196 1.86602824147116
0.184526802660869 1.58120335704578
1.13759218473582 2.75291318078464
0.653009580336237 2.06841695348468
-0.174042687821034 2.26647625863608
-0.12397920523863 1.72748572219231
0.709592943705061 1.5400617961229
-0.245506324151151 1.79192620156429
0.795982118621352 0.937829501701059
0.379797559129753 2.2774024262054
1.1926171249501 2.32183263191299
0.678943039508622 1.94627770107971
4.35613284395228 1.40957260156224
3.75408185324532 0.588810424119252
4.56277750181331 0.642968154653065
3.73250096821571 0.591847264740989
4.35924050301965 0.169231099675516
4.15009908449726 0.667356155197842
4.01035158056797 0.639813843861754
5.1162696063222 0.0729335914505541
4.23193819608249 1.18383464888407
3.89439733523624 0.176075573805158
4.39675600079216 0.370452440064759
4.89345999285621 0.578395203260865
4.69087794961439 -0.109677007809495
3.29659823623293 1.03137757066456
4.03442089407106 -0.022990650360407
2.36441768156397 4.06764252663433
1.37682012239208 3.684205223522
2.09909961103222 3.59799769258729
1.65054973958495 5.51110247294991
2.24303864382264 4.67866428627661
2.6154590541374 3.78094956239864
1.42094389265937 4.48893691070601
1.51721559374282 5.40264533859033
3.13982068345093 4.29002699973662
1.69948827304625 4.37439554016587
2.95201135513617 5.05983148551878
2.85952000495294 4.65366253072709
2.13048201301213 4.32287357067261
1.83700013307988 4.43519604821629
1.58033313285901 3.92587194723705
3.77614159572459 3.78695338013681
4.15214066930169 3.39812638587126
3.61304467915143 3.25139144898575
3.77432503929899 3.03673805396702
3.80568288328117 4.0981965564884
4.22541161936372 3.83924867226503
3.3585297114081 3.58123058353655
3.83537479366335 2.99733393918579
3.88868099701446 3.22446409449218
4.18576285335499 3.80079722913947
3.87693769738706 3.9958245292524
4.35081993135333 3.43298262205007
4.76329271622294 3.72225511164421
4.55216906119493 3.17071568792079
4.39432127600225 4.176258908723

(c) at (2, -3.25)

tick pos=left,
x grid style=white!69.0196078431373!black,
xtick style=color=black,
y grid style=white!69.0196078431373!black,
ytick style=color=black,
[draw=black, fill=black, mark=*, only marks,  mark options=scale=0.55]
x  y
0.733946262972445 3.07641444911783
0.530923767101193 3.36009739234221
1.26144890580026 3.28102689016969
0.190519971697715 3.53355970386617
0.603226422142779 3.24873481944079
1.55629180421773 4.42044464317965
1.07170919981815 3.73594841587969
0.244656931660877 3.93400772103108
0.294720414243281 3.39501718458731
1.12829256318697 3.2075932585179
0.17319329533076 3.45945766395929
1.21468173810326 2.60536096409606
0.798497178611664 3.9449338886004
1.61131674443201 3.989364094308
8.85380087091318 1.33561459187555
8.65291156939552 1.93800677815766
8.05086057868856 1.11724460071467
8.85955622725655 1.17140233124849
8.02927969365894 1.12028144133641
8.65601922846288 0.697665276270939
8.4468778099405 1.19579033179326
8.30713030601121 1.16824802045718
9.41304833176544 0.601367768045977
8.52871692152572 1.7122688254795
8.19117606067947 0.704509750400581
8.69353472623539 0.898886616660182
9.19023871829945 1.10682937985629
8.98765667505763 0.418757168785928
4.35621995100723 1.13983909157169
5.09404260884536 0.0854708705467301
5.4652385747353 0.286440192493094
4.47764101556341 -0.0969971106192413
5.19992050420355 -0.183204641553949
4.75137063275628 1.72990013880867
5.34385953699397 0.897461952135369
5.71627994730873 -0.000252771742601965
4.52176478583069 0.70773457656477
4.61803648691415 1.62144300444909
6.24064157662226 0.508824665595378
4.80030916621757 0.593193206024635
6.0528322483075 1.27862915137754
5.96034089812426 0.872460196585849
2.84324825266627 -0.0727720927700143
2.54976637273403 0.0395503847736625
2.29309937251315 -0.469773716205582
2.65050419825878 0.377752830520416
3.02650327183589 -0.0110741637451357
2.48740728168562 -0.157809100630647
2.64868764183318 -0.372462495649376
2.68004548581537 0.688996006872007
3.09977422189792 0.430048122648628
2.2328923139423 0.172030033920149
2.70973739619755 -0.411866610430607
2.76304359954865 -0.184736455124218
3.06012545588918 0.39159667952307
2.75130029992125 0.586623979636005
4.76799584127959 8.8375257675201
5.1804686261492 9.12679825711424
4.96934497112119 8.57525883339081
4.81149718592852 9.58080205419303
4.4251610580929 8.72759991063558
3.75241636467768 8.99351585091385
5.19985043053437 8.81937715037243
4.18499723012237 8.51322924009426
4.29429515967712 9.67879810504629
4.67630403492794 9.20316101718151
3.56207318925492 8.89194935397031
4.69095981874476 8.89715258011234
4.52527085016623 9.46690233312756
4.48968490669652 8.33889177209827
5.91718621067327 5.11643153207035
5.58945345303313 5.78753137061499
5.17574432115884 5.38450094344596
4.73222401580206 5.20418875323988
4.93417440880543 5.6655744251586
5.85064147448457 4.86844680301869
4.59099391887501 4.52750186904266
5.25922594797643 5.65222506891482
5.85714304797049 5.51076222651752
5.60687876091084 5.17566669857284
5.93348644300988 5.44151796961424
6.11378936823836 5.30422809458967
4.95926110117644 5.31161635348533
5.97389420408793 5.6963613484283
8.60039329804436 7.41830938838559
8.55546166187354 6.59896969128856
7.98934335916969 6.63892428452844
8.02735095025646 6.16396297320017
8.12567842444629 7.10986483519257
8.09092588797321 7.28645817105779
8.91363943027089 6.03981985187294
8.10048799281179 7.71477089792857
8.47672648627162 7.13840767733028
8.58926151536638 7.36536752177539
8.04592575766058 7.23879611294763
8.48674606777021 7.14924207794173
8.17526455158412 6.91250610855729
7.72346440941793 6.47124024702413
3.96729747679078 6.33777898271532
2.85105045841825 5.24130880284875
3.8341677161593 6.22361859747858
3.36199024226808 6.38188059835359
2.86471838539624 5.80456129203673
3.10735106024398 5.76281304254609
2.79605257841908 6.0704699151241
2.87287803689587 5.58564283514939
3.84583030545538 5.43398932957189
3.53576077461134 6.06357454246733
4.35016029655426 5.7800654190334
3.05397976209526 5.37804458519096
3.45883772254856 6.24636720903415
3.19463655440697 6.05445549619084

() [below=of a, yshift=1.cm] (a);
() [below=of b, yshift=1.cm] (b);
() [below=of c, yshift=1.cm] (c);

Synthetic 2-dimensional data used for clustering. In (a), the data is tightly clustered with four clusters with 60 points in total which we consider an easy clustering. In (b) the data is more scattered with four clusters and 60 points total which we consider a hard clustering. In (c) are eight clusters with 14 points per cluster for a total of 112 points.

To perform the quantum distance estimation algorithm, the generated data points firstly need to be embedded into a multi-qubit quantum state. For this, we use two common types of embeddings, namely amplitude embedding and angle embedding [4], and test them independently. To perform the embeddings, we use the circuit structure shown in Fig. <ref> and Fig. <ref> respectively.  To implement amplitude embedding in code, we use the built-in  function offered by , which is a function that takes as input a real vector and returns the necessary gate set for complex amplitude embedding [18]. For angle embedding, we use two-dimensional rotations to embed two dimensions of a data vector per one qubit. This type of embedding is also referred to as “dense angle embedding” [19], but in this work we will only use the name “angle embedding” to refer to it. The scaling in terms of circuit depth and number of two-qubit gates varies significantly between the two embeddings. When embedding data using angle embedding, gate depth does not increase with the data dimension, but circuit width grows linearly. On the other hand, embedding classical data using amplitude encoding can scale quite poorly in depth with respect to the data dimension [8]. When using NISQ-era quantum devices, width and depth are some of the properties that should be reduced as far as possible to reduce the effects of noise in any algorithm. We plot the experimental scaling with respect to the data dimension in Fig. <ref>. The figure shows both the circuit depth and number of non-local gates required for initializing data for a connected quantum computer (i.e. one in which any two qubits can interact without any state-swapping) (solid line), and the 65-qubit IBM Brooklyn topology (dashed line), followed by a swap-test. For the encoding methods, Fig. <ref> shows the qubit resource requirement trends against feature vector dimension. The connectivity of the quantum computer topology determines the number of local swaps needed to perform two qubit gates, which results in deeper circuits with more non-local gates.

[scale=0.85] at (0, 0)
@C=1.5em @R=1.5em
|0⟩     3ℰ_ψ

|0⟩     ℰ_ψ

.5em⋮     ℰ_ψ

|0⟩     ℰ_ψ

|0⟩     ℰ_ϕ      [-1]

|0⟩     H     -1     H

Circuit for embedding classical data using amplitude embedding. We make use of the built in features of  to initialize the amplitude encoded data.

[scale=0.85] at (0, 0)
@C=1em @R=0.8em
|0⟩     U(a'_1, a'_2)

|0⟩     U(a'_3, a'_4)

.5em⋮                         .5em⋮

|0⟩     U(a'_n-1, a'_n)              -2⋯

|0⟩     U(b'_1, b'_2)                     [-4]

|0⟩     U(b'_3, b'_4)                 [-4]

.5em⋮                         .5em⋮

|0⟩     U(b'_n-1, b'_n)         [-4]     -2⋯

|0⟩     H         -1         -3     -4     H

Circuit for embedding classical data using angle embedding with swap test.

§.§ Quantum Circuits for Distance Estimation

To perform clustering, we replace the distance calculation from the classical algorithm with a quantum algorithm for distance estimation. Using amplitude embedding, we use a Euclidean distance approximation based on the one developed in [5] and reiterated in [20]. For angle embedding, we define a simple encoding that scales the data for embedding. The algorithm used for distance estimation firstly embeds the data for two vectors and then performs a swap-test. To approximate the distance, a number of repetitions, or shots, of the circuit are used to aggregate measurement statistics for a single ancilla qubit. The number of repetitions to use will vary problem to problem and hardware to hardware. Theoretically, using a higher number of shots will produce a more precise distance estimates, but each hardware will have a finite precision, and so more shots does not always lead to more accuracy. Moreover, some datasets do not require high-precision distance estimation to cluster accurately if they, for example, have well separated clusters. We explore this further. Once the repetitions are complete, the distance estimation can be calculated via the probabilities of a 0 or 1 measurement outcome of the ancilla qubit

\begin{align}
\Pr(0) &= \frac{1}{2} + \frac{1}{2} \left| \braket{\psi}{\phi} \right|^2\;, \\
\Pr(1) &= 1 - \Pr(0) = \frac{1}{2} - \frac{1}{2} \left| \braket{\psi}{\phi} \right|^2\;, \label{eq:p1}
\end{align}

Thus, the estimate $\left| \braket{\psi}{\phi} \right|^2$ provides an approximation to the inner product for our choice of embedding, or at least a measure that scales with the inner-product in the case of angle embedding.

For each of the two embeddings used, the swap-test procedure differs in terms of number of controlled swaps—also known as Fredkin gates[21]—used due to the difference in qubit resources required to perform the data embedding as well as the data representation strategy. For two (not necessarily normalized) data vectors $a:=(a_1, a_2, ..., a_n)$ and $b:=(b_1, b_2, ..., b_n)$—which in the case for clustering or classification would be one centroid and one data point—the two quantum states that are compared when performing the swap-test when using amplitude embedding are given by

\begin{align}
\ket{\psi} &\coloneqq \frac{1}{\sqrt{2}}\left( \ket{0}\ket{a} + \ket{1}\ket{b} \right)\;,\\
\ket{\phi} &\coloneqq \frac{1}{\sqrt{Z}}\left( |a|\ket{0} - |b|\ket{1} \right)\;,
\end{align}

where $Z\coloneqq |a|^2 + |b|^2$ [5]. To recover the distance estimation in this case, an ancilla qubit initialized in the $\ket{0}$ state is added to the system, and, after applying a Hadamard gate to it, a Fredkin (or controlled-swap) gate is applied with the ancilla as the control with $\ket{\psi}$ and $\ket{\phi}$ as the target systems. In this case, since $\ket\phi$ is just one qubit, one  Fredkin gate is needed, thereby greatly reducing the number of controlled swaps needed. Another Hadamard gate is applied to the ancilla qubit and then it is measured. By repeating the process a number of times, $\Pr(0)$ can be estimated to finally recover the distance:

\begin{align}
\left|a - b\right|^2=4Z(\Pr(0) - 0.5)\;.
\end{align}

The circuit for this process is depicted in Fig. <ref>.

For the angle embedding version of distance estimation, we prepare the two angle-encoded data vectors in the following way. Given the classical input vectors $a$ and $b$ defined above, let

\begin{align}
a'_i &\coloneqq \tfrac{\pi}{2}(a_i + 1) \quad \text{and} \quad \label{eq:a_angle_enc}\\
b'_i &\coloneqq \tfrac{\pi}{2}(b_i + 1)\;,\label{eq:b_angle_enc}
\end{align}

such that the angle embedded representations are given by $a':=(a'_1, a'_2, ..., a'_n)$ and $b':=(b'_1, b'_2, ..., b'_n)$. The mappings given by Eqns. <ref> and <ref> used to ensure the values are between 0 and $\pi$. With this embedding, we can encode data using a two-dimensional rotation operation defined by

\begin{align}
U(\theta, \gamma) \coloneqq
\left(\begin{tabular}{cc}
$\cos\tfrac{\theta}{2}$ & $-\sin\tfrac{\theta}{2}$ \\
$e^{i\gamma} \sin\tfrac{\theta}{2}$ & $e^{i\gamma}\cos\tfrac{\theta}{2}$
\end{tabular}\right)\;.
\end{align}

We encode the two vectors $a'$ and $b'$ in $\lceil n /2 \rceil$ qubits, using 1 qubit per two dimensions of each vector resulting in the final states

\begin{align}
\ket\psi &\coloneqq \bigotimes_{i \in odd(n)} U(a_i', a_{i+1}')\ket{0} \quad \text{and} \quad \\
\ket\phi &\coloneqq \bigotimes_{i \in odd(n)} U(b_i', b_{i+1}')\ket{0}\;,
\end{align}

where $odd(n)$ is the set of odd numbers from $1$ to $n$. To recover the distance estimation, again an ancilla qubit is introduced to the system. A Hadamard gate is applied to the ancilla followed by a series of $n/2$ controlled-swap gates using the ancilla as the control and one qubit from $\ket\psi$ and one from $\ket\phi$. A final Hadamard gate is applied to the ancilla qubit and then is measured. The overall circuit is depicted in Fig. <ref>. The goal in this case is to produce an estimate for $\Pr(1)$, which a valid distance metric. Because we are using arbitrary data which is not normalized in advance, we accommodate for this in the distance metric. For this, we set $Z\coloneqq |a|^2+|b|^2$ such that $a$ and $b$ are normalized as $a=a/\sqrt{Z}$ and $b=b/\sqrt{Z}$. The final distance metric is therefore given by

\begin{align}
d(a,b) &= \sqrt{Z \cdot P(1)}\;,
\end{align}

where $P(1)$ is given in Eqn. (<ref>).

(a) at (0, 0)

tick align=outside,
tick pos=left,
legend cell align=left,
legend style=
fill opacity=1,
draw opacity=1,
text opacity=1,
at=(0.01, 0.99),
anchor=north west,
legend image code/.code=
[mark repeat=2,mark phase=2]
plot coordinates
x grid style=white!69.0196078431373!black,
xtick=2, 4, 8, 16, 32, 64, 128, 256, 512,
ytick=0, 2000, 4000, 6000, 8000, 10000,
xlabel=Data Dimension,
xtick style=color=black,
y grid style=white!69.0196078431373!black,
ytick style=color=black,
log basis x=2
[very thick, color0, smooth]
2 30
4 51
8 82
16 158
32 314
64 630
128 1266
256 3537
512 6720
Circuit Depth
[very thick, color1, smooth]
2 9
4 15
8 21
16 37
32 69
64 133
128 261
256 1011
512 1917
Non-local Gates
[very thick, color0, smooth, dashed]
2 36
4 70
8 113
16 220
32 387
64 771
128 1583
256 5267
512 9866
Circuit Depth: IBMQ Brooklyn
[very thick, color1, smooth, dashed]
2 13
4 32
8 51
16 94
32 170
64 389
128 733
256 2697
512 5254
Non-local gates: IBMQ Brooklyn

(b) [below=of a, yshift=1cm]

tick align=outside,
tick pos=left,
scaled y ticks=base 10:-3,
legend cell align=left,
legend style=
fill opacity=1,
draw opacity=1,
text opacity=1,
at=(-0.01, 1.15),
anchor=north west,
legend image code/.code=
[mark repeat=2,mark phase=2]
plot coordinates
x grid style=white!69.0196078431373!black,
xtick=2, 4, 8, 16, 32, 64, 128, 256, 512,
ytick=0, 500, 1000, 1500, 2000, 2500,
xlabel=Data Dimension,
xtick style=color=black,
y grid style=white!69.0196078431373!black,
ytick style=color=black,
log basis x=2
[very thick, color0, smooth]
2 22
4 30
8 46
16 78
32 142
64 270
128 526
256 1038
512 2062

[very thick, color1, smooth]
2 7
4 14
8 28
16 56
32 112
64 224
128 448
256 896
512 1792

[very thick, color0, smooth, dashed]
2 22
4 75
8 126
16 221
32 623
64 1195

[very thick, color1, smooth, dashed]
2 10
4 47
8 100
16 284
32 1117
64 2559

The circuit-depth and number of non-local gates in a circuit that embeds classical data using amplitude encoding and performs the swap test of varying dimension transpiled with the basis gates under full connectivity and for the IBMQ Brooklyn device. The upper plot demonstrates results using amplitude embedding, and the bottom plot from angle embedding.

tick align=outside,
tick pos=left,
legend cell align=left,
legend style=
fill opacity=1,
draw opacity=1,
text opacity=1,
at=(0.01, 0.99),
anchor=north west,
legend image code/.code=
[mark repeat=2,mark phase=2]
plot coordinates
x grid style=white!69.0196078431373!black,

xlabel=Data Dimension,
ylabel=Logical Qubits,
xtick style=color=black,
y grid style=white!69.0196078431373!black,
ytick style=color=black,
log basis x=2,
[very thick, color0, smooth, samples at=2,4,8,16,...,512]
x / 2 + 1
Angle Embedding
[very thick, color1, smooth, samples at=2,4,8,16,...,512]
log2(2*x) + 2
Amplitude Embedding

The number of qubits required to embed classical data of varying dimension.

§.§ Running Clustering on the Quantum Cloud

To implement the circuit preparation and execution of the quantum circuits in software, we use IBM's  Python Software Development Kit (SDK) [22].

A property of the $k$-means clustering algorithm is that it is highly parallelizable, and we use this property to execute the clustering algorithm more time-efficiently. In each iteration of $k$-means clustering, a distance is calculated between the current set of centroids and each point in the dataset. These distance calculations are independent of each other and can be computed in parallel using multi-processing or in a batch job. In the quantum case, to parallelize, we take two approaches. Firstly, we prepare one circuit per distance estimation and then send the collection of circuits as a batch job to the cloud service. The response is the measurement results of the circuits which can then be post-processed according the embedding. The second way we parallelize the algorithm is to embed multiple swap-tests into one circuit and execute them on the same quantum computer at once. This allows for multiple distance estimations to be done on a single quantum computer.

We developed the first parallel approach in two ways, one using our own approach and later, when it became available, using a  native approach. For the first approach, we use many computational thread processes (locally) to send requests simultaneously to the server to reduce computation time. In simulation, the approach improved performance, but when there is only one quantum computer, this makes no difference. The advantage from parallel execution is achieved with multiple quantum computers working together to compute distance estimations as described in [23].

The second approach was sending batches of circuit jobs via a recently added feature called . This feature allows the user to submit many circuit jobs at once such that there is only one job to queue. The performance improvement between parallel execution via multi-processing and batch-circuit  execution that we observed was significant. The complete algorithms for the two applied $k$-means clustering approaches are described by Algorithms <ref> and <ref> respectively.

Clustering on the Quantum Cloud with Multi-processing

* $k$: The number of clusters

* data: The data to cluster

* embedding: The choice of data embedding

* $\epsilon$: The minimum distance between two cluster centers

* $maxIterations$: The maximum number of iterations to make

* $processes$: A list of running processes

Output: An ordered list of labels for the data points
[1]
$centroids\gets$ initialize the centroids using $\epsilon$ min distance
$convergence \gets$ false, $i\gets 0$
not $convergence$
$circuits \gets $generate all circuits with the data, centroids,
and embedding choice
$dists \gets $ initialize empty shared storage
not all circuits have been processed
a process is idle
$job\gets$ send single circuit to server and await response
$dist \gets $ process $job$ results according to the embedding
add $dist$ with circuit number to shared storage
Sort $dists$ according to circuit number
$dists \gets$ using the returned, ordered measurement results from
the server, complete the distance estimation procedure
$labels \gets $ using the distances to the centroids, label the
data points
$centroids \gets $ with the updated labels, recompute the centroids
as an average position of the labeled data.
Delete centroids for empty clusters.
Check for centroid convergence, update $convergence$
$i\gets i + 1$
Check if $i = maxIterations$ and break accordingly
return $labels$

Clustering on the Quantum Cloud with Batched Circuits

* $k$: The number of clusters

* data: The data to cluster

* embedding: The choice of data embedding

* $\epsilon$: The minimum distance between two cluster centers

* $maxIterations$: The maximum number of iterations to make

Output: An ordered list of labels for the data points
[1]
$centroids\gets$ initialize the centroids using $\epsilon$ min distance
$convergence \gets$ false, $i\gets 0$
not $convergence$
$circuits \gets $generate all circuits with the data, centroids,
and embedding choice
$job \gets $ send the collection of circuits to the cloud server
for processing and await response
$dists \gets$ using the returned, ordered measurement results from
the server, complete the distance estimation procedure
$labels \gets $ using the distances to the centroids, label the
data points
$centroids \gets $ with the updated labels, recompute the centroids
as an average position of the labeled data.
Delete centroids for empty clusters.
Check for centroid convergence, update $convergence$
$i\gets i + 1$
Check if $i = maxIterations$ and break accordingly
return $labels$

§ BENCHMARKING DISTANCE ESTIMATION

To develop a clear understanding of how well clustering and nearest-neighbor classification can be performed using current quantum hardware, it is helpful to test how accurately distance estimation can be performed on quantum devices. In this section, we benchmark a variety of cases for performing distance estimation and compare the estimations using simulation and real quantum hardware. Simulation in this case is done using the noiseless quantum computing simulation platform offered via the  framework using the OpenQASM backend. Software for the simulation is prepared in exactly the same way in which the quantum circuit logic is sent to the quantum cloud services, we can simply switch the target backend from the simulated backend to the hardware. To perform the analysis, we test three difference cases. We firstly test how varying the number of circuit shots affects the estimation in both two and four dimensions. Next, we vary the distance of the data points also in two and four dimensions. Lastly, we test how varying the data dimensions affects the estimation up to 32 dimensions using amplitude embedding and up to 26 dimensions using angle embedding.

In all tests, for each resulting data point, we use 100 repetitions, plotting the average output and the standard deviation. In each case, we use the measurement error mitigation feature when running the experiments on the physical hardware. To execute the 100 instances, we make 100 copies of the circuits and use the circuit-runner service to execute the circuits in a batched job.

The results of varying the number of circuit shots are plotted in Fig. <ref>. In this experiment, we created a circuit for the vectors $(1,0)$ and $(1,1)$. Comparing simulation to the physical device results, in simulation we see a convergence in the number of shots to the true answer, and moreover the average is close to the true distance as desired. With the real hardware, we see no convergence trends behind the dotted line, and using more shots than around 2,000 does not generally perform better than using the maximum number of shots 8,192. In some cases, a lower number of shots performed better, having a lower variance in the standard deviation than with more shots. On the other hand, when we switched to a quantum computer that supported a higher number of shots, much better and more consistent results are seen. For 4D, the points $(1,0,0,0)$ and $(1,1,1,1)$ are used, and the same effects are more or less seen. Convergence is not reached using real hardware, but a relatively rapid convergence is seen in simulation, where with a high number of shots, the results improve significantly. We reiterate that in some cases, depending on the dataset, high-precision distance estimation is not necessary for clustering.

An important point of note is that for angle embedding, the difference of output between the simulation and the hardware is much starker than with amplitude embedding. The reason behind this is due to the fact that on the IBM quantum devices, the accuracy of qubit rotations is less precise with the available gate basis of $[CX, ID, RZ, SX, X]$ and therefore significant differences between the simulation, where such rotations are highly precise, are observed [24]. Another noteworthy aspect is that in some instances, the variance in the standard deviation can become very small for the 100 samples, with no recognizable trend. See for example Fig. <ref>, the 7,000 shots point in the upper-left plot and the 6,000 shot point in the lower-left plot. We suspect this may come from a periodic hardware calibration that is performed by IBM that was executed on the quantum devices between experimental runs.

For the next set of experiments, we vary the distance between two points in 2D and 4D (see Fig. <ref>). The vectors we chose have the form $(1,..., 1)$ and $(x, ...,x)$ where we vary $x$ to modify the distance between the points. The results of the 2D experiments show that simulation and the physical device have similar outputs for $x\leq 5$, but for $x>5$, the outputs from simulation and real device start to diverge. In 4D, the effects of encoding show a stark difference between amplitude and angle embeddings. Interestingly, the simulation results for 4D amplitude embedding match very closely to the hardware execution for all tested values of $x$, more so even than in 2D. On the other hand, angle embedding performs far worse in 4D than in 2D, where already for $x = 5$, the difference between simulation and real hardware is significant. This extra noise is again likely due the fact that for more dimensions, the limited precision of the angle embedding is now applied for another two dimensions and that an additional controlled-swap is introduced.

(a) at (0, 0)

x y error
10 1.2360000000000002 1.2863529842154524
50 1.0464000000000002 0.6690104931912505
100 1.0308 0.5918068603860555
200 0.9636000000000002 0.3804037854701237
300 0.9708000000000004 0.3054101504534517
400 1.0038 0.29071903962417056
500 0.9780000000000001 0.26490118912530375
600 1.0074 0.2343613449355503
700 0.9963428571428572 0.22455546290029854
800 0.9969000000000002 0.23740237993752303
900 0.9885333333333335 0.21108835432901873
1000 0.99684 0.20151608968020385
2000 0.98586 0.13476832120346396
3000 1.0094400000000003 0.10127273275665084
4000 1.0080900000000002 0.09846624751659835
5000 0.9947760000000003 0.07898698262372099
6000 0.9947000000000001 0.07589802368968511
7000 0.99684 0.06525576455887454
8192 1.0059375000000002 0.07031771220915535
12000 0.9968 0.0515
16000 1.0001 0.04648
24000 1.00014 0.0357
32000 1.0001 0.03275

x y error
10 1.416 1.4537345012071499
50 1.6944 0.8243013041358118
100 1.4292000000000002 0.5040271421262947
200 1.1352000000000002 0.5194544830877871
300 0.7460000000000001 0.6841841857277907
400 1.4268 0.3019234340027286
500 1.3094400000000004 0.27307992676137893
600 1.1712000000000002 0.3564190791750633
700 0.802114285714286 0.6888540759545406
800 1.3333500000000003 0.4220888857811824
900 0.7453333333333336 0.7062199846129157
1000 1.4041199999999998 0.19670115810538602
2000 1.1551200000000004 0.37595013711927283
3000 1.5414 0.20148439145502067
4000 1.51935 0.09948551402088647
5000 0.6735120000000001 0.6644520956818482
6000 0.89046 0.7749434485173742
7000 1.4553942857142856 0.10180951625462134
8192 0.8729003906250001 0.746430548100126
12000 0.9854 0.10457
16000 1.1915 0.05162
24000 1.1399 0.08878
32000 0.8982 0.08476

tick align=outside,
tick pos=left,
scaled x ticks=base 10:-3,
ytick=0, 1, 2, 4,
legend cell align=left,
legend style=
fill opacity=1,
draw opacity=1,
text opacity=1,
at=(0.73, 1.05),
anchor=north west,
legend image code/.code=
[mark repeat=2,mark phase=2]
plot coordinates
x grid style=white!69.0196078431373!black,

xlabel=Number of shots,
ylabel=Avg. Distance,
xtick style=color=black,
y grid style=white!69.0196078431373!black,
ytick style=color=black,

[color0, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] data.dat;

[color1, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] realdata2d.dat;

[name path=upper,draw=none] table[x=x,y expr=y+error] realdata2d.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] realdata2d.dat;
[fill=color1!30, opacity=0.5, draw=color1!50] fill between[of=upper and lower];

[name path=upper,draw=none] table[x=x,y expr=y+error] data.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] data.dat;
[fill=color0!30, opacity=0.5, draw=color0!50] fill between[of=upper and lower];

[thick, samples=50, smooth,domain=0:6,black, dotted] coordinates (11000,-4)(11000,4);

(b) [below=of a, yshift=1cm]

x y error
10 0.126 0.1858063508064243
50 0.10020000000000003 0.07871442053397842
100 0.117 0.06356886030125129
200 0.10890000000000001 0.03750719930893268
300 0.10960000000000004 0.034290523472236475
400 0.11122500000000002 0.027414628850305458
500 0.10608000000000002 0.024634804647084178
600 0.10965 0.022806303953074033
700 0.10980000000000002 0.018491056856585277
800 0.11107500000000002 0.020884369154944567
900 0.1078666666666667 0.018454267799075642
1000 0.10740000000000002 0.01679464200273409
2000 0.10918500000000002 0.013885001800504027
3000 0.10977000000000002 0.010207698075472258
4000 0.10890000000000001 0.008887420885723822
5000 0.10952999999999999 0.007846190158287017
6000 0.108215 0.007129254869900501
7000 0.10889571428571433 0.007153958658658569
8192 0.10931030273437502 0.005945825637348152
12000 0.1087 0.0051
16000 0.109402 0.0045348
24000 0.10904 0.00384
32000 0.109360 0.0029519

x y error
10 0.5219999999999999 0.3713704350106508
50 0.42900000000000005 0.15235156710713546
100 0.7326 0.2533599021155479
200 0.9204000000000002 0.11514920755263582
300 0.7008000000000001 0.29616779028111756
400 0.6849750000000001 0.2544613170503525
500 0.91458 0.18473620002587474
600 0.5233000000000001 0.20228719682668997
700 0.733457142857143 0.22671632729299515
800 0.6822750000000002 0.21185131726047873
900 0.6058333333333333 0.1801180939766402
1000 0.71604 0.21437424845349312
2000 0.9735600000000002 0.20057674690751176
3000 0.7725000000000002 0.27236635254744673
4000 0.7624950000000001 0.30580565924292513
5000 0.7272000000000002 0.2972599710690964
6000 0.7493899999999999 0.016561639411604157
7000 0.4598142857142859 0.09329062883575945
8192 0.4852990722656251 0.11858837177686586
12000 0.74779 0.193763
16000 0.684525 0.197944
24000 0.643236 0.20539
32000 0.726828 0.03333

tick align=outside,
scaled x ticks=base 10:-3,
tick pos=left,

yticklabel style=
/pgf/number format/fixed,
/pgf/number format/precision=2
scaled y ticks=false,
legend cell align=left,
legend style=
fill opacity=1,
draw opacity=1,
text opacity=1,
at=(0.73, 1.05),
anchor=north west,
legend image code/.code=
[mark repeat=2,mark phase=2]
plot coordinates
x grid style=white!69.0196078431373!black,

xlabel=Number of shots,
ylabel=Avg. Distance,
xtick style=color=black,
y grid style=white!69.0196078431373!black,
ytick style=color=black,

[color0, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] data2d_ang.dat;

[color1, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] realdata2d_ang.dat;

[name path=upper,draw=none] table[x=x,y expr=y+error] realdata2d_ang.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] realdata2d_ang.dat;
[fill=color1!30, opacity=0.5, draw=color1!50] fill between[of=upper and lower];

[name path=upper,draw=none] table[x=x,y expr=y+error] data2d_ang.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] data2d_ang.dat;
[fill=color0!30, opacity=0.5, draw=color0!50] fill between[of=upper and lower];

[thick, samples=50, smooth,domain=0:6,black, dotted] coordinates (11000,-2)(11000,4);

(c) [right=of a, xshift=-0.75cm]

x y error
10 3.12 2.5190474390134066
50 3.072 1.3492279273717986
100 2.9960000000000004 0.970764647069515
200 3.0200000000000005 0.7303423854604085
300 3.03 0.5475906824951968
400 2.99 0.5015974481593781
500 3.138000000000001 0.43782644963501244
600 2.950333333333333 0.4102436945144787
700 2.9817142857142853 0.3677958617472025
800 3.0277499999999993 0.3461375268589061
900 2.9708888888888882 0.3191144382370657
1000 2.9598 0.2811333491423601
2000 2.9875 0.2083428664485542
3000 2.999333333333333 0.18800591007258832
4000 3.0077499999999997 0.15099234252106963
5000 3.026360000000001 0.1377070455713868
6000 2.9881999999999995 0.1232471951450056
7000 2.993485714285714 0.11880567567009823
8192 3.0024169921875 0.10019365573279207
12000 2.9938 0.08087
16000 3.0037 0.07768
24000 2.9931 0.048971
32000 3.0049 0.054417

x y error
10 2.92 2.5678
50 1.512 1.5269
100 2.552 1.057
200 2.6829 0.9023
300 3.05733 0.5842
400 1.9085 0.7304
500 2.082 1.0747
600 1.652 0.4701
700 1.8 0.37129
800 2.951 0.559
900 1.9948 0.4996
1000 2.6368 0.4024
2000 1.7288 0.95646
3000 2.2297 0.3205
4000 2.36614 0.7187
5000 2.5906 0.1475
6000 2.8306 0.45615
7000 2.78822 0.24259
8192 2.5785 1.02167
12000 2.7361 0.97914
16000 2.6323 0.780258
24000 3.0400 0.15407
32000 3.4826 0.20886

tick align=outside,
tick pos=left,
scaled x ticks=base 10:-3,

legend cell align=left,
legend style=
fill opacity=1,
draw opacity=1,
text opacity=1,
at=(0.73, 1.05),
anchor=north west,
legend image code/.code=
[mark repeat=2,mark phase=2]
plot coordinates
x grid style=white!69.0196078431373!black,

xlabel=Number of shots,
ylabel=Avg. Distance,
xtick style=color=black,
y grid style=white!69.0196078431373!black,
ytick style=color=black,

[color0, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] data4d.dat;

[color1, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] realdata4d.dat;

[name path=upper,draw=none] table[x=x,y expr=y+error] realdata4d.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] realdata4d.dat;
[fill=color1!30, opacity=0.5, draw=color1!50] fill between[of=upper and lower];

[name path=upper,draw=none] table[x=x,y expr=y+error] data4d.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] data4d.dat;
[fill=color0!30, opacity=0.5, draw=color0!50] fill between[of=upper and lower];

[thick, samples=50, smooth,domain=0:6,black, dotted] coordinates (11000,-8)(11000,8);

(d) [right=of b, xshift=-0.775cm]

x y error
10 0.58 0.5035871324805669
50 0.649 0.23853511271928082
100 0.6415 0.16748955191294768
200 0.6619999999999997 0.12265194658055777
300 0.6668333333333333 0.09900883798934315
400 0.6651249999999999 0.08500542262114812
500 0.6601000000000002 0.07877175889873222
600 0.664 0.06491318989405946
700 0.6602142857142858 0.06532692509874578
800 0.6591875 0.05857323807636043
900 0.6586666666666667 0.05346234396490882
1000 0.6684499999999999 0.05786058675817245
2000 0.6574 0.03357067172399147
3000 0.65995 0.02877542836827591
4000 0.6580125 0.026055886451049788
5000 0.6607900000000001 0.025052462952771727
6000 0.6586666666666666 0.021142702970265874
7000 0.6581714285714287 0.021214482923566282
8192 0.659197998046875 0.01883791637270578
12000 0.65789 0.01208
16000 0.65985 0.01538
24000 0.65933 0.01096
32000 0.65809 0.00837

x y error
10 2.435 0.7831187649392652
50 2.005 0.5020707121511868
100 1.9679999999999997 0.3180817504982013
200 2.0309999999999997 0.2358262071950444
300 1.7770000000000001 0.15200109648727317
400 1.7534999999999998 0.4238148180514693
500 1.6034 0.1668845109649185
600 2.4247500000000004 0.17669203827249513
700 2.603857142857143 0.29745248291422405
800 1.686 0.27479554899961534
900 2.303833333333333 0.21422656605784976
1000 1.78405 0.10973079558628927
2000 1.9956500000000004 0.13735748068452625
3000 1.9469 0.4242355228984118
4000 2.8551250000000006 0.14086535015751744
5000 1.8128399999999996 0.16965298229032108
6000 2.1518249999999997 0.2638745676084672
7000 2.074278571428571 0.4419635165361272
8192 1.71470947265625 0.1343230784818166
12000 2.17655 0.107064
16000 2.103809 0.059288
24000 1.92759 0.2019426
32000 1.85891 0.09388

tick align=outside,
tick pos=left,
scaled x ticks=base 10:-3,

legend cell align=left,
legend style=
fill opacity=1,
draw opacity=1,
text opacity=1,
at=(0.73, 1.05),
anchor=north west,
legend image code/.code=
[mark repeat=2,mark phase=2]
plot coordinates
x grid style=white!69.0196078431373!black,

xlabel=Number of shots,
ylabel=Avg. Distance,
xtick style=color=black,
y grid style=white!69.0196078431373!black,
ytick style=color=black,

[color0, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] data4d_ang.dat;

[color1, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] realdata4d_ang.dat;

[name path=upper,draw=none] table[x=x,y expr=y+error] realdata4d_ang.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] realdata4d_ang.dat;
[fill=color1!30, opacity=0.5, draw=color1!50] fill between[of=upper and lower];

[name path=upper,draw=none] table[x=x,y expr=y+error] data4d_ang.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] data4d_ang.dat;
[fill=color0!30, opacity=0.5, draw=color0!50] fill between[of=upper and lower];

[thick, samples=50, smooth,domain=0:6,black, dotted] coordinates (11000,-4)(11000,4);

The distance estimation for amplitude encoding (upper) and angle embedding (lower) of $(1, 0)$ and $(1, 1)$ in 2D (left) and $(1,0,0,0)$ $(1,1,1,1)$ in 4D (right). The circuit for measuring the distance between these the two points is generated and ran a varying number of shots. Displayed is the average output of 100 trials with the standard deviation shaded around the average. The black dotted line indicates where the quantum hardware used switches from IBMQ Bogata on the left of the line to IBMQ Casablanca on the right.

(a) at (0, 0)

x y error
1 0.07914062500000002 0.11258490177382525
2 2.0205078125000004 0.46544550565860343
3 7.927343749999999 0.8256858979953802
4 18.04921875 1.448021742852447
5 31.990156250000005 2.2859451416054792
6 50.60183593749999 3.137885944839267
7 71.791015625 3.9921468893176604
8 98.67050781250002 5.242643928498579
9 128.7784375 7.410915470792685
10 162.0852734375 7.914075611859047

x y error
1 0.6147 0.1832
2 2.4966 1.24609
3 7.402 0.7774
4 16.95 1.175
5 28.1338 6.0204
6 37.0216 10.08
7 42.195 18.3663
8 77.9492 6.8824
9 100.1617 7.8900
10 121.7207 10.821

tick align=outside,
tick pos=left,
legend cell align=left,
legend style=
fill opacity=1,
draw opacity=1,
text opacity=1,
at=(0.01, 0.99),
anchor=north west,
legend image code/.code=
[mark repeat=2,mark phase=2]
plot coordinates
x grid style=white!69.0196078431373!black,

ylabel=Avg. Distance,
xtick style=color=black,
y grid style=white!69.0196078431373!black,
ytick style=color=black,

[color0, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] data_dist.dat;

[color1, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] realdata2d_dist.dat;
IBMQ Bogota

[name path=upper,draw=none] table[x=x,y expr=y+error] realdata2d_dist.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] realdata2d_dist.dat;
[fill=color1!30, opacity=0.5, draw=color1!50] fill between[of=upper and lower];

[name path=upper,draw=none] table[x=x,y expr=y+error] data_dist.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] data_dist.dat;
[fill=color0!30, opacity=0.5, draw=color0!50] fill between[of=upper and lower];

(b) [below=of a, yshift=1cm]

x y error
1 0.0 0.0
2 0.44404296875000004 0.04543283203997802
3 1.7297851562499997 0.1104306530041582
4 3.8276562500000004 0.2200984041176064
5 6.662753906250001 0.33705698451801575
6 10.357832031249998 0.5446647260219658
7 15.03857421875 0.7541849678586935
8 20.283935546875004 1.1811886514143073
9 26.18314453125 1.48351961514909
10 33.334931640625 1.5374988987306213

x y error
1 0.7311328125000002 0.10886327697497664
2 2.2572265625 0.21675626907170362
3 3.5117187499999996 0.16275520824999729
4 7.457919921875001 1.1829515672815627
5 11.314824218750003 1.3897681232223862
6 20.022275390624998 4.82832176562091
7 27.45068359375 6.599332696963519
8 30.450341796875005 6.107041085537743
9 58.06625 8.046271995951722
10 76.81917968750001 2.0025968654411836

tick align=outside,
tick pos=left,
legend cell align=left,
legend style=
fill opacity=1,
draw opacity=1,
text opacity=1,
at=(0.01, 0.99),
anchor=north west,
legend image code/.code=
[mark repeat=2,mark phase=2]
plot coordinates
x grid style=white!69.0196078431373!black,

ylabel=Avg. Distance,
xtick style=color=black,
y grid style=white!69.0196078431373!black,
ytick style=color=black,

[color0, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] data_dist_ang.dat;

[color1, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] realdata2d_dist_ang.dat;
IBMQ Bogota

[name path=upper,draw=none] table[x=x,y expr=y+error] realdata2d_dist_ang.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] realdata2d_dist_ang.dat;
[fill=color1!30, opacity=0.5, draw=color1!50] fill between[of=upper and lower];

[name path=upper,draw=none] table[x=x,y expr=y+error] data_dist_ang.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] data_dist_ang.dat;
[fill=color0!30, opacity=0.5, draw=color0!50] fill between[of=upper and lower];

(c) [right=of a, xshift=-0.65cm]

x y error
1 0.11046875 0.1995998805227285
2 3.959375 0.9215359546024235
3 16.02109375 1.7628661728998851
4 36.041328125 2.9715386357935296
5 64.03109375 4.277395330739221
6 99.22359375 6.280127463049491
7 144.890625 8.105384976976726
8 196.89921875 11.470633493371576
9 256.32046875 12.696306690879329
10 326.52984375 15.668158768481252

x y error
1 1.82875 0.6478326245065157
2 11.95390625 5.79988282183962
3 25.01875 12.108680020379492
4 33.767578125 11.63221242654549
5 71.34765625 8.520912170294164
6 113.6709375 13.075349741005377
7 155.8125 22.073477372636884
8 168.355078125 20.19095387488381
9 275.11 22.501777807368633
10 361.745703125 20.124149201220856

tick align=outside,
tick pos=left,
legend cell align=left,
legend style=
fill opacity=1,
draw opacity=1,
text opacity=1,
at=(0.01, 0.99),
anchor=north west,
legend image code/.code=
[mark repeat=2,mark phase=2]
plot coordinates
x grid style=white!69.0196078431373!black,

ytick=0, 100, 200, 300, 400,
ylabel=Avg. Distance,
xtick style=color=black,
y grid style=white!69.0196078431373!black,
ytick style=color=black,

[color0, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] data_dist_4d.dat;

[color1, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] realdata4d_dist.dat;
IBMQ Bogota

[name path=upper,draw=none] table[x=x,y expr=y+error] realdata4d_dist.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] realdata4d_dist.dat;
[fill=color1!30, opacity=0.5, draw=color1!50] fill between[of=upper and lower];

[name path=upper,draw=none] table[x=x,y expr=y+error] data_dist_4d.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] data_dist_4d.dat;
[fill=color0!30, opacity=0.5, draw=color0!50] fill between[of=upper and lower];

(d) [right=of b, xshift=-0.65cm]

x y error
1 0.0 0.0
2 1.01435546875 0.0951700615842411
3 3.9458984375 0.29059526845147826
4 8.5896484375 0.5502009284857151
5 15.070859375 0.8249907558963634
6 23.15173828125 1.1211030628628327
7 33.2724609375 1.4269376063136088
8 44.9541015625 2.519787679235156
9 58.43140625 2.6179272112304384
10 73.31376953125 3.646520574846679

x y error
1 3.6447265625 0.4090014901355562
2 9.70751953125 1.973962755290558
3 14.59921875 1.1836952050164375
4 22.6691015625 1.8187411106587155
5 43.9846875 4.974270183150536
6 75.32390625 9.345741329108172
7 98.5703125 22.3665029065902
8 117.228515625 13.485923987540842
9 128.1650390625 40.323090766695785
10 159.64904296875 12.292567337143408

tick align=outside,
tick pos=left,
legend cell align=left,
legend style=
fill opacity=1,
draw opacity=1,
text opacity=1,
at=(0.01, 0.99),
anchor=north west,
legend image code/.code=
[mark repeat=2,mark phase=2]
plot coordinates
x grid style=white!69.0196078431373!black,

ylabel=Avg. Distance,
xtick style=color=black,
y grid style=white!69.0196078431373!black,
ytick style=color=black,

[color0, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] data_dist_4d_ang.dat;

[color1, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] realdata4d_dist_ang.dat;
IBMQ Bogota

[name path=upper,draw=none] table[x=x,y expr=y+error] realdata4d_dist_ang.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] realdata4d_dist_ang.dat;
[fill=color1!30, opacity=0.5, draw=color1!50] fill between[of=upper and lower];

[name path=upper,draw=none] table[x=x,y expr=y+error] data_dist_4d_ang.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] data_dist_4d_ang.dat;
[fill=color0!30, opacity=0.5, draw=color0!50] fill between[of=upper and lower];

Plots for varying the distance between points. The plots on the left are for amplitude (top) and angle (bottom) embedding in two dimensions. The right plots are for amplitude (top) and angle (bottom) embedding in four dimensions. We run the experiments for a vector of shape $(1, ...,1)$ for the base points and, $(x, ..., x)$ for the varying point. We repeat the experiments 100 times with 2,048 shots plotting the average with the standard deviation.

In the last set of experiments, we vary the dimension of the data to observe the limits to the number of features we can use and with what level of accuracy. We test up to 32 dimensions for amplitude embedding and up to 26 dimensions for angle embedding, using the 27 qubit device IBMQ Sydney to its capacity in the angle embedding case. We compare vectors with shape $(1,...,1)$, to vectors $(2,...,2)$, $(3,...,3)$, and $(4,...,4)$. In Tables <ref> and <ref>, we show the percent-difference between the simulation outputs and the results from the quantum computer for amplitude and angle embedding respectively, where Fig. <ref> displays the corresponding results. We observe that at further distances, simulation and hardware results tend to agree more closely in both embedding types. These results motivate data scaling techniques, where mapping the data into a space where the data is more separated could result in more accuracy, a hypothesis we intend to explore in future work.

(a) at (0, 0)

x y error
2 2.0265625000000003 0.4215956829971994
4 3.877734375 0.8207561114499373
8 7.940625000000001 1.7717509877237267
16 15.7484375 3.1979222227829047
32 32.096875000000004 7.364570883417108

x y error
2 4.0357421875 0.3791040781086037
4 11.303125 1.2809346029486635
8 36.334375 2.1352773074445155
16 73.5234375 2.925622179420772
32 111.90937500000001 27.74197149486451

tick align=outside,
tick pos=left,
legend cell align=left,
legend style=
fill opacity=1,
draw opacity=1,
text opacity=1,
at=(0.01, 0.99),
anchor=north west,
legend image code/.code=
[mark repeat=2,mark phase=2]
plot coordinates
x grid style=white!69.0196078431373!black,
xtick=2, 4, 8, 16, 32,

xlabel=Data Dimension,
ylabel=Avg. Distance,
xtick style=color=black,
y grid style=white!69.0196078431373!black,
ytick style=color=black,

log basis x=2

[color0, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] data_dim.dat;

[color0, mark=triangle*, only marks, mark options= mark size=2pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] realdata_dim.dat;
IBMQ Sydney

[name path=upper,draw=none] table[x=x,y expr=y+error] realdata_dim.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] realdata_dim.dat;
[fill=color0!30, opacity=0.5, draw=color0!50] fill between[of=upper and lower];

[name path=upper,draw=none] table[x=x,y expr=y+error] data_dim.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] data_dim.dat;
[fill=color0!30, opacity=0.5, draw=color0!50] fill between[of=upper and lower];

(b) [below=of a, yshift=1cm]

x y error
2 8.11796875 0.9000729001508362
4 16.08203125 1.7399745965615956
8 32.471875 3.57634235069505
16 63.0625 6.29871638709031
32 129.18124999999998 13.596212420652302

x y error
2 7.371874999999999 0.8973342410910075
4 21.828125 5.619170156009471
8 61.27812499999999 6.521388338335246
16 110.88125 29.371787723298354
32 209.44999999999996 23.83443543489125

tick align=outside,
tick pos=left,
legend cell align=left,
legend style=
fill opacity=1,
draw opacity=1,
text opacity=1,
at=(0.01, 0.99),
anchor=north west,
legend image code/.code=
[mark repeat=2,mark phase=2]
plot coordinates
x grid style=white!69.0196078431373!black,
xtick=2, 4, 8, 16, 32,

xlabel=Data Dimension,
ylabel=Avg. Distance,
xtick style=color=black,
y grid style=white!69.0196078431373!black,
ytick style=color=black,

log basis x=2

[orange, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] data_dim_2.dat;

[orange, mark=triangle*,, only marks, mark options= mark size=2pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] realdata_dim_2.dat;
IBMQ Sydney

[name path=upper,draw=none] table[x=x,y expr=y+error] realdata_dim_2.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] realdata_dim_2.dat;
[fill=orange!40, opacity=0.55, draw=orange!50] fill between[of=upper and lower];

[name path=upper,draw=none] table[x=x,y expr=y+error] data_dim_2.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] data_dim_2.dat;
[fill=orange!40, opacity=0.55, draw=orange!50] fill between[of=upper and lower];

(c) [below=of b, yshift=1cm]

x y error
2 17.878554687500003 1.2342581895630338
4 35.629609375 3.136167175002083
8 72.20484375000001 5.900589588771378
16 144.925 11.536568048763462
32 288.38375 22.645053302266703

x y error
2 15.584218750000002 2.5627802295325313
4 39.06546875 9.88524820404951
8 78.55859375000001 15.112609428722667
16 204.46279 13.747548
32 369.73840 33.50718

tick align=outside,
tick pos=left,
legend cell align=left,
legend style=
fill opacity=1,
draw opacity=1,
text opacity=1,
at=(0.01, 0.99),
anchor=north west,
legend image code/.code=
[mark repeat=2,mark phase=2]
plot coordinates
x grid style=white!69.0196078431373!black,
xtick=2, 4, 8, 16, 32,

xlabel=Data Dimension,
ylabel=Avg. Distance,
xtick style=color=black,
y grid style=white!69.0196078431373!black,
ytick style=color=black,

log basis x=2

[color1, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] data_dim_3.dat;

[color1, mark=triangle*,, only marks, mark options= mark size=2pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] realdata_dim_3.dat;
IBMQ Sydney

[name path=upper,draw=none] table[x=x,y expr=y+error] realdata_dim_3.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] realdata_dim_3.dat;
[fill=color1!30, opacity=0.5, draw=color1!50] fill between[of=upper and lower];

[name path=upper,draw=none] table[x=x,y expr=y+error] data_dim_3.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] data_dim_3.dat;
[fill=color1!30, opacity=0.5, draw=color1!50] fill between[of=upper and lower];

(d) [right=of a, yshift=-0.5mm, xshift=-0.65cm]

x y error
2 0.44951171875000007 0.049095071076721356
4 1.01064453125 0.09686687804599635
8 2.1732421875 0.19977050966236665
16 4.487109375 0.38986860360405
26 7.436914062499999 0.7713757958600469

x y error
2 1.125927734375 0.10766594919215636
4 6.23916015625 0.4023885342756171
8 20.522070312500006 0.4497691516032271
16 37.10625 1.7224452464311093
26 64.38110351562499 1.477146800049244

tick align=outside,
tick pos=left,
legend cell align=left,
legend style=
fill opacity=1,
draw opacity=1,
text opacity=1,
at=(0.01, 0.99),
anchor=north west,
legend image code/.code=
[mark repeat=2,mark phase=2]
plot coordinates
x grid style=white!69.0196078431373!black,
xtick=2, 4, 8, 16, 26,

xlabel=Data Dimension,
ylabel=Avg. Distance,
xtick style=color=black,
y grid style=white!69.0196078431373!black,
ytick style=color=black,
log basis x=2

[color0, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] data_dim_ang.dat;

[color0, mark=triangle*, only marks, mark options= mark size=2pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] realdata_dim_ang.dat;
IBMQ Sydney

[name path=upper,draw=none] table[x=x,y expr=y+error] realdata_dim_ang.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] realdata_dim_ang.dat;
[fill=color0!30, opacity=0.5, draw=color0!50] fill between[of=upper and lower];

[name path=upper,draw=none] table[x=x,y expr=y+error] data_dim_ang.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] data_dim_ang.dat;
[fill=color0!30, opacity=0.5, draw=color0!50] fill between[of=upper and lower];

(e) [right=of b, xshift=-0.775cm]

x y error
2 1.7402343749999998 0.12233175128741867
4 3.880859375 0.249197625966038
8 8.29765625 0.536542456490805
16 17.15625 1.0770488288315903
26 27.68974609375 1.5023329426440697

x y error
2 3.2991210937499993 0.2894055943969247
4 15.0193359375 0.4939707202342366
8 39.8609375 1.0311659530144748
16 78.6609375 1.927583620308403
26 129.608984375 3.1885045043281797

tick align=outside,
tick pos=left,
legend cell align=left,
legend style=
fill opacity=1,
draw opacity=1,
text opacity=1,
at=(0.01, 0.99),
anchor=north west,
legend image code/.code=
[mark repeat=2,mark phase=2]
plot coordinates
x grid style=white!69.0196078431373!black,
xtick=2, 4, 8, 16, 26,

xlabel=Data Dimension,
ylabel=Avg. Distance,
xtick style=color=black,
y grid style=white!69.0196078431373!black,
ytick style=color=black,
log basis x=2

[orange, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] data_dim_ang_2.dat;

[orange, mark=triangle*, only marks, mark options= mark size=2pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] realdata_dim_ang_2.dat;
IBMQ Sydney

[name path=upper,draw=none] table[x=x,y expr=y+error] realdata_dim_ang_2.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] realdata_dim_ang_2.dat;
[fill=orange!40, opacity=0.55, draw=orange!50] fill between[of=upper and lower];

[name path=upper,draw=none] table[x=x,y expr=y+error] data_dim_ang_2.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] data_dim_ang_2.dat;
[fill=orange!40, opacity=0.55, draw=orange!50] fill between[of=upper and lower];

(f) [right=of c, xshift=-0.775cm]

x y error
2 3.8065722656250007 0.20450665610936944
4 8.6029296875 0.4836841800672866
8 18.194648437500003 0.9574710492968961
16 37.37078125 2.2868276259526676
26 60.41242187499999 3.1552132529901162

x y error
2 7.168056640625001 0.3210233541947471
4 25.39142578125 2.7001260388237545
8 68.38515625000001 1.6435513336455678
16 136.049140625 3.1798349733537545
26 212.41035156249995 5.8822814993559085

tick align=outside,
tick pos=left,
legend cell align=left,
legend style=
fill opacity=1,
draw opacity=1,
text opacity=1,
at=(0.01, 0.99),
anchor=north west,
legend image code/.code=
[mark repeat=2,mark phase=2]
plot coordinates
x grid style=white!69.0196078431373!black,
xtick=2, 4, 8, 16, 26,

xlabel=Data Dimension,
ylabel=Avg. Distance,
xtick style=color=black,
y grid style=white!69.0196078431373!black,
ytick style=color=black,
log basis x=2

[color1, mark=*, only marks, mark options= mark size=1pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] data_dim_ang_3.dat;

[color1, mark=triangle*, only marks, mark options= mark size=2pt,  error bars/.cd, y dir=both, y explicit]
table[x=x, y=y] realdata_dim_ang_3.dat;
IBMQ Sydney

[name path=upper,draw=none] table[x=x,y expr=y+error] realdata_dim_ang_3.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] realdata_dim_ang_3.dat;
[fill=color1!30, opacity=0.5, draw=color1!50] fill between[of=upper and lower];

[name path=upper,draw=none] table[x=x,y expr=y+error] data_dim_ang_3.dat;
[name path=lower,draw=none] table[x=x,y expr=y-error] data_dim_ang_3.dat;
[fill=color1!30, opacity=0.5, draw=color1!50] fill between[of=upper and lower];

Results for varying data dimension using the vector $(1,...,1)$, estimating distance to vectors $(2, ..., 2), (3, ..., 3), (4, ..., 4)$. The plots are ordered respectively from top to bottom. We run the experiment 100 times with 2,048 circuit shots and plot the average output and standard deviation of simulation after running on the IBMQ Sydney device for up to 32 dimensions with amplitude embedding (left) and 26 dimensions with angle embedding (right).

Dim.      $x=2$     $x=3$     $x=4$

2     66.44%      9.56%     13.69%

4     97.95%      30.29%     9.21%

8     128.25%     61.44%     8.42%

16     133.22%     54.98%     34.08%

32     110.86%     47.40%     24.72%

Amplitude Embedding: Percent difference comparison between simulation and real data for the distance between data points of varying dimension and distance on IBMQ Sydney.

Dim.      $x=2$     $x=3$     $x=4$

2     85.87%     61.87%     61.26%

4     144.24%     117.87%     98.77%

8     161.70%     131.13%     115.94%

16     156.84%     128.40%     113.8%

26     158.58%     129.59%     111.42%

Angle Embedding: Percent difference comparison between simulation and real data for the distance between data points of varying dimension and distance on IBMQ Sydney.

§ BENCHMARKING QUANTUM CLUSTERING

In this section we benchmark the quantum $k$-means clustering algorithm using various dimensions and number of clusters using synthetic data. To determine the accuracy of clustering using the quantum approaches, we generated three types of synthetic data using two and four dimensions. The first two types of data that we generate are an easy dataset, a hard dataset both with four clusters and 15 data points in each cluster, as seen in Fig. <ref> (a) and (b). This totals 60 data points. The third dataset we use has a variance between the easy and hard sets, but with eight clusters and 14 points per cluster, seen in Fig. <ref> (c). The number of data points and clusters was selected to most easily work with the  service, reaching the limits to how many circuits can be sent at once.

In the case of the four cluster easy and hard datasets, we analyze the quantum clustering approach using the same execution parameters for both datasets. We use both amplitude and angle embedding with a maximum of five iterations, or until convergence of the centroid locations is reached.

We use the outputs of the classical algorithm implementation as the base truth, 8,192 shots for each experiment, and use the option for measurement error mitigation in all cases. For these sets of experiments, we submit jobs to quantum devices which have a quantum volume of 32. The results of the experiments for 2D are seen in Figs. <ref>. The results displayed are, on the left side, left column, the confusion matrices comparing the classical baseline to the quantum outputs using amplitude embedding, and the equivalent for angle embedding in the right column. We observe that in the simulation setting the classical outputs are matched perfectly, however, for real hardware, the results show a relatively low accuracy in the labeling for both embeddings. The results are similar for the hard dataset as seen on the right side of Figs. <ref>.

For the 8-cluster data, we perform the same simulation steps, but for a maximum of three iterations with 8,192 shots. In simulation, convergence is reached with two iterations with perfect labeling results. We test both 2D and 4D datasets. The 2D results are shown in  Fig. <ref>. For 4D data the results had very low accuracy, with essentially a random labeling and we neglect showing the results here.

Overall, these experiments motivate that using one instance of executing the distance estimation circuit with low shot counts produce a distance estimation that is not accurate enough to cluster data. To mitigate noise, we predict that we can instead average multiple distance estimations to improve estimation consistency while simultaneously increasing the circuit shots. We test this hypothesis in the next section.

(1) at (0, 0)

(a) [scale=0.88] at (0, 0) ;
(b) [scale=0.88, right=of a, xshift=-1.5cm] ;
(c) [scale=0.88, below =of a, yshift=0.5cm]
(d) [scale=0.88, below right=of a, yshift=0.5cm,  xshift=-1.5cm]
at (0.5, -1.45) (a) Simulation;
at (4.85, -1.45) (b) Simulation;
at (0.55, -4.55) (c) Real Hardware;
at (4.85, -4.55) (d) Real Hardware;
(-0.8, 0.39) rectangle ++(2.91, -1.52);
(-0.8, -2.69) rectangle ++(2.93, -1.52);
(3.375, 0.39) rectangle ++(2.93, -1.52);
(3.375, -2.69) rectangle ++(2.93, -1.52);

(1) at (0, 0)

(a) [scale=0.88] at (0, 0) ;
(b) [scale=0.88, right=of a, xshift=-1.5cm] ;
(c) [scale=0.88, below =of a, yshift=0.5cm]
(d) [scale=0.88, below right=of a, yshift=0.5cm,  xshift=-1.5cm]
at (0.5, -1.45) (a) Simulation;
at (4.85, -1.45) (b) Simulation;
at (0.55, -4.55) (c) Real Hardware;
at (4.85, -4.55) (d) Real Hardware;
(-0.8, 0.39) rectangle ++(2.91, -1.52);
(-0.8, -2.69) rectangle ++(2.93, -1.52);
(3.375, 0.39) rectangle ++(2.93, -1.52);
(3.375, -2.69) rectangle ++(2.93, -1.52);

The confusion matrices for the execution for clustering the easy (right) and hard dataset (left) with two features using amplitude (left column) and angle (right column) embeddings. In (a) and (b) are the clustering outcome of the noiseless quantum simulation.  In (c) and (d) are the results of running on the real IBMQ Sydney device. Each instance ran for a maximum of five iterations using the maximum number of shots 8,192.

(a) [scale=0.95] at (0,0)

1c    1c    cPredicted

0      1         0         0        0     0         0         0     0
1      0         0.93      0.07     0     0         0         0     0
2      0         0         1        0     0         0         0     0
3      0         0         1        0     0         0         0     0
4      0.06      0         0        0     0.64      0         0.28     0
5      0.14      0         0        0     0.29      0.35      0.21     0
6      0         0.07      0        0     0.07      0.07      0.78     0
7      0.57      0         0        0     0.43      0         0     0
(b) [scale=0.95, right=of a]

1c    1c    cPredicted

0      0.79     0         0        0        0         0         0      0.21
1      0        1         0        0        0         0         0      0
2      0        0.29      0.64     0        0         0.07      0      0
3      0        0         0.28     0.71     0         0         0      0
4      0        0.07      0        0        0.50      0.14      0      0.28
5      0        0.36      0        0        0      0.57      0      0.07
6      0        0.64      0        0        0.07      0.28      0      0
7      0        0.07      0        0        0.14      0.21      0      0.57
[below=of a, xshift=0.75cm, yshift=0.9cm](a);
[below=of b, xshift=0.75cm, yshift=0.9cm](b);
(-2.442, 1.239) rectangle ++(6.339, -3.305);
(6.58, 1.239) rectangle ++(6.339, -3.305);

Results from clustering 2D synthetic data as depicted in Fig. <ref>(c) using amplitude encoding (a) and angle embedding in (b) on hardware running circuits for 8,192 shots on IBMQ Sydney.

§ APPLICATIONS FOR ENERGY SUBGRID CLUSTERING

The motivation for performing a detailed analysis on how well real quantum hardware performs on various distance related metrics for high dimensional data is because, typically, many real-world datasets are non-trivial, high dimensional, and not well clusterable. In classical computing solutions involving unsupervised clustering, the problem of aggregating and grouping sets of objects usually involves some dimension reduction techniques and some type of domain knowledge to tune any machine learning algorithm used. Indeed, a standard $k$-means approach—in the classical sense—when used in practice involves a fine balance of mitigation and optimization techniques depending on the data. Selecting the optimal clusters, choosing the initial centroid locations, choosing an optimal subset size of the dataset for large datasets, dealing with outliers, and dimension reduction are all points to consider when applying $k$-means to an unlabelled dataset. Celebi et al. analyze the effects of these points in [25].

Here, we focus more on the quantum aspect of $k$-means clustering. After using standard techniques for pre-processing the data and selecting initial centroids we direct our efforts to improving the distance estimation accuracy. Since quantum machine learning and variations of clustering are touted as being a possible avenue for quantum advantage, we aim to employ the findings in the previous sections to a real use-case which provides business value. In doing so, we propose an alternative implementation of the distance estimation circuit to overcome some of the deficiencies revealed in the previous section, namely, the inability of the vanilla quantum k-means algorithm to be able to handle classical input vector dimensions more than four.

§.§ German Electricity Grid Data

Predictive maintenance is a major area of applied research in the energy operations sector [26, 27]. The ability to determine areas of the electrical grid which are susceptible to failing in some pre-determined timespan has many obvious benefits for customers downstream from any grid infrastructure which may fail. One possible approach to this problem is using data-driven analysis of different partitions of the full network grid to group and find similar types of subgrid assets. This can be done by taking into account data features such as 1) the amount of renewable and non-renewable electricity flowing through the grid subsection; 2) the number of power lines within a subsection; and 3) descriptive statistics about the ages of the assets contained in the subsection. Given such a collection of asset properties for electrical grid assets, we aim to employ unsupervised $k$-means clustering to classify various subgrids of part of the German Electrical Grid [28].

The dataset consists of 81,350 low voltage power lines from a Distribution System Operator (DSO) grid in Germany. Each power line has seven numerical features as described in Table <ref>. Low voltage subgrid networks are connected to high voltage entry and exit points in the grid. For a given high voltage transformer in the grid network, we collect the low voltage lines which are part of its respective sub-network and compute numerical features describing the entire subset of low power lines. Specifically, for each subgrid we compute: the number of non-powerline assets, the total number of connected assets, and the minimum, maximum and sum of each of the features listed in Table <ref>. There are 1,037 subgrids and therefore we have a final dataset of 1,037 feature vectors, each of dimension 26.

Name     Unit

Conductor cross-section     $\text{cm}^2$

Operating Voltage     kV

Average Renewable Energy In-feed Load     MWh

Average Non-Renewable Energy In-feed Load     MWh

Number of Exits of Next Major Substation     #

Line Length     m

Sum MVA at closest HV exist     MVA

Description of the features for each powerline in the dataset.

§.§ Results

To cluster the data, we firstly perform a preprocessing step to reduce the total feature vector dimension to eight using Principal Component Analysis (PCA) which results in a 97.7% explained variance. We also produced a dataset with six dimensions using PCA which accounted for 91.4% of the variance. This second dataset was used for the angle embedding approach to fit in a 7-qubit quantum computer, the quantum computer topology we had most access to in this work.

With an initial classical analysis using the elbow-method [29], the optimal number of clusters for this dataset was determined to be $k=5$. From this dimension-reduced dataset of 1,087 points, we randomly selected 180 points to cluster, where 180 points allows us to send 900 circuits ($180 \cdot 5 = 900$) to IBM's cloud service in one job (an upper limit for some hardware). Important to any unsupervised clustering algorithm is the choice of initial centroid points. In order to ensure a quick convergence, and to reduce the number of quantum iterations, we ran the classical algorithm with a variety of random seeds such that convergence was reached within three iterations. The classical clustering results are depicted in Fig. <ref>(a), using t-Distributed Stochastic Neighbor Embedding (t-SNE) [30] on the high-dimensional data to generate a 2D projection. Using the initial centroids that achieved this, we then ran the quantum clustering experiment.

(a) at (0,0)

axis background/.style=fill=white!90!black,
axis line style=white,
tick align=outside,
x grid style=white,
xmin=-270.245212554932, xmax=322.785724639893,
xtick style=color=white!15!black,
y grid style=white,
ymin=-301.42621307373, ymax=535.987828063965,
ytick style=color=white!15!black,
[colormap/viridis, only marks, scatter, scatter src=explicit]
table [x=x, y=y, meta=colordata]
x  y  colordata
26.0927829742432 -106.207450866699 1.0
233.840179443359 -6.29642486572266 2.0
-101.014030456543 346.880249023438 3.0
-103.683532714844 -40.9615898132324 1.0
-30.4603118896484 -16.7578353881836 1.0
104.102813720703 15.8835458755493 2.0
-37.9138603210449 -200.689239501953 1.0
-176.16357421875 461.520751953125 0.0
104.542724609375 -241.682403564453 1.0
-67.7712707519531 -180.736557006836 1.0
30.999397277832 -136.947372436523 1.0
-82.992301940918 360.154724121094 3.0
-151.768203735352 351.248809814453 3.0
76.6130752563477 -153.290939331055 1.0
-16.0711917877197 -180.931365966797 1.0
189.236618041992 18.4476642608643 2.0
-126.790885925293 469.430084228516 0.0
-100.902656555176 433.99951171875 0.0
-11.3177270889282 -29.3276996612549 1.0
-101.484230041504 475.200164794922 0.0
185.827209472656 -107.604759216309 2.0
-120.951011657715 361.768768310547 3.0
-64.2290267944336 83.6723251342773 1.0
281.538787841797 18.008186340332 2.0
227.868240356445 -85.1491012573242 1.0
65.3683853149414 -55.5843048095703 1.0
54.1235847473145 -163.351409912109 1.0
50.4187469482422 -189.671020507812 1.0
-3.34288907051086 -142.963500976562 1.0
-227.76416015625 9.93789291381836 4.0
-56.1024475097656 334.334259033203 3.0
-62.9842567443848 455.780853271484 0.0
-217.738677978516 -39.0016098022461 4.0
164.77067565918 -175.948623657227 1.0
20.5430717468262 -16.5104637145996 1.0
133.160018920898 -191.80778503418 1.0
122.306549072266 -261.707183837891 1.0
-62.9960289001465 52.1273422241211 1.0
178.903457641602 -92.9919891357422 2.0
-29.2492332458496 12.804141998291 1.0
-184.015014648438 433.165069580078 0.0
75.568962097168 -199.944580078125 1.0
-9.93087863922119 -5.625807762146 1.0
117.24333190918 -52.8762168884277 1.0
-219.53385925293 -16.7012672424316 4.0
76.9552230834961 92.2527770996094 1.0
-5.84138250350952 101.374778747559 1.0
-61.6728744506836 288.413604736328 3.0
29.0828742980957 28.8328971862793 1.0
84.0670547485352 -82.2088012695312 1.0
4.41703510284424 36.6223106384277 1.0
181.735488891602 -37.8200187683105 2.0
-49.015625 -133.401657104492 1.0
209.044891357422 28.4056949615479 2.0
295.829772949219 50.4815940856934 2.0
153.07861328125 22.4834060668945 2.0
-243.289260864258 -32.3488273620605 4.0
-18.2178440093994 -77.1219329833984 1.0
-4.19389533996582 -54.027286529541 1.0
-108.614593505859 455.191467285156 0.0
-80.6699142456055 338.6845703125 3.0
-129.535583496094 496.875061035156 0.0
124.968772888184 -31.3037776947021 1.0
-69.0532760620117 177.744369506836 2.0
222.811508178711 -137.66455078125 1.0
-163.955184936523 -22.6330623626709 4.0
281.339447021484 -44.2510719299316 2.0
-18.7028732299805 80.5609970092773 1.0
7.36731910705566 137.132751464844 1.0
-150.824630737305 451.314208984375 0.0
-177.618667602539 410.713775634766 0.0
-121.901512145996 416.763214111328 0.0
230.870162963867 -167.594314575195 1.0
-205.288467407227 1.56231379508972 4.0
-42.974422454834 -33.4354705810547 1.0
-159.855072021484 134.880676269531 1.0
207.258575439453 -185.387344360352 1.0
-131.378662109375 339.934020996094 3.0
237.86669921875 -34.0131759643555 2.0
-25.3522396087646 -149.621673583984 1.0
-103.298217773438 303.353515625 3.0
63.0459747314453 -243.162384033203 1.0
151.241775512695 45.265007019043 2.0
-155.93977355957 427.353698730469 0.0
263.831756591797 34.574348449707 2.0
230.058456420898 -65.3130187988281 2.0
94.6841049194336 -183.490478515625 1.0
99.2372436523438 -156.341079711914 1.0
26.4959125518799 145.850189208984 1.0
-82.0684661865234 169.426498413086 2.0
-41.2952156066895 -175.615737915039 1.0
-101.523048400879 8.81440734863281 1.0
71.6778259277344 -177.242095947266 1.0
66.2731018066406 -27.4770412445068 1.0
-61.2394371032715 -153.537704467773 1.0
-181.290267944336 8.18028831481934 4.0
84.26220703125 -263.361938476562 1.0
210.060989379883 55.0637817382812 2.0
-16.7070941925049 52.2373237609863 1.0
-48.1372947692871 30.4000473022461 1.0
183.552612304688 90.6265106201172 2.0
-178.800308227539 37.8208122253418 4.0
29.7334671020508 -80.5212936401367 1.0
-194.070022583008 -20.5122184753418 4.0
58.5937881469727 140.126266479492 1.0
-82.3757095336914 -20.6731452941895 1.0
256.5146484375 16.2403392791748 2.0
104.251518249512 -82.5637359619141 1.0
57.024112701416 -212.550857543945 1.0
-56.9397239685059 358.015838623047 3.0
-42.393180847168 69.5676116943359 1.0
258.060882568359 -67.1297760009766 2.0
-42.2848968505859 -84.8449630737305 1.0
130.961059570312 -98.7165832519531 1.0
-60.6245460510254 -202.680267333984 1.0
-39.100025177002 -221.054473876953 1.0
31.7839832305908 -205.177093505859 1.0
-126.381614685059 319.41357421875 3.0
255.839111328125 -156.798614501953 2.0
-69.1334381103516 -45.8811950683594 1.0
30.940258026123 -173.612533569336 1.0
-25.6779727935791 -49.5771636962891 1.0
-82.7503356933594 315.775177001953 3.0
-91.4603118896484 -223.007064819336 1.0
-82.2798538208008 -134.867523193359 1.0
9.17959594726562 -72.0056762695312 1.0
81.4499893188477 0.288182854652405 1.0
100.997192382812 -207.456939697266 1.0
8.66903018951416 80.2231597900391 1.0
-242.287048339844 -8.97995853424072 4.0
-154.091827392578 479.204650878906 0.0
-133.788436889648 57.7797737121582 1.0
93.9646224975586 -44.908073425293 1.0
-59.4038696289062 -19.6894969940186 1.0
-102.476493835449 -69.2863006591797 1.0
229.78645324707 32.8473587036133 2.0
190.444351196289 49.5985832214355 2.0
59.8330345153809 81.8757400512695 1.0
4.61865282058716 -95.9295883178711 1.0
-35.9074058532715 346.284423828125 3.0
-74.7538146972656 4.92165374755859 1.0
-100.89909362793 326.604034423828 3.0
-207.022415161133 412.896484375 0.0
-86.4594192504883 455.198394775391 0.0
22.0752258300781 -43.9733123779297 1.0
213.099533081055 -44.7401695251465 2.0
-192.215286254883 -44.8335647583008 4.0
20.6656150817871 118.092796325684 1.0
133.514663696289 -151.835845947266 1.0
-18.4472503662109 118.023445129395 1.0
-125.089172363281 440.203216552734 0.0
202.024353027344 -64.6460571289062 1.0
-102.992782592773 -179.779357910156 1.0
58.2043724060059 -138.446273803711 1.0
-89.2171630859375 30.9171352386475 1.0
69.0767059326172 -114.701072692871 1.0
203.253448486328 88.6626968383789 2.0
-203.709228515625 23.2864151000977 4.0
236.494567871094 73.0027313232422 2.0
213.661422729492 -24.1187744140625 2.0
-75.9971160888672 431.023620605469 0.0
-78.149299621582 -77.2572479248047 1.0
-25.0924377441406 364.429382324219 4.0
-52.2927207946777 2.90604686737061 1.0
96.4801406860352 -113.917419433594 1.0
234.04719543457 93.5351486206055 2.0
-8.52636051177979 -202.774078369141 1.0
-160.167083740234 314.61962890625 3.0
-101.566535949707 497.923553466797 0.0
79.6267929077148 -224.621948242188 1.0
-94.8399200439453 412.130584716797 0.0
44.0397415161133 -23.7994575500488 1.0
230.950881958008 -118.922142028809 1.0
-176.238830566406 135.813186645508 1.0
54.1775856018066 -93.1738586425781 1.0
-38.938591003418 100.478240966797 1.0
-47.9940032958984 -64.0798034667969 1.0
210.729629516602 6.2219033241272 2.0
40.1304550170898 -230.53076171875 1.0
-77.5131607055664 479.990509033203 0.0

(b) [below=of a, yshift=0.3cm]

axis background/.style=fill=white!90!black,
axis line style=white,
tick align=outside,
x grid style=white,
xmin=-270.245212554932, xmax=322.785724639893,
xtick style=color=white!15!black,
y grid style=white,
ymin=-301.42621307373, ymax=535.987828063965,
ytick style=color=white!15!black
[colormap/viridis, only marks, scatter, scatter src=explicit]
table [x=x, y=y, meta=colordata]
x  y  colordata
26.0927829742432 -106.207450866699 2.0
233.840179443359 -6.29642486572266 1.0
-101.014030456543 346.880249023438 2.0
-103.683532714844 -40.9615898132324 2.0
-30.4603118896484 -16.7578353881836 2.0
104.102813720703 15.8835458755493 0.0
-37.9138603210449 -200.689239501953 2.0
-176.16357421875 461.520751953125 1.0
104.542724609375 -241.682403564453 2.0
-67.7712707519531 -180.736557006836 2.0
30.999397277832 -136.947372436523 2.0
-82.992301940918 360.154724121094 0.0
-151.768203735352 351.248809814453 1.0
76.6130752563477 -153.290939331055 2.0
-16.0711917877197 -180.931365966797 2.0
189.236618041992 18.4476642608643 2.0
-126.790885925293 469.430084228516 0.0
-100.902656555176 433.99951171875 1.0
-11.3177270889282 -29.3276996612549 0.0
-101.484230041504 475.200164794922 1.0
185.827209472656 -107.604759216309 0.0
-120.951011657715 361.768768310547 2.0
-64.2290267944336 83.6723251342773 2.0
281.538787841797 18.008186340332 2.0
227.868240356445 -85.1491012573242 2.0
65.3683853149414 -55.5843048095703 2.0
54.1235847473145 -163.351409912109 2.0
50.4187469482422 -189.671020507812 2.0
-3.34288907051086 -142.963500976562 1.0
-227.76416015625 9.93789291381836 2.0
-56.1024475097656 334.334259033203 2.0
-62.9842567443848 455.780853271484 1.0
-217.738677978516 -39.0016098022461 2.0
164.77067565918 -175.948623657227 2.0
20.5430717468262 -16.5104637145996 2.0
133.160018920898 -191.80778503418 1.0
122.306549072266 -261.707183837891 2.0
-62.9960289001465 52.1273422241211 0.0
178.903457641602 -92.9919891357422 1.0
-29.2492332458496 12.804141998291 0.0
-184.015014648438 433.165069580078 1.0
75.568962097168 -199.944580078125 2.0
-9.93087863922119 -5.625807762146 2.0
117.24333190918 -52.8762168884277 2.0
-219.53385925293 -16.7012672424316 0.0
76.9552230834961 92.2527770996094 2.0
-5.84138250350952 101.374778747559 2.0
-61.6728744506836 288.413604736328 0.0
29.0828742980957 28.8328971862793 0.0
84.0670547485352 -82.2088012695312 2.0
4.41703510284424 36.6223106384277 0.0
181.735488891602 -37.8200187683105 2.0
-49.015625 -133.401657104492 0.0
209.044891357422 28.4056949615479 1.0
295.829772949219 50.4815940856934 0.0
153.07861328125 22.4834060668945 2.0
-243.289260864258 -32.3488273620605 0.0
-18.2178440093994 -77.1219329833984 2.0
-4.19389533996582 -54.027286529541 0.0
-108.614593505859 455.191467285156 1.0
-80.6699142456055 338.6845703125 0.0
-129.535583496094 496.875061035156 2.0
124.968772888184 -31.3037776947021 2.0
-69.0532760620117 177.744369506836 0.0
222.811508178711 -137.66455078125 0.0
-163.955184936523 -22.6330623626709 2.0
281.339447021484 -44.2510719299316 0.0
-18.7028732299805 80.5609970092773 0.0
7.36731910705566 137.132751464844 0.0
-150.824630737305 451.314208984375 2.0
-177.618667602539 410.713775634766 1.0
-121.901512145996 416.763214111328 0.0
230.870162963867 -167.594314575195 0.0
-205.288467407227 1.56231379508972 0.0
-42.974422454834 -33.4354705810547 0.0
-159.855072021484 134.880676269531 0.0
207.258575439453 -185.387344360352 0.0
-131.378662109375 339.934020996094 0.0
237.86669921875 -34.0131759643555 1.0
-25.3522396087646 -149.621673583984 1.0
-103.298217773438 303.353515625 0.0
63.0459747314453 -243.162384033203 1.0
151.241775512695 45.265007019043 1.0
-155.93977355957 427.353698730469 0.0
263.831756591797 34.574348449707 2.0
230.058456420898 -65.3130187988281 1.0
94.6841049194336 -183.490478515625 2.0
99.2372436523438 -156.341079711914 2.0
26.4959125518799 145.850189208984 1.0
-82.0684661865234 169.426498413086 1.0
-41.2952156066895 -175.615737915039 2.0
-101.523048400879 8.81440734863281 2.0
71.6778259277344 -177.242095947266 2.0
66.2731018066406 -27.4770412445068 2.0
-61.2394371032715 -153.537704467773 2.0
-181.290267944336 8.18028831481934 1.0
84.26220703125 -263.361938476562 2.0
210.060989379883 55.0637817382812 1.0
-16.7070941925049 52.2373237609863 2.0
-48.1372947692871 30.4000473022461 2.0
183.552612304688 90.6265106201172 2.0
-178.800308227539 37.8208122253418 1.0
29.7334671020508 -80.5212936401367 2.0
-194.070022583008 -20.5122184753418 2.0
58.5937881469727 140.126266479492 1.0
-82.3757095336914 -20.6731452941895 2.0
256.5146484375 16.2403392791748 2.0
104.251518249512 -82.5637359619141 2.0
57.024112701416 -212.550857543945 2.0
-56.9397239685059 358.015838623047 2.0
-42.393180847168 69.5676116943359 2.0
258.060882568359 -67.1297760009766 2.0
-42.2848968505859 -84.8449630737305 2.0
130.961059570312 -98.7165832519531 1.0
-60.6245460510254 -202.680267333984 2.0
-39.100025177002 -221.054473876953 2.0
31.7839832305908 -205.177093505859 1.0
-126.381614685059 319.41357421875 0.0
255.839111328125 -156.798614501953 1.0
-69.1334381103516 -45.8811950683594 2.0
30.940258026123 -173.612533569336 2.0
-25.6779727935791 -49.5771636962891 2.0
-82.7503356933594 315.775177001953 0.0
-91.4603118896484 -223.007064819336 2.0
-82.2798538208008 -134.867523193359 2.0
9.17959594726562 -72.0056762695312 2.0
81.4499893188477 0.288182854652405 2.0
100.997192382812 -207.456939697266 2.0
8.66903018951416 80.2231597900391 2.0
-242.287048339844 -8.97995853424072 2.0
-154.091827392578 479.204650878906 0.0
-133.788436889648 57.7797737121582 1.0
93.9646224975586 -44.908073425293 2.0
-59.4038696289062 -19.6894969940186 0.0
-102.476493835449 -69.2863006591797 2.0
229.78645324707 32.8473587036133 2.0
190.444351196289 49.5985832214355 1.0
59.8330345153809 81.8757400512695 2.0
4.61865282058716 -95.9295883178711 1.0
-35.9074058532715 346.284423828125 0.0
-74.7538146972656 4.92165374755859 1.0
-100.89909362793 326.604034423828 2.0
-207.022415161133 412.896484375 2.0
-86.4594192504883 455.198394775391 0.0
22.0752258300781 -43.9733123779297 2.0
213.099533081055 -44.7401695251465 1.0
-192.215286254883 -44.8335647583008 1.0
20.6656150817871 118.092796325684 1.0
133.514663696289 -151.835845947266 0.0
-18.4472503662109 118.023445129395 0.0
-125.089172363281 440.203216552734 1.0
202.024353027344 -64.6460571289062 1.0
-102.992782592773 -179.779357910156 1.0
58.2043724060059 -138.446273803711 2.0
-89.2171630859375 30.9171352386475 2.0
69.0767059326172 -114.701072692871 2.0
203.253448486328 88.6626968383789 1.0
-203.709228515625 23.2864151000977 2.0
236.494567871094 73.0027313232422 2.0
213.661422729492 -24.1187744140625 2.0
-75.9971160888672 431.023620605469 0.0
-78.149299621582 -77.2572479248047 2.0
-25.0924377441406 364.429382324219 0.0
-52.2927207946777 2.90604686737061 2.0
96.4801406860352 -113.917419433594 1.0
234.04719543457 93.5351486206055 2.0
-8.52636051177979 -202.774078369141 2.0
-160.167083740234 314.61962890625 0.0
-101.566535949707 497.923553466797 0.0
79.6267929077148 -224.621948242188 2.0
-94.8399200439453 412.130584716797 0.0
44.0397415161133 -23.7994575500488 2.0
230.950881958008 -118.922142028809 1.0
-176.238830566406 135.813186645508 0.0
54.1775856018066 -93.1738586425781 2.0
-38.938591003418 100.478240966797 2.0
-47.9940032958984 -64.0798034667969 2.0
210.729629516602 6.2219033241272 2.0
40.1304550170898 -230.53076171875 1.0
-77.5131607055664 479.990509033203 0.0

(c) [below=of b, yshift=0.3cm]

axis background/.style=fill=white!90!black,
axis line style=white,
tick align=outside,
x grid style=white,
xmin=-270.245212554932, xmax=322.785724639893,
xtick style=color=white!15!black,
y grid style=white,
ymin=-301.42621307373, ymax=535.987828063965,
ytick style=color=white!15!black
[colormap/viridis, only marks, scatter, scatter src=explicit]
table [x=x, y=y, meta=colordata]
x  y  colordata
26.0927829742432 -106.207450866699 1.0
233.840179443359 -6.29642486572266 2.0
-101.014030456543 346.880249023438 0.0
-103.683532714844 -40.9615898132324 1.0
-30.4603118896484 -16.7578353881836 1.0
104.102813720703 15.8835458755493 2.0
-37.9138603210449 -200.689239501953 1.0
-176.16357421875 461.520751953125 0.0
104.542724609375 -241.682403564453 1.0
-67.7712707519531 -180.736557006836 1.0
30.999397277832 -136.947372436523 1.0
-82.992301940918 360.154724121094 0.0
-151.768203735352 351.248809814453 0.0
76.6130752563477 -153.290939331055 2.0
-16.0711917877197 -180.931365966797 1.0
189.236618041992 18.4476642608643 2.0
-126.790885925293 469.430084228516 0.0
-100.902656555176 433.99951171875 0.0
-11.3177270889282 -29.3276996612549 1.0
-101.484230041504 475.200164794922 0.0
185.827209472656 -107.604759216309 2.0
-120.951011657715 361.768768310547 0.0
-64.2290267944336 83.6723251342773 1.0
281.538787841797 18.008186340332 2.0
227.868240356445 -85.1491012573242 1.0
65.3683853149414 -55.5843048095703 2.0
54.1235847473145 -163.351409912109 2.0
50.4187469482422 -189.671020507812 1.0
-3.34288907051086 -142.963500976562 1.0
-227.76416015625 9.93789291381836 1.0
-56.1024475097656 334.334259033203 0.0
-62.9842567443848 455.780853271484 0.0
-217.738677978516 -39.0016098022461 1.0
164.77067565918 -175.948623657227 1.0
20.5430717468262 -16.5104637145996 1.0
133.160018920898 -191.80778503418 1.0
122.306549072266 -261.707183837891 1.0
-62.9960289001465 52.1273422241211 1.0
178.903457641602 -92.9919891357422 1.0
-29.2492332458496 12.804141998291 1.0
-184.015014648438 433.165069580078 0.0
75.568962097168 -199.944580078125 1.0
-9.93087863922119 -5.625807762146 1.0
117.24333190918 -52.8762168884277 2.0
-219.53385925293 -16.7012672424316 1.0
76.9552230834961 92.2527770996094 1.0
-5.84138250350952 101.374778747559 1.0
-61.6728744506836 288.413604736328 0.0
29.0828742980957 28.8328971862793 1.0
84.0670547485352 -82.2088012695312 1.0
4.41703510284424 36.6223106384277 1.0
181.735488891602 -37.8200187683105 1.0
-49.015625 -133.401657104492 1.0
209.044891357422 28.4056949615479 2.0
295.829772949219 50.4815940856934 2.0
153.07861328125 22.4834060668945 2.0
-243.289260864258 -32.3488273620605 1.0
-18.2178440093994 -77.1219329833984 1.0
-4.19389533996582 -54.027286529541 1.0
-108.614593505859 455.191467285156 0.0
-80.6699142456055 338.6845703125 0.0
-129.535583496094 496.875061035156 0.0
124.968772888184 -31.3037776947021 2.0
-69.0532760620117 177.744369506836 2.0
222.811508178711 -137.66455078125 1.0
-163.955184936523 -22.6330623626709 1.0
281.339447021484 -44.2510719299316 2.0
-18.7028732299805 80.5609970092773 1.0
7.36731910705566 137.132751464844 1.0
-150.824630737305 451.314208984375 0.0
-177.618667602539 410.713775634766 0.0
-121.901512145996 416.763214111328 0.0
230.870162963867 -167.594314575195 2.0
-205.288467407227 1.56231379508972 1.0
-42.974422454834 -33.4354705810547 1.0
-159.855072021484 134.880676269531 1.0
207.258575439453 -185.387344360352 1.0
-131.378662109375 339.934020996094 0.0
237.86669921875 -34.0131759643555 1.0
-25.3522396087646 -149.621673583984 1.0
-103.298217773438 303.353515625 0.0
63.0459747314453 -243.162384033203 1.0
151.241775512695 45.265007019043 2.0
-155.93977355957 427.353698730469 0.0
263.831756591797 34.574348449707 1.0
230.058456420898 -65.3130187988281 2.0
94.6841049194336 -183.490478515625 1.0
99.2372436523438 -156.341079711914 1.0
26.4959125518799 145.850189208984 1.0
-82.0684661865234 169.426498413086 1.0
-41.2952156066895 -175.615737915039 1.0
-101.523048400879 8.81440734863281 1.0
71.6778259277344 -177.242095947266 1.0
66.2731018066406 -27.4770412445068 1.0
-61.2394371032715 -153.537704467773 1.0
-181.290267944336 8.18028831481934 2.0
84.26220703125 -263.361938476562 1.0
210.060989379883 55.0637817382812 2.0
-16.7070941925049 52.2373237609863 1.0
-48.1372947692871 30.4000473022461 1.0
183.552612304688 90.6265106201172 1.0
-178.800308227539 37.8208122253418 1.0
29.7334671020508 -80.5212936401367 1.0
-194.070022583008 -20.5122184753418 1.0
58.5937881469727 140.126266479492 1.0
-82.3757095336914 -20.6731452941895 1.0
256.5146484375 16.2403392791748 2.0
104.251518249512 -82.5637359619141 1.0
57.024112701416 -212.550857543945 1.0
-56.9397239685059 358.015838623047 0.0
-42.393180847168 69.5676116943359 1.0
258.060882568359 -67.1297760009766 2.0
-42.2848968505859 -84.8449630737305 1.0
130.961059570312 -98.7165832519531 2.0
-60.6245460510254 -202.680267333984 1.0
-39.100025177002 -221.054473876953 1.0
31.7839832305908 -205.177093505859 1.0
-126.381614685059 319.41357421875 0.0
255.839111328125 -156.798614501953 1.0
-69.1334381103516 -45.8811950683594 1.0
30.940258026123 -173.612533569336 1.0
-25.6779727935791 -49.5771636962891 1.0
-82.7503356933594 315.775177001953 0.0
-91.4603118896484 -223.007064819336 1.0
-82.2798538208008 -134.867523193359 1.0
9.17959594726562 -72.0056762695312 1.0
81.4499893188477 0.288182854652405 2.0
100.997192382812 -207.456939697266 1.0
8.66903018951416 80.2231597900391 1.0
-242.287048339844 -8.97995853424072 1.0
-154.091827392578 479.204650878906 0.0
-133.788436889648 57.7797737121582 1.0
93.9646224975586 -44.908073425293 2.0
-59.4038696289062 -19.6894969940186 1.0
-102.476493835449 -69.2863006591797 1.0
229.78645324707 32.8473587036133 2.0
190.444351196289 49.5985832214355 2.0
59.8330345153809 81.8757400512695 1.0
4.61865282058716 -95.9295883178711 1.0
-35.9074058532715 346.284423828125 0.0
-74.7538146972656 4.92165374755859 1.0
-100.89909362793 326.604034423828 0.0
-207.022415161133 412.896484375 0.0
-86.4594192504883 455.198394775391 0.0
22.0752258300781 -43.9733123779297 1.0
213.099533081055 -44.7401695251465 1.0
-192.215286254883 -44.8335647583008 1.0
20.6656150817871 118.092796325684 1.0
133.514663696289 -151.835845947266 1.0
-18.4472503662109 118.023445129395 1.0
-125.089172363281 440.203216552734 0.0
202.024353027344 -64.6460571289062 1.0
-102.992782592773 -179.779357910156 1.0
58.2043724060059 -138.446273803711 1.0
-89.2171630859375 30.9171352386475 1.0
69.0767059326172 -114.701072692871 2.0
203.253448486328 88.6626968383789 2.0
-203.709228515625 23.2864151000977 1.0
236.494567871094 73.0027313232422 2.0
213.661422729492 -24.1187744140625 2.0
-75.9971160888672 431.023620605469 0.0
-78.149299621582 -77.2572479248047 1.0
-25.0924377441406 364.429382324219 0.0
-52.2927207946777 2.90604686737061 1.0
96.4801406860352 -113.917419433594 2.0
234.04719543457 93.5351486206055 2.0
-8.52636051177979 -202.774078369141 1.0
-160.167083740234 314.61962890625 0.0
-101.566535949707 497.923553466797 0.0
79.6267929077148 -224.621948242188 1.0
-94.8399200439453 412.130584716797 0.0
44.0397415161133 -23.7994575500488 1.0
230.950881958008 -118.922142028809 1.0
-176.238830566406 135.813186645508 1.0
54.1775856018066 -93.1738586425781 1.0
-38.938591003418 100.478240966797 1.0
-47.9940032958984 -64.0798034667969 1.0
210.729629516602 6.2219033241272 2.0
40.1304550170898 -230.53076171875 1.0
-77.5131607055664 479.990509033203 0.0

[below=of a,yshift=0.9cm](a);
[below=of b,yshift=0.9cm](b);
[below=of c,yshift=0.9cm](c);

(a) Classical clustering output after t-SNE is performed on the subgrid data. (b) Quantum labeling output using 8D amplitude encoding for five iterations with 12,000 shots per distance estimation on IBM Casablanca. (c) Quantum clustering output using the split distance estimate (<ref>) of the subgrid data using angle encoding, two estimates per circuit, for five iterations with 12,000 shots per distance estimation on IBM Perth.

To validate the quantum approaches we used, we firstly compare the labeling output from noiseless simulation to the labels output using the classical approach, and then repeat the comparison running on real quantum devices. Because the classical approach converged in three iterations, we allow the quantum versions to run with a maximum of five iterations. In simulation, the balanced accuracy of the experiments were 100% with amplitude embedding and 97.8% for angle embedding. Given that simulation produces high-accuracy, we performed a series of tests on the quantum hardware.

§.§.§ Clustering using amplitude encoding

The first test we perform is to simply run the same logic as in the simulation. We use 12,000 shots per distance estimate and run the full clustering algorithm for five iterations. The clustering result using amplitude encoding are given in Fig. <ref>(b). The grid data is of relative high-dimension and the circuits to prepare the data are roughly 120 gate-depth with approximately 70 non-local gates for amplitude embedding. For angle embedding, the gate depth is expectantly shallower at approximately 86 but with roughly 103 non-local gates, depending on the randomization of circuit transpilation step. With the level of noise occurring, five iterations does not improve the results, and indeed we speculate further iterations would not have led to improved results either. Here, our observation is that the labeling is essentially random due to the noise in the distance estimation circuits, never leading to a converging state.

§.§.§ Classification using amplitude encoding

As a second test, we implemented a pure nearest-neighbor classification application. We being by training the model offline classically to determine optimal centroid locations, then, at runtime, we compute only the prediction step quantumly to determine which cluster test set data points belong to. Fig. <ref>(a) shows the accuracy results of the outcome, where we used 30,000 shots to estimate the distances using amplitude embedding in 8D. We see the majority of points were assigned to one class, similarly to how the five iterations of clustering performed.

[trim left=-1.0cm]
(a) at (0, 0)

1c    1c    cIBMQ Lagos

0     0      0      0     1     0
1     0      0.14      0     0.86     0
2     0      0     0.44     0.56     0
3     0      0      0.03     0.97     0
4     0      0      0     1     0
(b) [below=of a]

1c    1c    cIBMQ Jakarta

0     1      0      0     0     0
1     0      0.57      0     0     0.43
2     0      0      0.66     0.33     0
3     0      0      0     1     0
4     0      0      0     0     1
(c) [below=of b]

1c    1c    cIBM Perth

0     1      0      0     0     0
1     0      0      0     0     1
2     0      0      0.66     0.33     0
3     0      0      0     1     0
4     0      0      0     0     1
[below=of a, xshift=0.75cm, yshift=0.85cm] (a);
[below=of b, xshift=0.75cm, yshift=0.85cm] (b);
[below=of c, xshift=0.75cm, yshift=0.85cm] (c);
(-1.33, 0.65) rectangle ++(4.17, -2.17);
(-1.33, -3.65) rectangle ++(4.17, -2.17);
(-1.33, -7.94) rectangle ++(4.17, -2.17);

The results of classifying the test set of 60 data points using a nearest-neighbor prediction. In (a), we use amplitude encoding in 8 dimensions and 30,000 shots per distance estimation. The balanced accuracy in this case is 17.0% and the raw accuracy 46.7%. Weighted precision cannot be computed since some classes are empty. In (b) we repeat the classification using 15,000 shots using the divided distance estimation in four 2D estimates, using an averaged five estimates per distance. The results have a balanced accuracy of 84.8%, a raw accuracy of 90.0% and a weighted precision score of 92.1%. In (c), the classification is done using the vector subspace parallelization circuit which uses two swap-tests per circuit. This approach reduces the total number of circuits by 50%. The results improved significantly to have a balanced accuracy of 73.3%, a raw accuracy of 83.3%.

§.§.§ Distance estimation with vector subspace parallelization

So far, our approach to distance estimation has been to use the approach as stated in [5], however, the accuracy in practice using this approach has thus far been relatively low. From the benchmarking section, the highest accuracy was seen in the two-dimensional data experiments. Using this as motivation, we propose a new technique of parallelizing the distance calculation for high dimensional vectors by using distances between two-dimensional subspaces of the full feature vectors.

Given input data vectors $a\coloneqq(a_1, a_2, ..., a_n)$ and $b\coloneqq(b_1, b_2, ..., b_n)$, the distance between them can be decomposed as

\begin{align}\label{eq:metric}
\begin{aligned}
d(a, b) = \hspace{1mm}&d(a_{1,2}, b_{1,2}) + d(a_{3,4}, b_{3,4})  \\ &+  \dots +         d(a_{n-1,n}, b_{n-1,n}),
\end{aligned}
\end{align}

where $a_{i,j}=\mathcal{P}_{i,j}(a)$ and $b_{i,j}=\mathcal{P}_{i,j}(b)$ are projections of the respective vectors to the $(i,j)$-th vector subspace. The circuit for this parallel distance estimate using angle embedding is depicted in Fig. <ref>.

This approach has various benefits in terms of mitigating noise. Firstly, it uses only low-dimensional projections. In this case, we use two-dimensional projections, aligned with our benchmarking results, but as hardware improves, we can extend this to larger dimensions to reduce the number of total independent measurements until we can eventually use the entire vector. Next, these low-dimensional circuits will be in general shallower and thinner, which will improve the accuracy and moreover reduce the computation time, allowing for more shots within the same execution timespan. Because in some cases we observed a large standard deviation, with shorter execution time, one can also execute the circuit many times to produce an average distance estimate the same timespan, mitigating Gaussian noise in the system.

Because the distance estimation circuits are indeed thinner, we can load multiple circuits into one QPU proportional to the number of qubits. For example, because the swap-test with angle embedding in 2D uses three qubits per swap-test, we can load two distance calculations at a time in a seven qubit quantum computer, reducing the number of total circuits to execute by 50%. This approach could be generalized to contain as many swap-tests as there are (the floor of) one third the number of qubits, which could in turn result in again using one circuit for distance estimation, simply with a modified pre- and post-processing step. These benefits make this much more NISQ compatible than performing the distance estimation with all dimensions considered at once.

After verifying this approach produced accurate results in simulation, to tested how well it mitigates the effects of noise in the classification task, we ran the circuit implementing (<ref>) using two approaches. For the first approach we used amplitude encoding and executed each distance estimation circuit independently five times, averaging the results and using the average as the distance estimate. We used 15,000 shots per execution and since the circuit uses four qubits, we could fit just one circuit at a time on the 7-qubit device. The confusion matrix of the results is in Fig. <ref>(b), showing a vast improvement.

[scale=0.85, draw, dashed] at (0, 0)
@C=1.74em @R=1.1em
|0⟩     U(a'_1, a'_2)

|0⟩     U(a'_3, a'_4)

|0⟩     H     -2     H

[] at (0, -1.38) $\vdots$;
[scale=0.85, draw, dashed] at (0, -3)
@C=1.3em @R=1.1em
|0⟩     U(a'_n-3, a'_n-2)

|0⟩     U(a'_n-1, a'_n)

|0⟩     H     -2     H

Circuit for processing multiple distances in one circuit using angle embedding with swap tests. The dashed boxes separation each independent swap-test.

For the second approach, we perform classification again, now using angle embedding, but in this case, since just three qubits per swap-test are required, we could load two distance estimates in parallel into the 7-qubit device. Using 15,000 shots with, in this case, two repetitions per circuit, we again use the average for the estimate. The results of the classification are shown in Fig. <ref>(c). Again, we see a strong improvement for the classification problem over the standard method, increasing the balanced accuracy from 17% in the standard approach to 73.3% using this novel approach, a difference of 56.3%.

§.§.§ Clustering with vector subspace parallelization

Given the promising results from the classification task using the vector subspace parallelization, we again perform the full clustering algorithm using the angle embedding approach. We  use the distance estimation (<ref>) with 12,000 shots and one repetition on the IBM Perth machine with a total of five iterations for the clustering algorithm. The clustering results are shown in Fig. <ref>(c). Although the labels were reduced to three classes, two fewer than in the classical algorithm, we see a much clearer separation of the classes in comparison to using amplitude encoding for all eight dimensions.

§ CONCLUSION AND OUTLOOK

In this work, we thoroughly investigated the potential of using quantum $k$-means clustering in a practical manner on current NISQ quantum hardware. In terms of distance estimation comparison between classical and quantum distance calculations, we clearly observed a high level of difference between simulation and running on physical devices—especially comparing the distance estimation results using angle embeddings. The results which used batched job submission via  showed to vastly improve performance, allowing for more circuit executions, improving reliability, as well as drastic speed improvements when dealing with large datasets due to the reduction in job-queuing time.

The best $k$-means clustering results observed were from clustering datasets of 2-dimensional data points. When we increased the number of clusters from four to a more complex scenario of eight clusters, and changed the input vector dimension from two to four, the results worsened. We experimented with an industrial unsupervised learning problem, labeling high-dimensional energy grid data using $k$-means clustering. Using the state-of-the-art approach, the clustering and classification results proved inaccurate when executed over real hardware. When we changed the distance metric and used our vector subspace parallelization approach, we saw a significant improvement in both our classification and clustering experiments. For amplitude embeddings, the balanced accuracy of the classification went from 17% using the standard approach to 84.8% with this novel distance estimation method. With angle embedding, loading two swap-tests into one circuit to execute in parallel, albeit an overall wider circuit, proved to also have a large performance improvement over the amplitude encoding approach, with a balanced classification accuracy of 73.3% and raw accuracy of 83.3%.

This work provides a first step into quantum clustering for practical, industrial use-cases, but still there are questions to be answered. Future work will be to consider other clustering algorithms such as $k$-medoids which uses alternative distance metrics, considering other quantum approaches for distance estimation as in [14, 31] or those better suited for NISQ hardware as proposed in [32]. Indeed, many algorithms require a distance calculation step, and so benchmarking their quantum performance leaves many possibilities for future work.

Although it is well known that quantum computing is in its early stages of development, it is important to investigate what boundaries exist in relation to non-trivial problems that move beyond fundamental algorithm proof-of-concepts. Clustering, and particularly distance estimation, are widely used in various industry applications. With this work, we have tested a large set of experiments that can be performed on the quantum cloud using only the core features of the platform.

Quantum technology is continuously and rapidly improving and we expect that as NISQ-era quantum computers mature, these types of analysis and industry-driven use-case studies will continue to be necessary to provide valuable insight into how they will be used for real-life applications.

§ ACKNOWLEDGMENT

We acknowledge the use of IBM Quantum services for this work. The views expressed are those of the authors, and do not reflect the official policy or position of IBM or the IBM Quantum team.

[1]
C. G. Almudever, L. Lao, X. Fu, N. Khammassi, I. Ashraf, D. Iorga,
S. Varsamopoulos, C. Eichler, A. Wallraff, L. Geck et al., “The
engineering challenges in quantum computing,” in Design, Automation &
Test in Europe Conference & Exhibition (DATE), 2017.1em plus 0.5em
minus 0.4emIEEE, 2017, pp. 836–845.

[2]
“Quantum services.” [Online]. Available:

[3]
S. Lloyd, “Least squares quantization in pcm,” IEEE transactions on
information theory, vol. 28, no. 2, pp. 129–137, 1982.

[4]
M. Schuld and F. Petruccione, Supervised learning with quantum
computers.1em plus 0.5em minus 0.4emSpringer, 2018, vol. 17.

[5]
S. Lloyd, M. Mohseni, and P. Rebentrost, “Quantum algorithms for supervised
and unsupervised machine learning,” arXiv preprint arXiv:1307.0411,

[6]
H. Buhrman, R. Cleve, J. Watrous, and R. De Wolf, “Quantum fingerprinting,”
Physical Review Letters, vol. 87, no. 16, p. 167902, 2001.

[7]
L. K. Grover, “A fast quantum mechanical algorithm for database search,” in
Proceedings of the twenty-eighth annual ACM symposium on Theory of
computing, 1996, pp. 212–219.

[8]
M. Plesch and Č. Brukner, “Quantum-state preparation with universal gate
decompositions,” Physical Review A, vol. 83, no. 3, p. 032302, 2011.

[9]
E. Tang, “Quantum principal component analysis only achieves an exponential
speedup because of its state preparation assumptions,” Physical Review
Letters, vol. 127, no. 6, p. 060503, 2021.

[10]
S. U. Khan, A. J. Awan, and G. Vall-Llosera, “K-means clustering on noisy
intermediate scale quantum computers,” arXiv preprint
arXiv:1909.12183, 2019.

[11]
S. Johri, S. Debnath, A. Mocherla, A. Singh, A. Prakash, J. Kim, and
I. Kerenidis, “Nearest centroid classification on a trapped ion quantum
computer,” npj Quantum Information, vol. 7, no. 1, p. 122, Aug. 2021.

[12]
V. Kumar, G. Bass, C. Tomlin, and J. Dulny, “Quantum annealing for
combinatorial clustering,” Quantum Information Processing, vol. 17,
no. 2, pp. 1–14, 2018.

[13]
D. Arthur et al., “Balanced k-means clustering on an adiabatic quantum
computer,” Quantum Information Processing, vol. 20, no. 9, pp. 1–30,

[14]
K. Benlamine, Y. Bennani, A. Zaiou, M. Hibti, B. Matei, and N. Grozavu,
“Distance estimation for quantum prototypes based clustering,” in
International Conference on Neural Information Processing.1em
plus 0.5em minus 0.4emSpringer, 2019, pp. 561–572.

[15]
K. Benlamine, Y. Bennani, N. Grozavu, and B. Matei, “Quantum collaborative
k-means,” in 2020 International Joint Conference on Neural Networks
(IJCNN).1em plus 0.5em minus 0.4emIEEE, 2020, pp. 1–7.

[16]
I. Kerenidis, J. Landman, A. Luongo, and A. Prakash, “q-means: A quantum
algorithm for unsupervised machine learning,” in Advances in Neural
Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer,
F. d'Alché-Buc, E. Fox, and R. Garnett, Eds.,
vol. 32.1em plus 0.5em minus 0.4emCurran Associates, Inc.,
2019. [Online]. Available:

[17]
C.-H. Nguyen, K.-W. Tseng, G. Maslennikov, H. Gan, and D. Matsukevich,
“Experimental swap test of infinite dimensional quantum states,”
arXiv preprint arXiv:2103.10219, 2021.

[18]
Qiskit, “Initialize.” [Online]. Available:

[19]
R. LaRose and B. Coyle, “Robust data encodings for quantum classifiers,”
Physical Review A, vol. 102, no. 3, p. 032420, 2020.

[20]
D. Kopczyk, “Quantum machine learning for data scientists,” arXiv
preprint arXiv:1804.10068, 2018.

[21]
E. Fredkin and T. Toffoli, “Conservative logic,” International Journal
of theoretical physics, vol. 21, no. 3, pp. 219–253, 1982.

[22]
A. Cross, “The ibm q experience and qiskit open-source quantum computing
software,” in APS March Meeting Abstracts, vol. 2018, 2018, pp.

[23]
R. Parekh, A. Ricciardi, A. Darwish, and S. DiAdamo, “Quantum algorithms and
simulation for parallel and distributed quantum computing,” arXiv
preprint arXiv:2106.06841v2, to appear in IEEE SC21 Proceedings, 2021.

[24]
Qiskit, “More circuit identities.” [Online]. Available:

[25]
M. E. Celebi, H. A. Kingravi, and P. A. Vela, “A comparative study of
efficient initialization methods for the k-means clustering algorithm,”
Expert systems with applications, vol. 40, no. 1, pp. 200–210, 2013.

[26]
R. Fioravanti, K. Kumar, S. Nakata, B. Chalamala, and Y. Preger,
“Predictive-maintenance practices: For operational safety of battery energy
storage systems,” IEEE Power and Energy Magazine, vol. 18, no. 6, pp.
86–97, 2020.

[27]
M. A. Mahmoud, N. R. Md Nasir, M. Gurunathan, P. Raj, and S. A. Mostafa, “The
current state of the art in research on predictive maintenance in smart grid
distribution network: Fault’s types, causes, and prediction methods—a
systematic review,” Energies, vol. 14, no. 16, p. 5078, 2021.

[28]
T. P. Carvalho, F. A. Soares, R. Vita, R. d. P. Francisco, J. P. Basto, and
S. G. Alcalá, “A systematic literature review of machine learning
methods applied to predictive maintenance,” Computers & Industrial
Engineering, vol. 137, p. 106024, 2019.

[29]
R. L. Thorndike, “Who belongs in the family?” Psychometrika, vol. 18,
no. 4, pp. 267–276, 1953.

[30]
L. Van der Maaten and G. Hinton, “Visualizing data using t-sne.”
Journal of machine learning research, vol. 9, no. 11, 2008.

[31]
A. Kuzmak, “Measuring distance between quantum states on a quantum computer,”
arXiv preprint arXiv:2103.05301, 2021.

[32]
M. Fanizza, M. Rosati, M. Skotiniotis, J. Calsamiglia, and V. Giovannetti,
“Beyond the swap test: optimal estimation of quantum state overlap,”
Physical review letters, vol. 124, no. 6, p. 060503, 2020.