QuAnt: Quantum Annealing with Learnt Couplings
Authors: Marcel Seelbach Benkner
Maximilian Krahn
Edith Tretschk
Zorah Lähner
Michael Moeller
Vladislav Golyanik
Venue: ICLR 2023 notable top 25% (2023)

Abstract: Modern quantum annealers can find high-quality solutions to combinatorial optimisation objectives given as quadratic unconstrained binary optimisation (QUBO) problems. Unfortunately, obtaining suitable QUBO forms in computer vision remains challenging and currently requires problem-specific analytical derivations. Moreover, such explicit formulations impose tangible constraints on solution encodings. In stark contrast to prior work, this paper proposes to learn QUBO forms from data through gradient backpropagation instead of deriving them. As a result, the solution encodings can be  chosen flexibly and compactly. Furthermore, our methodology is general and virtually independent of the specifics of the target problem type. We demonstrate the advantages of learnt  QUBOs on the diverse problem types of graph matching, 2D point cloud alignment and 3D rotation estimation. Our results are competitive with the previous quantum state of the art while requiring much fewer logical and physical qubits, enabling our method to scale to larger problems. The code and the new dataset are available at https://4dqv.mpi-inf.mpg.de/QuAnt/.

Published as a conference paper at ICLR 2023
QUANTUM ANNEALING WITH LEARNT COU- PLINGS
QUANT:
Marcel Seelbach Benkner Universität Siegen
Maximilian Krahn MPI for Informatics, SIC Aalto University
Edith Tretschk MPI for Informatics, SIC
Zorah Lähner & Michael Moeller Universität Siegen
Vladislav Golyanik MPI for Informatics, SIC
ABSTRACT
Modern quantum annealers can find high-quality solutions to combinatorial opti- misation objectives given quadratic unconstrained binary optimisation (QUBO) problems. Unfortunately, obtaining suitable QUBO forms in computer vision re- mains challenging and currently requires problem-specific analytical derivations. Moreover, such explicit formulations impose tangible constraints on solution en- codings. In stark contrast to prior work, this paper proposes to learn QUBO forms from data through gradient backpropagation instead of deriving them. As a re- sult, the solution encodings can be chosen flexibly and compactly. Furthermore, our methodology is general and virtually independent of the specifics of the tar- get problem type. We demonstrate the advantages of learnt QUBOs the di- verse problem types of graph matching, 2D point cloud aligmment and 3D ro- tation estimation. Our results are competitive with the previous quantum state of the art while requiring much fewer logical and physical qubits, enabling our method to scale larger problems. The code and the new dataset are available https://4dog mp - inf mpg. de de/QuAnt/
INTRODUCTION
Hybrid computer vision methods that can be executed partially on quantum computer (QC) are an emerging research area (Boyda et al. 2017 Cavallaro et al., 2020 Seelbach Benkner et al.) 2021 Yurtsever al. 2022). Compared to classical methods, they promise to solve computationally demanding (e.g., combinatorial) sub-problems faster, with improved scaling, and without relaxations that often lead to approximate solutions. Although quantum primacy has not yet been demonstrated in remotely practical usages of quantum computing, all existing quantum computer vision (QCV) methods fundamentally assume that it will be achieved in the future. Thus, solving these suitable algorithmic parts on QC has the potential reshape the field. However, reformulating them for execution on QC is often non-trivial.
QCV continues building up momentum, fuelled by accessible experimental quantum annealers (QA) allowing to solve practical (A'P-hard) optimisation problems. Existing QCV methods using QAs rely on analytically deriving QUBOs (both QUBO matrices and solution encodings) for a specific problem type, which is challenging, especially since solutions need to be encoded as binary vectors (Li & Ghosh 2020 Seelbach Benkner et al. 2020 202T Birdal et al., 2021). This often leads to larger encodings than necessary, severely impacting scalability. Alternatively, QUBO derivations with neural networks are conceivable but have not yet been scrutinised in the QA literature.
In stark contrast to the state of the art, this paper proposes, for the first time, to learn QUBO forms from data for any problem type using backpropagation (see Fig. []. Our framework captures, in the weights of neural network, the entire subset of QUBOs belonging to a problem type; a single forward pass yields the QUBO form for a given problem instance. It is thus a meta-learning approach in the context of hybrid classicm neural network training, in which the superordinate network instantiates the parameters of the QUBO form. We find that sampling instantiated QUBOs can be reasonable alternative to non-quantum neural baselines that regress the solution directly.

---

Published as a conference paper at ICLR 2023
Encode
Regress Couplings with MLP
Initialise Quantum Annealer
QUBO
Problem Instance
Set QUBO
Anneal
Solution
p
A
X
1.4
-..3
2.3
arg min x T Ax {0(0,1}
3.1
1.0
-1.2
Qubits
Qublts
Backpropagate & Update MLP
Classical Quantum
Compute Losses
Figure We propose QuAnt for QUBO learning, i.e. quantum-classicl meta-learning algorithm that avoids analytical QUBO derivations by learning to regress QUBOs to solve problems of a given type. We first represent problem instance the QUBO matrix A. We then initialise quantum annealer with A and quantum annealing find QUBO minimiser and extract as the solution
vector and then feed it into MLP that regresses the entries of
the problem instance. We define losses involving x" that avoid backpropagation through the annealing and backpropagate gradients through the MLP to train it. We demonstrate the generalisability of QuAnt on graph matching, point set registration, and rotation estimation.
In particular, we show how a (combinatorial) quantum annealing solver can be integrated into vanilla neural network as custom layer and be used in the forward and backward passes, which may be useful in other contexts. To that end, we introduce contrastive loss that circumvents the inherently discontinuous and non-differentiable nature QUBO solvers. Our method compatible with any QUBO solver at training and test time consider parallelised exhaustive search, sim- ulated annealing, and quantum annealing. QUBQ learning, i.e., determining a function returning QUBO forms given a problem instance of some problem type input, is non-trivial and challeng- ing task. In summary, this paper makes several technical contributions to enable QUBO learning:
1. QuAnt, Le., QAs for computer vision problems. While prior methods rely on analytical derivations, we learn QUBOs from data (Sec.3.1)
meta-learning approach to obtain QUBO forms executable modern
2. A new training strategy for neural methods with backpropagation involving finding low- energy solutions to instantaneous (optimised) QUBO forms, independent of the solver (Secs. 3.2 and 3.3).
3. Application the new framework to several problems with solutions encoded by permu- tations and discretised rigid transformations (Secs. 3.4 and 3.5).
We show that our methodology is a standardised way of obtaining QUBOs independent of the target problem type. This paper focuses on three problem types already tackled by QCV methods relying on analytical QUBO derivations: graph matching and point set alignment (with and without known prior point matches in the 3D and 2D cases, respectively). We emphasise that we do not claim to outperform existing specialised methods for these problem types that QA is particularly well- suited for them. Rather, we show that this wide variety of problems can be tackled successfully and competitively by our general quantum approach already now, before quantum primacy. Thus, in the future, computer vision methods may readily benefit from the (widely expected) speed-up QC through easy and flexible re- re-formulation of algorithmic parts QUBOs, thanks to proposed method. We run our experiments on D- Wave Advantage5.1 (Dattani et al. 2019), an experimental realisation of AQC with remote access. This paper assumes familiarity with the basics of quantum computing. For convenience, we summarise several relevant definitions in the Appendix.
RELATED WORK
The two main paradigms for quantum computing are gate-based QC and adiabatic quantum comput- ing (AQC). Our method uses quantum annealing, which is derived from AQC, and is not gate-based. The predominantly theoretical field of quantum machine learning (QML) investigates how quantum computations be integrated into machine learning (Biamonte et al. 2016 Dunjko & Briegel, Sim et al. 2019; Havličck et al.] [2019] [uu et al., [2000] Maniela & Simonetto
2018
al.
2021). Many QMI methods assume gate-based quantum computers and define quantum
2

---

Published as a conference paper at ICLR 2023
variational layer, i.e,, a sequence of parametrised unitary transformations meant for execution on quantum hardware (Mitarai et al. 2018). QML methods are often optimised using variants of the
backpropagation algorithm (McClean et al. 2018 Verdon et al., 2019 Beer et al.] 2020). Quantum
variational models were recently applied to combinatorial optimisation (Khairy et al. 2020) and
reinforcement learning (Dunjko al., 2016 Lockwood & Si 2020). Instead of learning to regress
unitary transformation parameters for gate-based QC, we learn to regress QUBO forms for QA.
In contrast to gate-based machines, QAs can already solve real problems formulated QUBOs
(Neukart et al. 2017 TTplukhin et al. 2019 Stollenwerk et al. 2019) Orus et al., 2019 Mato et al.)
2021| et al. ). Recently, QCV has rapidly transitioned from theoretical considerations Venegas-Annraca & Bose, 2003) Chin et al. 2020 Neven et al. 2008b ap to practical algorithms effects of quantum computers, ranging from image retrieval and processing (Venegas-Andraca & Bose, 2003; Yan et al. 2016), classification (Boyda et al. 2017;
leveraging quantum-
Nguyen & Kenyon| 2019:
| Cavallaro et al. 2020 Willsch et al. 2020 [ema et al. 20200 and track-
ing (Li & Ghosh| [0200] Zaech et al., 2022). to problems on graphs (Zick et al. 2015 Seelbach
Benkner et al., |020 Mariella & Simonetto (02T), consensus maximisation (Doan et al. 2022).
shape alignment Noormandipour & Wang (2021); Seelbach Benkner et al. (2021). segmentation
(Arrigoni et al. 2022) and ensuring coce--oonssteecyy (Birdal et al. [002] Yurtsever et al. (002)..
Many of these methods are evaluated on real quantum hardware, as both gate- base- and QA ma- chines can be accessed remotely (D-Wave Systems 2022] Rigetti Computing 2022).
We demonstrate the efficacy of our QuAnt approach on the applications of graph matching and point set alignment where we compare against recent quantum state-of-the methods /Seelbach Benkner al. (2020); Golyanik & Theobalt (2020), respectively.
Another line of work in different domains concerns learning the best adiabatic quantum algorithm. While some works (Pastorello et al., 2021 Pastorello & Blanzieri 2019) develop an algorithm in- spired by tabu search, our method uses a neural network to output a coupling matrix. Orthogomal to our work, others train neural networks to solve problem-specific QUBOs (Gabor et al. 2020). NūBlein et al. (2022) optimize a blackbox function by finding a QUBO as surrogate model. QML on gate-based based QC has been studied at length, but machine learning with QA remains largely under- explored, with only a few exceptions (e.g., linear regression (Date & Potok (021) and binary neural
networks (Sasdelli & Chin (02T)). In stark contrast to existing QCV methods with analytically
derived QUBOs (Li & Ghosh 2020, [Seelbach Benkner et al.) 2020 2021 Birdal et al. 2021). our approach enables more flexible and compact solution encodings.
QuAnt is also related to recent non-quantum approaches that aim to improve combinatorial optimi- sation by seamlessly integrating deep learning and combinatorial building blocks as custom layers and backpropagating through them (Ferber et al., 2020; Rolinek et al., 22200) Vlastelica et al.) 2020 In this respect, ours is the first work that uses a quantum QUBO solver in neural architectures.
QUBO LEARNING APPROACH
We present a new meta-learning approach for regressing quadratic unconstrained binary optimisation problems (QUBOs) suitable for modern quantum annealers (QA); see Fig. [ While existing works analytically derive QUBOs for different problems (Birdal et al. 2021 Seelbach Benkner et al. 2020
202T Zaech et al. 2022), we propose to instead learn a function that turns problem instance into a QUBO to be solved by a QA. Specifically, we train a multi-layer perceptron (MLP) that takes vectorised problem instance and regresses the QUBO weights such that the QUBO minimiser is the solution to the problem. Note that we only specify the bit encoding of the solution but let the network learn to derive QUBOs. Crucially, we show how training the MI. is possible despite quantum annealing (like any QUBO solver) being discontinuous and non-differentiable.
3.1 QUBOS AND QUANTUM ANNEALING
Quantum annealing is metaheuristic to solve -ard problems of the form arg (aiills((-1]]pp) s Js + bTs, where s is a binary vector, J E gaxn is a matrix of cou- plings, and b E RR contains biases (McGeoch) 2014). We can rewrite this as a QUBO: arg (i x_ Ax, by substituting [( 1, and A } +JJ++(J] [JI,, + J[ + diag(b).
3

---

Published as a conference paper at ICLR 2023
In quantum annealing, the binary n-dimensiional vector x describes the measurement outcomes of qubits. Annealing starts out with an equal superposition quantum state of the qubits that assigns an equal probability to all possible binary states {0, 1)". During the anneal, the couplings and biases of A are gradually imposed on the qubits. The adiabatic theorem (Born & Fock 1928) implies that doing so sufficiently slow forces the qubits into quantum state that assigns nonvanishing probability only to binary states that minimise the QUBO (Farhi et al., 2001). We then only need to measure the qubits to determine their binary state, which is our solution x. For a more detailed description of quantum annealing, we refer to prior computer- -iisinn works (Seelbach Benkner et al. 2020 2021 Golyanik & Theobalt 2020 Li & Ghosh 2020) and Appendix|A]
3.2 NETWORK ARCHITECTURE AND LOSSES
In this section, we describe the network architecture that takes as input problem instance and re- gresses a QUBO whose solution (e.g., obtained via quantum annealing) solves the problem instance. For a given problem type, we require problem description that is amenable to QUBO learning: A parametrisation of problem instances as real-valued vectors p E RT and a parametrisation of solutions as binary vectors x E {0, 1 Since we use supervised training, we additionally need training set D = (Pp. xa)) containing D problem instances Pa with ground-trume solutions Xy-
We use multilayer perceptron (MLP) with L layers and H hidden dimensions, ReLU activations (except for the last layer, which uses sin (Sitzmann et al. 2020)), and concatenating skip connections from the input into odd-numbered layers (except for the first and last layers). The input to the network is problem instance p. and the output is a QUBO matrix A: A = MLP(p).
We could now rectly. However, this requires specifying how A is to be derived for certain instance, which comes with two downsides:
dataset of problem instances and corresponding A to supervise the MLP di-
(1) A probsei-type-speccfie algorithm for analytically deriving instance- specific A needs to be designed to generate enough training data [(ps. Aa) which is non- trivial, and (2) The binary parametrisation (x) of the solution space depends on the algorithm, which can lead to more variables than intrinsically needed by the problem (c.g., if x needs to represent one of i numbers, one-hot parametrisation would have length n=k: while binary-encoding parametrisation would have length n= log k). This is particularly problematic as contemporary quantum hardware only provides a limited number of qubits. We thus choose to supervise A not directly and, instead, supervise the solutions of the QUBO. This strategy tackles both issues as it lets the network learn an algorithm compatible with the (potentially shorter) solution parametrisation. Therefore, our method is casily applicable to new problem types,
show in Secs. 3.4 and 3.5
The regressed A defines a QUBO, which can be solved by any QUBO solver. But how can we, dur- ing training, backpropagate gradients from the solution binary vector x through the QUBO solver despite these solvers having zero gradients almost everywhere (Vlastelica et al. 2020)? We cir- cumvent this issue by exploiting a contrastive loss (cf. [eCunn et al. (2006] Eq. (10))) follows: We know the energy of the ground-truth solution & of the problem instance, namely x A&. If the energy of the minimiser x (A) of the current QUBO is lower, then A does not yet describe a QUBO that outputs the right solution. We, therefore, seek to push the energy of x lower while pulling the energy of the minimiser x" up:
(1) which has a zero gradient if x- x x, as desired. Leep avoids backpropagation through x* and is even compatible with automatic differentiation. It yields the following update for entry of A, which can then be further backpropagated into the MLP via the chain rule:
Lgap = Ax",
=x,
OL A)
28,8, 2xxx] 2 0x 0x*(A)
Ax".
(2)
iAi.j
dA..i
where the last term comes from the dependency of x* on A via the QUBO solver. While intuitively useful, note that this term is zero "almost everywhere" (in the mathematical sense), and we hence ignore it as it provides almost no information. Note that this is common approximation (e.g., auto-differentiation frameworks backpropagate through max(-) pooling in the same manner).
Unfortunately, Lgap alone would not prevent degenerate A, which have multiple solutions, including undesirable ones. We, therefore, discourage such A that have more than one solution x":
Lunique
1x
AA x Axt
(3)
4

---

Published as a conference paper at ICLR 2023
where x* is the that minimises x" Ax over f0, 1)" fx*), ,, and |-] is the absolute value operator.
In addition to these data terms, we found it helpful to regularise the network by encouraging sparsity on all intermediate features of the MLP (Liu et al.) (0015):
Lmpp Σ
[f]]
(4)
FEFF
where the set of all network layer outputs (except for the last layer). The total loss then reads:
L = Lyap + Aunique Lunique + Ampp -mlp:
(5)
where we Ampp 10 and Xunique 10 regardless of problem type.
3.3 QUBOS ON D- WAVE QUANTUM ANNEALERS
We can use D)- Wave to solve any generated QUBO A, where Aij E IR describes the direction and coupling strength between logical qubits and j. However, each physical qubit in the annealer is only connected to a small subset of other physical qubits, which makes the regressed A not directly compatible with the annealer. We tackle this issue by manually pre-determining sparse connectiv- ity pattern of the physical qubits and then masking out the other entries of A before solving, such that the MLP focuses on only these sparse entries. For example, when E IR" with n=8, we can use D- D-Wave's Chimera architecture, which is made up of interconnected K4,4 unit cells (Dattani al. 2019p. (Ka,4 is complete bipartite graph with two sets of four qubits each.) Since n=8, we can fit problem instance into unit cell, which allows to anneal many problem instances in parallel by putting them in different unit cells. This speeds up training and saves expensive time on the quantum annealer. For larger problems with n=32, we can D-aa's's 's Pegasus architecture (Boothby et al. 2020), which has more interconnections (qubit couplings) between its K4,,a unit cells than Chimera. We use four such unit cells per problem instance, following D-Wave's pattern (Til). See Fig. 4b for an exemplary colour-coded qubit connectivity pattern of A.
Given our full method, next show how it can be applied to three problem types, i.e., graph matching, point set registration, and rotation estimation; see Appendix for further details.
3.4 GRAPHI MATCHINN
The goal of graph matching is to determine correspondences from 1e key points in two im- ages or graphs; see Fig. 2 for an example. This can be formalised as a quadratic assignment problem with permutation matrix representing the matching (Seelbach Benkner al.] 2020
arg x Wx, where P& is the set of permutation matrices, x vec(X) E {0, 1
the vectorised permutation matrix, and W E x contains pairwise weights. Unfortunately, the permutation constraint cannot be directly realised on the quantum annealer.
Instead, note that a permutation P: [k] -> [k] is fully de- Our method
fined by the sequence P(1), P(2)..... Plk).
efficient binary encoding for each entry of this sequence, using only l: log l binary variables in total. Note that not all vectors tations. As an optional post-processing step, we can per- form projection to the nearest permutation with respect to the Hamming distance in our binary encoding. Unless stated otherwise, we do not apply this post-processing.
{0, & are valid permu-
(a) Source
(b) Target
In addition to the solution parametrisation, we also need to design the problem description p. For real data, we use p vec(W), where the diagonal contains cosine similarities between the feature vectors extracted with AlexNet (Krizhevsky et al. 2012) pre-trained on Ima- geNet (Deng et al. (2009) of all key point pairs, and the off-diagonal follows the geometric term from Torresani et al. 2008 Eq. (6)). For evaluation,
Figure 2: Example matching on four key points from the Willow dataset (Cho et al. 2013). Corresponding points (same colours) are found based feature similarity.
also introduce the synthetic RandGraph
dataset; uses matrices of random distances D E R with entries Dr, E U(0, 1) to define
= Drj - DP().P)) The MLP thus learns to compress the input matrix into
much smaller QUBO.
5

---

Published as a conference paper at ICLR 2023
3.5 POINT SET REGISTRATION AND ROTATION ESTIMATION
In 2D point set registration, we are given two point sets with potentially different numbers of points and no correspondences, and we seek to find rotation angle that best aligns them. We follow Golyanik et al. (Golyanik & Theobalt (220) and use the vectorised form of their input matrix to represent a problem instance. We parametrise the solution space of x E {0, 1 by splitting the output space [0, |r] into 2 equally sized bins and consecutively indexing them with 9-bit integer.
In 3D rotation estimation, we are given two 3D point clouds with known matches and seek to esti- mate the 3D rotation aligning them. We represent a problem instance by the vectorised covariance matrix of the two point clouds; 3D rotation is parametrised by Euler angles a, 3, 7, We discretise each angle into 2 bins, such that x E {0, 1
EXPERIMENTAL EVALUATION
We next experimentally evaluate QuAnt. Our goal is to show that it outperforms the previous quan- tum state of the art. For reference, we also report comparisons against specialised classical methods.
Data. We evaluate graph matching on the Willow object dataset (Cho et al. 2013), which contains labelled key points. We use k=4 randomly chosen key point pairs per image. We use 5640 images for training, and test on 846 images. Both of the sets are obtained via pygmtools (ThinkLab) 2021]. We also evaluate on our synthetic dataset RandGraph (see Sec. (3.4, with both k=4 and k=5. We evaluate 2D point set registration on the 2D Shape Structure dataset (Carlier et al. 2016) providing 2D silhouette images of real-world objects. We treat the silhouette outlines as 2D points. We use 500 shapes from various classes for training. and test on 50 shapes. For each shape, we apply 1000 (for train) or 100 (for test) different rotations of up to 60% and pick random pairs to generate problem instances. For 3D rotation estimation, we evaluate on ModelNet10 (Wu et al. 2015). which contains CAD models of ten object categories. We proceed with point cloud representations of each shape. We use 300 shapes from various classes for training, and test on 30 shapes from various classes. For each shape, we apply 1000 different 3D rotations with angle ranges a E ", g
and B E | 18 n, 18 x] and pick random pairs to generate problem instances.
Comparisons. We compare QuAnt to two baselines and specialised methods. depending on the problem type. For all problem types, we demonstrate the power of using QUBOs compared to the Diag baseline that regresses a diagonal QUBO matrix A (which is trivially solvable). While this baseline ablates the QUBO itself, we also consider a more natural neural network baseline, i.e., Pure, that regresses the binary solution directly (there is activation after the last layer) and uses an lolloss between the output and & instead of Lgap and Lunique- At test time, we threshold the network output of Pure at to obtain binary vectors. For QuAnt, Diag and Pure variants, we experiment with all combinations of the numbers of layers L E {3, 5} and hidden dimensions H E {32, 78}.
We compare our graph matching results with the Direct baseline on Willow (Cho al., 2013); we directly solve the quadratic assignment problem given by W with exhaustive search, which provides an upper bound for our method. We also compare against Quantum Graph Matching (QGM) (Seel- bach Benkner et al. 2020), to which we pass our input matrices W. For 2D point set registration, we compare against the analytic quantum method (AQM) (Golyanik & Thcoball 2020), which an upper bound for our technique since we take its vectorised QUBO as input, and against the classical, specialised ICP algorithm (Lu Milios] 1997). For 3D rotation estimation, we use Procrustes as a classical specialised method, which is thus an upper bound for our (general) method.
Metrics. We measure accuracy of the graph matching solutions as the percentage of correctly recov- ered permutation matrices. For 2D point set registration and 3D rotation estimation, we quantify the difference between the known ground-truth rotations and the estimated rotations by their geodesic distances (angles) in the rotation groups S2) and SO(3), respectively.
QUBO Solvers. For graph matching, we follow Sec. 3.3 to make our regressed QUBOs compatible with the QA. Due to restricted QA compute budget, we train and test with simulated annealing unless stated otherwise. For the point cloud experiments, we regress dense and use our exhaustive search implementation at train and test time unless stated otherwise. When evaluating the QA, we rely on minor embeddings to make the regressed A compatible with the QA. Please refer to the A Appendix for the details.

---

Published as a conference paper at ICLR 2023
4.1 RESULTS
General Baselines. The quantitative results for graph matching, point set registration, and rotation estimation are reported in Tables and respectively, Across network sizes and all three problem types, the results show that having full, P'r-dard QUBO (ours) instead of only a diagonal QUBO (Diag) is advantageous. We also find that the proposed method yields better results than Pure on both point set registration and rotation estimation, although Pure yields better results for graph matching.
Table I: Comparison to general baselines on graph matching. We report the accuracy (in %).
(a) RandGraph for k=4.
(b) Willow object datasct (Cho al. 2013 for k=
Ours
Diag
Pure
Trained for 300 epochs with L=5, 1878
L.3, H
9
8
9T
L=3, H=
18
Ours 69
Diag
Pure
Direct
T,=5, H
11
11
89
53
90
97
L=5, H
49
43
96
Table Comparison to general baselines on point set registration. We report averages of the mean errors and their standard deviations over three runs.
Table 3: Comparison to general baselines on rotation estimation. We report averages of the mean errors and their standard deviations over three runs.
Ours
Diag
Pure
Ours
Diag
Pure
L-3, H
32
8.8008
11.1
1.3
1.2
1=3,4=33
5,9
3.0
5,4 1.0
7.9 + 0.5
1.3,
18
1.111
0.7
9.3 9.3
1,9
L 1-3,H-78
4.1 0.5
3,0 3.0
0.1
L-
11
0.6
10.9
1.2
9.3
1.5, H=32
377 0.8
5.0 0.4
16.2 7.1
1= H=78
688 0.3
7.7
0.5
41.3
L H-
34 0.4
4.7 0.2
10.1 = 1.8
Specialised Methods. For reference, we compare QuAnt to methods specialised to a certain prob- lem type. Since our approach is general, they mostly provide an upper bound for our performance.
We evaluate QGM (Seelbach Benkner et al., 2020) on several RandGraph instances. We confirm their finding that strongly enforcing permutation constraints eventually retrieves the right permu- tation as the sample with the lowest energy. However, using the analytical bound for the penalty term leads to a success probability (i.e,, the probability of getting the best solution across anneals) smaller than random guessing due to experimental errors in the couplings. Next, we find that the QUBOs of QuAnt are much smaller and better suited to be solved with quantum annealer than QGM's. For RandGraph with k=5, our method needs 15 physical qubits while their baseline and row-wise methods need 89 qubits average and a chain length of four, and their Inserted method needs, on average, 39 qubits and a chain length of three on D-Wave Advantage. Thus, our success probability of 26% when evaluating on test data is orders of magnitude higher than Inxerted's 0.22% (best in QGM). This shows how QuAnt improves over the quantum state of the art even though we merely focus on the solution with the lowest energy across anneals, while they focus on the success probabilities. We refer to Appendix D for a detailed evaluation. Table Tb confirms that Direct is an upper bound to our approach.
Table 8 shows quantitative results for 2D point set matching without noise. AQM slightly outperforms QuAnt, which is expected as we take AQM's QUBO as input; hence, its performance is an upper bound for our method. Fig. 3 shows qualitative example.
Regress Couplings with ML
QUBO Solution
Decoda QUBO Solution
Probiem Inateence
X
As expected, quantitative results in Table 7 (with no incorrect correspondences) show that classical, spe- cialised Procrustes performs better than our general method on 3D rotation estimation. Note that technique yields better results than Procrustes under test-time noise, discuss later in detail.
Figure 3: Test-time example inputs and outputs of QuAnt trained for 2D point set registration.
7

---

Published as a conference paper at ICLR 2023
4.2 ABLATION
For graph matching, we use RandGraph with k-4. We find that removing either uuique Lmp leads mixed results graph matching and worse results in almost all cases for points set registration and rotation estimation.
We ablate Lunique and Lmpp in Table (
Table Loss ablations. We report accuracy for graph matching (in and mean/median error otherwise.
Graph Matching w/o Lanp
Point Set Registration
Rotation Estimation
w/o Larige
Ours
w/n Lanipe
w/o LAmP
Ours
w/o Farine
w/o
Qurs
L-3, 32
7
9
17.8712.0
18.6/134
15.0 8.7
5.175.0
3,4/3.0
3,47 3.0
1.=3, H=18
30
29
15.5
21.8/170
14.5/
2.9/3.0
4.6/500
4.2/4.0
L=5, H-32
14
18.1/
19.0/7.7
4.0
3,4/3,0
2.5/2.0
2.3/2.0
11-111-77
46
54
49
18.3/
11.7
17.8/177
18.5
377/4,0
4.1/4.0
3.0/3.0
4.3 EVALUATION ON D- D-WAVE
By design, our QuAnt is agnostic to the type of QUBO solver used. After training with exhaustive search, we compare how the performance on the test set differs under exhaustive search, SA, or QA. The results in Fig. 4a show that the exact solutions of exhaustive search only slightly outperform the less computationally expensive QA and SA. Moreover SA yields results very similar to QA.
Insunesia in 1000
Epoch 0
Epoch 245
Epoch 450
ES
2
2
2
of RRsullt
QA
1
1
0.2
SA
2
6 810
14
0
2
4
6
8
810
14
0
0
4 6 810
14
0.1
2 3
9 10
Error degree
(a) Errors on rotation estimation.
(b) Evolution of result (top) and coupling matrix (bottom).
Figure 4: (a) Histogram of errors for rotation estimation using exhaustive search (ES), quantum annealing (QA), and simulated annealing (SA) at test time. The maximum eтrоr on the x-axis amounts to 59 and no methods have higher errors than shown. (b) Evolution over different epochs of the Hamming distance between predicted solutions and the ground truth (top), and coupling matrix when training our approach for graph matching (bottom). (Top)): The x-axis shows the Hamming distance. Blue indicates unprojected results, and red means after projection to permutation. We only project after training.
Next, we compare the test-time results of QA and SA (after training the method with the same technique, QA and SA, respectively). See Table 5 for the results, both with and without projecting the final binary solution to a valid permutation encoding during post- processing. Training with QA delivers better results than training with SA. We attribute this to a better second-best solution x+ used by Lumique- While SA yields solutions x" that are comparable QA, its second-best best solutions are worse than QA's. We refer to the appendix for details. Unfortunately, real-world compute resources for training with QA remain limited, as of this writing. We, therefore, fall back on SA for larger- scale experiments in this work. However, Table 3 suggests that our results could improve noticeably on QA.
Table 5: QuAnt (L=5, H=78) on RandGraph (k=5) trained for 450 epochs (QA or SA).
SA
QA
Before projection
10
After projection
24
36
4.4 FURTHER ANALYSIS
Training. Fig. 4b visualises how the instantaneous solution and A matrix evolve for graph matching.
Varying Problem Difficulty. We provide a more detailed analysis of the performance of our method on point set registration for varying difficulty levels. Table that larger input misalignment between the two point clouds worsens the results, as expected.
8

---

Published as a conference paper at ICLR 2023
Table 6: Interval analysis for point set registration with L=5, -878. We evaluate point cloud pairs with ground-truth angles uniformly sampled within the given intervals. We report the mean/median error in degrees.
angle interval
0- 1 -
1 2
2 3
3 4
4 5
5.4-- 6
mean median
4.0 1.9
5.1/2.6
6.0/
7.9
7.9/388
8.4/
Robustness to Noise. We investigate the robustness of our method and other approaches against input noise at test time after training without noisy data. We look rotation estimation, where we randomly pick fixed percentage of points and randomly permute their correspondences (among themselves). T contains results. The quality of QuAnt's re- sults barely degrades with increasing noise levels. even for 20% of incorrect correspondences. QuAnt already outperforms the classical Procrustes for even 1% of incorrect correspondences, even though Pro- crustes also starts from the same covariance matrix. We observe that the advantage of our method grows with larger noise levels. QuAnt also consistently performs better than the general baselines, which similarly robust increasing noise levels.
Table 7: Robustness to varying amounts of in- conrect test-time correspondences in rotation timation. We report mean/median error L=3, ==32. The first column specifies the percentage of incorrect correspondences at test time.
%
Ours
Procrustes
Diag
Pure
3.974.0
0.070.0
56/660
8.1 8.178.0
3.4/3.0
5.8/3.0
5.7/600
6.2/8.0
3,4/3.0
25.7/ 13.0
6.0/6.0
8.2 8.0
10
3.2/3.0
43.8/210
6.2/6.0
8.2 8.0
15
/,0
64.7/
6.2/6.0
8.2/ 8.0
20
3.7/
75.3/ 79.0
6.0
8.2/8.0
We next look at point set registration under input noise test time and after training without noise. Here, we add uniform noise to one point cloud, where the range of the noise is a percentage of the maximum extent of the point cloud. Table [ con- tains the results. ICP, an iterative approach, ro- bust to the noise, gives highly accurate results and, thus, outperforms the competing non-iterative ap- proaches. Since QuAnt takes as input the vectorised QUBO that AQM solves, AQM constitutes an upper bound for the performance of our approach. How- ever, QuAnt could, in principle, scale to 3D point set matching while AQM's solution parametrisation severely inhibits scaling to larger problems. Finally, QuAtt performs better than the general baselines.
Table 8: Robustness to varying amounts of uni- form noise in point set registration. We report mean/median error for L=5, H=78 and the ber of logical/physical qubits. The first column states the range of the noise in of the maximum extent of the point cloud. "f": uncoupled qubits.
%
Ours
Diag
Pure
AQM
5,8/3.5
7.3/4.7
6,8
4.3 2.6
5
6.4/3.3
7.0/5.2
7.0/6.1
4.5 / 2,9
3.5
8.4/522
7.166.5
5.6/
15
7.2/
9.5/5
7.9/6.7
5.6/
20
10.3/5.4
11.6/6.6
5 8.2
Qubits
9/14
(9/9))
n/a
21/~55
DISCUSSION
Limitations and Future Work. As all learning-basee based approaches, QuAnt can perform worse problem instances that fall significantly outside the training distribution. While our general method does not outperform classical methods specialised on certain problem types, achieve perfor- mance on par with hand-crafted QUBO designs used in state-of-the-art QCV methods. We achieve this while greatly reducing the effort required for new problem types. For our point cloud experi- ments, we rely on minor embeddings to transfer the regressed dense QUBOs to the QA. On existing hardware, large minor embeddings can worsen the resulting quality noticeably. However, we only need to embed a QUBO with nine logical qubits into 14 physical qubits. Although our focus is on a general design, our core idea of learning QUBOs can be specialised to any given problem type by designing more specific network architecture and losses that capture priors for the problem type.
We showed that learning to regress QUBO forms for different problems instead of de- riving them analytically can be a reasonable alternative to existing methods. We showed the gener- ality of QuAnt on diverse problem types. Our experiments demonstrated that learning QUBO forms and solving them either on quantum annealer or with simulated annealing, in most cases, leads to better results than directly regressing solutions. Moreover, QuAnt significantly outperformed the previous quantum state of the art in graph matching and rotation estimation in the setting with noise. We believe our work considerably broadens the available toolbox for development and analysis of quantum computer vision methods and opens up numerous avenues for future research.
Conclusion.

---

Published as a conference paper at ICLR 2023
REFERENCES
Source code for
hoom:/pooeettsssyteemlell en/ stt.sstaa st www.e/ htt.a//eeee/aaeeeeeettee//////oa
html, Accessed: 2022-02-09.
Tameem Albash and Daniel A Lidar. Adiabatic quantum computation. Reviews of Modern Physics, 90(1):01500,, 2018.
Federica Arrigoni, Willi Menapace, Marcel Seelbach Benkner, Elisa Ricci, and Vladislav Golyanik. Quantum motion segmentation. In European Conference Computer Vision (ECCV), 2022.
Kerstin Beer, Dmytro Bondarenko, Terry Farrelly, Tobias J. Osborne, Robert Salzmann, Daniel Scheiermann, and Ramona Wolf. Training deep quantum neural networks. Nature Communica- tions, (808), 2020.
Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning. Nature, 549, 11 2016.
Tolga Birdal, Vladislav Golyanik, Christian Theobalt, and Leonidas Guibas. Quantum permutation synchronization. In Computer Vision and Pattern Recognition (CVPR), 2021.
Kelly Boothby, Paul Bunyk, Jack Raymond, and Aidan Roy. Next-Generation Topology of D-wave Quantum Processors. arXiv e-prints, 2020.
Max Born and Vladimir Fock. Beweis des adiabatensatzes. Zeitschrift für Physik, 51(3):165-180, 1928.
Edward Boyda, Saikat Basu, Sangram Ganguly, Andrew Michaelis, Supratik Mukhopadhyay, and Ramakrishna R. Nemani. Deploying quantum annealing processor to detect tree cover in acrial imagery of california. PLoS ONE, 12, 2017.
Jun Cai, William G. Macready, and Aidan Roy. A practical heuristic for finding graph minors. arXiv e-prints, 2014.
Axel Carlier, Kathryn Leonard, Stefanie Hahmann, Geraldine Morin, and Misha Collins. The 2d shape structure dataset: user annotated open access database. Computers & Graphics, 58: 23-30, 2016.
Gabriele Cavallaro, Dennis Willsch, Madita Willsch, Kristel Michielsen, and Morris Riedel. Ap- proaching remote sensing image classification with ensembles of support vector machines on the d-wave quantum annealer. In IEEE International Geoscience and Remote Sensing Symposium (IGARSS), 2020.
Tat-Jun Chin, David Suter, Shin-Fang Ch'ng, and James Quach. Quantum robust fitting. In Pro- ceedings of the Asian Conference on Computer Vision (ACCV), November 2020.
Minsu Cho, Karteek Alahari, and Jean Ponce. Learning graphs match. In International Confer- ence on Computer Vision, pp. 25-32, 2013.
D- DaWe Systems. Leap. https: /obo:://c0 /ww... hww.aeayss.co/booo//aattt////aaa 2022. online; accessed on the 24.01.2022.
D. Wave Systems, Inc. D-wave system documentation. https://bos..daaeeys..oo
html online; accessed 2022-03-06.
D- Wave Systems, Inc. dimod simulated annealing sampler.
https://
test- pest-pprojetttemllatee samplers htm 2022a. online.
D- D-ve Systems, Inc. http://wwww....aaa//////////ttta 2022b. online.
D- Wave Systems, Inc D-wave ocean. stablel 2022c. online.
kttps:/Bcc..cean..wvveeee cowp////essscccc......oo
10

---

Published as a conference paper at ICLR 2023
Prasanna Date and Thomas Potok. Adiabatic quantum linear regression. Scientific Reports, 11, 2021.
Nike Dattani, Szilard Szalay, and Nick Chancellor. Pegasus: The second connectivity graph for large-scale quantum annealing hardware. arXiv e-prints, 2019.
Dema, Junya ARAI, and Keitarou HORIKAWA. Support vector machine for multiclass classifi-
cation using quantum annealers. 2020.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In Computer Vision and Pattern Recognition, pp. 248-255. IEEE, 2009.
Anh-Dzung Doan, Michele Sasdelli, David Suter, and Tat-Jun Chin. hybrid quantum- algorithm for robust fitting. In Computer Vision and Pattern Recognition (CVPR), 2022.
Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, and Dacheng Tao. Expressive power of parametrized quantum circuits. Phys. Rev. Research, 2:033125, 2020.
Vedran Dunjko and Hans J Briegel. Machine learning artificial intelligence in the quantum do- main: review of recent progress. Reports on Progress in Physics, 81(7):074001, 2018.
Vedran Dunjko, Jacob Taylor, and Hans J. Briegel. Quantum-enhanced machine learning. Phys. Rev. Lett., 117:130501, 2016.
Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda. quantum adiabatic evolution algorithm applied to random instances of an no-complete problem. Science, 292(5516):472 475, 2001.
Aaron Ferber, Bryan Wilder, Bistra Dilkina, and Milind Tambe. Mipaal: Mixed integer program as layer. AAAI Conference on Artificial Intelligence, 34:1504-151, 2020.
Thomas Gabor, Sebastian Feld, Hila Safi, Thomy Phan, and Claudia Linnhoff-Popien. Insights on training neural networks for qubo tasks. In Proceedings of the IEEF/ACM 42nd International Conference Software Engineering Workshops, pp. 436-441, 2020.
Frank Gaitan and Lane Clark. Graph isomorphism and adiabatic quantum computing. Phys. Rev. A. 89:022342, Feb 2014. doi: 10.1 htt.//hyysee....00222333.. URL httpp::///iitt aps. / 11 1013/10.103/Phyyseet
89. 022342
Vladislav Golyanik and Christian Theobalt. A quantum computational approach to correspondence problems on point sets. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9182-9191 2020.
Vojtéch Havlíček, Antonio D. Córcoles, Kristan Temme, Aram W. Harrow, Abhinav Kandala, Jerry M. Chow, and Jay M. Gambetta. Supervised learning with quantum-enhanced feature spaces. Nature, 567:209-212, 2019.
Sami Khairy, Ruslan Shaydulin, Lukasz Cincio, Yuri Alexeev, and Prasanna Balaprakash. Learning to optimize variational quantum eircuits to solve combinatorial problems. In AAAI Conference on Artificial Intelligence, 2020.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization, arXiv preprint 1rXiv:1412.69888 2014.
Alex Krizhevsky, llya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 25, 2012.
Jonas M. Kübler, Simon Buchholz, and Bernhard Schölkopf. The inductive bias of quantum kernels. In Neural Information Processing Systems (NIPS), 2021.
Yann LeCun, Sumit Chopra, Raia Hadsell, Fu Jie Huang, and et al. A tutorial on energy-based learning. In Predicting Structured Data. MIT Press, 2006.
11

---

Published as a conference paper at ICLR 2023
Junde Li and Swaroop Ghosh. Quantum-soft qubo suppression for accurate object detection. In European Conference on Computer Vision (ECCV), 2020.
Baoyuan Liu, Min Wang, Hassan Foroosh, Marshall Tappen, and Marianna Pensky. Sparse convo- lutional neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 406-814, 2015.
Owen Lockwood and Mei Si. Reinforcement learning with quantum variational circuit. AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), 16:245-251,
2020.
Feng Lu and Evangelos Milios. Robot pose estimation in unknown environments by matching 2d range seans. Journal of Intelligent and Robotic systems, 18(3):249-275, 1997.
Nicola Mariella and Andrea Simonetto. A Quantum Algorithm for the Sub-Graph Isomorphism Problem. arXiv e-prints, 2021.
Kevin Mato, Riccardo Mengoni, Daniele Ottaviani, and Gianluca Palermo. Quantum molecular unfolding. arXiv e-prints, 2021.
Jarrod R. McClean, Sergio Boixo, Vadim N. Smelyanskiy, Ryan Babbush, and Hartmut Neven. Bar- ren plateaus quantum neural network training landscapes. Nature Communications, 9(4812), 2018.
Catherine C. McGeoch. Adiabatic quantum computation and quantum anncaling: Theory and prac- tice. Synthesis Lectures Quantum Computing, 5(2):1-93, 2014.
K. Mitarai, M. Negoro, M. Kitagawa, and K. Fujii. Quantum circuit learning. Phys. Rev. A, 98: 032309, 2018.
Florian Neukart, Gabriele Compostella, Christian Seidel, David von Dollen, Sheir Yarkoni, and Bob Parney. Traffic flow optimization using a quantum annealer. Frontiers in ICT, 4, 2017.
Hartmut Neven, Vasil Denchev, Geordie Rose, and William Macready. Training binary classifier with the quantum adiabatic algorithm. arXiv e-prints, 2008a.
Hartmut Neven, Geordie Rose, and William G. Macready. Image recognition with an adiabatic quantum computer i. mapping to quadratic unconstrained binary optimization. arXiv e-prints, 2008b.
Nga T. T. Nguyen and Garrett T. Kenyon. Image classification using quantum inference on the d-wave 2x. arXiv e-prints, 2019.
Mohammadreza Noormandipour and Hanchen Wang. Matching point sets with quantum circuit learning. arXiv e-prints, 2102.06697, 2021.
Jonas Nüßlein, Christoph Roch, Thomas Gabor, Claudia Linnhoff- Maanofff-Popien and Sebastian Feld. Black box optimization using qubo and the cross entropy method. arXiv preprint arXiv:2206. 0e.22200..2100.. 2022.
T. P. Orlando, J. E. Mooij, Lin Tian, Caspar H. van der Wal, L. S. Levitov, Seth Lloyd, and J. J. Mazo. Superconducting persistent-curren qubit. Phys. Rev. B, 60:15398-15544 15413, Dec 1999.
Roman Orus, Samuel Mugel, and Enrique Lizaso. Forecasting financial crashes with quantum com- puting. Physical Review A, 99, 06 2019.
Davide Pastorello and Enrico Blanzieri. Quantum annealing learning search for solving qubo prob- lems. Quantum Information Processing, 18(10):1-17, 2019.
Davide Pastorello, Enrico Blanzieri, and Valter Cavecchia. Learning adiabatic quantum algorithms optimization problems. Quantum Machine Intelligence, 3(1):1-19, 2021.
12

---

Published as a conference paper at ICLR 2023
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024 8035. Curran Associates, Inc., 2019.
Rigetti Computing. Rigetti quantum cloud services. 2022. online; accessed the 24.01.2022
https://dbcs.rigge
qcs/
Michal Rolínek, Paul Swoboda, Dominik Zietlow, Anselm Paulus, Vít Musil, and Georg Martius. Deep graph matching via blackbox differentiation of combinatorial solvers, In European Confer- ence on Computer Vision (ECCV), pp. 407-424, 2020.
Michele Sasdelli and Tat-Jun Chin. Quantum annealing formulation for binary neural networks.
arXiv preprint arXiv:2107.0227 22200.7.571, 2021.
Marcel Seelbach Benkner, Vladislav Golyanik, Christian Theobalt, and Michael Moeller. Adiabatic quantum graph matching with permutation matrix constraints. In International Conference on 3D Vision (3DV), 2020.
Marcel Seelbach Benkner, Zorah Lähner, Vladislav Golyanik, Christof Wunderlich, Christian Theobalt, and Michael Moeller. Q-match: Iterative shape matching via quantum annealing. In International Conference Computer Vision (ICCV), 2021.
Sukin Sim, Peter D. Johnson, and Alán Aspuru-Guzik. Expressibility and entangling capability of parameterized quantum eircuits for hybrid quantum-classical algorithms. Advanced Quantum Technologies, 2(12):1900070, 2019.
Vincent Sitzmann, Julien N.P. Martel, Alexander W. Bergman, David B. Lindell, and Gordon Wet- zstein. Implicit neural representations with periodic activation functions. In Proc. NeurIPS, 2020.
Stefano Speziali, Federico Bianchi, Andrea Marini, Lorenzo Menculini, Massimiliano Proietti, Loris Francesco Termite, Alberto Garinei, Marcello Marconi, and Andrea Delogu. Solving sen- sor placement problems in real water distribution networks using adiabatic quantum computation. Quantum Computing and Engineering (QCE), 2021.
Tobias Stollenwerk, Elisabeth Lobe, and Martin Jung. Flight gate assignment with a quantum an- nealer. In Quantum Technology and Optimization Problems, 2019.
Alexander Teplukhin, Brian K. Kendrick, and Dmitri Babikov. Calculation of molecular vibrational spectra on quantum annealer. Journal of chemical theory and computation, 2019.
ThinkLab, pygmtools. Shanghai Jiao Tong University. Github, 2021. URL httph:tt///// //
com/ Thinklar GUTU/pygmtools
Lorenzo Torresani, Vladimir Kolmogorov, and Carsten Rother. Feature correspondence via graph matching: Models and global optimization. In European conference computer vision, pp. 596-609. Springer, 2008
Salvador E. Venegas- Andraca and Sougato Bose, Storing, processing, and retrieving an image using quantum mechanics. In Quantum Information and Computation, volume 5105, pp. 137 147, 2003.
Guillaume Verdon, Jason Pye, and Michael Broughton. A universal training algorithm for quantum deep learning. In APS March Meeting Abstracts, 2019.
Marin Vlastelica, Anselm Paulus, Vít Musil, Georg Martius, and Michal Rolínek. Differentiation of blackbox combinatorial solvers. In International Conference Learning Representations (ICLR), 2020.
D. Willsch, M. Willsch, H. De Raedt, and K. Michielsen. Support vector machines on the d-wave quantum annealer. Computer Physics Communications, 248: 107006, 2020. ISSN 0010-4655, doi: https///bb..rr//1..000......p 107000. URL https: www. www.eeedireet......m com/
13

---

Published as a conference paper at ICLR 2023
Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao. 3d shapenets: A deep representation for volumetric shapes. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1912-1920, 2015.
Fei Yan, Abdullah liyasu,, and Salvador Genegas-Andratt survey of quantum image representa- tions. Quantum Information Processing. 15, 2016.
Alp Yurtsever, Tolga Birdal, and Vladislav Golyanik. Q-fw: A hybrid classical-quantum frank-wolfe for quadratic binary optimization. In European Conference on Computer Vision (ECCV), 2022.
Jan-Nico Zaech, Alexander Liniger, Martin Danelljan, Dengxin Dai, and Luc Van Gool. Adiabatic Quantum Computing for Multi Object Tracking. In Computer Vision and Pattern Recognition (CVPR), 2022.
Kenneth M. Zick, Omar Shehab, and Matthew French. Experimental quantum annealing: case study involving the graph isomorphism problem. Scientific reports, 5(1), 2015.
APPENDIX
This appendix provides more details on adiabatic quantum computing in Sec. We provide training and implementation settings in Sec. B
Further details the problem description for graph match-
Sec. D contains deeper comparison with QGM (Seelbach) Benkner al. 2020) and Sec. [ compares SA and QA. In Sec. [ we provide further quantitative and qualitative results on rotation estimation. Finally, Sec. G contains more details and experiments
ing and a failure case are Sec.
C
on point set registration.
A QUANTUM COMPUTING BACKGROUND
A.1 QUANTUM ANNEALING IN DETAIL
As we have seen, quantum annealing is metahcuristic to solve the N'P-hard Ising problem:
arg min S Js + bTs.
(6)
=E(-1,1}
where is binary vector, J E R is matrix of couplings, and b E R" contains biases (McGeoch] 2014). Here, we give brief overview of how this fits in the framework of quantum mechanics. D-Wave quantum annealers rely on magnetic fluxes in superconducting Niobium loops (Olladdo et al. 1999). The direction of the current flowing through them can be modelled as a qubit, f.e., as wioddmmesionnal, complex, normalised vector (v) C² in the Dirac notation. In the so-called computational basis, the basis vectors correspond to the current flowing clockwise or anti-clockwise. After measuring the state, the system will collapse either basis state. The absolute value of the complex-valuee coefficients of the linear combination (probability amplitudes) is the probability of each outcome after measurement (e.g., clockwise anti-clockwise current). The state
space of n E N qubits can be expressed with the tensor product
x C² and is thus a 2" ddmeeniiona
:=1
complex vector space. We need that many parameters because entangled states cannot be described separately. If the two states (wb) (o) corresponding to different physical systems (e.g., two niobium loops or two atoms) can deseribed independent from each other, the whole system is described by (v)) & (o). Note that if every state could be decomposed this way, one would only need 2n parameters.
The evolution of a quantum state (tb) over time can be described with the time-dependent Schrödinger equation:
i 1 = in a
H (
(16
where the Hamilton operator H is a Hermitian Matrix describing the possible energies of the system, i the imaginary unit, h is a constant, and t denotes time. For adiabatic quantum computing, one needs problem Hamiltonian Hp, where the eigenvector corresponding the lowest eigenvalue is
14

---

Published as a conference paper at ICLR 2023
solution to the particular Ising problem, and an initial Hamiltonian H with easy-to to-prepare ground state. The Adiabatic Theorem (Born Fock 1928) states that we start with the ground state of H, and take sufficiently long time gradually change from H to H p, e.g., with:
(1)) = (1- (1 HPp
(8)
then we end up in the ground state of Hp. From the latter, we can deduce the solution of the par- ticular Ising problem. Simulating this whole process classically can be difficult (or even intractable) because dealing with 2n 2" matrices H and Hp, where is the number of qubits. How difficult the classical simulation is, depends on the exact form of the Hamiltonians. (Particularly promising for speed-ups are, e.g., so-called non-stoquastic Hamiltonians (Albash & Lidar 2018)
A.2 LOGICAL AND PHYSICAL QUBITS
The QUBO defines the couplings between logical qubits i and Such QUBO can contain couplings between any two qubits. However, in contemporary hardware realisations, each physical qubit is only connected to few others (see Fig. Salad 55). In the main paper, we show how the QUBO matrix A can account for this sparse connectivity pattern by setting entries between logical qubits and j to if the physical qubits and j have no connection. Still, D-Wave supports denser connectivity patterns than what is implied by the hardware: Multiple physical qubits can be chained together to represent a single logical qubit of x that has many connections. The physical qubits in the chain will then have strong couplings along the chain to encourage them to all end up in the same final state (either all or all 1), representing the final state of the corresponding logical qubit. This is formalised connectivity graph of the physical qubits. Using the heuristic method of Cai and colleagues (Cai al. 2014) is popular determine the minor embeddings in practice.
minor embedding (of the connectivity graph of the logical qubits) into the
(a) Chimera
(b) Pegasus
Figure 5: Visualisation of qubit connectivitics. (a) The connectivity pattern of the physical qubits the Chimera architecture. The unit cells (green boxes) have fewer interconnections than on Pegasus. (b) The connectivity pattern of the physical qubits in the Pegasus architecture. Green, red, and yellow correspond to one problem instance each. Images due D-Wave (D-Wave Systems, Inc.).
B IMPLEMENTATION DETAILS
Our code, which we will release, is implemented in Pytorch (Paszke et al.) 2019). We use Adam (Kingma Bal 2014) with a learning rate of 10-3 for training. For graph matching on RandGraph with 4-4, we use batch size of 141 and train for 150 epochs, which takes about seven hours. For RandGraph k=5,, we use 450 epochs, which takes about 23 hours. For Willow, we train for 300 epochs, which takes about 14 hours. The baselines epochs. While Diag takes a comparable amount of time, the Pure baseline takes about three minutes to train. For the experiments with k=5, 10-5 the learning rate.
trained for the same number of
15

---

Published as a conference paper at ICLR 2023
For the point cloud experiments, about four hours. We train Pure and Diag with the same batch sizes and epochs. The training of the Diag baseline takes four hours well, and Pure is trained within three hours. When solving
batch size of 32 and train for 20 epochs, which takes
a QUBO on a QA, we anneal 100 times and pick the lowest-energy solution. We access the QA
via Leap (D-Wave Systems 2022) using the Ocean SDK (D-Wave Systems, Inc. 2022c). When solving with SA, we use 100 iterations from the default neal SA sampler.
C GRAPH MATCHING
C.I PROBLEM DESCRIPTION
Here, we describe the design of the problem description p for graph matching. We use p vee W), where the diagonal of W contains cosine similarities between the feature vectors extracted with AlexNet (Krizhevsky et al., 2012) pre-trained on ImageNet (Deng et al., 2009) of all pairs key points. The off diagonaa follows the geometric term described in (Eq. (7)) from Torresani et al. (Tor- resani et al. 2008). In particular, we use the term W goom from Eq. (7) from Torresani et al. (Toresami al. 2008) with minus signs in the beginning and in the exponential, and set 1z=0.98. The convex combination with W Alex, where the cosine similarities of the feature vectors are on the diagonal, is then:
W = WTTWAA + (1 T) W goom-
(9)
We choose 0-0.81 and 07.9. such that the QAP often coincides with the ground-truth correspon- dences (see Tab "Direct" from the main paper).
C.2 FAILURE CASE
We show a failure case of our method when applied to graph matching in Fig. 6 It occurs due to large differences in the observed appearance.
(a) Source
(b) Matching
Figure 6: Failure case for graph matching. We visualise the ground truth of an image pair. Here, our method does not find the correct matching: Only the beak and neck are matched correctly, while the geometric infor- mation for the other key points differs too strongly.
D DETAILED COMPARISON WITH QGM (SEELAAH BENKNER ET AL. 2020
Here, we compare our method with QGM (Seelbach Benkner et al. 2020 in detail. Note that the focus of both works differs. Their work focuses more on the probability distribution of the retrieved solutions. Our work is more concerned with incorporating the quantum annealer into the training pipeline. When training the neural network, Lgap equation [ uses the retrieved solution with the smallest energy across anneals, while they are also interested in the success probabilities, i.e. the probability to get the best solution across anneals.
The individual QUBOs occurring in QuAnt framework are much easier to solve by the QA than QUBOs that would arise in QGM (Seelbach Benkner et al.) 2020). To show this, we compute the average success probabilities of the various methods from QGM (Seelbach Benkner al. 2020
16

---

Published as a conference paper at ICLR 2023
Table 9: Average success probabilities of different QGM variants (Seelbach Benkner al. 2020
141
problem instances RandGraph compared to QuAnt with 5. in %..
Inserted 0.22
Baseline
Row-wise
Ours
0.07
0.07
26
We also apply QuAnt to these problem instances. We solve the resulting QUBO with QA and find the average probability to 26% with standard deviation of 18%, better than any method from the QGM paper (Seelbach Benkner al, 2020).
over 141 instances of RandGraph with k=5; see Table 9
This difference is not surprising since we construct our method such that we only use trivial em- beddings and do not need to apply the minorma moinerrrrr heuristic (Cai et al.] 2014). Because that, for RandGraph with k 5, our method needs only 15 physical qubits while their baseline and row-wise methods need 89 qubits, on average, and a chain length of 4; their Inserted method needs, on average, 39 qubits and chain length of 3 D-Wave Advantage. Note that heuristic search for better penalty parameters, as in Q-Syne (Birdal et al. 2021). could give rise to better results for the methods from QGM (Seelbach Benkner et al. 2020 in Table [ However, the corresponding embeddings would still be problematic. Directly using the binary encoding for permutations (Gaitan Clark 2014) requires additional qubits because the problem would a priori not be quadratic.
E SOLUTION QUALITY OF SA AND QA
In the main paper, we show that training with QA yields better performance than training with SA. Here, we analyse the quality of the solutions found by both techniques further. Fig. 7 contains histograms that depict the output of the quantum annealer and the two different simulated anneal- ing solvers from neal WD-Wave Systems, Inc. (022b) and from dimod (D- Da-e Systems, Inc. 2022a). In contrast to the solver from dimod, neal highly optimised for performance, so we used it for our experiments.
We focus our analysis on the number sweeps SA, i.e., the number of steps in the "cooling' schedule. We observe that it strongly influences the quality of the second-best solution.
occurrences (x 100)
10
10
10
10
5
0
0.5 0 Energy
0.5
-1
-Q.5 O Energy
0.5
-1
-0.5 Energy
0.5
0.5 Energy
0.5
0.5
0.5
Energy
(a) SA, 10 sweeps (b) SA, 10 sweeps
(c) SA, sweeps
(d) D Dimod
(e) QA
Figure 7: Energy histograms of (idcally optimal) 10 samples for SA (different number of sweeps and dimod) and QA on one instance of RandGraph with k=5 after 150 epochs training.
Table 10 illustrates this by averaging fraction of the second-best energies over 141 instances and analysing 1000 samples from different solvers. We see that the quantum annealer produces the second-be best samples with the lowest energies.
Note, however, that do not claim that this is intrinsic general advantage of QA over SA, but merely that in our setting, QA outperforms SA. Still, prior work (Willsch et al.) (020)) also reaches the conclusion that quantum annealing has much potential for finding reasonable near-optimal solu- tions.
The dimod sampler also produces second-best solutions with low energies but is computationally expensive (D-Wave Systems, Inc. 2002a).. This is, perhaps, because many non-optimal solutions produced compared to the implementation from neal.
17

---

Published as a conference paper at ICLR 2023
Table 10: Second-best energies of SA relative (in %) to the second-best energies of QA. We report the mean and std. deviation over 141 instances. The higher the better.
SA (neal), 10 sweeps
SA (neal), 10 sweeps
SA (dimod)
94.2 10.3
86.0 19
99.8 0.9
3D ROTATION ESTIMATION
F.1 THREE STAGES (EULER ANGLES)
We obtain improved results when regressing three Euler angles one after another compared to direct regression of three angles. Thus, we use one stage per angle, i.e. with one network per stage. The training setup is as follows. We feed the first network with problem instances where a, 9, 7 + O. The network then regresses a. We feed the second stage network with problem instances, where 0 and B.Y # O. Subsequently, the network regresses B. Lastly, feed the third network with problem instances, where a, B = 0 and y * 0. Here it regresses v. During test time, the first network determines which is then applied to the input. The updated input is re-encoded before the second stage, which outputs B. Finally, with a and / applied already, the third stage regresses y. Fig. shows how the three different networks regress the angles and how the solution progresses towards the final one.
(a) Initial prohlem instance
(b) Application of the a rotation
(c) Application of the ar B rotations
(d) Application of the B, rotations
Figure Visualisation the different steps our cotation-estimatin network. show (blue) the original 3D point cloud and (red) the rotated point cloud. The green points are points of the red point cloud with unknown correspondences. Here, 10% of the correspondences are unknown.
F.2 VARIANCE ACROSS RUNS
To better judge the stability under different ran- dom seeds, we repeat the main experiment from the paper three times for our QuAnt method and each baseline. In Table 11 we report the mean and std. deviation of the median. Here, similar to the results from the main paper, we outper- form the Diag and Pure baselines in all but one setting.
Table 11: Comparison to general baselines on rotation estimation. We report the of the per-experiment median and std. deviation across experiments for three different random seeds.
Ours
Diag
Pure
L-3, H-
6,0 3.6
5.3
7.0 1.0
L-3, H1788
4.0 + 1.0
5.0 + 0.0
7.0 4 0.0
5 H-
3.7 + 1.2
5.0 0.0
16.3 = 7.2
5, H-78
3.7
3.7000 0.6
5.0 0.0
9.0 1.0
F.3 TRAINING ON NOISY DATA
Table shows how our method performs on free and noisy test data after training on noisy data. We observe that the noisy training data appears negatively affect the training and its performance drops, while Diag improves and Pure remains unchanged.
F.4 QUALITATIVE COMPARISON ON NOISY TEST DATA
Fig. g visualises differences between our solution after training on noise-free data and Procrustes alignment problem with noisy data (unknown correspondences).
18

---

Published as a conference paper at ICLR 2023
Table 12: Robustness varying amounts of incorrect test-time correspondences in rotation estimation. We report the mean'median error L=3, =2. The first column specifies the percentage of incorrect corre- spondences at test time.
(a) Training without noise
(b) Training with 10% incorrect correspondences
%
Ours
Procrustes
Diag
Pure
%
Ours
Procrustes
Diag
Pure
4,9740
0.0
5.676.0
8.1/8.0
4.474.0
0.0/0.0
4.675.0
8.178.0
3.4/3.0
5.8/3.0
5.7/6.0
8.2/8.0
4.3/4.0
5.8/3.0
5.1/5.0
8.0
5
3.4 3.0
23.7/13.0
6.0/6.0
8.2/8.0
5.0/5.0
25.7/
5.1/5.0
8.2
10
3,2/3.0
43.8/21.0
6.2/6.0
8.2/8.0
10
5.2/5.0
21.8/21.0
5.2/5.0
8.2/8.0
15
3.0
64.7/58.0
6.2/6.0
8.2/8.0
15
5.2/5.0
58.7/58.0
5.0/5.0
8.2/8.0
3.7/3.0
79.0
5.8
8.2/8.0
5.6/6.0 20
75.3 79.0
4.9
8.2/8.0
(a) Initial problem setting
(b) Our solution
(c) Solution by Procrustes
Figure 9: Comparison of initial input rotation, method and Procrustes. The initial 3D point cloud blue and rotated one red, where the unknown correspondences are displayed in green. Here, 10% correspondences are unknown.
F.5 COMPARISON TO AQM (GOLYANIK & THEOBALT
2020
QuAnt can estimate 3D rotations with known point matches. However, AQM (Golyanik & Theobalt, 2020) would require 81 densely connected logical qubits, which not supported by the current guantum-hardwarr generations. Hence, we cannot compare against AQM for this problem setting and instead only compare classical methods such as Procrustes.
G 2D POINT SET REGISTRATION
G.1 SETTING DETAILS
We encode the point set registration instances similar to Golyanik et al. (Golyanik & Theobali, 2020). As the correspondences between the template and the reference point set registration are not known, we use k-nearest neighbours to find possible correspondences. Our network is trained with three nearest neighbours per each template point.
G.2 VARIANCE
In Table 13 we report the mean median. Here, we outperform the baselines in all cases. In nearly all setups, we outperform the baselines, and only for one case, we are par with the Pure baseline. Still, even that case, QuAnt performs more consistently, evidenced by its lower std. deviation. These experiments show that consistently outperform the baselines and the performance is not dependent on the random seed.
Table 13: Comparison of QuAnt to general baselines
on point set registration. We report the mcan of the per-experiment median and std. deviation across exper- iments three different random seeds.
Ours
Diag
Pure
L-3, 32
4,8 1 0.6
6.8 = 0.2
5.8 0.9
L-3 H-
3.7 0.3
5.1
4.3
T- H-
4.6 0.1
7.1 1.0
7.1
--5, H-78
3,4 0.1
4.9 0.0
7.9
19

---

Published as a conference paper at ICLR 2023
Table 14: Robustness to varying amounts of uniform noise. We report the mean/median error for I.3,, H7-2. The first column specifies the range of the added uniform noise, in %, of the maximum extent of the point cloud.
%
Ours
Diag
Pure
AQM
0
7.4/ 4.2
11.37700
7.8 6.66.6
4.37
6.7
1..7/73
8.0/
4,5
4.5
/
8.6/7.0
5.6/38
8.9
12.6/6.8
9.7
5.6/3.8
20
11.0/ 6.0
8..9/8.2
14.3/10.
5.3/3.
G.3 NOISE
In addition to the experiments in the main paper that uses the largest architecture, we also test the noise resistance on the smallest network setup with 3, H 32; see Table 14 Here, while QuAnt is better than the baselines, we do not outperform AQM. However, by construction, AQM is an upper bound for our method as the matrix introduced by Golyanik et al. (Gollanik & Theobali 2020 is the same as our input into the network, but it gets directly solved by the QA.
G.4 QUALITATIVE ABLATION RESULTS
In addition to the quantitative loss ablation in the paper, we visualise the effect of the losses here. In Figure TO the full loss results in nearly ground-truth rotation. However, if we leave out Tap or LLPP during training, a significant reduction in rotational accuracy is visible.
(a) Initial problem instance
(b) Ours with the full loss
(c) Ours without LMLP
(d) Ours without
Luuiqque
Figure 10: Qualitative loss ablations. show the original point cloud (blue) and rotated point cloud (red).
Removing either Lyrique or Lmlp leads to significantly worse results.
G.5 FAILURE CASE
We continue our analysis with failure cases. Results the main paper show that an increasing input angle leads to reduction in the accuracy of our regressed angle. This can be traced back to our problem-ine problem-instance instance encoding as Golyanik et al. (Golyanik & Theobalt, (220)) mention that an increasing angle makes finding the correspondences more error- proonp Therefore, imperfect input encoding makes it is also more likely for us to regress wrong angles.
Similar to most prior work point set registration, nearly symmetric shapes be difficult, as most points can be nearly perfectly aligned even with wrong rotations. Fig. [[ contains such a failure case. The initial angle of this problem instance, 50.8%, is relatively large for our setup, and the shape (which looks like the silhouette of a fish) is nearly rotationally symmetric. cases like this, our method has difficulties regressing the correct rotation after single QUBO sampling.
20

---

Published as a conference paper at ICLR 2023
(a) Initial problem instance
(b) Failing to regress correct rotation
Figure 11: Example of a failure case point set registration. We show the initial image (blue) as well as the rotated image (red).
21


Reviews:
[{"review_id": "O3ZlJ6scwj", "reviewer": "Reviewer_2Ews", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents a new approach for learning QUBO formulation for problems to be solved on quantum annealers using machine learning in comparison to previous work on quantum computer vision that relied on hand-crafted QUBO formulations. The paper proposes learning to regress a coefficient matrix for QUBO using contrastive loss based on the energies of solutions found the quantum annealer (or other QUBO solvers). Experiments on different computer vision problems show competitive results with previous quantum SOTA while requiring fewer qubits.\n", "summary_of_the_review": "I think this is an interesting paper that presents a novel and innovative approach with good experimental results. The main weaknesses include the fact that such formulations are learned and may therefore not generalize well or maintain similar guarantees as hand-crafted QUBO formulations, as well as the relatively modest gains in performance compared to SOTA. Despite the weaknesses, I think this is a nice contribution to the research on quantum computer vision (with potential impact beyond computer vision due to the generality of the approach).", "strength_and_weaknesses": "Strengths:\n* Innovative approach for learning QUBO formulations of problems to be solved on quantum annealers.\n* Unlike previous work on quantum computer vision, the proposed approach is general and not problem-specific.\n* Experiments on graph matching and point set alignment show the approach is competitive with previous quantum SOTA approaches while requiring fewer qubits.\n\n\nWeaknesses:\n* Learned QUBO can be more sensitive to distribution shift than hand-crafted QUBO design in SOTA approaches. While the noise experiments are interesting it would be valuable to design experiments to compare the proposed approach and the hand-crafted QUBO approaches in terms of generalization to out-of-distribution test instances.\n* Learned QUBO formulations can be less interpretable compared to hand-crafted QUBO formulations. In particular, when designing QUBO we often convert problem constraints to penalty terms in the objective. Knowing the penalty terms and their weight can provide some guarantees on the obtained solutions with respect to the satisfaction of domain-specific constraints. While learning QUBO may involve implicitly learning such constraints from data, we have no way of knowing what constraints have been learnt (in human-understandable mathematical notation as often done in the hand-crafted QUBO formulations).\n* Experiments do not show significant gains in performance over SOTA. However, I think that obtaining competitive results using fewer qubits and in a problem-independent approach is impressive.\n\nMinor question: How did you create mini-batches for training? Did you accumulate the results of multiple runs with the QA hardware into mini-batches?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "I-3i5JCrOS", "reviewer": "Reviewer_kb2o", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper tackles the problem of generating QUBO forms from an unspecified problem instance. It learns a low-energy formulation of quadratic unconstrained binary optimization problems with multilayer perceptron and gradient backpropagation, instead of problem-specific analytical derivations.  After learning a QUBO form, they solve it with existing quantum annealing techniques. Their model excels previous models on some benchmarks both in computational expenditure and performance.\n\nChallenge: \n\nDepth: A new training strategy for neural methods with backpropagation, independent of the solver.\nResults:\n-Task: graph matching, 2D point cloud alignment, and 3D rotation estimation.\n-Metric: Accuracy, and the number of qubits of the forms obtained by the proposed algorithms.", "summary_of_the_review": "About Challenge:\n- Obtaining suitable QUBO forms in computer vision remains challenging and currently requires problem-specific analytical derivations.\n- The MLP is trained with the results from AQM, resulting in its performance bounded by AQM. Given such deficiency, is it really fair to conclude that QUBO learning is capable to deal with a general problem?\n- The results are not impressive. Their MLP surprisingly fails to beat binary regression (“pure”) in some cases. Is it an isolated incident that QUBO learning beats some SOTA? \n\nAbout Contribution:\n-The paper contributes to the area by looking beyond the traditional approach of deriving and solving QUBO from a specific problem. It addresses a bigger picture concerning how to identify and classify a mission. By aiming at generality, it extends the application of quantum annealing as well.", "strength_and_weaknesses": "Pros:\n- The idea of finding the forms of QUBO with gradient is interesting.\n- A wide variety of problems can be tackled successfully and competitively by the proposed general quantum approach.\n- The proposed algorithm finds formulation with fewer qubits than state-of-the-art.\n\nCons:\n- The selected baselines are not strong enough. It is not clear how the selected baselines, Diag and Pure measure the quality of the solution. The author should compare to state-of-the-art.\n- The comparisons with specialized methods are limited. \n- The synthetic data are relatively small, e.g., random matrix 4 by 4 and 5 by 5. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "--_iDQC397w", "reviewer": "Reviewer_12QQ", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies the problem of classical-quantum hybrid learning to solve computer vision (QCV) problems. The model contains classical neural network layers and a quantum annealer. The whole system is trained with gradient back-propagation. The experiments on graph matching and point set registration show effectiveness of the proposed method with higher accuracy than baselines.", "summary_of_the_review": "Interesting meta-learning method for QUBO problems for quantum computer vision, with experiments results on real D-Wave quantum machines.\n\nThanks for the response! I have read it and would like keep the score.", "strength_and_weaknesses": "Strengths: The idea of learning and updating QUBO forms is novel. The new neural meta-learning approach is applied to the QUBO on modern QA. The paper shows diverse and detailed experimental results. The paper also runs experiments on the D-Wave real quantum \nmachines to evaluate their method. \n\nWeakness: \nIt seems the method requires the classical part to finish the whole back-propagation pass. How will that scale with the number of qubits? will that be the bottleneck of the training efficiency?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%