Quantum algorithm for large-scale market equilibrium computation
Authors: Po-Wei Huang
Patrick Rebentrost
Venue: NeurIPS 2024 poster (2024)
Keywords: market equilibrium computation
quantum algorithm
Primary area: algorithmic_game_theory
TL;DR: We provide the first quantum algorithm for market equilibrium computation with sub-linear performance.

Abstract: Classical algorithms for market equilibrium computation such as proportional response dynamics face scalability issues with Internet-based applications such as auctions, recommender systems, and fair division, despite having an almost linear runtime in terms of the product of buyers and goods. In this work, we provide the first quantum algorithm for market equilibrium computation with sub-linear performance. Our algorithm provides a polynomial runtime speedup in terms of the product of the number of buyers and goods while reaching the same optimization objective value as the classical algorithm. Numerical simulations of a system with 16384 buyers and goods support our theoretical results that our quantum algorithm provides a significant speedup.

Quantum algorithm for large-scale market equilibrium computation
Po- Wei Huang' and Patrick Rebentrost
CCentre for Quantum Technologies, National University of Singapore, Singapore 117543 *Department of Computer Science, National University of Singapore, Singapore 117417 huangpove 220uu nus edu, patrickdcomp. nus. edu.
Abstract
Classical algorithms for market equilibrium computation such as proportional response dynamics face scalability issues with Internet-based applications such as auctions, recommender systems, and fair division, despite having an almost linear runtime terms the product of buyers and goods. In this work, we provide the first quantum algorithm for market equilibrium computation with sub-linear performance. Our algorithm provides polynomial runtime speedup in terms of the product of the number of buyers and goods while reaching the same optimization objective value as the classical algorithm. Numerical simulations of a system with 16384 buyers and goods support our theoretical results that our quantum algorithm provides significant speedup.
Introduction
The balance of supply and demand a fundamental and well-known law that determines the price of goods in market. In market with set of n buyers and goods, the competitive equilibrium [1, 2] determines the optimal price and allocation of goods such that the supply equals the demand the given market. The computation of the competitive equilibrium is known the market equilibrium computation problem, whose unique solution was shown to exist under general model of the economics in the seminal work of Arrow and Debreu [3]. The relevance of such problems in algorithmic game theory [4, 5] is substantiated by the first welfare theorem, which implies that the competitive equilibria better without making another one worse. In competitive equilibrium from equal income (CEEI) scenarios, such equilibria are further known by envy-free [7, 8]. where no agent would prefer an allocation received by another agent over their own.
Pureto-efficien [6], where no allocation is available that makes agent
The market equilibrium computation problem has, in recent years, been extended to various large-scale titemet-based markets [9], including auction markets [10], fair item allocation/fair division [1 [11-13], scheduling problems [14] and recommender systems [15]. Such developments call for the need to further develop algorithmic theories for markets and the computation of market equilibria. We focus on particular type of market known the Fisher market [16, 17], where there is set of n buyers interested in buying m infinitely-diviiille goods, and where each buyer has their monetary budget that has no intrinsic value apart from being used purchase goods. We mainly consider Fisher markets with linear utilitics, where the total utility gained by purchasing goods is strictly linear to the value and proportion of the goods obtained.
For combinatorial formulations the market equilibrium problem, algorithms have been discovered that obtain exact and approximate solutions [18-21]. these algorithms scale poorly against the growing number of buyers and goods. One can also formulate the market equilibrium computation problem as an optimization problem that maximizes a convex objective function known the Eisenberg-Gar (EG) convex program [22, 23]. For such optimization problems, approximate
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Algorithm
Iterations
Runtime
Memory
Result Prep.
PR dynamics [24]
log m
m
(mm)
N/A, in RAM
E 2 log m
mn max (m, n)
QA: (poly log mn SA: mm))
Our work
Om + n))
g2
Table 1: Main results. In this work, is the number of buyers, is the number of goods, and indicates the additive error of the computed values to the minimally-achieee achievable EG objective value. The memory complexity for the quantum algorithm (annotated with *) refers to the use of quantum query access to classical memory, achievable by QRAM (see Definition 3), instead of classical RAM. As the computed competitive equilibrium consumes (mm) memory, our quantum algorithm does not provide the entire bid matrix, but instead provides quantum query access (QA) and sample access (SA) to the competitive equilibrium. The result preparation column refers to the additional runtime cost of preparing QA and SA.
solutions can be found much faster. One such algorithm of the market equilibrium problem is the proportional response (PR) dynamics [24, 25J. The PR dynamics is an iterative algorithm that converges with rate of where T the number of iterations. Each iteration has a cost of (mm) from proportionally updating individual bids of each buyer for different goods.
Given the high number of buyers and goods that can exist in Internet-based markets, the problem of further algorithmic speedups to the computation continues to be an active field of research. Gao and Kroer [26] discovered that by using projected gradient descent instead of PR dynamics, the market cquilibrium can be found with linear convergence. Other attempts that aim to reduce the cost per iteration, such as using clustering to reduce the problem size [15], have also been made. However, is unclear whether advantages beyond a constant-facto speedup can be provided.
While it is unclear whether additional classical strategies can provide further algorithmic speedup to the market equilibrium computation problem, one can utilize algorithmic developments in quantum computation achieve such goals. Quantum computation [27] is an emerging technology that has been utilized for algorithmic speedups in various optimization problems [28] such as linear programming [29] and semidefinite programming [30-33].
In this work, we consider a Fisher market with n buyers and m goods, where the objective is to find an approximate market equilibrium whose EG objective function is within an additive error e of the optimal EG objective value. We provide a method to reduce the cost per iteration by utilizing quantum norm estimation and quantum inner product estimation [34, 35] and provide the first quantum algorithm to achieve sublinear performance in terms of the product of the buyers and goods in market equilibrium computation. To arrive at the quantum algorithm, version of the PR dynamics with erroneous updates, which we term the faulty proportional response (FPR) dynamics. We then provide a quantum algorithm that provides quadratic speedup in terms of the smaller dimension between buyers and goods, as well as less memory consumption, albeit being based on QRAM instead of classical RAM. We summarize our results in Table 1.
show an alternate
Unlike the classical PR algorithm, which provides an entire matrix corresponding to the competitive equilibrium with storage O(mn) space,' we provide quantum query and sample access to the values of the competitive equilibrium, which allows access to the individual values by index querying as well as &1 sample access to the values. This access format has previously been used as the output model for quantum recommendation systems [36], quantum linear system solvers [37], but has been pointed out to have significant caveats [38]. While the quantum algorithm does not exactly "solve" the market equilibrium problem in the sense of outputting the entire matrix, quantum query and sample access provide preparation of a quantum state encoding the solution that can be used for further computation. for extracting only a small set of values within the matrix, or for extracting certain properties of the matrix, which may indeed be the use case for large-scale distributed systems.
'Given that it takes (mm) to even output the entire matrix, sublinear algorithm would require a different output model in the first place, since the sublinearity would be undone by the solution generation.

---

2 Preliminaries
Notations. Let [n] (0, 1, ................................ n 1]. We to represent element-wise multiplication, as well as @ for bit-wise XOR operation and & for tensor products. For vectors v E RRN, we denote a
vector's lp norm by ||0|| :- //2i", Jus|P. Let MMx (R) indicate the space of square matrices of size M N over R. We denote the i-th row vector of A by Ai.. and the j-th column vector of A by A..- We further define Il as (0. 1). and the n-unit simplex as S" i.e. S" = (u E T", ||||||| = 1}. For sets of numbers, we add the subscript ++ indicate constraint positivity for elements in the set. We use [k) to denote a binary encoding of a real number k up to arbitrary precision into quantum state, and (0) to denote multi--ubit zero state whose number of qubits can be inferred from the context. Lastly, we use (-) omit polylogarithmic factors in asymptotic runtime/memory analysis.
Quantum computation. Quantum algorithms are shown to be able to provide asymptotic speedups over classical counterparts [28, 39, 40] by utilizing characteristics of quantum mechanics such as preparing superpositions of different computational paths.
This property of quantum algorithms allows one to simulate the probability distribution of classical randomized algorithms directly as amplitudes of the quantum state, with the accepted results of the classical algorithms labelled as "good" states, and the rejected results as "bad" states. The quantum amplitude amplification (QAA) [41] technique amplifies the amplitudes "good" states such that the success probability increases to sufficiently high occurrence from its original p upon measurement at a runtime cost of (L1 /P). This provides a quadratic speedup compared to classical Monte Carlo methods, which take average (1/pp) samples to achieve success. The QAA technique gives way to another technique known as quantum amplitude estimation (QAE) [41], which combines QAA with eigenvalue estimation via quantum phase estimation (QPE) [42] to directly estimate the probability value of the occurrence of a certain event with a quadratic speedup.
Theorem 1 (Quantum amplitude estimation; Theorem 12, [41], Formulation of [43]). Let t N. We are given one copy of a quantum state ( as input, as well as a unitary transformation = I-2 w) (bb), and unitary transformation V = I - 2P for some projector P. There exists a quantum algorithm that outputs a, an estimate of a = |P (b) II?, such that
S 2T aalla)
x²
M +
M²
with probability at least 8/7², using M applications of U and each.
In this paper, we use QAE to estimate & norms and inner products of vectors v E 1N to multiplicative error in M E O N 1o)())) runtime with probability 1 5 [35], invoking quadratic speedup in both the dimension and the error rate. We defer the formulation and details to Appendix A.
Apart from quantum subroutines that provide speedups, we also require the usage of arithmetic operations such as addition, subtraction, multiplication, and division on quantum computers. We assume the arithmetic model, which would allow us to ignore issues arising from the fixed point representation of numbers.? We further assume that we have access to quantum arithmetic circuits [44, 45] that can perform such arithmetic operations in O(1) gates, and that by using such circuits, computation of the n-th power of a number, where n E N. can be achieved in Oppoly log n) gates, using methods like binary cxponentiation [46]. We note that quantum arithmetic circuits can be used to execute the same operation on multiple numbers in parallel if the numbers are held in superposition.
In regards to the access of data encoding in quantum states, there are two main models quantum query access and quantum sample access. For clarity, we highlight quantum states that indicate the index in such access models in bold font throughout the manuscript.
Definition (Quantum query access). Let n E N and e E (1). Let a vector of bit strings wr be such that Vj E [m], My E (0, 13s and let an arbitrary bit string be E {0, 1). We define quantum query access to w as the access individual bit strings in w for j [m]] in the format of
(o) (a) lj) |xr wy)
operating on Ollog n) qubits.
'If the fixed point representation with an additive error of μ is considered, the additional multiplicative cost required for operations is then (pooly log 1)) Considering μ 22(1/ poly(m,n) n)), the additional cost O log(m, rt)), which are polylogarithmic factors that already omit in this paper.
3

---

Note 1.1. Note that when x = 0, the quantum register stores (ay) after the query. When z = wy, the quantum register stores (0) after the query. Hence, two consecutive queries onto a quantum register the identity operation.
Definition 2 (Quantum sample access). Let n. E N and R", We define quantum sample access to w as the access to the index j E [n]] by probability wi/ [t/[|uu ||w]|| in the format of
0) - j=0 100 (j)
operating on (loo n) qubits.
Note 2.1. In quantum mechanics, Born's rule [47] postulates that the probability of measurement outcome corresponding to state Ij) is proportional the square of its amplitude under superposition. Hence, the square root in the amplitude regarding the format of quantum sample access.
Lastly, we need to access the input matrices and intermediate vectors as a superposition of encoded quantum states. Such quantum query access to classical data in memory can be achieved by quantum random access memory (QRAM) as follows.? We refer the reader to [49] for a detailed survey.
Definition 3 (Quantum random access memory; [52, 53]). Let E N and e O(1). Also let w be a vector of bit strings such that Vi E [r.], w; E {0, 135. A quantum RAM provides quantum query access to wi in superposition after a one-time construction cost of (n)) where each access costs Opooy log
Note 3.1. Quantum sample access can also be provided by QRAM via Grover-Rudolpp procedure [54] during construction with logarithmic overhead but is not used in this work.
Fisher market equilibrium. In the Fisher market model [16, 17], infinitely divisible goods to be divided among n buyers. Without loss of generality, we assume a unit supply for each good. Each buyer i E [m] has budget of B, 0 that has no intrinsic value apart from being used to purchase goods where, again without loss of generality, we assume that the corresponding vector B E S". Each buyer also has utility function u, RT - R. that maps an allocation of portions of m items to a utility value. We can then define the allocation matrix Max (I) such that Tzy is the portion of item j allocated to buyer where I, E I is the bundle of products allocated to buyer i. In this paper, we consider linear utility functions such that u, (2:4
given market of m
EjE(m) UijZaj. where Vij > 0 the value for unit of item j for buyer
Given the Fisher market, want to compute its competitive equilibrium, which consists of the price vector p E IRT for each item and allocation matrix x such that each buyer i exhausts their entire budget B, acquire bundle of items x; that maximizes each of their utility ux(x.).
The market equilibrium of Fisher markets can be captured by solving the Fisenberg- Gale (EG) convex program [22, 23]. The program is derived from maximizing the gudget-weighter geometrie mean of the buyers' utilities i.c. the Nash social welfare, satisfying natural properties such as invariance the optimal solution to rescaling and splitting [55], and balances the efficiency and fairness regarding the allocation of goods. Applying the log on the geometric mean, the EG program is as follows:
max Eie(n] B, log un (z+) s.t. Σie(n) Tij = 1, Vj E [m].
(I)
where the price pj is the dual variable of the constraint on Tij. Such convex programs (maximization of a concave function subject to constraints) can be solved by interior point methods [56], but may not scale to large markets. We discuss this further in Section 6.
For the linear Fisher market, an alternative convex program that obtains the same market equilibrium was shown by Shmyrev [57]. Supposing that each buyer submits bid biy for item j such that the sum of the bid of the buyer matches their budget B, such that each buyer is allocated Taj = biz/P
of item j. we have the following convex program:
maxx20 Eij bij log
tia s.t. Eie(n) bij = Pj. Vj E [m]:Ejenn byj = B,, Vi E [m].
(2)
Pj
As the allocation matrix and price vector can be directly computed from and conversely, be used to compute the bid matrix, the bid matrix can be used direct representation of the market equilibrium itself, and hence, is the output of the algorithm we discuss in our paper.
3 'Our memory unit can more precisely termed QRACM [48, 49], including classical memory, or quantum read-only memory (QROM) [50] as opposed to QRAQM [48, 49] or the quantum random access gate (QRAG) [51], whose memory registers store quantum states instead of classical numbers. However, both are more commonly and jointly referred QRAM in the literature.

---

Proportional response dynamics. The proportional response (PR) dynamics is an iterative algo- rithm [24, 25, 58] that obtains the Fisher market equilibrium computation by updating the bids bij submitted by buyer i for item j. For each time step L, the elements of the price vector pj (t) are com- puted by summing the bids for item j such that P] Σ, bjj The allocation zij is then obtained by taking z;j
(e) = Dij /pj (t) The buyers then update the bids such that the new bid is proportional to
(t) (t) (c) = E, Bij gained in the current time step such that (f+1)) BRusz /u; It the utility u;
(4)
was shown by Birnbaum et al. [59] that the PR dynamics is equivalent to mirror descent [60, 61] with respect to Bregman divergence [62] of the Shmyrev convex program.
For case of discussion, we write the objective function of the EG and Shmyrev convex programs as functions of the bid matrix b, obtaining the EG objective function k(b) > Sien| B, log u,
and Shmyrev objective function (b) = [iE(m))dE(m) bij log Pi We denote the optimal bid 6"
Vay" arg m (b), where S = b E Muxm (I) ΣjE(m) bij = B.}.
The convergence bounds of the PR dynamics regarding the EG and Shmyrev objective functions for linear Fisher markets were found as follows:
Theorem 2 (Convergence of PR dynamics; [59]). Considering a linear Fisher market, for big as
iteratively defined by the proportional response dynamics where 110 Bs
we have
m
T (b(TT) - vv((*) <
logm
+(b(T-1)) + (b*) S
log
(3)
We provide an altemnate end-to-end proof of the convergence of both convex programs in Appendix B that varies from Birnbaum et al. [59]'s approach and, unlike the latter, is centered around the EG function instead of the Shmyrev function. Elements of this proof are used in the proof of theorems in later sections. Two notable results that we prove and utilize are: 1) (((((++2) S & ((((1) + Eig(n] B, log B, S (b(+)), and 2) the telescoping sum of the difference of the KI. divergence [63] of the optimal bid and the iterating bids can be lower bounded by the difference of the current EG objective function and the optimal EG function.
3 Faulty proportional response dynamics
Before moving on to our quantum algorithm, we propose the faulty proportional response (FPR) dynamics, which computes an erroneous update to compute sequence of bids g(() Such updates still retain a convergence guarantee, and serve as a counterpart to Theorem 2. We first define faulty update we use for the FPR dynamics:
Definition 4 (Faulty proportional response update). Lett 2 and B(t) E &Mxm (T4)). ). Let us be given Ep E (0, 0.5) and 7(9) such that Vj, 10 0 S 1) Ep where 1/0) Eie(n) ((0) Further, let us be given &, E (0, 0.5) and (0() such that Vi, 1, (o(() - 1111 I of0 en where D! = = Ejemm my m /r/ A faulty proportional response update of the bids from timestep to to is then expressed as follows:
g
((++)) ij
B
Note that while 6y provides an estimation to the price DÚ Eie(m) big. in does not provide an estimation to the exact utility û, = jja(( (iyk vizbez/ fb.. Instead, in estimates 2ú which replaces pú in the computation of u, with Pj-
We find the convergence bounds of the FPR dynamics regarding the EG objective function for linear Fisher markets are follows:
Theorem 3 (Convergence of the FPR dynamics). Considering a linear Fisher market, for bl) as iteratively defined by the faulty proportional response dynamics where B1) = B, we have
minsery (bb10) (bbb) < 2 2 m
when En <
log m and Ep < 8T
log m 67
5

---

A high-level idea of the proof follows from the telescoping sum trick to upper bound the EG objective functions with KL divergence from our proof of PR dynamics but with the consideration of error. We show an end-to-end proof of the convergence of the EG objective function in Appendix C.
Notice that in the FPR dynamics, we do not enforce the monotonicity of the iterations, but instead simply take the minimum value over all iterations. The error terms Ep and E, in the FPR dynamics are only upper bounded such that the total sum of objective values over I iterations (plus the original iteration) can be upper bounded by log m plus an accumulated error over I iterations also within log m. we enforce the monotonicity of the iterations to take the last iteration, the error would require ( precision and would incur further multiplicative overhead of T in our algorithm.
However, given the formulation of faulty update, problem that comes into question is whether the computation of the exact value of the function (b(b) is supported, as we do not compute u, in the
process of updating. Without computation of Φ (bb), one can not be sure which iteration of 8(() is the minimum. On the other hand, we can use the computed value of 7 as an estimator for the function (b). The following result is then obtained.
Theorem 4. Considering a linear Fisher market, for (1) as iteratively defined by the faulty propor-
tional response dynamics where ((0) R.
m Let 1t* = arg [ Eie[n] Be log (!)) Then
((((")) -bbb)) 2 log
when En and
log m ST
Ep S
log m 6T
The proof of this theorem can similarly be found in Appendix C, which has the same proof idea as Theorem apart from some slight differences in error handling.
4 Quantum algorithm
We present our quantum algorithm for solving linear Fisher market equilibrium computation based on the FPR dynamics. Our quantum algorithm does not aim to provide speedups in terms of the number of iterations but provides speedups on the iteration cost of the PR dynamics algorithm. Our algorithm, while reducing the runtime in terms of the number of buyers n or goods m, increases runtime in terms of the number of iterations T but the T is logarithmically dependent on m, there is an overall quadratic speedup provided in the smaller of the two dimensions.
In this section, we further assume that & E MM (T+)). We note that the multiplicative scaling of My does not affect the bid matrix generated in the FPR dynamics as errors are multiplicative. Hence if the values are larger than 1, we scale down the values by dividing the queried Usj by number that larger than max;, Vig-
To compute the market equilibrium for the Fisher market by the FPR dynamics in the quantum setting, we require the data input of both the budget vector B S" and the value matrix MMxmm (I+)). ). We assume quantum query access to the budget and vector and value matrix by the index is readily given us as part of the problem input without having to load classical data into a quantum system. That is, given an index state and ancilla quantum registers we can store the value of the budget and value according to the index in the ancilla register. Note that these operations can be performed in superposition, such that 1 Ev, [)) J0] < E., (t) ()) |oiz).
v mm
We do not explicitly state how the data input of the budget and value entries are generated; they could be extracted from entries of a matrix already preloaded QRAM, or generated/reconsrructe from a low-rank approximation of the matrix [15], which takes Ol poly log mn) cost to access k-rank approximations using quantum arithmetic circuits, but with much lower memory consumption." We note that the low-rank approximation assumption of the value matrix has not yet been utilized to produce reductions in resource consumption in classical methods as the PR dynamics and other methods to compute market equilibrium [26] require all mn entries of the full value matrix as input.
Storing the results of the computed bids ((0) E MMxx (I+) in QRAM would require cost of ((m)) which would remove all possibility of potential speedups. The same applies to the allocation matrix
With lowk approximations, loading classical data into QRAM would only take Ölk(mn + n)) runtime.

---

a00), Hence, every time we require the usage of B(+) or s(1), we compute them on-the-fly as follows:
Given quantum query access to the values of (I))), II o and (I))); := 8. one can encode the values of B(t+1) and ((*) into quantum state in superposition via quantum arithmetic circuits in runtime of (poly log tmn). In our algorithm, we compute and store the vectors 11," and n in QRAM, after which, query access to such values cost (polly log mn). Taking the 1-th power of the budget and value cost Oppoly log by using CNOT gates and binary exponentiation [46].
The remaining steps are to compute the price vector P and utility vector in each iteration. Each entry Pj is the estimation of the l norm of b and each entry P; is the estimation of the inner product between dy,, and Ug,., which can both be obtained using QAE. 11,5) and 11 can then be iteratively updated by multiplying by the values of and & each iteration. The full algorithm is shown in Algorithm 1, and the algorithmic guarantee shown Theorem 5.
Algorithm 1: Quantum algorithm for faulty proportional response dynamics
Input: Quantum query access to B and Timestep limit T, Price error Ep. Utility error ev maxEGVal = -oo b/y R
2 for == to T do
for j = m do
P = 11 Ep) via Q norm est. (Lemma A.1) with success prob. 1 5
2m
5 Store vector 11 = p(0) @ 11 (t-1) into QRAM
6 Gain access to z! via u1 and (1 in QRAM
7
for = 0 to n do
1 ( Ug (1 via Q inner prod. est. (Lemma A.3) with success prob.
(1)
T
Store vector II!" 7(0 II! (t-1) into QRAM
9
Gain access ((+1) via II, and IT in QRAM
Classically compute (+) Exen) B, log(
if (+)) > moxEGVal then
12
maxEGVal ()),, bestPiP 11(""1, bestPiNu 11$-1)
return bestPiP and bestPiNu QRAM
Theorem 5 (Quantum algorithm for the faulty proportional response dynamics). Let 6 E (0, 0.5), m. T E N, Ep 8T and access QRAM, with success probability such that query and sample access to the values of i(te) can be constructed, where
log
and ex log m Given quantum query access to B and
69 Algorithm produces values stored QRAM
((b(tt)) 4bb') 2lngm
with ÕTT / mm max(m, r.) log {) runtime and Öm + n) QRAM space. To provide query access to ((t") an additional cost of O(poly log ('n) is incurred.fro accessing 11 (1) and 11ft" in QRAM. Providing sample access k(1") requires additional cost of (( poly log T) from QAA.
Proof. Per union bound [64], we find that the total success probability at least 1 - 8. The output of Algorithm of bestPiP and bestPiNu corresponds to the values of IT (t"--) and (!((" 1), This gives us the guarantee of convergence shown in Theorem 4.
For the rumtime analysis, the quantum norm estimation subroutine (Lemma A.1) takes O /2 log mf
Ep
for mf iterations, while quantum inner product (Lemma A.3) estimation takes O /m
log 4f
nf
for
7

---

nT' iterations, resulting in a total runtime of Ö(T² mn max n)) log 3.). For uses of QRAM, the construction on Lines 5 and 9 a one-time cost of (n) and ((m), respectively, with a total runtime of ( i + n)). The classical computation of the EG value in Line 11 costs (Tn). We note that the quantum norm and inner product estimation subroutine is the main bottleneck of the algorithm, and hence the total runtime is then Ö(T², v mn max n) log })-
For the memory complexity, for the t-th iteration, we require 6 vectors in QRAM: the current iteration 11," and 11!", the best iteration bestPiP and bestPiNu and the previous iteration 113" 11f'-1) and I in case need to update bestPiP and bestPiNu. Note that to update the best iteration, simply reroute the register of the previous iteration to being the best iteration. There is no need to copy data or reconstruct new QRAM as the data from the previous iteration is longer needed in the next iteration. Therefore, the memory is Om + n) for storing the 6 vectors.
The values bestPiP and bestPiNu can be used to construct query access ((*") per Equation (4). To prepare quantum sample access to the matrix (((*), using quantum query access to (((*) from Algorithm and Equation (4) addition to conditioned rotation gates, we can encode the values of B(t*) onto the amplitudes of an ancilla qubit via Lemma A.1 such that we obtain
(i)i (0) +
Σ
(V 8 [0) + V 111 B5. (1)
(5)
Note that states where the last qubit is {0} are the "good" states that we want, while the states where the last qubit is 11) are "bad" states. To get rid of the "bad" states, we use QAA to amplify the amplitudes of the "good" states. Rewriting the above terms and ignoring the ancilla qubits, we obtain
1160011 lla
10) + +VV
||b(1*)]| Il1
1-832
11)
(6)
man
We see from the above that the success probability of obtaining "good" states is _
costs O (V 1100 query accesses to b((*), and while the exact value of ||((t")] mn 1l, Hence, QAA
is not known, by
Definition 4, Itf S 18000) 111 S - Hence, the query complexity of (())) can be further upper bounded (0(mm(1 + Ex)) c O(Vmn). On the other hand, the cost of query access to b((") has Opooly log T mm)) cost, therefore, the total cost for sample access to b(e") is O(ymn poly log T).
Numerical simulations
We simulate the market equilibrium computation under PR dynamics and quantum algorithm." To showcase the effects of quantum speedups, we fixed the number of queries to all bid matrices ((t)
and observed the reduction of the objective value over the number of queries.
As an actual simulation of QAE using quantum gates over multiple qubits is costly, we directly compute the probability vector of Pr[2 = 2] for 2 [M] that one would obtain by QAE [41] for target value
sin (MA
Pr| = 2] M (A.
(7)
where A; min([= - sin "Vaa="/V
sin "saa M is the number of times that call the unitaries U and V in QAE (see Theorem 1). and is linearly correlated to the runtime, We then sample the output according to the computed probabilities to obtain an estimator ā = sin 2 )
For our experiments, we generate the input data where the value v is sampled from a uniform distribution with range (0, 1] and a normal distribution [0 0.25), where we resample values that fall outside the range of (0. 1]. For the budget B, we either sample from the same distribution as the value matrix or set the same budget for all buyers to simulate competitive equilibrium from equal income (CEEI) applications. Our simulation includes n = 16384 buyers, m 16384 goods, and
'The codebase can be found at https: //tg:::///ttttt com/ wtt./oooo//eeeeee georggeshuaggg//////o/ wwwpangggggg-ageeeeeeeeee www.et-eeuilleeeeeee equilibrium.

---

(a)
Uniform
Uniform CEBI
Normal
Normal CEET
0.3
Olgenttie Natua
TIG Olpectio Salae
0.0
0.2
-02
-3.3
-0.3
-0.4
0.5
Querles
Qutites
Queeles
1ed
Queries
(b)
PR dysamiss
Prodeted Geudiont Descentt
Quadiam Aguetihu:
Optinal objective valus
Uniiform
Unifform CEFT
Normal
Normal CEBI
E0 Oldoestivv Saloo
BU Osjecttive Value
0.390
-0.002
0,188
0.208
-0.004
0.186
2
3
0.000
2 Quarii
0.006
2
3
Querta
Dieettes
1n
Osrctee
Quentum Algeettm
Optimsl objectivn velon ....
Figure 1: Experimental results. We perform our experiments on 16384 buyers and 16384 goods given the same amount of queries for all algorithms. We observe in Figure la that over different distributions, our quantum algorithm (green) significantly outperforms the PR dynamics (blue), which aligns with our theoretical results. Furthermore, our results also show that both our quantum algorithm and the PR dynamics outperform projected gradient descent (orange) in the mid-accuracy regime. Figure 1b shows the convergence single run of the quantum algorithm despite its instability from faulty updates, well the variance over the multiple runs (shaded in gray).
iterate for T 16 iterations for the PR dynamics. For the quantum algorithm, note that the queries per iteration would be reduced by v we use an actual quantum computer, hence increasing the number of iterations to fix the number of queries. For QAE, we run for VTVR 512 iterations and set M O( vT). As the classical algorithms are deterministic, rerun quantum algorithm over 15 times with the same sample of B and v to observe the variance of convergence progress. Results shown in Figure 1. Details on implementation and setup found in Appendix D)
From the plots of Figure 1, we note that the results fit our theoretical results in that the quantum algorithm converges much faster than that of the PR dynamics [24]. Further, also compare against the convergence of projected gradient descent, which supports empirical results by Gao and Kroer [26] that in the regime of mid-level accuracy and low iterations, PR dynamics-related algorithms, both classical and quantum, converge faster than projected gradient descent.
Discussion
Quasi-linear utilities. For the bulk of our paper, focus the setting of linear utilities for Fisher markets. However, applications of market equilibrium computation in large-scale Fisher
markets involve mostly quasi-linear utilities [9]. An approach for using PR dynamics for quasi-linear utilities proposed by Gao and Kroer [26]e includes the usage of slack variables = (61, ... 5m)
that represent the buyers' leftover budgets. The PR updates are then modified as follows:
(++1) B
(1+1)
B
8(0)
(8)
Ey
Further, PR dynamics for quasi-linett utilities exhibit a convergence rate of O (oggm++))))))))) the methods discussed in previous sections, the quasi-linear version of PR dynamics readily adapted to its quantum version by employing the same techniques of computing and storing
T Using
then be
in QRAM the values II and II with on-the-fly computation of ((++1), a(()) and 8(++1).
Constant number of buyers. Notice that our quantum algorithm provides a quadratic speedup on the smaller value in regards to the number of buyers and number of goods m. Therefore given extreme cases where the number of buyers n E O(1), our algorithm does not provide a speedup.
'There is another method proposed by Cheung et al. [65]. which we find difficult to convert to quantum due its use of thresholding, which would cause problems with faulty updates from the FPR dynamics.

---

However, in such cases, quantum speedups may still be obtained simply by removing the QAE step for estimating the price for each item and replacing with using quantum arithmetic circuits to compute the exact sum. We use a total of (n? poly log(T, m,))) qubits to compute the values of bi. separately on the i-th set of qubits, and only conduct QAE when estimating the utility value for
each buyer. Given that in this setting. n E (1), the total runtime would then be ( /mlog !)) gaining quadratic speedup over the number of goods m.
Dequantization. Given the work in recent years towards the development of quantum-inspiree classical algorithms [66-69] that achieve similar performances as quantum algorithms using sampling- based techniques, natural question that arises is whether our algorithm can be "de-quantized", The main speedup in our algorithm stems from the usage of estimation of & norms and inner products. While the use of sampling techniques can indeed provide inner product estimations, they retain the same (11/=²) dependency instead of the (1/EE) dependency of QAE. Hence, our algorithm performance may be hard to replicate in classical settings.
On the other hand, while it has been suggested that the computation of market equilibrium may benefit from low-rank approximations [15], methods of using such properties to accelerate the computation of gradients have not been proposed, given that the update of the PR dynamics rely on element- wise multiplication of matrices instead matrix multiplication. This would suggest that using sampling techniques to accelerate updates would be similarly difficult.
Practicality. Our quantum algorithm relies mostly on the QAE subroutine to achieve quantum speedups. In its original formulation, QAE involves the usage of QPE subroutine, which requires multiple controlled unitaries and the quantum Fourier transform [70]. QAE is thus regarded as fault-tolerant quantum subroutine, whose execution may be beyond the capabilities of current quantum hardware. However, many subtle improvements to the QAE algorithm have since been made after its discovery, such as simplifying subroutines [71 [71-76] or trading circuit depth with speedup factors [75, 77, 78]. Such improvements pave the way for potential implementation of QAE, and by extension, this paper, on next-generation quantum hardware in the early fault-tolerant regime [79, 80].
Potential and limitations for further quantum speedups. Our quantum algorithm shares sim- ilarities to other quantum algorithms that are based on the multiplicative weight update (MWU) method [81, 82]. Such methods have found success in obtaining quantum speedups for LPs [29] and SDPs [30-33], which have been extended to applications such as zero-sum games [29, 83]. quadratic binary optimization [84], and financial applications [35, 85]. Apart from the MWU-esque
PR dynamics, various other methods for computing market equilibrium have also been proposed. Can quantum speedups obtained from these methods exceed those of our quantum algorithm?
Tracing back to the roots of the EG convex program [22, 23] and Shmyrev convex program [57]. it is well known that such programs can be solved in polynomial time with interior-point methods (IPM) [56]. However, as IPMs require using linear solvers as subroutines, and as there is no guarantee of well-conditioned systems, the quantum linear systems solver [37, 86] may not provide significant speedup. Therefore, it may be unlikely that quantum IPMs [87] can provide significant speedups.
First-order methods such as the Frank-Wolff (FW) algorithm [88] and projected gradient descent (PGD) have also been discussed as candidates for solving market equilibrium [26], with PGD achieving linear convergence classically. While PGD obtains superior asymptotic convergence rate in terms of the error compared to PR dynamics, as our quantum speedups stem from faster computations of results within a single iteration, it may be harder to find such speedups for PGD as there has been no evidence for quantum speedups in projections onto a simplex (89, 90] as required.
On the other hand, the FW algorithm has been shown to provide quantum speedups for regression [91, 92]. However, convergence results of FW [93, 94] show that (bb(T)) ((b²) < Cs C+ can be shown to be (n) by computing relevant values. The number of iterations T required for convergence to additive error is then O(x) as compared to O log m of PR dynamics. This matches the results of Gao and Kroer [26], which show that FW has slow convergence empirically for market equilibrium computation. Prior no-go results suggest that quantum algorithms cannot provide speedups for 7 when 7 is independent of the problem dimension [95, 96]. Assuming no quantum speedups in T. given the ((n) upper bound the FW algorithm, the quantum algorithm based on FW can potentially have higher dependency on n than the classical PR dynamics.
(T+2)) where
10

---

Acknowledgments and Disclosure of Funding
The authors thank Gregory Kang Ruey Lau, Jinge Bao, and Warut Suksompong for discussions. This work is supported by the National Research Foundation, Singapore, and A under its CQT Bridging Grant and its Quantum Engineering Programme under grant NRF2021-0EPP200-P5.
References
[1] K. J. Arrow, An extension of the basic theorems of classical welfare economics, in Proceedings of the Second Berkeley Symposium Mathematical Statistics and Probability, Berkeley Symp. Math. Statist. and Prob (University of California Press, Berkeley, California, USA, 1951) pp. 507-532.
[2] G. Debreu, The coefficient of resource utilization, Econometrica 19, 273 (1951).
[3] K. J. Arrow and G. Debreu, Existence of equilibrium for a competitive economy, Econometrica 22, 265 (1954).
[4] V. V. Vazirami, Combinatorial algorithms for market equilibria, in Algorithmic Game Theory, edited by
N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (Cambridge University Press, 2007) p. 103-134.
[5] B. Codenotti and K. Varadarajan, Computation of market equilibria by convex programming, in Algorithmic Game Theory, edited by N. Nisan, Roughgarden, Tardos, and V. Vazirani (Cambridge University Press, 2007) p. 135-158.
[6] A. Mas-Colell, M. D. Whinston, and J. R. Green, Equilibrium and its basic welfare properties, in Microe- conomic theory (Oxford Univ. Press, 1995) Chap. 16.
[7] D. K. Foley, Resource allocation and the public sector, Ph.D. thesis, Yale University (1967).
[8] H. R. Varian, Equity, envy, and efficiency, J. Econ. Theory 9, 63-91 (1974).
[9] C. Kroer and N. E. Stier-Moses, Market equilibrium models in large-scale internet markets, in Springer Series in Supply Chain Management (Springer International Publishing, 2021) p. 147-189.
[10] V. Conitzer, C. Kroer, D. Panigrahi. Schrijvers, E. Stier-Moses, Sodomka, and A. Wilkens, Pacing equilibrium in first price auction markets, Manag. Sci. 68, 8515 8535 (2022).
[11] A. Othman, T. Sandholm, and E. Budish, Finding approximate competitive equilibria: efficient and fair course allocation, in Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: Volume 1 Volume 1, AAMAS '10 (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, 2010) p. 873-880.
[12] E. Budish, G. Cachon, B. Kessler, and Othman, Course match: large-scale implementation of approximate competitive equilibrium from equal incomes for combinatorial allocation, Oper. Res. 65, 114-336 (2017).
[13] M. Babaioff, N. Nisan, and I. Talgam- Fair allocation through competitive equilibrium from generic incomes, in Proceedings the Conference Fairness, Accouniability, and Transparency, FAT '19 (Association for Computing Machinery, New York, NY, USA, 2019) p. 180.
[14] S. Im, J. Kulkarni, K. Munagala, Competitive algorithms from competitive equilibria: Non-clairvoyant scheduling under polyhedral constraints, J. ACM 65 (2017).
[15] C. Kroer, A. Pcysakhovich, E. Sodomka, and N. E. Sticr-Moses, Computing large market equilibria using abstractions, Oper. Res. 70, 329-351 (2022).
[16] I. Fisher, Mathematical investigations in the theory value and prices, Ph.D. thesis, Yale University (1891).
[17] Brainard and H. E. Scarf, How to compute equilibrium prices in 1891, Am. Econ. Sociol. 64. 57-83 (2005).
[18] H. E. Scarf, The core of an person game, Econometrica 35, 50 (1967).
[19] N. R. Devanur, C. H. Papadimitriou. A. Saberi, and V. V. Vazirani, Market equilibrium via primal-dum dual algorithm for convex program, J. ACM 55 (2008).

---

[20] J. B. Orlin, Improved algorithms for computing Fisher's market clearing prices. in Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC' '10 (Association for Computing Machinery, New York, NY, USA, 2010) p. 291-300.
[21] I. A. Végh, Strongly polynomial algorithm for class of minimum-cost flow problems with separable convex objectives, in Proceedings of the Foury-hourth Annual ACM Symposian on Theory of Computing, STOC '2 (Association for Computing Machinery, New York, NY. USA, 2012) p. 27-40.
[22] E. Eisenberg and D. Gale, Consensus of subjective probabilities: The pari-mutuel method, Ann, Math. Stat. 30, 165-166, (1959).
[23] E. Eisenberg, Aggregation of utility functions, Manag, Sci. 7, 337-350 (1961).
[24] F. Wu and L. Zhang, Proportional response dynamics leads to market equilibrium, in Proceedings of the Thirty- Ninrt Anmual ACM Symposium on Theory of Computing, STOC '07 (Association for Computing Machinery, New York, NY, USA, 2007) p. 154-363.
[25] L. Zhang, Proportional response dynamics in the Fisher market, Theor. Comput. Sci. 412, 2691-26999 (2011).
[26] Y. Gao and C. Kroer, First-order methods for large-scale market equilibrium computation, in Advances in Neural Information Processing Systems, Vol. 33, edited by H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (Curran Associates, Inc., 2020) pp. 21738-21750.
[27] M. A. Nielsen and L. Chuang, Quantum Computation and Quantion Information (Cambridge University Press, 2010).
[28] A. Abbas, A. Amhainis, B. Augustino, A. Bärtschi, H. Buhrman, C. Coffrin, G. Cortiana, V. Dunjko, D. J. Egger, B. G. Elmegreen, N. Franco, F. Fratini, B. Fuller, J. Gacon, C. Gonciulea, S. Gribling. S. Gupta, S. Hadfield, R. Heese. G. Kircher. T. Kleinert, T. Koch, G. Korpas, S. Lenk, J. Marecek, V. Markov, G. Mazzola, S. Mensa, N. Mohseni, G. Nannicini, C. O'Meara, E. P. Tapia, S. Pokutta, M. Proissl, P. Rebentrost, E. Sahin, B. B. Symons, S. Tornow, V. Valls, S. Woemnr, M. L. Wolf-Bauwens. J. Yard,
S. Yarkoni, D. Zechiel, S. Zhuk, and C. Zoufal, Challenges and opportunitics in quantum optimization, Nat. Rev. Phys. (2024).
[29] van Apeldoor and A. Gilyén, Quantum algorithms for zero-sum games (2019), wtXiv:1904.0313. [quant-ph].
[30] F. G. S. I., Brandão and K. M. Svore, Quantum speed-ups for solving semidefinite programs, in 2017 IEFE 58th Annual Symposium on Foundations of Computer Science (FOCS) (IEEE Computer Society, Los Alamitos, CA, USA, 2017) pp. 415-426.
[31] F. G. S. Brandão, A. Kalev, T. Li. C. Y.-Y. Lin, K. M. Svore, and X. Wu, Quantum SDP solvers: Large speed-ups, optimality, and applications to quantum learning, in 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Leibniz International Proceedings in Informatics (LIPlcs), Vol. 132, edited by C. Baier, I. Chatzigiannakis, P. Flocchini, and S. Leonardi (Schloss Dagstuhl- Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2019) pp. 27:1-27:14.
[32] J. van Apeldoom and A. Gilyén, Improvements in quantum sol-son with applications, in 46th International Colloquiun on Automata, Languages. and Programming (ICALP 2019), Leibniz International Proceedings in Informatics (LIPles), Vol. 132, edited by Baier, Chatzigiannakis, Flocchini. and S. Leonardi (Schloss Dagstuhl Leitniz-Zeetuum für Informatik, Dagstuhl, Germany, 2019) pp. 99:1- 99:15.
[33] van Apeldoorn, Gilyén, S. Gribling, and R. de Wolf, Quantum SDP-solvers: Better upper and lower bounds, Quantum 4, 230 (2020).
[34] T. Li, S. Chakrabarti, and X. Wu, Sublinear quantum algorithms for training linear and kernel-based classifiers. in Proceedings of the 36th International Conference on Machine Learning. Proceedings of Machine Learning Research, Vol. 97, edited by K. Chaudhuri and R. Salakhutdinov (PMLR, 2019) pp. 3815-3824.
[35] P. Rebentrost, Y. Hamoudi, M. Ray, X. Wang, S. Yang, and M. Santha, Quantum algorithms for hedging and the learning of Ising models, Phys. Rev. A 103, 012418 (2021).
[36] Kerenidis and A. Prakash. Quantum recommendation systems, in Innovations in Theoretical Computer Science Conference (ITCS 2017), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 67, edited by C. H. Papadimitriou (Schloss Dagstuhl Zentrum für Informatik, Dagstuhl, Germany, 2017)
pp. 49:1-49:22 14:211.
12

---

[37] A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum algorithm for linear systems of equations, Phys. Rev. Lett. 103, 150502 (2009).
[38] S. Aaronson, Read the fine print, Nat. Phys. 11, 2 (2015).
[39] A. Montanaro, Quantum algorithms: overview, upj Quantum Inf. 2 (2016).
[40] A. M. Dalzell, S. McArdle, M. Berta, P. Bienias, C.-F. Chen, A. Gilyén, C. T. Hann, M. J. Kastoryano, E. T. Khabiboulline, A. Kubíca, G. Salton, S. Wang, and F. G. Brandão, Quantum algorithms: A survey of [quant-ph].
applications and and-to-end complexities (2023), arXiv:2310.002
[41] G. Brassard, P. Høyer, M. Mosca, and A. Tapp, Quantum amplitude amplification and estimation, in Quantum computation and information, Contemporary Mathematics, Vol. 305 (American Mathematical Society, Providence, RI, USA, 2002) pp. 53-74.
[42] A. Y. Kitaev, Quantum measurements and the Abelian stabilizer problem (1995), arXiviquant-p//99 1026 [quant-ph].
[43] A. Montanaro, Quantum speedup of Monte Carlo methods, Proc. Soc. A: Math. Phys. Eng. Sei. 471, 201 50350301 (2015).
[44] V. Vedral, Barenco, and A. Ekert, Quantum networks for elementary arithmetic operations, Phys. Rev. A 54, 147-153 (1996).
[45] Y. Takahashi, Quantum arithmetic circuits: A survey, IEICE Trans. Fundam. Electron, Commun. Comput. Sci. E92-A, 1276-1283 (2009).
[46] P. L.. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Math. Comput. 48, 243-264 (1987).
[47] M. Born, Zur Quantenmechanik der Stoßvorgääge, Z. Physik 37, 863-867 (1926).
[48] G. Kuperberg. Another subexponential-time quantum algorithm for the dihedral hidden subgroup problem, in 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013), Leibniz International Procesdings in Informatics (LIPles), Vol. 22 (Schloss Dagstuhl Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2013) pp. 20 34.
[49] S. Jaques and A. G. Rattew, QRAM: A survey and critique (2023), arXiv:2305. 10310 [quant-ph].
[50] R. Babbush, C. Gidney, D. W. Berry, N. Wiebe, J. McClean, A. Paler, A. Fowler, and H. Neven, Encoding electronic spectra in quantum circuits with linear T complexity, Phys. Rev. X 8, 041015 (2018).
[51] A. Amhainis, Quantum walk algorithm for element distinctness, SIAM J. Comput. 37, 210-239 (2007).
[52] V. Giovannetti, S. Lloyd, and L. Maccone, Quantum random access memory, Phys. Rev. Lett. 100, 160501 (2008).
[53] V. Giovannetti, S. Lloyd, and I.. Maccone, Architectures for quantum random access memory, Phys. Rev. 78, 052310 (2008).
[54] L. Grover and Rudolph, Creating superpositions that correspond to efficiently integrable probability distributions (2002), www::quuntttp/000000 12 [quant-ph].
[55] K. Jain and V. V. Vazirani, Eisenherg-Gale markets: Algorithms and game-theoretic properties, Games Econ. Behav. 70, 84-106 (2010).
[56] S. Boyd and L. Vandenberghe, Interior-point methods, in Convex Optimization (Cambridge University Press, 2004) p. 561-630.
[57] V. I. Shmyrev, An algorithm for finding equilibrium in the linear exchange model with fixed budgets, J. Appl. Ind. Math. 3. 518 (2009).
[58] D. Levin. K. LaCurts, N. Spring, and Bhattacharjee, Bittorrent an auction: Analyzing and improving bittorrent's 's incentives, SIGCOMM Comput. Commun. Rev. 38, 243-254 (2008).
[59] B. Birnbau, N. R. Devanur, and L. Xiao, Distributed algorithms via gradient descent for Fisher markets, in Proceedings of the 12th ACM Conference on Electronic Commerce, EC '1 (Association for Computing Machinery, New York, NY, USA, 2011) p. 127-136.
13

---

[60] A. S. Nemirovsky and D. B. Yudin, Problem complexity and method efficiency in optimization (Wiley. 1983).
[61] A. Beck and M. Teboulle, Mirror descent and nonlinear projected subgradient methods for convex opti- mization, Oper. Res. Lett. 31, 167- 175 (2003).
[62] L. Bregman, The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming, USSR Comput. Math. Math. Phys. 7, 200-217 (1967).
[63] S. Kullback and R. A. Leibler, On information and sufficiency, Ann. Math. Stat. 22, 79-89988 86 (1951).
[64] G. Boole, The Mathematical Analysis of Logic (Cambridge University Press, 1847).
[65] Y. K. Cheung, S. Leonardos, and G. Piliouras, Learning in markets: Greed lcads to chaos but following the price is right, in Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, 21, edited by Z.-H. Zhou (International Joint Conferences Artificial Intelligence Organization, 2021) pp. 111-117.
[66] E. Tang, quantum-inspired classical algorithm for recommendation systems, Proceedings the 5 Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 (Association for Computing Machinery, New York, NY, USA, 2019) p. 217-228.
[67] J. M. Arrazola, A. Delgado, B. R. Bardhan, and S. Lloyd, Quantum-inspired algorithms in practice, Quantum 4, 307 (2020).
[68] E. Tang, Quantum principal component analysis only achieves exponential speedup because of its state preparation assumptions, Phys. Rev. Lett. 127, 060503 (2021).
[69] N.-H. Chia, A. P. Gilyén, T. Li, H.-H. Lin, E. Tang, and C. Wang, Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning. J. ACM 69 (2022).
[70] D. Coppersmith, An approximate Fourier trunsform useful quantum factoring. Tech. Rep. (IBM Research Division, 1994).
[71] Y. Suzuki, S. Uno, R. Raymond, T. Tanaka, T. Onodera, and N. Yamamoto, Amplitude estimation without phase estimation, Quantum Inf. Process. 19 (2020).
[72] D. Grinko, J. Gacon, C. Zoufal, and S. Woemner, Iterative quantum amplitude estimation, npj Quantum Inf. (2021).
[73] K. Nakaji, Faster amplitude estimation, Quantum Inf. Comput. 20, 1109 1123 (2020).
[74] S. Aaronson and P. Rall, Quantum approximate counting, simplified, in Symposium Simplicity in Algorithms (Socicty for Industrial and Applied Mathematics, 2020) p. 24-32.
[75] P. Rall and Fuller, Amplitude estimation from quantum signal processing, Quantum 7, 937 (2023).
[76] F. Labib, B. D. Clader, N. Stamatopoulos, and W. J. Zeng, Quantum amplitude estimation from classical signal processing (2024), arXiv:2405.1465 14697 [quant-ph].
[77] T. Giurgica- Tiron, I. Kerenidis, F. Labib, A. Prakash, and W. Zeng, Low depth algorithms for quantum amplitude estimation, Quantum 6, 745 (2022).
[78] D.-L. Vu, B. Cheng, and P. Rehentrost, Low depth amplitude estimation without really trying (2024), #xXiv:2400.0119 [quant-ph].
[79] E. T. Campbell, Early fault-tolerant simulations of the Hubbard model, Quantum Sci. Technol. 7, 015007 (2021).
[80] A. Katabarwa, K. Gratsea, A. Caesura, and P. D. Johnson, Early fault-tolerant quantum computing, PRX Quantum 020101 (2024).
[81] S. Arora, E. Hazan, and Kale, Fast algorithus for approximate semidefinite programming using the multiplicative weights update method, in 46th Anmual IEEE Symposium on Foundations of Computer Science (5) (2005) pp. 339-348.
[82] S. Arora, E. Hazan, and S. Kale, The multiplicative weights update method: a meta-algorithm and applications, Theory Comput. 8, 121-164 (2012).
14

---

[83] R. Jain, G. Piliouras, and R. Sim, Matrix multiplicative weights updates in quantum zero-sum games: Conservation laws & recurrence, in Advances in Neural Information Processing Systems, Vol. 35, edited by Koyejo, Mohamed, A, Agarwal, D. Belgrave, K. Cho, and A. Oh (Curran Associates, Inc., 2022) pp. 1123-4135.
[84] F. G.S L. Brandão, Kueng, and D. Stilek França, Faster quantum and classical SDP approximations for quadratic binary optimization, Quantum 6, 625 (2022).
[85] D. Lim and P. Rebentrost, A quantum online portfolio optimization algorithm, Quantum Inf. Process, 23 (2024).
[86] A. M. Childs, Kothari, and R. D. Somma, Quantum algorithm for systems of linear equations with exponentially improved dependence on precision, SIAM J. Comput. 46, 1920-1950 (2017).
[87] Kerenidis and A. Prakash, quantum interior point method for LPs and SDPs, ACM Trans. Quantum Comput. (2020).
[88]
Frank and Wolfe, An algorithm quadratic programming, Nav. Res. Logist. 3.3, 95-110-11 (1956).
[89] J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra, Efficient projections onto the f--hall for learning in high dimensions, in Proceedings of 25th International Conference on Machine Learning, ICML '08 (Association for Computing Machinery, New York, NY, USA, 2008) p. 272-279.
[90] L. Condat, Fast projection onto the simplex and the & ball, Math. Program. 158, 575-585 (2015).
[91] Y. Du, M.-H. Hsich, T. Liu, You, and D. Tao, Quantum differentially private sparse regression learning, IEEE Trans. Inf. Theory 68, 5217-5233 (2022).
[92] Y. Chen and R. de Wolf, Quantum algorithms and lower bounds for linear regression with norm constraints, in 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), Leibniz International Proceedings in Informatics (LIPlcs), Vol. 261, edited by K. Etessami, U. Feige, and G. Puppis (Schloss Dagstuhl Leibniz Zentrrum für Informatik, Dagstuhl, Germany, 2023) pp. 38:1-38:21.
[93] K. L. Clarkson, Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm, ACM Trans. Algorithms 6 (2010).
[94] M. Jaggi, Revisiting Frank-Wolfe: Projection-fres sparse convex optimization, in Proceedings of the 30th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 28, edited by S. Dasgupta and D. McAllester (PMLR, Atlanta, Georgia, USA, 2013) pp. 427-435.
[95] A. Garg, R. Kothari, P. Netrapalli, and S. Sherif, No quantum speedup over gradient descent for non- smooth convex optimization, in 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), Leibniz International Proceedings in Informaties (LIPIcs). Vol. 185, edited by J. R. Lee (Schloss Dagstuhl Leibniz-Zentrum für Informaiik, Dagstuhl, Germany, 2021) pp. 53:1-53:20.
[96] A. Garg, R. Kothari, Netrapalli, and S. Sherif, Near-optimal lower bounds for convex optimization for all orders of smoothness, in Advances in Neural Information Processing Systems, Vol. 34, edited by M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan (Curran Associates, Inc., 2021) pp. 29874 298844.
[97] M. R. Jerrum, L. G. Valiant, and V. V. Vazirani, Random generation of combinatorial structures from a uniform distribution, Theor. Comput. Sci. 43, 169-188 (1986).
[98] C. Dur and P. Høyer, A quantum algorithm for finding the minimum (1996), wxXiv:quant-ph/966701 [quant-ph].
[99] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang, Z. DeVito, M. Raison, A. Tejani, S. Chilamkurthy, B. Steiner, L. Fang, Bai, and S. Chintala, PyTorch: An imperative style, high performnree deep learning library, in Advances Neural Information Processing Systems, Vol. 32, edited by H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buc, E. Fox, and R. Gameet (Curran Associates, Inc., 2019).
15

---

A Quantum subroutines
In this section, show prior results that obtain & norms and inner products with quadratic speedups with QAE.
Lemma A.1 (Quantum state preparation and norm estimation; Lemma 5, [35]), Let n N. We are given quantum query access to non-zero vector w E I", with max, Wj = 1.
1 1. There exists quantum circuit that prepares the state va Ej=1 (vuj (0) + vI w/ (1)) with two queries and O (log gates.
Let > O and ò E (0, 1). There exists a quantum algorithm that provides an estimate Iw of the 4-norm ||w|| such that |||/|| - ww S =||w|],, with probability at least 1 - 8. The algorithm
requires O y log }) queries and ò v log quantum gates.
Proof. We reiterate the proof of Lemma 5 in [35] for the convenience of the reader.
1. First, using Ologg) Hadamard gates, prepare the state v 1ブ) Then, by quantum query access to w, obtain J Ei= (5) (my)- By controlled rotation gates, we can then ob- tain v Eー=ıb> (wy) (vTn (0) + vI- wy [1)). By another quantum query access to w, can uncompute the intermediate registers and obtain J Eÿ=1 15) TT (0) + -1 wy (1)).
2. First observe that that with projector P In @ [0)(0] and (v) t Ei=1 (5) (/w, 10)
VI=w) wy [1)), one can obtain estimate
||P 11
Iwll Setting M z da Vn, we obtain an
n
Va(1 a) x² 8 M
(2va+ + E ) - 3
V
Lestt al S 2T
2n S (A.1)
M 6
6
with probability at least S.. Using the powering lemma [97]. we can boost the success probability to d by taking the median of O(log }) runs the QAE algorithm.
Remark A.I.I. Note that Lemma A. has the requirement that max, w, = For cases where this not the case, we can use maximum finding algorithm to divide all entries by the largest value. Such can be achieved by the following quantum maxiimmmmmxximum finding algorithm O( (n)) runtime, which we introduce below. Recall that division takes (1) runtime with quantum arithmetic circuits. Lemma A.2 (Quantum minimum finding; Theorem 1, [98]). Let E N. Given quantum query access to non-zero vector w E I", we can find the minimum Wmin = minje[n] Wy with success probability
1- 8 with O (vTo log 4) queries and Ô (Vī log 1) quantum gates.
Corollary A.2.1 (Quantum maximum finding). Let n E N. Given quantuum query access to non-zero vector I" we can find the maximum Wmax maxje(() Wj with success probability 1 8 with O (Vrilog })) queries and (Vn log }) quantum gates.
Below we present a quantum inner product estimation algorithm simplified from Lemma 6 of [35]. Lemma A.3 (Quantum inner product estimation with relative accuracy). Let E N, E < 0 and 8 E 1). We are given quantum query access to two vectors u, v E I An estimate T uu for the inner product can be provided such that [uu, ul < u e with success probability 1 8. This
estimate is obtained with O y log b) queries and Ô y log 1 } quantum gates.
Proof. Using quantum arithmetic circuits, we can obtain 2, = u Uj. i.e., 2 u v. by the following:
(o) - 1o)) (uz) (1y) + (5) (2,) (12)) - (b) |m,) 10)
(A.2)
6/2, we can then obtain 2z/ 33/2max- Lastly, using Lemma 1. we can obtain T.... = r such that aT.. u vl =
Using quantum maximum finding in Corollary A.2.1 to find Zmax up to probability
[ - |=|||| S eu e up to probability - 8/2. Using a union bound [64], we find the total success probability of the entire process is 1 8.
16

---

B Convergence guarantees for the PR dynamics
We show the convergence guarantee of the proportional response (PR) dynamics in regards the Eisenberg-Gaid Gale convex program by Zhang [25] and improved upon by Birnbaum et al. [59], and the convergence in regards to the Shmyrev convex program, first shown also by Birbbuum al. [59]. Recall that the negative target function from the Eisenberg- Gale convex program is
((b)
Σ iE(n]
B, log Us
(B.1)
and the negative target function from the Shmyrev convex program is
w (b)
Σ
bis log
Vij
(B.2)
Pj
(E(M].E[m)
We first set up the following convex set:
B = b DE Mnxm(R4)
boy B
(B.3)
3
To show the convergence of the PR dynamics, first need the following inequalities:
Lemma B.I. Let b* arg mingeg (b). Then x(b*) ((b) Eiejn] B, log B,.
Proof. Recall that the price Pj is the dual variable of the constraint may for the Eisenberg-Gaie convex program, and that u, = Ej DzjViy- By the KKT stationarity constraint, we see that
a doy
Σ B, log + Σpj
Σ Kay -ay-1)
Biyij U
+ Pj
(B.4)
from which we can infer that Benyy = pj and show x(b') = V((b)) - Eie(n) Bi log Br. We have that,
((b²) =
Σ KE[N]
B, log u
Σ
by log
=-
Σ
big log B, Uij
(B.5)
sE [E(m
iE|m],jE(m]
bi log
Ujj pj
Σ
lo B, v((b)
B, log B,
(B.6)
#EIn].JE[m]
sE[n]
iE ml
Lemma B.2 (Lemma 19, (59]). vb E B, (bb) < (bb) - -ie(jn) B, log B,.
Proof. We reiterate the proof of Lemma 19 in [59] for the convenience of the reader. By convexity of log we see that,
bij m4
(bb =
Σ
Bg log u; =
Σ
Bg log
(B.7)
Pj
kE(n]
:E(m]
[m)]
bij Uij
Σ
B₁ log
log B,
(B.8)
B, Pj
iE/ml
jE/ml
TE|m]
<
Σ
bij
B, log
Vij
B, log B;
(B.9)
B.
Pj
<E(m)
(bb Σ
B, log B,
(B.10)
kE(m
17

---

byju//ps
Lemma B.3. Let Vig B,
Then Ab E B, (b) S (b(b) + Eie(n) Bi log Bi.
ui
Proof. Let p/ = Ei b/j. By concavity of log:
P1
v(6)) -
Usg log
B₁
log
(B.11)
Vij
Vig
(E|m],JE[m]
(E(M).JE(m)
B log
beyU Pp 1/3
Σ
B,
1
(B.12)
U4
Vij
Ui
Pj
2E|m]
jE/m]
iE(n)
JE(m
bisp's
Σ
B₁ log
Σ
By log us +
Σ
B, log Bi
(B.13)
BiPj
.E[n]
JELm]
EE(n]
sE|m]
bypp
S log
Σ
B, log us +
Σ
B, log B;
(B.14)
Pj
(e(m).Je(m (m)
(c(n)
iE|n]
log
Σ ph
B₁ log u4
B, log B
(B.15)
jElm)
iE(m]
iE(M)
=b) +
Σ
B, log B,
(B.16)
<E(n)
From the above two lemmas, we gain the monotonically decreasing properties of iteratively updating b via the PR dynamics on the negative target functions of the Eisenberg- and Shmyrev convex programs:
Lemma B.4. A1 1 0, ((((+1) < ((b()).
Proof. Apply Lemma B.2 and Lemma B.3 consequently.
Corollary B.4.1 (Lemma 5, [59]). 11 2 0, v(((++1) < (b(())
We now use the following lemmas to construct an end-to-end proof of the convergence of the PR dynamics. In slight abuse of notation, adapt the definition of KL divergence to matrices such that for u, U E M(R pxx. let D(ullv) == E'elp.eel Ui log lii, The following can then be shown:
Lemma B.5. Vt 2 O, Σt (b(()) +bb))) ((b*)(()))
Proof. Similar by the proof of Theorem 3 of [25], we first lower bound A, D(b*)1b(0) D(b ((((+1)) as follows:
A. = -(bb11b0) D(b" (1(+1))
(B.
(1-1) bi log
bi log Baysy 1 (1) Pj u;
Σ
Σ SE(m].E[(m]
(B.18)
(1)
(E(m).J[[m]
ig
Σ [E(m)JE[m]
big log
Vij
+ big
log
D
big log ut + big log B,
(B.19)
Dj
Pj
(1)
big log
Vij +
Σ
Pj log
p2
B, log u + Σ
B, log B
(B.20)
[E[m).[[m]
P
%E[m)
Pj
kE[m]
<c(n]
= =-b(b") + D(pi11, + (1) +
Σ
B, log B
(B.21)
TE(m]
= -(pi)lo5)) (0)) + ((b(t)) 2bb²)
(B.22)
18

---

2 ((b()) (bb")
(B.23)
where the second-to-last equality is by Lemma B.1 and the inequality is by the positivity of KL. divergence. Taking the telescoping sum of A, we see that
T
Σ t=0
Σ D(b
- D(6 = -
(o((()) (b"))
(B.24)
Hence, we obtain Σ (D(b1)) ((b*)) 2 (bb'))
Proposition B.6. Vt 2 0, (b(TT1)) - ((b)) < D(b'))1)1)
Proof. Combining Lemma B.4 and Lemma B.5, can write
T Σ
((1()) D(b)) S 1660)
-167-11)-(00 -
(B.25)
T
t=
Corollary B.6.1 (Lemma 3, [59]). Vt 2 0, (bb(T) ((bb) lbb')
Proof. Apply Lemma B.3 to Proposition B.6.
Lastly, we can upper bound the value D( (16)) in terms of dimensions m and n given that each buyer initially divides the budget equally between all items such that 6/)
Lemma B.7 (Lemma 13, [59]; Theorem 7, [26]). If 1b log m.
B. for all and j. then D(b*lb(()) s
m
Proof. Evaluating D(b*l16(0) we have
by
mb; B;
log b
D(b*)1/0))-
Σ
big log
big
log
log m +
Σ ij
big
S log m, (B.26)
B
ij
as b < B, and log Mi B, is negative.
Plugging Lemma B.7 into Proposition B.6 and Corollary B.6.1, we obtain the convergence guarantee of Theorem
C Convergence guarantees for the FPR dynamics
In this section, we prove the convergence guarantee of the faulty proportional response (FPR) dynamies. We first examine the immediate effects of allowing erroneous estimations of u and p
in the FPR dynamics. Let (((() = [m B Note that B.dh * B, as the normalization step of constructing dig is erroneous. By the construction ((0) by the FPR dynamics,
1)--1)
B
Uij
(C.1)
p
we can find that
Σ
Σ
B
(t-1)
(1-1)
B
Uij
itt
(t-1)
(1-1)
ij
(t-1)
(111)
(C.2)
[m(m)
jE(m]
3E(m]
1
where we can obtain the following inequality by definition of i;;
B
B
<
(1)
<
(C.3)
1 1
1 E,
19

---

By summing B,, we find that
Σ
10
Σ Je|m]
19 1 Pj
(C.4)
I+ Sv
1 Ev
sE/n]
We now prove Theorem 3.
Theorem 3 (Convergence of the FPR dynamics). Considering a linear Fisher market, for by) as iteratively defined by the faulty proportional response dynamics where 8 B, we have
1)
min $(b10) (bb)) < 2
T
when E, S 8T
and Ep S
log 67
Proof. Similar to the proof of Lemma B.5, we first lower bound Å. = -EE(n))e(m
by by log go
bi where we use as follows:
Eie())aE(m) bi log gett
1(++1
Bavsj (10) (1)
A E
big log
bi log
(C.5)
((0)
iE [m)
iE
(E(M)JJ((m) [m]]
Pj
Σ
big log
Usi
big log
P3
bi log v.00 + big log B₁
(C.6)
[E(m],E[mm]
P3
Dj
(t)
Σ
big log
Mij pj
+
Σ
pj log
P
Σ
B, log log
+
Σ NEim]
B, log B
(C.7)
jE[m]
se|m]
((b") +
Pj
log
P
(1)
Σ
B, log 1
(C.8)
jE[m)
(E(M)
We now lower bound the second and third terms from the above individually as follows. Starting with the second term,
(e)
P (1)
P
Σ Pj log jE(m)
Σ
[m]
Pj
log
Dj
(1)
Σ
E
Dj
+
je(m)
Pj
log
P
(1)
je(m)
Σ
log
f'E(m)
Σ
(C.9)
D/1
(t)
D
+
Σ
Pj
log
log
Σ
Pj
(t)
(C.10)
Σ j' j'Elm (m) D
jE(m)
D3
JE(m)
(1))
1
D
Pj
+
Pj log
loog
(C.11)
Σ E'r Elm) D
1 + Ep
1 Ev
jE[m]
p
2 D
p)
28, 2 -6p 28v
(C.12)
Σ Ey'(m [im] Dg
Moving on the the third term,
(1)
Σ
B, log 1:(0
= Σ
B, log log 1050)
Σ
B, log
(C.13)
D
(t)
(E(M)
vE(n)
1E|n]
Σ kE(n)
B, log D
Σ
B, log + Ev)
(C.14)
iE|n]
(
((0) if
=
B, log
log(1 + Ev)
(C.15)
(E(m)
jE(m]
Pj
20

---

1igbiy ((0
2 Σ
B₁ log
E
-log(1 + Ev)
(C.16)
1 - Ep
Pj
jE[m]
Vigl
((6)
B₁ log Σ
+ log(1 - Ep) - -log(1 + t.)
(C.17)
VE(M)
je(m)
Dj
2 $(b(t))
28p Ev
(C.18)
Hence, in total, we find that
((++1)
Å =
Σ
big log
2 +(((t)) - -((b") - -3cp - -Ee--
(C.19)
((0)
EE SEinJJi mm]
1
Taking the telescoping sum of Å., we see that
b
T
Σ
big log
Σ
bi log
Σ ((b)))))(b))) 3Ep 38v)
((+1)
RE[M].JE[m]
ij
iEIn],E[mm]
1=0
(C.20)
Taking the upper bound of > h=
Åo we obtain
T
bi
6i big log
A =
Σ
bi log
Σ
(C.21)
(0)
((++1) B
t=0
JE[m]
[E(m].E(m)
bi by log
b
Σ
Σ (E(M).JE(m)
bi log ((+11)
(C.22)
(0)
((++1)
(E(m)
Σ KE (E
big log PElN)
Σ
g(++1)
((++
= D(b")1(0)) - D
6²
+ log
Σ
j(++1)
(C.23)
g(++1) Σ Eeeln))E D'y" 1(++1)
s D(b11110)) - D
6-
+ log(1 + 6x)
(C.24)
Σ Eve(n),ee(m "3'
S D(b +
(C.25)
+3T Hence, we obtain Σ (x((1)) ()(())))(bb))) - +3T 4)E, (3T + 3).. Instead of T, we plug in T to obtain
( ((b')) < D(bb(1b(0) + (3T + 1)E, + 3T
(C.26)
With a simple observation that
T min
4166))
((66))))(11))
(C.27)
TE
we find
D(b*1100 (b(0))
min T
(1(()))) -
T + 48, + 35p
(C.28)
From Lemma B.7, know that (bb* (1(0)) log m. Then by setting eu we obtain
log m ST
and Ep < log
2 log
min ((((t) +(b²) 5
(C.29)
tE[T]
T
21

---

Next, we prove Theorem 4.
Theorem 4. Considering a linear Fisher market, for bij as iteratively defined by the faulty propor-
tional response dynamics where (10) ij m
B._ Let t* = arg (e Eie(n) B, log a!!) Then
{b $(b*)=
when S
log m and Ep I ST
log m 61
Proof. We slightly modify the proof of Theorem 3, and note that by Equation (C.8) and Equa- tion (C.12), we have
Å = ((b') +
Pj
log
B, log E 2 -bbb") - E -25
Σ
B, log (1)
jE(m]
Pj
(E(n]
<c(n]
(C.30)
Taking the telescoping sum and the upper bound from Equation (C.25), we obtain
T-1
Bi log o - 0(65)
Å + 2T,, + TTp S D(b*)b(0)) + (27 + 1)e, + Tep.
1=
dE [m]
t=
(C.31)
where we can note
D(b0)
min (E[T]
Σ iein
B₁ log ((9) - -b(b))
+ 3e, + Ep-
(C.32)
T
Let 1* = arg min
(- Eiejn) B₁ log (0(0 - ((b))
Then by Equation (C.18), we have the
following:
Σ
B₁ log (1)) 2 +(((1)) - 28p Ev
(C.33)
Then we can obtain
D(b0))((0))
(b(())) - ((b') v
+ 4Ew + 3Ep-
(C.34)
T
Lastly by setting e, S
logu 8T
and Ep S
log 67
we obtain
2 log
((b(t)) 4(b))
(C.35)
T
D Experimental and implementation details
Our experiments are conducted on a single NVIDIA P100 GPU and written with the PyTorch library [99]. The optimal objective value is approximately computed by taking the results of the 1000-th iteration of the PR dynamics.
For the projected gradient descent (PGD) algorithm, our implementation is unlike Gao and Kroer [26), whose task is based on the CEEI scenario where agents are given a unit of fake money and whose end goal is only the allocation. We require information hence our algorithm output should be the bids b. Therefore, instead of formulating the problem after the EG objective function, we mirror? the PR dynamics in its equivalence to mirror descent [59] on the Shmyrev objective function and perform PGD on the latter (see Algorithm 2).
both the allocation and price p,
We formulate the Shmyrev objective function into the following form to obtain convergence guarantees and the step size:
f(x) = h(Ar) + (g.
(D.1)
Pun intended.
22

---

Algorithm 2: Projected Gradient Descent
Input: Budget B, Value v, Learning rate 7, Iterations T
Output: Bids b
Dij
B,
for & 0 to T do
r(())
[1 = b/3 -y. (1 log Usg////) // Gradient step
3
4
for = 10 do
b((++1) Proj(r (0) + fo R T. B,))
// Projection step onto B_i-simplex
6 return ((T)
where a E R" A E Maxn (R),h: (a),( Rd q. R". Considering a flattened vector of the bids we note that if
0
log en
log 612
= n
M(x) = Σ Ty log aq
(D.2)
log Umn
then / Then by Theorem 3 of [26], by setting a learning rate of 7 = 1/L||A/| where L = 1/ min,, p/" we get linear convergence. Note that || = n. Gao and Kroer [26] further provide a line search procedure to set the constant multiplier in the learning rate as well as provide sharper convergence guarantees, but as we only run for 16 iterations, we do not perform the line search and fix the learning rate to initial learning rate that Gao and Kroer [26] use in their empirical studies, which is 1000/L]|A||?
32. We scale down M by the constant factor of 16 to save memory consumption on the GPU, as we simulate QAE by computing the full probability distribution over [M]. We compensate for the loss in accuracy of the estimation by employing the median-of- estimators constructed from the mean means estimator [60], where we take the median perform the maximum finding classically by samples from the QAE subroutine. In addition,
For QAE, we set M T/TTT//
line search in our simulation as opposed to a randomized protocol in the quantum algorithm, whose effects only in regard ignoring the failure possibility.
23

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction state our contribution in proposing quantum
algorithm that provides polynomial speedup in comparison classical algorithms.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We discuss the potential and possible limitations of further quantum speedups in the Discussion section. Further, we state additional assumptions that our quantum algorithm requires in the opening paragraph of Section 4 as well as in the theorem statements.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
24

---

Answer: [Yes]
Justification: We formulate the assumptions required by our theorems directly in the the- orem statement. Further implementation requirements such QRAM also stated and introduced in Sections 2 and 4. The complete proof is shown in Appendix B and C, with proof sketches and intuitions provided in the corresponding main text.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: We state clearly in Section how our input data is randomly generated and how exactly we implement amplitude estimation on classical computers with GPU. The algorithm itself written as step-by-step pseudocode on page 7. We further provide implementation details in Appendix D.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may tricky in some cases, in which case authors welcome describe the particular way they provide for reproducibility.
25

---

In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
We attach the full simulation code the supplementary material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/ gewudeeeCooeeuuiieeeeeeeeee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
//n /nips. cttpp/cccpbbbc/guuuu guwde//dee//eee /CodeSubmis ss onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
We attach the full simulation code in the supplementary material.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: Our experiments are run over 15 iterations to account for randomness of our algorithm. Error bars are present in the attached image as shading.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
26

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: We state the simulation details with software and hardware stated in Appendix
D.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: /ttee///nnuuipeeeeee httpp//p.....ppblltetchhccccceaa
Answer: [Yes]
Justification: The authors have read and noted that this research conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g.. if there special consid- eration due to laws or regulations in their jurisdiction..
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
The authors have discussed the potential applications of this work in Internet- based large-scale markets and its various applications. The work is theory paper on computing market equilibria with quantum computers. We believe there are no negative socictal impacts arising from this work.
Justification:
27

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification:
The authors have properly cited its usage of the Py Pyrocc library in Appendix
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
28

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com comdattasess has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
29

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
30


Reviews:
[{"review_id": "7HdVuoC4jw", "reviewer": "Reviewer_B4u4", "summary": "This paper focuses on market equilibrium computation with linear utility. Traditional algorithms like proportional response (PR) dynamics, despite having nearly linear runtimes relative to the number of buyers and goods, struggle with the massive scale of modern internet-based markets.\n\nThe authors introduce a quantum algorithm to reduce the cost of each iteration of the PR dynamics. They first provide a modified version of the PR dynamics called faulty proportional response (FPR). Leveraging quantum norm and inner product estimation, the algorithm achieves quadratic speedup and reduced memory usage using quantum random access memory (QRAM).", "questions": "None", "limitations": "The authors have discussed the limiations in Section 6.", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "I am not familiar with quantum computing. From the perspective of market equilibrbium computation, the proposed algorithm shows significant improvements in efficiency. Simulation results demonstrate that the algorithm can achieve higher EG object value than PR dynamics within the same number of queries to the value and bidding matrix.", "weaknesses": "I am wondering about the practicality of the algorithm, since we need an accurate valuation profile of all buyers and goods, and the current limitations of quantum hardware pose significant challenges. However, I think this work is still valuable as a theoretical study.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments. \n\n### Access to accurate valuation.\n> I am wondering about the practicality of the algorithm, since we need an accurate valuation profile of all buyers and goods, and the current limitations of quantum hardware pose significant challenges.\n\nOur assumption of having the full valuation profile as part of our input is inherited from the setting of other classical market equilibrium computation algorithms such as Refs. [18] to [21], [25] and [26]. On the other hand, the scenario where there are missing entries in the valuation matrix $v$ has been discussed in Ref [15], where these values are first filled using low-rank reconstruction, and then fed as input to the PR dynamics algorithm. Further, using low-rank reconstructions to construct the $v$ is compatible with the input model of our algorithm, as we can use quantum arithmetic circuits to produce each value in $v$ in superposition. We leave for future quantum algorithm work the settings without the need for the full valuation profile.", "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": "", "extra_scores": {}}, {"review_id": "GBeyeye7xP", "reviewer": "Reviewer_vuEH", "summary": "This paper proposes a quantum-assisted algorithm for market equilibrium computation by first introducing the faulty proportional response dynamics and then constructing its quantum implementation. This algorithm has provable quadratic speedups. Simulation studies show its effectiveness.", "questions": "1.   How  to address the practical limitations posed by current quantum hardware, specifically QRAM? Are there any near-term developments in quantum technology that you believe will make your algorithm more feasible to implement?\n \n2.  The numerical simulations are based on specific conditions and assumptions. How to handle more complex, real-world scenarios that may introduce additional challenges?\n\n3. Quantum hardware is prone to noise and high error rates. How robust is the algorithm to these practical issues?", "limitations": "The limitations have been well discussed in this paper.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper introduces a new version of proportional response dynamics called faulty proportional response (FPR) dynamics, which helps in applying quantum computing techniques effectively.\n\n2. The quantum algorithm provides a significant speedup (quadratic) and uses less memory compared to classical algorithms, thanks to using quantum RAM (QRAM).\n\n3. To the best of my knowledge, this is the first quantum algorithm that achieves sublinear performance in computing market equilibrium.", "weaknesses": "1. The proposed quantum algorithm relies on QRAM, which is not widely available and is still under development. This dependency limits the practical applicability of the algorithm with current quantum hardware.\n\n2.  The numerical simulations provided in the paper are based on specific conditions and assumptions. Real-world scenarios might introduce complexities that are not addressed by the current simulations, potentially affecting the algorithm's performance.\n\n3. The theoretical guarantees of the quantum algorithm's convergence and error bounds are strong, but the practical implementation might face issues with noise and error rates in quantum hardware, affecting the accuracy and reliability of the results.\n\n4. The paper assumes quantum query access to the data without detailing the process of loading classical data into a quantum system. The practical steps and overheads involved in this data preparation are not fully addressed, which could impact the overall efficiency.\n\n5. Minor points.\n\n   - Line 256, \"For our experiments, we generate data the input data $v$\".\n\n   - Figure 1, \"We perform a on $n$ = 16384 buyers\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and concerns. We address the concerns and questions as follows:\n\n### Regarding robustness and additional error terms.\nOur analysis of FPR dynamics is not constrained to error terms stemming from quantum amplitude estimation only but applies to errors from other sources (such as hardware) as well. The update rules FPR are robust to error terms as long as the accumulated sum of the multiplicative error terms for the quantum subroutines across $T$ iterations are restricted to polylogarithmic terms of the input dimensions of $m$ and $n$ as well as sublinear to $T$. Such errors would incur a polylogarithmic multiplicative overhead to the runtime, but the polynomial speedup is still retained. Of course, when the error term is larger than such polylogarithmic factors, the speedup that the algorithm provides will start to decline as the errors grow larger.\n\n### Regarding QRAM.\nWe agree with the reviewer that developments of QRAM  lag behind of developments in quantum computers. QRAM can be potentially used in two parts of our algorithm -- the input data and the storing of intermediate values. Regarding storing intermediate values, our usage of QRAM only requires $O(m+n)$ memory, and we have included the cost of the construction of QRAM as part of the runtime analysis. \n\n### Regarding quantum queries for input data.\nStoring the matrix $v$ both classically and quantumly costs $\\tilde{\\mathcal O}(mn)$. The setting of our paper is that we consider the number of accesses to the data input as the main figure of merit. Similar access models are also used in quantum algorithms for linear programming, semidefinite programming, and matrix algebra, for example, Refs [65] to [69].\n\nNevertheless, as we mention in the paper, there are cases where the encoding of classical values into quantum states can be efficient, in particular, when $v$ is a sparse matrix, or when $v$ can constructed by a low-rank approximation. For example, if $v$ admits a low-rank approximations where the rank $r \\in \\tilde{\\mathcal O}(\\sqrt{\\min(m,n)})$, then one can load the data into QRAM in $\\tilde{\\mathcal O}(\\sqrt{mn\\max(m,n)})$ time using $\\mathcal O(\\sqrt{mn\\max(m,n)})$ memory and construct the full access to elements $v$ with an additional $\\tilde O(r)$ runtime via quantum arithmetic circuits. Such low-rank markets have also been discussed in detail in Ref [25] as well.\n\n### Regarding implementation on current quantum hardware.\nOur algorithm is primarily targeted for quantum computers in the fault-tolerant regime. The usage of QRAM and amplitude estimation is beyond the capabilities of present-day (NISQ) hardware. However, one can replace quantum amplitude estimation using techniques such as Iterative Amplitude Estimation (Ref [34]) or Maximum Likelihood Amplitude Estimation (Ref [33]) to reduce circuit depth. \n\nIn light of the clarifications provided, we sincerely hope the reviewer will reconsider their evaluation.", "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": "", "extra_scores": {}}, {"review_id": "Az2DPwh6a2", "reviewer": "Reviewer_sd1G", "summary": "The paper studies the problem of computing an equilibrium for the Fisher market. Roughly speaking, this is a fractional matching problem with a particular objective function, namely a sum of logarithms of utilities. In the classical world, this problem is usually approximated with a local search algorithm, but the running time is too big for the applications in mind. One approach is to model the problem as a linear program with a convex objective, the so-called Eisenberg-Gale program. This LP is solved with a linear search approach, by simulating the proportional response dynamics. Here the convergence rate is inverse proportional to the number of iterations.\n\nThis is the state of the art, and the paper proposes to compute the proportional response with a quantum algorithm, obtaining roughly a quadratic speedup relative to standard algorithms. The quantum ingredient is the quantum amplitude estimation algorithm. The contribution of the paper is to reduce the proportional response problem to the quantum amplitude estimation problem, and to do a careful analysis concerning the required precision epsilon. Numerical simulations are also provided.", "questions": "In the paragraph of line 32 you eliminate quite quickly the exact and approximation algorithms. I would like to see at this place how they compare to the PR dynamics. But this is done later in the experimental section.\n\nI think that since quantum computers have so little resource today and in the near future in terms of number of qbits and possible number of operations, we should change perspective. The classic approach says if we want a result with this precision/approximation, then we need that much memory and running time. But here, every hidden constant in the complexity matters, so we need to present results in the form, if we have so much memory and so much available running time, we can achieve this performance.\n\nLine 707, do you mean classic or quantum maximum finding algorithm? In the latter case it is quite a simplification to assume success probability 1.\n\nTo make (1) and (2) consistent I would write either =1 and =p or <=1 and <=p.", "limitations": "Quantum computers do not scale yet.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper is carefully written, the experiments well documented, and I really appreciate the discussion section, which gets into a lot of details concerning extensions and variants.", "weaknesses": "It would have been nice to report experiments on a real quantum computer (e.g., Google or IBM quantum computers).\n\nDoes the paper fit into an Artificial Intelligence / Machine Learning conference? Some discussion on this matter would be significant.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and their appreciation of the discussion section. We address the reviewer's concerns and questions as follows.\n\n### Scope and venue. \nIn regards to the scope of the paper and compatibility with an artificial intelligence/machine learning conference, we believe this paper is a good fit for NeurIPS as our work fits into the **\"theory - algorithmic game theory\"** as well as the **\"optimization - convex optimization\"** areas of research listed in the NeurIPS 2024 call for papers.\n\n### Experiments on real hardware.\nWe agree with the reviewer that experiments on real quantum computers such as those provided by IBM can be beneficial for a paper in general. Such experiments for market equilibrium computation at this point in time would only be proof-of-concept based, given the capacity and scale of current quantum computers. On the available hardware it is difficult to run the estimation subroutines to give convincing results, but we are aiming to use next generation hardware for an experimental demonstration of the FPR dynamics quantum algorithm.\n\n### Complexity Measures.\n> But here, every hidden constant in the complexity matters, so we need to present results in the form, if we have so much memory and so much available running time, we can achieve this performance.\n\nWe agree with the reviewer that current quantum computers have quite limited resources, and asymptotic runtime measures are not able to fully quantify the cost of algorithm execution. However, the constant factors are device dependent, e.g. a decomposition of a quantum logic gate into hardware native gates may vary different platforms and cost differently. Our paper discusses algorithms without going into hardware-specific implementations, and we leave discussions on resource constrained implementations to future work involving the experimental demonstrations mentioned prior.\n\n### Discussion on combinatorial algorithms.\n> In the paragraph of line 32 you eliminate quite quickly the exact and approximation algorithms. I would like to see at this place how they compare to the PR dynamics. But this is done later in the experimental section.\n\nIn the introduction, the algorithms that we eliminate as part of the discussion are _combinatorial optimization_ algorithms for exact or approximation solutions. These algorithms do not rely on convex optimization techniques but instead typically reduce the problem to other combinatorial problems such as _Max-Flow_. To the best of our knowledge, the fastest algorithm in such regimes runs in $O(n^4 +n^2(m+n\\log n)\\log n)$, which was proposed by Végh in Ref [21], which has a significantly longer runtime compared to PR dynamics if we do not require the exact solution. In experiments, we benchmark our algorithm against other _convex optimization_ algorithms, and the optimal/maximum value obtainable for the EG objective function and do not provide comparisons to combinatorial algorithms given the different nature of the algorithms.\n\n### Quantum maximum finding in simulations.\n> Line 707, do you mean classic or quantum maximum finding algorithm? In the latter case it is quite a simplification to assume success probability 1.\n\nIn line 707, we do not run the quantum maximum algorithm and only run the classical maximum algorithm in replacement. Hence the success probability would be 1. We agree that this is indeed a simplification on our part for simulations.", "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": "", "extra_scores": {}}, {"review_id": "8pIqGLS76y", "reviewer": "Reviewer_vnkg", "summary": "This paper proposes quantum faulty proportional response (FPR) dynamics, a quantum algorithm that mimics classical proportional response (PR) dynamic with quantum speed-up, to compute the \"part of\" market equilibrium. Specifically, a market equilibrium specifies the allocation of each good to each buyer, and this algorithm aims at computing the allocation of some pre-specified good to some pre-specified buyer. The authors theoretically show that FPR has a square-root speed-up over the classical PR algorithm, which is the square root of the minimum number of buyers and goods. Experimental results show that FPR outperforms classical algorithms prominently, with quantum steps simulated by classical steps.", "questions": "1. Following the weakness, can these results be extended if the goal is to compute the allocation of all goods to some pre-specified buyer, or some pre-specified good to all buyers? Note that the memory of this task is $O(\\max(m,n))$, which is still within $O(\\sqrt{mn\\max(m,n)})$ runtime.\n2. Since the quantum steps in experiments are simulated by classical steps, and the simulated FPR performs better than other baselines, does this imply that the classically-simulated FPR is actually a classical algorithm that outperforms other classical algorithms in the Fisher market computation problem? Why?\n3. See above weakness 2.", "limitations": "The algorithm proposed in this paper is far from practical, as quantum computation is not yet mature, and the largest quantum computer has only $O(1)$ qubits as far as I know. Additionally, see the weakness.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper combines the problem of market equilibrium computation with a quantum algorithm, which is interesting. Theoretical and empirical results demonstrate the effectiveness of using a quantum algorithm to compute the \"part of\" market equilibrium, marking a significant step towards market equilibrium computation. Additionally, this paper is easy to follow.", "weaknesses": "1. The goal of FPR is to compute the allocation of some pre-specified good to some pre-specified buyer, which seems fairly limited, since classical algorithms aim to compute the allocation of all goods to all buyers. Moreover, comparing the runtime complexity (as well as other complexities) between FPR and PR is not fair due to their different goals.\n2. For experiments, the goal is optimizing the EG objective value, which\nseems to deviate from the original goal of computing the equilibrium allocation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the comments. We address the reviewer's concerns and questions as follows.\n\n### Allocation computation for all buyers and goods.\n> The goal of FPR is to compute the allocation of some pre-specified good to some pre-specified buyer, which seems fairly limited, since classical algorithms aim to compute the allocation of all goods to all buyers.\n\nWe want to clarify while indeed the FPR dynamics algorithm computes the allocation of pre-specified goods to buyers, so does the PR dynamics. Both algorithms compute the allocation of all buyers and goods by applying the individual updates for all allocations. Hence, we believe that the goals of the FPR and PR updates are indeed the same and can be compared in parallel.\n\n> Can these results be extended if the goal is to compute the allocation of all goods to some pre-specified buyer, or some pre-specified good to all buyers?\n\nFor the quantum algorithm, the bids of each buyer on the goods can be computed simultaneously via the superposition of quantum states, and query access to all the bids can be provided from measurements of the solution quantum state that encodes all the bids. We do note that, as there are $mn$ bids in total, the extraction of each value of the bids would require $O(mn)$ measurements of the quantum state.\n\n### Optimizing EG.\n> For experiments, the goal is optimizing the EG objective value, which seems to deviate from the original goal of computing the equilibrium allocation.\n\nWe would like to point out that the task of market equilibrium computation can be formulated as the maximization of the budget-weighted Nash social welfare (NSW), which is in turn captured by the EG objective function (which is the logarithm of NSW). Hence, the goal of maximizing the EG objective function fits the objective of computing the market equilibrium by maximization of NSW. However, we agree that this aspect is not well documented in the current manuscript, and we will be including the motivation of maximization of NSW as a game-theoretical target as part of the next iteration of the manuscript. \n\n### Simulation of quantum queries on classical computers.\n> Since the quantum steps in experiments are simulated by classical steps, and the simulated FPR performs better than other baselines, does this imply that the classically-simulated FPR is actually a classical algorithm that outperforms other classical algorithms in the Fisher market computation problem?\n\nConcerning the simulation of quantum steps by classical steps, in the experiment results, we set the horizontal axis as the number of queries to data values or QRAM that we would make. In the quantum setting, queries can be made in superposition, a feature that the classical computer cannot make use of. In the classical simulation, we have to simulate a single quantum query with corresponding multiple classical queries. However, we count these classical queries as a single query to provide a comparison between classical algorithm and classically-simulated quantum algorithm. Hence, there is no implication that FPR is a better classical algorithm experimentally.", "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": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank all the reviewers for their detailed comments and suggestions, as well as for appreciating our contributions. 

- Reviewer B4u4 remarked that our results are "valuable as a theoretical study" and our results provide "significant improvements in efficiency". 
- Reviewer vuEH acknowledges that our algorithm "is the **first quantum algorithm** that achieves **sublinear** performance in computing market equilibrium". 
- Reviewer sd1G remarked that our results are "state of the art", and commented that our "paper is **carefully written** and the experiments **well documented**", and they "**really appreciate the discussion section**, which gets into a lot of details concerning extensions and variants." 
- Reviewer vnkg commented that our paper "demonstrated the effectiveness of using a quantum algorithm to compute the 'part of' market equilibrium, marking a significant step towards market equilibrium computation" and that our paper "is easy to follow".

We indeed believe that our paper is the first to discuss quantum algorithms for market equilibrium computation. The initial question for us was if and how quantum computers can help at all in this application domain. The challenge was to find the right setting, the proportional response (PR) dynamics, that allows for theoretical speedups and work out the theoretical guarantees. Our paper is indeed not an applied paper in particular use cases, say, using a standardized data set. 

We agree with the reviewers that subroutines in our algorithm may be beyond that capabilities of current hardware, and such limitations can provide significant challenges. However, recent hardware developments show the potential of quantum computing on next generation hardware and we believe the development of quantum algorithms for new application domains is interesting both theoretically and practically, as the usefulness of quantum hardware increases as we discover more applications of quantum computers. We hope that the work serves as a stepping stone to investigate other quantum algorithms for market equilibrium computation.

Meta-review: This work is on quantum equilibrium computation in a market with n buyers and m goods; we obtain a fractional-matching problem since the special case of Fisher markets where the goods are infinitely-divisible and utilities are linear, is considered in this work. The goal is to set prices and do the matching so that supply and demand are matched, in order to maximize the total utility. Optimal algorithms that approximate the optimal value of the Eisenberg-Gale program to within epsilon, typically do better than the published best combinatorial algorithms. Such optimization algorithms here typically use "Proportional Response" (PR) dynamics. 

This work develops an o(mn) quantum algorithm by improving the per-iteration complexity of PR dynamics. Of course, quantum computers are in currently in the "NISQ" stage where algorithms such as this paper's will not be implementable at a reasonable scale, but I think this work overall adds value and diversity to NeurIPS. Specifically, the paper's proposed quantum algorithm---QFPR dynamics---is based on FPR dynamics. Both QFPR and FPR are online-learning algorithms, which are relevant to the ML community at NeurIPS.
Decision: Accept (poster)