1,720,983 research outputs found
On the power of interleaved low-depth quantum and classical circuits
Full text linkLow-depth quantum circuits are a well-suited model for near-term quantum devices, given short coherence times and noisy gate operations, making it pivotal to examine their computational power. It was already known as early as 2004 that simulating such low-depth quantum circuits is classically hard under complexity-theoretic assumptions. Later, it was shown that low-depth quantum circuits interleaved with low-depth classical circuits can perform approximate quantum Fourier transform, the quantum subroutine of Shor's algorithm.
Given these salient features of low-depth quantum models, Terhal and DiVincenzo, Aaronson, and Jozsa have all independently conjectured regarding the elusive power of combining low-depth quantum circuits with efficient classical computation. However, much has remained unresolved in this interleaved setting. Therefore, in this thesis, we tackle the question of characterizing the computational power of interleaved low-depth quantum and classical circuits. We first review existing separations in the low-depth setting. Then, we formally define two interleaving models based on whether the quantum device is permitted to make subset measurements (weak interleaving) or must measure all qubits together (strict interleaving).
By combining existing techniques from quantum fan-out constructions, teleportation-based quantum computation, and Clifford + T circuit synthesis, we show several results regarding the power of variants of constant-depth quantum circuits (QNC0) strictly and weakly interleaved with constant-depth classical parity circuits. Our main new result is that QNC0 with access to cat states strictly interleaved with constant-depth classical parity circuits can simulate constant-depth threshold circuits (TC0), which neither of the classes can do on their own. This strictly separates this interleaved class from constant-depth classical circuits with unbounded fan-in mod p and OR gates (AC0[p])
Quantum Query Complexity of Hypergraph Search Problems
No full textIn the study of quantum query complexity, it is natural to study the problems of finding triangles and spanning trees in a simple graph. Over the past decades, many techniques are developed for finding the upper and lower quantum query bounds of these graph problems. We can generalize these problems to detecting certain properties of higher rank hypergraphs and ask whether these techniques are still available. In this thesis, we will see that when the rank increase, complexity bounds still holds for some problems, although less effectively. For some other problems, their nontrivial complexity bounds vanish. Moreover, we will focused on using the generalized adversary and learning graph techniques for finding nontrivial quantum query bounds for different hypergraph search problems. The following results are presented.
• Discover a general quantum query lower bound for subhypergraph-closed properties and monotone properties over r-partite r-uniform hypergraphs.
• Provide tight quantum query bounds for the connectivity and acyclicity problems over r-uniform hypergraphs.
• Present a nontrivial learning graph algorithm for the 3-simplex finding problem.
• Formulate nested quantum walk in the adaptive learning context and use it to present a nontrivial quantum query algorithm for the 4-simplex finding problem.
• Present a natural relationship of lower bounds for simplex finding of different ranks.
• Use the learning graph formalization of tetrahedron certificate structure to find a nontrivial quantum query lower bound of the 3-simplex sum problem
Variants of Pseudo-deterministic Algorithms and Duality in TFNP
Full text linkWe introduce a new notion of ``faux-deterministic'' algorithms for search problems in query complexity. Roughly, for a search problem \cS, a faux-deterministic algorithm is a probability distribution over deterministic algorithms such that no computationally bounded adversary making black-box queries to a sampled algorithm can find an input on which fails to solve \cS ((x, A(x))\notin \cS). Faux-deterministic algorithms are a relaxation of \emph{pseudo-deterministic} algorithms, which are randomized algorithms with the guarantee that for any given input , the algorithm outputs a unique output with high probability. Pseudo-deterministic algorithms are statistically indistinguishable from deterministic algorithms, while faux-deterministic algorithms relax this statistical indistinguishability to computational indistinguishability.
We prove that in the query model, every verifiable search problem that has a randomized algorithm also has a faux-deterministic algorithm. By considering the pseudo-deterministic lower bound of Goldwasser et al. \cite{goldwasser_et_al:LIPIcs.CCC.2021.36}, we immediately prove an exponential gap between pseudo-deterministic and faux-deterministic complexities in query complexity. We additionally show that our faux-deterministic algorithm is also secure against quantum adversaries that can make black-box queries in superposition.
We highlight two reasons to study faux-deterministic algorithms. First, for practical purposes, one can use a faux-deterministic algorithm instead of pseudo-deterministic algorithms in most cases where the latter is required. Second, since efficient faux-deterministic algorithms exist even when pseudo-deterministic ones do not, their existence demonstrates a barrier to proving pseudo-deterministic lower bounds: Lower bounds on pseudo-determinism must distinguish pseudo-determinism from faux-determinism.
Finally, changing our perspective to the adversaries' viewpoint, we introduce a notion of ``dual problem'' \cS^{*} for search problems \cS. In the dual problem \cS^*, the input is an algorithm purporting to solve \cS, and our goal is to find an adverse input on which fails to solve \cS. We discuss several properties in the query and Turing machine model that show the new problem \cS^* is analogous to a dual for \cS
A Generalized Adversary Method for Quantum Query Complexity
Full text linkQuantum query complexity measures the minimum number of queries a quantum algorithm needs to make to some input string to compute a function of that input. Query complexity models are widely used throughout quantum computing, from setting limits on quantum algorithms to analyzing post-quantum cryptography.
This thesis studies quantum adversary methods, a group of mathematical tools that prove lower bounds on quantum query complexity. I introduce a new general-purpose framework for adversary methods that generalizes over both the negative weight and multiplicative adversary methods. This framework unifies the lower bound proofs of both methods, even in the general case of quantum state conversion.
This generalized method also gives a new formula for the multiplicative adversary method based on max-relative entropy. This new definition is more concise and easier to reason about than existing definitions in the literature. I verify this by reproving several known results about the multiplicative adversary method. I also use this to reprove the strong direct product theorem for quantum query complexity
Query Complexity of Recursively Composed Functions
No full textIn this work, we explore two well-studied notions of randomized query complexity; bounded-error randomized (), and zero-error randomized (). These have their natural analogues from the classical model of computation, corresponding to BPP or ``Monte Carlo" algorithms and to ZPP or ``Las Vegas" algorithms.
For a query complexity measure , one can define the composition limit of on by . The composition limit is a useful way to understand the asymptotic complexity of a function with respect to a specific measure (e.g. if , then ).
We show that under the composition limit, Las Vegas algorithms can be reduced to Monte Carlo algorithms in the query complexity world. Specifically, \R_0^*(f) = \max(\C^*(f), \R^*(f)) for all possibly-partial boolean functions . This has wide-reaching implications for the classical query complexity of boolean functions that are still open. For example, this result implies that any bounded-error algorithm for recursive 3-majority can be converted into a zero-error algorithm with no additional cost (i.e. .
Furthermore, we explore one possible generalization of the recursive 3-majority problem itself, by analyzing 3-majority as a special case of a combinatorial game we call Denial Nim
Randomized Query Complexity of Sabotaged and Composed Functions
Full text linkWe study the composition question for bounded-error randomized query complexity: Is R(f circ g) = Omega(R(f)R(g))? We show that inserting a simple function h, whose query complexity is onlyTheta(log R(g)), in between f and g allows us to prove R(f circ h circ g) = Omega(R(f)R(h)R(g)).
We prove this using a new lower bound measure for randomized query complexity we call randomized sabotage complexity, RS(f). Randomized sabotage complexity has several desirable properties, such as a perfect composition theorem, RS(f circ g) >= RS(f) RS(g), and a composition theorem with randomized query complexity, R(f circ g) = Omega(R(f) RS(g)). It is also a quadratically tight lower bound for total functions and can be quadratically superior to the partition bound, the best known general lower bound for randomized query complexity.
Using this technique we also show implications for lifting theorems in communication complexity. We show that a general lifting theorem from zero-error randomized query to communication complexity implies a similar result for bounded-error algorithms for all total functions
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
- …
