Causal Inference on Discrete Data using Additive Noise Models (2009)
Peters, Jonas, Janzing, Dominik, Schölkopf, Bernhard
Inferring the causal structure of a set of random variables from a finite sample of the joint distribution is an important problem in science. Recently, methods using additive noise models have been...
Distinguishing Cause and Effect via Second Order Exponential Models (2009)
Janzing, Dominik, Sun, Xiaohai, Schoelkopf, Bernhard
We propose a method to infer causal structures containing both discrete and continuous variables. The idea is to select causal hypotheses for which the conditional density of every variable, given...
Justifying additive-noise-model based causal discovery via algorithmic information theory (2009)
Janzing, Dominik, Steudel, Bastian
A recent method for causal discovery is in many cases able to infer whether X causes Y or Y causes X for just two observed variables X and Y. It is based on the observation that there exist...
Telling cause from effect based on high-dimensional observations (2009)
Janzing, Dominik, Hoyer, Patrik O., Schoelkopf, Bernhard
We describe a method for inferring linear causal relations among multi-dimensional variables. The idea is to use an asymmetry between the distributions of cause and effect that occurs if both the...
Sparse Causal Discovery in Multivariate Time Series (2009)
Stefan Haufe, Klaus-robert Müller, Guido Nolte, Nicole Krämer, Isabelle Guyon, Dominik Janzing, ...
Our goal is to estimate causal interactions in multivariate time series. Using vector autoregressive (VAR) models, these can be defined based on non-vanishing coefficients belonging to respective...
Comparison of Granger Causality and Phase Slope Index (2009)
Guido Nolte, Andreas Ziehe, Nicole Krämer, Florin Popescu, Klaus-robert Müller, Isabelle Guyon, ...
We recently proposed a new measure, termed Phase Slope Index (PSI), It estimates the causal direction of interactions robustly with respect to instantaneous mixtures of independent sources with...
Nonlinear causal discovery with additive noise models (2009)
Patrik O. Hoyer, Dominik Janzing, Joris Mooij, Jonas Peters, Bernhard Schölkopf
The discovery of causal relationships between a set of observed variables is a fundamental problem in science. For continuous-valued data linear acyclic causal models with additive noise are often...
On the entropy production of time series with unidirectional linearity (2009)
There are non-Gaussian time series that admit a causal linear autoregressive moving average (ARMA) model when regressing the future on the past, but not when regressing the past on the future. The...
Thermodynamic efficiency of information and heat flow (2009)
Allahverdyan, Armen E., Janzing, Dominik, Mahler, Guenter
A basic task of information processing is information transfer (flow). Here we study a pair of Brownian particles each coupled to a thermal bath at temperature $T_1$ and $T_2$, respectively. The...
Nonlinear causal discovery with additive noise models (2009)
Hoyer, Patrik, Janzing, Dominik, Mooij, Joris, Peters, Jonas, Schölkopf, Bernhard
The discovery of causal relationships between a set of observed variables is a fundamental problem in science. For continuous-valued data linear acyclic causal models with additive noise are often...
Kernel Methods for Detecting the Direction of Time Series (2009)
Peters, Jonas, Janzing, Dominik, Gretton, Arthur
We propose two kernel based methods for detecting the time direction in empirical time series. First we apply a Support Vector Machine on the finitedimensional distributions of the time series...
Nonlinear causal discovery with additive noise models (2009)
Hoyer, Patrik, Janzing, Dominik, Mooij, Joris, Peters, Jonas, Schoelkopf, Bernhard
The discovery of causal relationships between a set of observed variables is a fundamental problem in science. For continuous-valued data linear acyclic causal models are often used because these...
Causal inference using the algorithmic Markov condition (2008)
Janzing, Dominik, Schoelkopf, Bernhard
Inferring the causal structure that links n observables is usually based upon detecting statistical dependences and choosing simple graphs that make the joint measure Markovian. Here we argue why...
A simple PromiseBQP-complete matrix problem (2008)
Dominik Janzing, Pawel Wocjan, D. Janzing, P. Wocjan
Abstract: Let A be a real symmetric matrix of size N such that the number of non-zero entries in each row is polylogarithmic in N and the positions and the values of these entries are specified by an...
Learning causality by identifying common effects with kernel-based dependence measures (2008)
Abstract. We describe a method for causal inference that measures the strength of statistical dependence by the Hilbert-Schmidt norm of kernelbased conditional cross-covariance operators. We consider...
A Kernel-based Causal Learning Algorithm (2008)
Xiaohai Sun, Dominik Janzing, Bernhard Schölkopf
We describe a causal learning method, which employs measuring the strength of statistical dependences in terms of the Hilbert-Schmidt norm of kernel-based cross-covariance operators. Following the...
Causal Reasoning by Evaluating the Complexity of Conditional Densities with Kernel Methods (2008)
Sun, Xiaohai, Janzing, Dominik, Schoelkopf, Bernhard
We propose a method to quantify the complexity of conditional probability measures by a Hilbert space seminorm of the logarithm of its density. The concept of reproducing kernel Hilbert spaces...
Relating the Thermodynamic Arrow of Time to the Causal Arrow. (2008)
Allahverdyan, Armen, Janzing, Dominik
Consider a Hamiltonian system that consists of a slow subsystem S and a fast subsystem F. The autonomous dynamics of S is driven by an effective Hamiltonian, but its thermodynamics is unexpected. We...
Janzing, Dominik, Wocjan, Pawel, Zhang, Shenghui
In measurement-based quantum computation, quantum algorithms are implemented via sequences of measurements. We describe a translationally invariant finite-range interaction on a one-dimensional qudit...
Causal inference using the algorithmic Markov condition (2008)
Janzing, Dominik, Schoelkopf, Bernhard
Inferring the causal structure that links n observables is usually based upon detecting statistical dependences and choosing simple graphs that make the joint measure Markovian. Here we argue why...
Janzing, Dominik, Wocjan, Pawel, Zhang, Shengyu
In measurement-based quantum computation, quantum algorithms are implemented via sequences of measurements. We describe a translationally invariant finite-range interaction on a one-dimensional qudit...
On causally asymmetric versions of Occam's Razor and their relation to thermodynamics (2007)
In real-life statistical data, it seems that conditional probabilities for the effect given their causes tend to be less complex and smoother than conditionals for causes, given their effects. We...
How much is a quantum controller controlled by the controlled system? (2007)
Janzing, Dominik, Decker, Thomas
We consider unitary transformations on a bipartite system A x B. To what extent entails the ability to transmit information from A to B the ability to transfer information in the converse direction?...
Relating the thermodynamic arrow of time to the causal arrow (2007)
Allahverdyan, Armen E., Janzing, Dominik
Consider a Hamiltonian system that consists of a slow subsystem S and a fast subsystem F. The autonomous dynamics of S is driven by an effective Hamiltonian, but its thermodynamics is unexpected. We...
A PromiseBQP-complete String Rewriting Problem (2007)
Janzing, Dominik, Wocjan, Pawel
We are given three strings s, t, and t' of length L over some fixed finite alphabet and an integer m that is polylogarithmic in L. We have a symmetric relation on substrings of constant length that...
Computer science approach to quantum control (2007)
Whereas it is obvious that every computation process is a physical process it has hardly been recognized that many complex physical processes bear similarities to computation processes. This is in...
BQP-complete Problems Concerning Mixing Properties of Classical Random Walks on Sparse Graphs (2006)
Janzing, Dominik, Wocjan, Pawel
We describe two BQP-complete problems concerning properties of sparse graphs having a certain symmetry. The graphs are specified by efficiently computable functions which output the adjacent vertices...
A Quantum Broadcasting Problem in Classical Low Power Signal Processing (2006)
Janzing, Dominik, Steudel, Bastian
We pose a problem called ``broadcasting Holevo-information'': given an unknown state taken from an ensemble, the task is to generate a bipartite state transfering as much Holevo-information to each...
Estimating diagonal entries of powers of sparse symmetric matrices is BQP-complete (2006)
Janzing, Dominik, Wocjan, Pawel
Let A be a real symmetric matrix of size N such that the number of the non-zero entries in each row is polylogarithmic in N and the positions and the values of these entries are specified by an...
Entanglement generation via scattering of two particles with hard-core repulsion (2006)
Schmüser, Frank, Janzing, Dominik
We analyse the entanglement generation in a one dimensional scattering process. The two colliding particles have a Gaussian wave function and interact by hard--core repulsion.In our analysis results...
Computer science approach to quantum control (2006)
This work considers several hypothetical control processes on the nanoscopic level and show their analogy to computation processes. It shows that measuring certain types of quantum observables is...
Causal Inference by Choosing Graphs with Most Plausible Markov Kernels. (2006)
Sun, Xiaohai, Janzing, Dominik, Schölkopf, Bernhard
We propose a new inference rule for estimating causal structure that underlies the observed statistical dependencies among n random variables. Our method is based on comparing the conditional...
Computer science approach to quantum control Elektronische Ressource (2006)
Zugl.: Karlsruhe, Univ., Habil.-Schr., 2006
Causal Inference By Choosing Graphs With Most Plausible (2006)
Markov Kernels Xiaohai, Xiaohai Sun, Dominik Janzing, Bernhard Schölkopf
We propose a new inference rule for estimating causal structure that underlies the observed statistical dependencies among n random variables. Our method is based on comparing the conditional...
If an absolute reference frame with respect to time, position, or orientation is missing one can only implement quantum operations which are covariant with respect to the corresponding unitary...
Janzing, Dominik, Decker, Thomas
In a previous paper we have presented a general scheme for the implementation of symmetric generalized measurements (POVMs) on a quantum computer. This scheme is based on representation theory of...
What is the simplest Hamiltonian which can implement quantum computation without requiring any control operations during the computation process? In a previous paper we have constructed a 10-local...
On Quantum A/D and D/A Conversion (2005)
Schmuser, Frank, Janzing, Dominik
An algorithm is proposed which transfers the quantum information of a wave function (analogue signal) into a register of qubits (digital signal) such that $n$ qubits describe the amplitudes and...
On the Computational Power of Molecular Heat Engines (2005)
A heat engine is a machine which uses the temperature difference between a hot and a cold reservoir to extract work. Here both reservoirs are quantum systems and a heat engine is described by a...
Every completely positive map G that commutes which the Hamiltonian time evolution is an integral or sum over (densely defined) CP-maps G_\sigma where \sigma is the energy that is transferred to or...
Implementation of group-covariant POVMs by orthogonal measurements (2004)
Decker, Thomas, Janzing, Dominik, Roetteler, Martin
We consider group-covariant positive operator valued measures (POVMs) on a finite dimensional quantum system. Following Neumark's theorem a POVM can be implemented by an orthogonal measurement on a...
Ergodic quantum computing (2004)
Janzing, Dominik, Wocjan, Pawel
We propose a (theoretical ;-) model for quantum computation where the result can be read out from the time average of the Hamiltonian dynamics of a 2-dimensional crystal on a cylinder. The...
Janzing, Dominik, Herrmann, Daniel
To learn (statistical) dependencies among random variables requires exponentially large sample size in the number of observed random variables if any arbitrary joint probability distribution can...
Quantum circuits for single-qubit measurements corresponding to platonic solids (2003)
Decker, Thomas, Janzing, Dominik, Beth, Thomas
Each platonic solid defines a single-qubit positive operator valued measure (POVM) by interpreting its vertices as points on the Bloch sphere. We construct simple circuits for implementing this kind...
Measuring 4-local n-qubit observables could probabilistically solve PSPACE (2003)
Wocjan, Pawel, Janzing, Dominik, Decker, Thomas, Beth, Thomas
We consider a hypothetical apparatus that implements measurements for arbitrary 4-local quantum observables A on n qubits. The apparatus implements the ``measurement algorithm'' after receiving a...
Janzing, Dominik, Beth, Thomas
We describe separable joint states on bipartite quantum systems that cannot be prepared by any thermodynamically reversible classical one-way communication protocol. We argue that the joint state of...
Two QCMA-complete problems (2003)
Wocjan, Pawel, Janzing, Dominik, Beth, Thomas
QMA and QCMA are possible quantum analogues of the complexity class NP. In QCMA the verifier is a quantum program and the proof is classical. In contrast, in QMA the proof is also a quantum state. We...
Identity check is QMA-complete (2003)
Janzing, Dominik, Wocjan, Pawel, Beth, Thomas
We define the problem identity check: Given a classical description of a quantum circuit, determine whether it is almost equivalent to the identity. Explicitly, the task is to decide whether the...
Cooling and Low Energy State Preparation for 3-local Hamiltonians are FQMA-complete (2003)
Janzing, Dominik, Wocjan, Pawel, Beth, Thomas
We introduce the quantum complexity class FQMA. This class describes the complexity of generating a quantum state that serves as a witness for a given QMA problem. In a certain sense, FQMA is the...
Selection Criterion for Log-Linear Models Using Statistical Learning Theory (2003)
Herrmann, Daniel, Janzing, Dominik
Log-linear models are a well-established method for describing statistical dependencies among a set of n random variables. The observed frequencies of the n-tuples are explained by a joint...
Wocjan, Pawel, Janzing, Dominik, Beth, Thomas
We construct a nearest-neighbor Hamiltonian whose ground states encode the solutions to the NP-complete problem INDEPENDENT SET in cubic planar graphs. The Hamiltonian can be easily simulated by...
Bounds on the entropy generated when timing information is extracted from microscopic systems (2003)
Janzing, Dominik, Beth, Thomas
We consider Hamiltonian quantum systems with energy bandwidth \Delta E and show that each measurement that determines the time up to an error \Delta t generates at least the entropy (\hbar/(\Delta t...
Janzing, Dominik, Beth, Thomas
To test the effectiveness of a drug one can advice two randomly selected groups of patients to take or not to take it, respectively. It is well-known that the causal effect cannot be identified if...
Janzing, Dominik, Decker, Thomas, Beth, Thomas
An n-qubit quantum register can in principle be completely controlled by operating on a single qubit that interacts with the register via an appropriate fixed interaction. We consider a hypothetical...
Required sample size for learning sparse Bayesian networks with many variables (2002)
Wocjan, Pawel, Janzing, Dominik, Beth, Thomas
Learning joint probability distributions on n random variables requires exponential sample size in the generic case. Here we consider the case that a temporal (or causal) order of the variables is...
Bounds on the number of time steps for simulating arbitrary interaction graphs (2002)
Janzing, Dominik, Wocjan, Pawel, Beth, Thomas
In previous papers we have considered mutual simulation of n-partite pair-interaction Hamiltonians. We have focussed on the running time overhead of general simulations, while considering the...
Are there quantum bounds on the recyclability of clock signals in low power computers? (2002)
Janzing, Dominik, Beth, Thomas
Even if a logical network consists of thermodynamically reversible gate operations, the computation process may have high dissipation rate if the gate implementation is controlled by external clock...
Lower Bound on the Chromatic Number by Spectra of Weighted Adjacency Matrices (2001)
Wocjan, Pawel, Janzing, Dominik, Beth, Thomas
A lower bound on the chromatic number of a graph is derived by majorization of spectra of weighted adjacency matrices. These matrices are given by Hadamard products of the adjacency matrix and...
Quasi-order of clocks and synchronism and quantum bounds for copying timing information (2001)
Janzing, Dominik, Beth, Thomas
The statistical state of any (classical or quantum) system with non-trivial time evolution can be interpreted as the pointer of a clock. The quality of such a clock is given by the statistical...
Simulating Hamiltonians in Quantum Networks: Efficient Schemes and Complexity Bounds (2001)
Wocjan, Pawel, Roetteler, Martin, Janzing, Dominik, Beth, Thomas
We address the problem of simulating pair-interaction Hamiltonians in n node quantum networks where the subsystems have arbitrary, possibly different, dimensions. We show that any pair-interaction...
Universal Simulation of Hamiltonians Using a Finite Set of Control Operations (2001)
Wocjan, Pawel, Roetteler, Martin, Janzing, Dominik, Beth, Thomas
Any quantum system with a non-trivial Hamiltonian is able to simulate any other Hamiltonian evolution provided that a sufficiently large group of unitary control operations is available. We show that...
Quantum algorithm for measuring the energy of n qubits with unknown pair-interactions (2001)
The well-known algorithm for quantum phase estimation requires that the considered unitary is available as a conditional transformation depending on the quantum state of an ancilla register. We...
Janzing, Dominik, Beth, Thomas
Estimating the eigenvalues of a unitary transformation U by standard phase estimation requires the implementation of controlled-U-gates which are not available if U is only given as a black box. We...
On Using Quantum Protocols to Detect Traffic Analysis (2001)
Steinwandt, Rainer, Janzing, Dominik, Beth, Thomas
We consider the problem of detecting whether an attacker measures the amount of traffic sent over a communication channel-possibly without extracting information about the transmitted data. A basic...
Janzing, Dominik, Wocjan, Pawel, Beth, Thomas
Well-known Nuclear Magnetic Resonance experiments show that the time evolution according to (truncated) dipole-dipole interactions between n spins can be inverted by simple pulse sequences....
Distinguishing n Hamiltonians on C^n by a single measurement (2001)
Janzing, Dominik, Beth, Thomas
If an experimentalist wants to decide which one of n possible Hamiltonians acting on an n dimensional Hilbert space is present, he can conjugate the time evolution by an appropriate sequence of known...
Quantum control without access to the controlling interaction (2001)
Janzing, Dominik, Armknecht, Frederik, Zeier, Robert, Beth, Thomas
In our model a fixed Hamiltonian acts on the joint Hilbert space of a quantum system and its controller. We show under which conditions measurements, state preparations, and unitary implementations...
A Complexity Measure for Continuous Time Quantum Algorithms (2000)
Janzing, Dominik, Beth, Thomas
We consider unitary dynamical evolutions on n qubits caused by time dependent pair-interaction Hamiltonians and show that the running time of a parallelized two-qubit gate network simulating the...
Remark on multi-particle observables and entangled states with constant complexity (2000)
Janzing, Dominik, Beth, Thomas
We show that every density matrix of an n-particle system prepared by a quantum network of constant depth is asymptotically commuting with the mean-field observables. We introduce certain pairs of...
Janzing, Dominik, Wocjan, Pawel, Zeier, Robert, Geiss, Rubino, Beth, Thomas
Landauer's principle states that the erasure of one bit of information requires the free energy kT ln 2. We argue that the reliability of the bit erasure process is bounded by the accuracy inherent...
Fragility of a class of highly entangled states of many quantum-bits (1999)
Janzing, Dominik, Beth, Thomas
We consider a Quantum Computer with n quantum-bits (`qubits'), where each qubit is coupled independently to an environment affecting the state in a dephasing or depolarizing way. For mixed states we...
Limesdynamik translationsinvarianter Quantengittersysteme / (1998)
Tübingen, Universiẗat, Diss., 1998 (Nur beschränkt für den Austausch).