Showing 1–14 of 14 results for author: Kivlichan, I D

A Taxonomy of Rater Disagreements: Surveying Challenges & Opportunities from the Perspective of Annotating Online Toxicity

Authors: Wenbo Zhang, Hangzhi Guo, Ian D Kivlichan, Vinodkumar Prabhakaran, Davis Yadav, Amulya Yadav

Abstract: Toxicity is an increasingly common and severe issue in online spaces. Consequently, a rich line of machine learning research over the past decade has focused on computationally detecting and mitigating online toxicity. These efforts crucially rely on human-annotated datasets that identify toxic content of various kinds in social media texts. However, such annotations historically yield low inter-r… ▽ More Toxicity is an increasingly common and severe issue in online spaces. Consequently, a rich line of machine learning research over the past decade has focused on computationally detecting and mitigating online toxicity. These efforts crucially rely on human-annotated datasets that identify toxic content of various kinds in social media texts. However, such annotations historically yield low inter-rater agreement, which was often dealt with by taking the majority vote or other such approaches to arrive at a single ground truth label. Recent research has pointed out the importance of accounting for the subjective nature of this task when building and utilizing these datasets, and this has triggered work on analyzing and better understanding rater disagreements, and how they could be effectively incorporated into the machine learning developmental pipeline. While these efforts are filling an important gap, there is a lack of a broader framework about the root causes of rater disagreement, and therefore, we situate this work within that broader landscape. In this survey paper, we analyze a broad set of literature on the reasons behind rater disagreements focusing on online toxicity, and propose a detailed taxonomy for the same. Further, we summarize and discuss the potential solutions targeting each reason for disagreement. We also discuss several open issues, which could promote the future development of online toxicity research. △ Less

Submitted 7 November, 2023; originally announced November 2023.

Comments: 21 pages, 2 figures

CrowdWorkSheets: Accounting for Individual and Collective Identities Underlying Crowdsourced Dataset Annotation

Authors: Mark Diaz, Ian D. Kivlichan, Rachel Rosen, Dylan K. Baker, Razvan Amironesei, Vinodkumar Prabhakaran, Emily Denton

Abstract: Human annotated data plays a crucial role in machine learning (ML) research and development. However, the ethical considerations around the processes and decisions that go into dataset annotation have not received nearly enough attention. In this paper, we survey an array of literature that provides insights into ethical considerations around crowdsourced dataset annotation. We synthesize these in… ▽ More Human annotated data plays a crucial role in machine learning (ML) research and development. However, the ethical considerations around the processes and decisions that go into dataset annotation have not received nearly enough attention. In this paper, we survey an array of literature that provides insights into ethical considerations around crowdsourced dataset annotation. We synthesize these insights, and lay out the challenges in this space along two layers: (1) who the annotator is, and how the annotators' lived experiences can impact their annotations, and (2) the relationship between the annotators and the crowdsourcing platforms, and what that relationship affords them. Finally, we introduce a novel framework, CrowdWorkSheets, for dataset developers to facilitate transparent documentation of key decisions points at various stages of the data annotation pipeline: task formulation, selection of annotators, platform and infrastructure choices, dataset analysis and evaluation, and dataset release and maintenance. △ Less

Submitted 9 June, 2022; originally announced June 2022.

Comments: 11 pages, Accepted at 2022 ACM Conference on Fairness, Accountability, and Transparency (FAccT). arXiv admin note: text overlap with arXiv:2112.04554

Measuring and Improving Model-Moderator Collaboration using Uncertainty Estimation

Authors: Ian D. Kivlichan, Zi Lin, Jeremiah Liu, Lucy Vasserman

Abstract: Content moderation is often performed by a collaboration between humans and machine learning models. However, it is not well understood how to design the collaborative process so as to maximize the combined moderator-model system performance. This work presents a rigorous study of this problem, focusing on an approach that incorporates model uncertainty into the collaborative process. First, we in… ▽ More Content moderation is often performed by a collaboration between humans and machine learning models. However, it is not well understood how to design the collaborative process so as to maximize the combined moderator-model system performance. This work presents a rigorous study of this problem, focusing on an approach that incorporates model uncertainty into the collaborative process. First, we introduce principled metrics to describe the performance of the collaborative system under capacity constraints on the human moderator, quantifying how efficiently the combined system utilizes human decisions. Using these metrics, we conduct a large benchmark study evaluating the performance of state-of-the-art uncertainty models under different collaborative review strategies. We find that an uncertainty-based strategy consistently outperforms the widely used strategy based on toxicity scores, and moreover that the choice of review strategy drastically changes the overall system performance. Our results demonstrate the importance of rigorous metrics for understanding and developing effective moderator-model systems for content moderation, as well as the utility of uncertainty estimation in this domain. △ Less

Submitted 9 July, 2021; originally announced July 2021.

Comments: WOAH 2021

Phase estimation with randomized Hamiltonians

Authors: Ian D. Kivlichan, Christopher E. Granade, Nathan Wiebe

Abstract: Iterative phase estimation has long been used in quantum computing to estimate Hamiltonian eigenvalues. This is done by applying many repetitions of the same fundamental simulation circuit to an initial state, and using statistical inference to glean estimates of the eigenvalues from the resulting data. Here, we show a generalization of this framework where each of the steps in the simulation uses… ▽ More Iterative phase estimation has long been used in quantum computing to estimate Hamiltonian eigenvalues. This is done by applying many repetitions of the same fundamental simulation circuit to an initial state, and using statistical inference to glean estimates of the eigenvalues from the resulting data. Here, we show a generalization of this framework where each of the steps in the simulation uses a different Hamiltonian. This allows the precision of the Hamiltonian to be changed as the phase estimation precision increases. Additionally, through the use of importance sampling, we can exploit knowledge about the ground state to decide how frequently each Hamiltonian term should appear in the evolution, and minimize the variance of our estimate. We rigorously show, if the Hamiltonian is gapped and the sample variance in the ground state expectation values of the Hamiltonian terms sufficiently small, that this process has a negligible impact on the resultant estimate and the success probability for phase estimation. We demonstrate this process numerically for two chemical Hamiltonians, and observe substantial reductions in the number of terms in the Hamiltonian; in one case, we even observe a reduction in the number of qubits needed for the simulation. Our results are agnostic to the particular simulation algorithm, and we expect these methods to be applicable to a range of approaches. △ Less

Submitted 23 July, 2019; originally announced July 2019.

Comments: 17 pages, 2 figures

Improved Fault-Tolerant Quantum Simulation of Condensed-Phase Correlated Electrons via Trotterization

Authors: Ian D. Kivlichan, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Wei Sun, Zhang Jiang, Nicholas Rubin, Austin Fowler, Alán Aspuru-Guzik, Hartmut Neven, Ryan Babbush

Abstract: Recent work has deployed linear combinations of unitaries techniques to reduce the cost of fault-tolerant quantum simulations of correlated electron models. Here, we show that one can sometimes improve upon those results with optimized implementations of Trotter-Suzuki-based product formulas. We show that low-order Trotter methods perform surprisingly well when used with phase estimation to comput… ▽ More Recent work has deployed linear combinations of unitaries techniques to reduce the cost of fault-tolerant quantum simulations of correlated electron models. Here, we show that one can sometimes improve upon those results with optimized implementations of Trotter-Suzuki-based product formulas. We show that low-order Trotter methods perform surprisingly well when used with phase estimation to compute relative precision quantities (e.g. energies per unit cell), as is often the goal for condensed-phase systems. In this context, simulations of the Hubbard and plane-wave electronic structure models with $N < 10^5$ fermionic modes can be performed with roughly $O(1)$ and $O(N^2)$ T complexities. We perform numerics revealing tradeoffs between the error and gate complexity of a Trotter step; e.g., we show that split-operator techniques have less Trotter error than popular alternatives. By compiling to surface code fault-tolerant gates and assuming error rates of one part per thousand, we show that one can error-correct quantum simulations of interesting, classically intractable instances with a few hundred thousand physical qubits. △ Less

Submitted 13 July, 2020; v1 submitted 27 February, 2019; originally announced February 2019.

Comments: 45 pages, 15 figures. Only difference from v3 is change to CC BY 4.0 license

Journal ref: Quantum 4, 296 (2020)

Quantum Chemistry in the Age of Quantum Computing

Authors: Yudong Cao, Jonathan Romero, Jonathan P. Olson, Matthias Degroote, Peter D. Johnson, Mária Kieferová, Ian D. Kivlichan, Tim Menke, Borja Peropadre, Nicolas P. D. Sawaya, Sukin Sim, Libor Veis, Alán Aspuru-Guzik

Abstract: Practical challenges in simulating quantum systems on classical computers have been widely recognized in the quantum physics and quantum chemistry communities over the past century. Although many approximation methods have been introduced, the complexity of quantum mechanics remains hard to appease. The advent of quantum computation brings new pathways to navigate this challenging complexity lands… ▽ More Practical challenges in simulating quantum systems on classical computers have been widely recognized in the quantum physics and quantum chemistry communities over the past century. Although many approximation methods have been introduced, the complexity of quantum mechanics remains hard to appease. The advent of quantum computation brings new pathways to navigate this challenging complexity landscape. By manipulating quantum states of matter and taking advantage of their unique features such as superposition and entanglement, quantum computers promise to efficiently deliver accurate results for many important problems in quantum chemistry such as the electronic structure of molecules. In the past two decades significant advances have been made in developing algorithms and physical hardware for quantum computing, heralding a revolution in simulation of quantum systems. This article is an overview of the algorithms and results that are relevant for quantum chemistry. The intended audience is both quantum chemists who seek to learn more about quantum computing, and quantum computing researchers who would like to explore applications in quantum chemistry. △ Less

Submitted 28 December, 2018; v1 submitted 24 December, 2018; originally announced December 2018.

Comments: 194 pages, 13 figures, 5 tables and 404 references. Fixed formatting issues from the previous version. Comments welcome

Quantum Simulation of Electronic Structure with Linear Depth and Connectivity

Authors: Ian D. Kivlichan, Jarrod McClean, Nathan Wiebe, Craig Gidney, Alán Aspuru-Guzik, Garnet Kin-Lic Chan, Ryan Babbush

Abstract: As physical implementations of quantum architectures emerge, it is increasingly important to consider the cost of algorithms for practical connectivities between qubits. We show that by using an arrangement of gates that we term the fermionic swap network, we can simulate a Trotter step of the electronic structure Hamiltonian in exactly $N$ depth and with $N^2/2$ two-qubit entangling gates, and pr… ▽ More As physical implementations of quantum architectures emerge, it is increasingly important to consider the cost of algorithms for practical connectivities between qubits. We show that by using an arrangement of gates that we term the fermionic swap network, we can simulate a Trotter step of the electronic structure Hamiltonian in exactly $N$ depth and with $N^2/2$ two-qubit entangling gates, and prepare arbitrary Slater determinants in at most $N/2$ depth, all assuming only a minimal, linearly connected architecture. We conjecture that no explicit Trotter step of the electronic structure Hamiltonian is possible with fewer entangling gates, even with arbitrary connectivities. These results represent significant practical improvements on the cost of most Trotter based algorithms for both variational and phase estimation based simulation of quantum chemistry. △ Less

Submitted 2 February, 2018; v1 submitted 13 November, 2017; originally announced November 2017.

Comments: 8 pages, 4 figures

Journal ref: Phys. Rev. Lett. 120, 110501 (2018)

OpenFermion: The Electronic Structure Package for Quantum Computers

Authors: Jarrod R. McClean, Kevin J. Sung, Ian D. Kivlichan, Yudong Cao, Chengyu Dai, E. Schuyler Fried, Craig Gidney, Brendan Gimby, Pranav Gokhale, Thomas Häner, Tarini Hardikar, Vojtěch Havlíček, Oscar Higgott, Cupjin Huang, Josh Izaac, Zhang Jiang, Xinle Liu, Sam McArdle, Matthew Neeley, Thomas O'Brien, Bryan O'Gorman, Isil Ozfidan, Maxwell D. Radin, Jhonathan Romero, Nicholas Rubin , et al. (10 additional authors not shown)

Abstract: Quantum simulation of chemistry and materials is predicted to be an important application for both near-term and fault-tolerant quantum devices. However, at present, developing and studying algorithms for these problems can be difficult due to the prohibitive amount of domain knowledge required in both the area of chemistry and quantum algorithms. To help bridge this gap and open the field to more… ▽ More Quantum simulation of chemistry and materials is predicted to be an important application for both near-term and fault-tolerant quantum devices. However, at present, developing and studying algorithms for these problems can be difficult due to the prohibitive amount of domain knowledge required in both the area of chemistry and quantum algorithms. To help bridge this gap and open the field to more researchers, we have developed the OpenFermion software package (www.openfermion.org). OpenFermion is an open-source software library written largely in Python under an Apache 2.0 license, aimed at enabling the simulation of fermionic models and quantum chemistry problems on quantum hardware. Beginning with an interface to common electronic structure packages, it simplifies the translation between a molecular specification and a quantum circuit for solving or studying the electronic structure problem on a quantum computer, minimizing the amount of domain expertise required to enter the field. The package is designed to be extensible and robust, maintaining high software standards in documentation and testing. This release paper outlines the key motivations behind design choices in OpenFermion and discusses some basic OpenFermion functionality which we believe will aid the community in the development of better quantum algorithms and tools for this exciting area of research. △ Less

Submitted 27 February, 2019; v1 submitted 20 October, 2017; originally announced October 2017.

Comments: 22 pages

qTorch: The Quantum Tensor Contraction Handler

Authors: E. Schuyler Fried, Nicolas P. D. Sawaya, Yudong Cao, Ian D. Kivlichan, Jhonathan Romero, Alán Aspuru-Guzik

Abstract: Classical simulation of quantum computation is necessary for studying the numerical behavior of quantum algorithms, as there does not yet exist a large viable quantum computer on which to perform numerical tests. Tensor network (TN) contraction is an algorithmic method that can efficiently simulate some quantum circuits, often greatly reducing the computational cost over methods that simulate the… ▽ More Classical simulation of quantum computation is necessary for studying the numerical behavior of quantum algorithms, as there does not yet exist a large viable quantum computer on which to perform numerical tests. Tensor network (TN) contraction is an algorithmic method that can efficiently simulate some quantum circuits, often greatly reducing the computational cost over methods that simulate the full Hilbert space. In this study we implement a tensor network contraction program for simulating quantum circuits using multi-core compute nodes. We show simulation results for the Max-Cut problem on 3- through 7-regular graphs using the quantum approximate optimization algorithm (QAOA), successfully simulating up to 100 qubits. We test two different methods for generating the ordering of tensor index contractions: one is based on the tree decomposition of the line graph, while the other generates ordering using a straight-forward stochastic scheme. Through studying instances of QAOA circuits, we show the expected result that as the treewidth of the quantum circuit's line graph decreases, TN contraction becomes significantly more efficient than simulating the whole Hilbert space. The results in this work suggest that tensor contraction methods are superior only when simulating Max-Cut/QAOA with graphs of regularities approximately five and below. Insight into this point of equal computational cost helps one determine which simulation method will be more efficient for a given quantum circuit. The stochastic contraction method outperforms the line graph based method only when the time to calculate a reasonable tree decomposition is prohibitively expensive. Finally, we release our software package, qTorch (Quantum TensOR Contraction Handler), intended for general quantum circuit simulation. △ Less

Submitted 22 December, 2018; v1 submitted 11 September, 2017; originally announced September 2017.

Comments: 21 pages, 8 figures

Journal ref: PLoS ONE 13(12): e0208510. (2018)

Bounding the costs of quantum simulation of many-body physics in real space

Authors: Ian D. Kivlichan, Nathan Wiebe, Ryan Babbush, Alan Aspuru-Guzik

Abstract: We present a quantum algorithm for simulating the dynamics of a first-quantized Hamiltonian in real space based on the truncated Taylor series algorithm. We avoid the possibility of singularities by applying various cutoffs to the system and using a high-order finite difference approximation to the kinetic energy operator. We find that our algorithm can simulate $η$ interacting particles using a n… ▽ More We present a quantum algorithm for simulating the dynamics of a first-quantized Hamiltonian in real space based on the truncated Taylor series algorithm. We avoid the possibility of singularities by applying various cutoffs to the system and using a high-order finite difference approximation to the kinetic energy operator. We find that our algorithm can simulate $η$ interacting particles using a number of calculations of the pairwise interactions that scales, for a fixed spatial grid spacing, as $\tilde{O}(η^2)$, versus the $\tilde{O}(η^5)$ time required by previous methods (assuming the number of orbitals is proportional to $η$), and scales super-polynomially better with the error tolerance than algorithms based on the Lie-Trotter-Suzuki product formula. Finally, we analyze discretization errors that arise from the spatial grid and show that under some circumstances these errors can remove the exponential speedups typically afforded by quantum simulation. △ Less

Submitted 6 June, 2017; v1 submitted 19 August, 2016; originally announced August 2016.

Journal ref: Journal of Physics A: Mathematical and Theoretical 50 (30), 305301 (2017)

Scalable Quantum Simulation of Molecular Energies

Authors: P. J. J. O'Malley, R. Babbush, I. D. Kivlichan, J. Romero, J. R. McClean, R. Barends, J. Kelly, P. Roushan, A. Tranter, N. Ding, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, A. G. Fowler, E. Jeffrey, A. Megrant, J. Y. Mutus, C. Neill, C. Quintana, D. Sank, A. Vainsencher, J. Wenner, T. C. White , et al. (5 additional authors not shown)

Abstract: We report the first electronic structure calculation performed on a quantum computer without exponentially costly precompilation. We use a programmable array of superconducting qubits to compute the energy surface of molecular hydrogen using two distinct quantum algorithms. First, we experimentally execute the unitary coupled cluster method using the variational quantum eigensolver. Our efficient… ▽ More We report the first electronic structure calculation performed on a quantum computer without exponentially costly precompilation. We use a programmable array of superconducting qubits to compute the energy surface of molecular hydrogen using two distinct quantum algorithms. First, we experimentally execute the unitary coupled cluster method using the variational quantum eigensolver. Our efficient implementation predicts the correct dissociation energy to within chemical accuracy of the numerically exact result. Second, we experimentally demonstrate the canonical quantum algorithm for chemistry, which consists of Trotterization and quantum phase estimation. We compare the experimental performance of these approaches to show clear evidence that the variational quantum eigensolver is robust to certain errors. This error tolerance inspires hope that variational quantum simulations of classically intractable molecules may be viable in the near future. △ Less

Submitted 3 February, 2017; v1 submitted 21 December, 2015; originally announced December 2015.

Comments: 13 pages, 7 figures. This revision is to correct an error in the coefficients of identity in Table 1

Journal ref: Phys. Rev. X 6, 031007 (2016)

Exponentially More Precise Quantum Simulation of Fermions in the Configuration Interaction Representation

Authors: Ryan Babbush, Dominic W. Berry, Yuval R. Sanders, Ian D. Kivlichan, Artur Scherer, Annie Y. Wei, Peter J. Love, Alán Aspuru-Guzik

Abstract: We present a quantum algorithm for the simulation of molecular systems that is asymptotically more efficient than all previous algorithms in the literature in terms of the main problem parameters. As in previous work [Babbush et al., New Journal of Physics 18, 033032 (2016)], we employ a recently developed technique for simulating Hamiltonian evolution, using a truncated Taylor series to obtain lo… ▽ More We present a quantum algorithm for the simulation of molecular systems that is asymptotically more efficient than all previous algorithms in the literature in terms of the main problem parameters. As in previous work [Babbush et al., New Journal of Physics 18, 033032 (2016)], we employ a recently developed technique for simulating Hamiltonian evolution, using a truncated Taylor series to obtain logarithmic scaling with the inverse of the desired precision. The algorithm of this paper involves simulation under an oracle for the sparse, first-quantized representation of the molecular Hamiltonian known as the configuration interaction (CI) matrix. We construct and query the CI matrix oracle to allow for on-the-fly computation of molecular integrals in a way that is exponentially more efficient than classical numerical methods. Whereas second-quantized representations of the wavefunction require $\widetilde{\cal O}(N)$ qubits, where $N$ is the number of single-particle spin-orbitals, the CI matrix representation requires $\widetilde{\cal O}(η)$ qubits where $η\ll N$ is the number of electrons in the molecule of interest. We show that the gate count of our algorithm scales at most as $\widetilde{\cal O}(η^2 N^3 t)$. △ Less

Submitted 25 May, 2017; v1 submitted 2 June, 2015; originally announced June 2015.

Comments: Complete rewrite (extended from 12 pages to 41 pages): results are now presented as formal proofs with clear assumptions

Journal ref: Quantum Science and Technology 3, 015006 (2018)

Exponentially more precise quantum simulation of fermions I: Quantum chemistry in second quantization

Authors: Ryan Babbush, Dominic W. Berry, Ian D. Kivlichan, Annie Y. Wei, Peter J. Love, Alán Aspuru-Guzik

Abstract: We introduce novel algorithms for the quantum simulation of molecular systems which are asymptotically more efficient than those based on the Trotter-Suzuki decomposition. We present the first application of a recently developed technique for simulating Hamiltonian evolution using a truncated Taylor series to obtain logarithmic scaling with the inverse of the desired precision, an exponential impr… ▽ More We introduce novel algorithms for the quantum simulation of molecular systems which are asymptotically more efficient than those based on the Trotter-Suzuki decomposition. We present the first application of a recently developed technique for simulating Hamiltonian evolution using a truncated Taylor series to obtain logarithmic scaling with the inverse of the desired precision, an exponential improvement over all prior methods. The two algorithms developed in this work rely on a second quantized encoding of the wavefunction in which the state of an $N$ spin-orbital system is encoded in ${\cal O}(N)$ qubits. Our first algorithm requires at most $\widetilde{\cal O}(N^8 t)$ gates. Our second algorithm involves on-the-fly computation of molecular integrals, in a way that is exponentially more precise than classical sampling methods, by using the truncated Taylor series simulation technique. Our second algorithm has the lowest gate count of any approach to second quantized quantum chemistry simulation in the literature, scaling as $\widetilde{\cal O}(N^{5} t)$. The approaches presented here are readily applicable to a wide class of fermionic models, many of which are defined by simplified versions of the chemistry Hamiltonian. △ Less

Submitted 28 September, 2015; v1 submitted 2 June, 2015; originally announced June 2015.

Comments: 13 pages, 1 figure. Part I of a two-paper series. For Part II see arXiv:1506.01029

Journal ref: New J. Phys. 18 (2016) 033032

Optical evidence of surface state suppression in Bi based topological insulators

Authors: Anjan A. Reijnders, Y. Tian, L. J. Sandilands, G. Pohl, I. D. Kivlichan, S. Y. Frank Zhao, S. Jia, M. E. Charles, R. J. Cava, Nasser Alidoust, Suyang Xu, Madhab Neupane, M. Zahid Hasan, X. Wang, S. W. Cheong, K. S. Burch

Abstract: A key challenge in condensed matter research is the optimization of topological insulator (TI) compounds for the study and future application of their unique surface states. Truly insulating bulk states would allow the exploitation of predicted surface state properties, such as protection from backscattering, dissipationless spin-polarized currents, and the emergence of novel particles. Towards th… ▽ More A key challenge in condensed matter research is the optimization of topological insulator (TI) compounds for the study and future application of their unique surface states. Truly insulating bulk states would allow the exploitation of predicted surface state properties, such as protection from backscattering, dissipationless spin-polarized currents, and the emergence of novel particles. Towards this end, major progress was recently made with the introduction of highly resistive Bi$_2$Te$_2$Se, in which surface state conductance and quantum oscillations are observed at low temperatures. Nevertheless, an unresolved and pivotal question remains: while room temperature ARPES studies reveal clear evidence of TI surface states, their observation in transport experiments is limited to low temperatures. A better understanding of this surface state suppression at elevated temperatures is of fundamental interest, and crucial for pushing the boundary of device applications towards room-temperature operation. In this work, we simultaneously measure TI bulk and surface states via temperature dependent optical spectroscopy, in conjunction with transport and ARPES measurements. We find evidence of coherent surface state transport at low temperatures, and propose that phonon mediated coupling between bulk and surface states suppresses surface conductance as temperature rises. △ Less

Submitted 2 April, 2014; originally announced April 2014.

Comments: 13 pages, 10 figures

Journal ref: Phys. Rev. B 89, 075138 (2014)