18,375 research outputs found
ADAM SMITH'S OPTIMISTIC TELEOLOGICAL VIEW OF HISTORY
No full textAdam Smith's four-stage theory provides the framework for his writings on history. The fourth stage is the commercial epoch; the culmination of history in this stage is a key component in the conventional interpretation of Adam Smith as a prophet of commercialism. In two historical case studies Smith shows the capacity of commercial society to regenerate itself. This potent capacity suggests that commercial society is inevitable. At a certain point in time it also overcomes the major obstacles to its permanence. Smith's philosophy of history anticipates the end of history views of Kant and Hegel.Political Economy,
Trading Inverses for an Irrep in the Solovay-Kitaev Theorem
No full textThe Solovay-Kitaev theorem states that universal quantum gate sets can be exchanged with low overhead. More specifically, any gate on a fixed number of qudits can be simulated with error epsilon using merely polylog(1/epsilon) gates from any finite universal quantum gate set G. One drawback to the theorem is that it requires the gate set G to be closed under inversion. Here we show that this restriction can be traded for the assumption that G contains an irreducible representation of any finite group G. This extends recent work of Sardharwalla et al. [Sardharwalla et al., 2016], and applies also to gates from the special linear group. Our work can be seen as partial progress towards the long-standing open problem of proving an inverse-free Solovay-Kitaev theorem [Dawson and Nielsen, 2006; Kuperberg, 2015]
How Might Adam Smith Pay Professors Today?
No full textAdam Smith’s proposal for paying professors was intended to induce increased faculty knowledge. If students have imperfect information about what they learn, and universities can only imperfectly measure the input of faculty time in student learning, publications may be used to measure faculty knowledge. If professors’ ability to publish is positively related to their ability to produce student learning, which universities can imperfectly measure, publications may be necessary to attract more able professors. Since research signals faculty knowledge, schools that do not value publications per se could require higher publication standards and pay higher wages than schools that value only publications.
Generation of universal linear optics by any beam splitter
No full textIn 1994, Reck et al. showed how to realize any unitary transformation on a single photon using a product of beam splitters and phase shifters. Here we show that any single beam splitter that nontrivially mixes two modes also densely generates the set of unitary transformations (or orthogonal transformations, in the real case) on the single-photon subspace with m ≥ 3 modes. (We prove the same result for any two-mode real optical gate, and for any two-mode optical gate combined with a generic phase shifter.) Experimentally, this means that one does not need tunable beam splitters or phase shifters for universality: any nontrivial beam splitter is universal for linear optics. Theoretically, it means that one cannot produce “intermediate” models of linear optical computation (analogous to the Clifford group for qubits) by restricting the allowed beam splitters and phase shifters: there is a dichotomy; one either gets a trivial set or else a universal set. No similar classification theorem for gates acting on qubits is currently known. We leave open the problem of classifying optical gates that act on three or more modes.National Science Foundation (U.S.) (Grant 0844626)National Science Foundation (U.S.) (Alan T. Waterman Award)National Science Foundation (U.S.). Graduate Research Fellowship Program (Grant 1122374)National Science Foundation (U.S.). Center for Science of Information (Grant Agreement CCF-0939370
Complexity Classification of Two-Qubit Commuting Hamiltonians
No full textWe classify two-qubit commuting Hamiltonians in terms of their computational complexity. Suppose one has a two-qubit commuting Hamiltonian H which one can apply to any pair of qubits, starting in a computational basis state. We prove a dichotomy theorem: either this model is efficiently classically simulable or it allows one to sample from probability distributions which cannot be sampled from classically unless the polynomial hierarchy collapses. Furthermore, the only simulable Hamiltonians are those which fail to generate entanglement. This shows that generic two-qubit commuting Hamiltonians can be used to perform computational tasks which are intractable for classical computers under plausible assumptions. Our proof makes use of new postselection gadgets and Lie theory
Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality (Abstract)
No full textThe AdS/CFT correspondence is central to efforts to reconcile gravity and quantum mechanics, a fundamental goal of physics. It posits a duality between a gravitational theory in Anti de Sitter (AdS) space and a quantum mechanical conformal field theory (CFT), embodied in a map known as the AdS/CFT dictionary mapping states to states and operators to operators. This dictionary map is not well understood and has only been computed on special, structured instances. In this work we introduce cryptographic ideas to the study of AdS/CFT, and provide evidence that either the dictionary must be exponentially hard to compute, or else the quantum Extended Church-Turing thesis must be false in quantum gravity.
Our argument has its origins in a fundamental paradox in the AdS/CFT correspondence known as the wormhole growth paradox. The paradox is that the CFT is believed to be "scrambling" - i.e. the expectation value of local operators equilibrates in polynomial time - whereas the gravity theory is not, because the interiors of certain black holes known as "wormholes" do not equilibrate and instead their volume grows at a linear rate for at least an exponential amount of time. So what could be the CFT dual to wormhole volume? Susskind’s proposed resolution was to equate the wormhole volume with the quantum circuit complexity of the CFT state. From a computer science perspective, circuit complexity seems like an unusual choice because it should be difficult to compute, in contrast to physical quantities such as wormhole volume.
We show how to create pseudorandom quantum states in the CFT, thereby arguing that their quantum circuit complexity is not "feelable", in the sense that it cannot be approximated by any efficient experiment. This requires a specialized construction inspired by symmetric block ciphers such as DES and AES, since unfortunately existing constructions based on quantum-resistant one way functions cannot be used in the context of the wormhole growth paradox as only very restricted operations are allowed in the CFT. By contrast we argue that the wormhole volume is "feelable" in some general but non-physical sense. The duality between a "feelable" quantity and an "unfeelable" quantity implies that some aspect of this duality must have exponential complexity. More precisely, it implies that either the dictionary is exponentially complex, or else the quantum gravity theory is exponentially difficult to simulate on a quantum computer.
While at first sight this might seem to justify the discomfort of complexity theorists with equating computational complexity with a physical quantity, a further examination of our arguments shows that any resolution of the wormhole growth paradox must equate wormhole volume to an "unfeelable" quantity, leading to the same conclusions. In other words this discomfort is an inevitable consequence of the paradox
ADAM SMITH'S VIEW OF HISTORY: CONSISTENT OR PARADOXICAL?
No full textThe conventional interpretation of Adam Smith is that he is a prophet of commercialism. The liberal capitalist reading of Smith is consistent with the view that history culminates in commercial society. The first part of the article develops this optimistic interpretation of Smith's view of history. Smith implies that commercial society is the end of history because 1) it supplies the ends of nature that he identifies; 2) it is inevitable; and 3) it is permanent. The second part of the article shows that Smith has some dark moments in his writings where he seems to reject completely such teleological notions. In this more civic humanist mood he confesses that commercial society does not supply the ends of nature, nor is it inevitable, nor is it permanent. Both views exist in Smith and the commentator is forced to choose between passages in Smith's work in order to support a particular interpretation of the former's view of history.Political Economy,
"Quantum Supremacy" and the Complexity of Random Circuit Sampling
No full textA critical goal for the field of quantum computation is quantum supremacy - a demonstration of any quantum computation that is prohibitively hard for classical computers. It is both a necessary milestone on the path to useful quantum computers as well as a test of quantum theory in the realm of high complexity. A leading near-term candidate, put forth by the Google/UCSB team, is sampling from the probability distributions of randomly chosen quantum circuits, called Random Circuit Sampling (RCS).
While RCS was defined with experimental realization in mind, we give strong complexity-theoretic evidence for the classical hardness of RCS, placing it on par with the best theoretical proposals for supremacy. Specifically, we show that RCS satisfies an average-case hardness condition - computing output probabilities of typical quantum circuits is as hard as computing them in the worst-case, and therefore #P-hard. Our reduction exploits the polynomial structure in the output amplitudes of random quantum circuits, enabled by the Feynman path integral. In addition, it follows from known results that RCS also satisfies an anti-concentration property, namely that errors in estimating output probabilities are small with respect to the probabilities themselves. This makes RCS the first proposal for quantum supremacy with both of these properties. We also give a natural condition under which an existing statistical measure, cross-entropy, verifies RCS, as well as describe a new verification measure which in some formal sense maximizes the information gained from experimental samples
Complexity Classification of Conjugated Clifford Circuits
No full textClifford circuits - i.e. circuits composed of only CNOT, Hadamard, and pi/4 phase gates - play a central role in the study of quantum computation. However, their computational power is limited: a well-known result of Gottesman and Knill states that Clifford circuits are efficiently classically simulable. We show that in contrast, "conjugated Clifford circuits" (CCCs) - where one additionally conjugates every qubit by the same one-qubit gate U - can perform hard sampling tasks. In particular, we fully classify the computational power of CCCs by showing that essentially any non-Clifford conjugating unitary U can give rise to sampling tasks which cannot be efficiently classically simulated to constant multiplicative error, unless the polynomial hierarchy collapses. Furthermore, by standard techniques, this hardness result can be extended to allow for the more realistic model of constant additive error, under a plausible complexity-theoretic conjecture. This work can be seen as progress towards classifying the computational power of all restricted quantum gate sets
- …
