9,064 research outputs found
Approximating Output Probabilities of Shallow Quantum Circuits Which Are Geometrically-Local in Any Fixed Dimension
No full textWe present a classical algorithm that, for any D-dimensional geometrically-local, quantum circuit C of polylogarithmic-depth, and any bit string x ∈ {0,1}ⁿ, can compute the quantity ||² to within any inverse-polynomial additive error in quasi-polynomial time, for any fixed dimension D. This is an extension of the result [Nolan J. Coble and Matthew Coudron, 2021], which originally proved this result for D = 3. To see why this is interesting, note that, while the D = 1 case of this result follows from a standard use of Matrix Product States, known for decades, the D = 2 case required novel and interesting techniques introduced in [Sergy Bravyi et al., 2020]. Extending to the case D = 3 was even more laborious, and required further new techniques introduced in [Nolan J. Coble and Matthew Coudron, 2021]. Our work here shows that, while handling each new dimension has historically required a new insight, and fixed algorithmic primitive, based on known techniques for D ≤ 3, we can now handle any fixed dimension D > 3.
Our algorithm uses the Divide-and-Conquer framework of [Nolan J. Coble and Matthew Coudron, 2021] to approximate the desired quantity via several instantiations of the same problem type, each involving D-dimensional circuits on about half the number of qubits as the original. This division step is then applied recursively, until the width of the recursively decomposed circuits in the D^{th} dimension is so small that they can effectively be regarded as (D-1)-dimensional problems by absorbing the small width in the D^{th} dimension into the qudit structure at the cost of a moderate increase in runtime. The main technical challenge lies in ensuring that the more involved portions of the recursive circuit decomposition and error analysis from [Nolan J. Coble and Matthew Coudron, 2021] still hold in higher dimensions, which requires small modifications to the analysis in some places. Our work also includes some simplifications, corrections and clarifications of the use of block-encodings within the original classical algorithm in [Nolan J. Coble and Matthew Coudron, 2021]
Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision
No full textWe study the problem of approximating the commuting-operator value of a two-player non-local game. It is well-known that it is NP-complete to decide whether the classical value of a non-local game is 1 or 1- epsilon, promised that one of the two is the case. Furthermore, as long as epsilon is small enough, this result does not depend on the gap epsilon. In contrast, a recent result of Fitzsimons, Ji, Vidick, and Yuen shows that the complexity of computing the quantum value grows without bound as the gap epsilon decreases. In this paper, we show that this also holds for the commuting-operator value of a game. Specifically, in the language of multi-prover interactive proofs, we show that the power of MIP^{co}(2,1,1,s) (proofs with two provers, one round, completeness probability 1, soundness probability s, and commuting-operator strategies) can increase without bound as the gap 1-s gets arbitrarily small.
Our results also extend naturally in two ways, to perfect zero-knowledge protocols, and to lower bounds on the complexity of computing the approximately-commuting value of a game. Thus we get lower bounds on the complexity class PZK-MIP^{co}_{delta}(2,1,1,s) of perfect zero-knowledge multi-prover proofs with approximately-commuting operator strategies, as the gap 1-s gets arbitrarily small. While we do not know any computable time upper bound on the class MIP^{co}, a result of the first author and Vidick shows that for s = 1-1/poly(f(n)) and delta = 1/poly(f(n)), the class MIP^{co}_delta(2,1,1,s), with constant communication from the provers, is contained in TIME(exp(poly(f(n)))). We give a lower bound of coNTIME(f(n)) (ignoring constants inside the function) for this class, which is tight up to polynomial factors assuming the exponential time hypothesis
Universality of EPR Pairs in Entanglement-Assisted Communication Complexity, and the Communication Cost of State Conversion
No full textIn this work we consider the role of entanglement assistance in quantum communication protocols, focusing, in particular, on whether the type of shared entangled state can affect the quantum communication complexity of a function. This question is interesting because in some other settings in quantum information, such as non-local games, or tasks that involve quantum communication between players and referee, or simulating bipartite unitaries or communication channels, maximally entangled states are known to be less useful as a resource than some partially entangled states. By contrast, we prove that the bounded-error entanglement-assisted quantum communication complexity of a partial or total function cannot be improved by more than a constant factor by replacing maximally entangled states with arbitrary entangled states. In particular, we show that every quantum communication protocol using Q qubits of communication and arbitrary shared entanglement can be epsilon-approximated by a protocol using O(Q/epsilon+log(1/epsilon)/epsilon) qubits of communication and only EPR pairs as shared entanglement. This conclusion is opposite of the common wisdom in the study of non-local games, where it has been shown, for example, that the I3322 inequality has a non-local strategy using a non-maximally entangled state, which surpasses the winning probability achievable by any strategy using a maximally entangled state of any dimension [Vidick and Wehner, 2011]. We leave open the question of how much the use of a shared maximally entangled state can reduce the quantum communication complexity of a function.
Our second result concerns an old question in quantum information theory: How much quantum communication is required to approximately convert one pure bipartite entangled state into another? We give simple and efficiently computable upper and lower bounds. Given two bipartite states |chi> and |upsilon>, we define a natural quantity, d_{infty}(|chi>, |upsilon>), which we call the l_{infty} Earth Mover’s distance, and we show that the communication cost of converting between |chi> and |upsilon> is upper bounded by a constant multiple of d_{infty}(|chi>, |upsilon>). Here d_{infty}(|chi>, |upsilon>) may be informally described as the minimum over all transports between the log of the Schmidt coefficients of |chi> and those of |upsilon>, of the maximum distance that any amount of mass must be moved in that transport. A precise definition is given in the introduction. Furthermore, we prove a complementary lower bound on the cost of state conversion by the epsilon-Smoothed l_{infty}-Earth Mover’s Distance, which is a natural smoothing of the l_{infty}-Earth Mover’s Distance that we will define via a connection with optimal transport theory
Matthew Henry: The Bible, Prayer, and Piety – A Tercentenary Celebration
No full textThe summer of 2014 marked the tercentenary of the death of Matthew Henry (1662–1714), a leading figure among early eighteenth-century Dissenters and author of the six-volume Exposition of the Old and New Testaments (1707–1714/25). This monumental work, which by 1855 had already been published in twenty-five different editions, attempted a peculiarly practical approach to the biblical text and continues to be widely used and readily accessible even today in both print and online versions. The theme of foreign (or ‘strange’) wives and Israelite intermarriage is one which occurs throughout the Hebrew Bible and, accordingly, throughout Matthew Henry’s commentary upon it. Where it appears, the practice of intermarriage is characterized by Henry as (at best) unwise and (at worst) a very real threat to both social and religious cohesion. This essay explores how Henry deals with the issue of ‘strange wives’, why he believes they continue to pose a threat, and (in view of the overall intention of his commentary) what ‘practical observations’ he offers to his reader as a result. In doing so it is argued that Henry’s commentary traces a thematic thread from the ante-diluvian age to the post-exilic period of calamities resulting from mixed marriages between ‘professors of religion’ and their ‘strange wives’
Citation expectations: are they realized? Study of the Matthew index for Russian papers published abroad
No full textWe consider the "Matthew effect" in the citation process which leads to reallocation (or misallocation) of the citations received by scientific papers within the same journals. The case when such reallocation correlates with a country where an author works is investigated. Russian papers in chemistry and physics published abroad were examined. We found that in both disciplines in about 60% of journals Russian papers are cited less than average ones. However, if we consider each discipline as a whole, citedness of a Russian paper in physics will be on the average level, while chemistry publications receive about 16% citations less than one may expect from the citedness of the journals where they appear. Moreover, Russian chemistry papers mostly become undercited in the leading journals of the field. Characteristics of a "Matthew index" indicator and its significance for scientometric studies are also discussed
Quantum algorithms and the power of forgetting
No full textThe so-called welded tree problem provides an example of a black-box problem
that can be solved exponentially faster by a quantum walk than by any classical
algorithm. Given the name of a special ENTRANCE vertex, a quantum walk can find
another distinguished EXIT vertex using polynomially many queries, though
without finding any particular path from ENTRANCE to EXIT. It has been an open
problem for twenty years whether there is an efficient quantum algorithm for
finding such a path, or if the path-finding problem is hard even for quantum
computers. We show that a natural class of efficient quantum algorithms
provably cannot find a path from ENTRANCE to EXIT. Specifically, we consider
algorithms that, within each branch of their superposition, always store a set
of vertex labels that form a connected subgraph including the ENTRANCE, and
that only provide these vertex labels as inputs to the oracle. While this does
not rule out the possibility of a quantum algorithm that efficiently finds a
path, it is unclear how an algorithm could benefit by deviating from this
behavior. Our no-go result suggests that, for some problems, quantum algorithms
must necessarily forget the path they take to reach a solution in order to
outperform classical computation.Comment: 49 pages, 9 figure
An Interview with Matthew Kaiser on Competition and Play
No full textAn Interview with Matthew Kaiser on Competition and Play, by Sean Scanlan. Matthew Kaiser, the author of The World in Play: Portraits of a Victorian Concept (Stanford UP, 2012) says that “[c]ompetition is the disease from which modern life suffers,” and that “[c]ompetition is the only cure” for this suffering. This contradictory pairing seems to get at the heart of his thesis: play, as a totalizing, umbrella-like concept, emanates from a host of philosophical, political, and scientific work produced by Victorians who posed many of their ideas of play in sports metaphors, competitive logics, and narratives of struggle. Kaiser goes beyond the dichotomy of competition and play/competition or play, by stating “I’m interested in the totalizing potential of both concepts, the way that play, or competition for that matter, swallows the world whole, becomes in the minds of so many people, the organizing principle of reality, whether of culture or nature or consciousness, or of all three.
Cardozo AELJ Author Interview Series: Matthew Goldman, Class of 2022
No full textThe Cardozo AELJ Author Interview Series seeks to give our readers further insight into the Articles and Notes published in the Cardozo Arts & Entertainment Law Journal. In this interview, Matthew Goldman discusses his Note, Fragmented Music Copyright Protection: A Better Arrangement, which was published in Volume 40, Issue 3.
This post was originally published on the Cardozo Arts & Entertainment Law Journal website on November 7, 2023. The original post can be accessed via the Archived Link button above
Recommended from our members
Cardozo AELJ Author Interview Series: Matthew Goldman, Class of 2022
No full textThe Cardozo AELJ Author Interview Series seeks to give our readers further insight into the Articles and Notes published in the Cardozo Arts & Entertainment Law Journal. In this interview, Matthew Goldman discusses his Note, Fragmented Music Copyright Protection: A Better Arrangement, which was published in Volume 40, Issue 3.
This post was originally published on the Cardozo Arts & Entertainment Law Journal website on November 7, 2023. The original post can be accessed via the Archived Link button above
Cardozo AELJ Author Interview Series: Matthew Goldman, Class of 2022
No full textThe Cardozo AELJ Author Interview Series seeks to give our readers further insight into the Articles and Notes published in the Cardozo Arts & Entertainment Law Journal. In this interview, Matthew Goldman discusses his Note, Fragmented Music Copyright Protection: A Better Arrangement, which was published in Volume 40, Issue 3.
This post was originally published on the Cardozo Arts & Entertainment Law Journal website on November 7, 2023. The original post can be accessed via the Archived Link button above
- …
