BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Richard Jozsa

Richard Jozsa appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
quant-phmath-phmath.MPComputational ComplexityData Structures and AlgorithmsInformation Theorymath.IT

Catalog footprint

What is connected

12works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

12 published item(s)

preprint2016arXiv

Quantum conditional query complexity

We define and study a new type of quantum oracle, the quantum conditional oracle, which provides oracle access to the conditional probabilities associated with an underlying distribution. Amongst other properties, we (a) obtain speed-ups over the best known quantum algorithms for identity testing, equivalence testing and uniformity testing of probability distributions; (b) study the power of these oracles for testing properties of boolean functions, and obtain an algorithm for checking whether an $n$-input $m$-output boolean function is balanced or $ε$-far from balanced; and (c) give a sub-linear algorithm, requiring $\tilde{O}(n^{3/4}/ε)$ queries, for testing whether an $n$-dimensional quantum state is maximally mixed or not.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Jordan-Wigner formalism for arbitrary 2-input 2-output matchgates and their classical simulation

In Valiant's matchgate theory, 2-input 2-output matchgates are 4x4 matrices that satisfy ten so-called matchgate identities. We prove that the set of all such matchgates (including non-unitary and non-invertible ones) coincides with the topological closure of the set of all matrices obtained as exponentials of linear combinations of the 2-qubit Jordan-Wigner (JW) operators and their quadratic products, extending a previous result of Knill. In Valiant's theory, outputs of matchgate circuits can be classically computed in poly-time. Via the JW formalism, Terhal & DiVincenzo and Knill established a relation of a unitary class of these circuits to the efficient simulation of non-interacting fermions. We describe how the JW formalism may be used to give an efficient simulation for all cases in Valiant's simulation theorem, which in particular includes the case of non-interacting fermions generalised to allow arbitrary 1-qubit gates on the first line at any stage in the circuit. Finally we give an exposition of how these simulation results can be alternatively understood from some basic Lie algebra theory, in terms of a formalism introduced by Somma et al.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Symmetric polynomials in information theory: entropy and subentropy

Entropy and other fundamental quantities of information theory are customarily expressed and manipulated as functions of probabilities. Here we study the entropy H and subentropy Q as functions of the elementary symmetric polynomials in the probabilities, and reveal a series of remarkable properties. Derivatives of all orders are shown to satisfy a complete monotonicity property. H and Q themselves become multivariate Bernstein functions and we derive the density functions of their Levy-Khintchine representations. We also show that H and Q are Pick functions in each symmetric polynomial variable separately. Furthermore we see that H and the intrinsically quantum informational quantity Q become surprisingly closely related in functional form, suggesting a special significance for the symmetric polynomials in quantum information theory. Using the symmetric polynomials we also derive a series of further properties of H and Q.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Classical simulation complexity of extended Clifford circuits

Clifford gates are a winsome class of quantum operations combining mathematical elegance with physical significance. The Gottesman-Knill theorem asserts that Clifford computations can be classically efficiently simulated but this is true only in a suitably restricted setting. Here we consider Clifford computations with a variety of additional ingredients: (a) strong vs. weak simulation, (b) inputs being computational basis states vs. general product states, (c) adaptive vs. non-adaptive choices of gates for circuits involving intermediate measurements, (d) single line outputs vs. multi-line outputs. We consider the classical simulation complexity of all combinations of these ingredients and show that many are not classically efficiently simulatable (subject to common complexity assumptions such as P not equal to NP). Our results reveal a surprising proximity of classical to quantum computing power viz. a class of classically simulatable quantum circuits which yields universal quantum computation if extended by a purely classical additional ingredient that does not extend the class of quantum processes occurring.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Entropy, subentropy and the elementary symmetric functions

We use complex contour integral techniques to study the entropy H and subentropy Q as functions of the elementary symmetric polynomials, revealing a series of striking properties. In particular for these variables, derivatives of -Q are equal to derivatives of H of one higher order and the first derivatives of H and Q are seen to be completely monotone functions. It then follows that exp (-H) and exp(-Q) are Laplace transforms of infinitely divisible probability distributions.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On exact quantum query complexity

We present several families of total boolean functions which have exact quantum query complexity which is a constant multiple (between 1/2 and 2/3) of their classical query complexity, and show that optimal quantum algorithms for these functions cannot be obtained by simply computing parities of pairs of bits. We also characterise the model of nonadaptive exact quantum query complexity in terms of coding theory and completely characterise the query complexity of symmetric boolean functions in this context. These results were originally inspired by numerically solving the semidefinite programs characterising quantum query complexity for small problem sizes. We include numerical results giving the optimal success probabilities achievable by quantum algorithms computing all boolean functions on up to 4 bits, and all symmetric boolean functions on up to 6 bits.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Properties of subentropy

Subentropy is an entropy-like quantity that arises in quantum information theory; for example, it provides a tight lower bound on the accessible information for pure state ensembles, dual to the von Neumann entropy upper bound in Holevo's theorem. Here we establish a series of properties of subentropy, paralleling the well-developed analogous theory for von Neumann entropy. Further, we show that subentropy is a lower bound for min-entropy. We introduce a notion of conditional subentropy and show that it can be used to provide an upper bound for the guessing probability of any classical-quantum state of two qubits; we conjecture that the bound applies also in higher dimensions. Finally we give an operational interpretation of subentropy within classical information theory.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy

We consider quantum computations comprising only commuting gates, known as IQP computations, and provide compelling evidence that the task of sampling their output probability distributions is unlikely to be achievable by any efficient classical means. More specifically we introduce the class post-IQP of languages decided with bounded error by uniform families of IQP circuits with post-selection, and prove first that post-IQP equals the classical class PP. Using this result we show that if the output distributions of uniform IQP circuit families could be classically efficiently sampled, even up to 41% multiplicative error in the probabilities, then the infinite tower of classical complexity classes known as the polynomial hierarchy, would collapse to its third level. We mention some further results on the classical simulation properties of IQP circuit families, in particular showing that if the output distribution results from measurements on only O(log n) lines then it may in fact be classically efficiently sampled.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Matchgate and space-bounded quantum computations are equivalent

Matchgates are an especially multiflorous class of two-qubit nearest neighbour quantum gates, defined by a set of algebraic constraints. They occur for example in the theory of perfect matchings of graphs, non-interacting fermions, and one-dimensional spin chains. We show that the computational power of circuits of matchgates is equivalent to that of space-bounded quantum computation with unitary gates, with space restricted to being logarithmic in the width of the matchgate circuit. In particular, for the conventional setting of polynomial-sized (logarithmic-space generated) families of matchgate circuits, known to be classically simulatable, we characterise their power as coinciding with polynomial-time and logarithmic-space bounded universal unitary quantum computation.

0 citations0 reviewsNo code linkedOpen access
preprint2000arXiv

Counterfactual Computation

Suppose that we are given a quantum computer programmed ready to perform a computation if it is switched on. Counterfactual computation is a process by which the result of the computation may be learnt without actually running the computer. Such processes are possible within quantum physics and to achieve this effect, a computer embodying the possibility of running the computation must be available, even though the computation is, in fact, not run. We study the possibilities and limitations of general protocols for the counterfactual computation of decision problems (where the result r is either 0 or 1). If p(r) denotes the probability of learning the result r ``for free'' in a protocol then one might hope to design a protocol which simultaneously has large p(0) and p(1). However we prove that p(0)+p(1) never exceeds 1 in any protocol and we derive further constraints on p(0) and p(1) in terms of N, the number of times that the computer is not run. In particular we show that any protocol with p(0)+p(1)=1-epsilon must have N tending to infinity as epsilon tends to 0. These general results are illustrated with some explicit protocols for counterfactual computation. We show that "interaction-free" measurements can be regarded as counterfactual computations, and our results then imply that N must be large if the probability of interaction is to be close to zero. Finally, we consider some ways in which our formulation of counterfactual computation can be generalised.

0 citations0 reviewsNo code linkedOpen access
preprint2000arXiv

Quantum factoring, discrete logarithms and the hidden subgroup problem

Amongst the most remarkable successes of quantum computation are Shor's efficient quantum algorithms for the computational tasks of integer factorisation and the evaluation of discrete logarithms. In this article we review the essential ingredients of these algorithms and draw out the unifying generalization of the so-called abelian hidden subgroup problem. This involves an unexpectedly harmonious alignment of the formalism of quantum physics with the elegant mathematical theory of group representations and fourier transforms on finite groups. Finally we consider the non-abelian hidden subgroup problem mentioning some open questions where future quantum algorithms may be expected to have a substantial impact.

0 citations0 reviewsNo code linkedOpen access