Search Results

Documents authored by Ramakrishnan, C. R.

Document
DOI: 10.4230/LIPIcs.DISC.2021.41
Efficient Distribution of Quantum Circuits

Authors: Ranjani G Sundaram, Himanshu Gupta, and C. R. Ramakrishnan

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
Quantum computing hardware is improving in robustness, but individual computers still have small number of qubits (for storing quantum information). Computations needing a large number of qubits can only be performed by distributing them over a network of smaller quantum computers. In this paper, we consider the problem of distributing a quantum computation, represented as a quantum circuit, over a homogeneous network of quantum computers, minimizing the number of communication operations needed to complete every step of the computation. We propose a two-step solution: dividing the given circuit’s qubits among the computers in the network, and scheduling communication operations, called migrations, to share quantum information among the computers to ensure that every operation can be performed locally. While the first step is an intractable problem, we present a polynomial-time solution for the second step in a special setting, and a O(log n)-approximate solution in the general setting. We provide empirical results which show that our two-step solution outperforms existing heuristic for this problem by a significant margin (up to 90%, in some cases).
Cite as

Ranjani G Sundaram, Himanshu Gupta, and C. R. Ramakrishnan. Efficient Distribution of Quantum Circuits. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 41:1-41:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gsundaram_et_al:LIPIcs.DISC.2021.41,
  author =	{G Sundaram, Ranjani and Gupta, Himanshu and Ramakrishnan, C. R.},
  title =	{{Efficient Distribution of Quantum Circuits}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{41:1--41:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.41},
  URN =		{urn:nbn:de:0030-drops-148434},
  doi =		{10.4230/LIPIcs.DISC.2021.41},
  annote =	{Keywords: Distributed Quantum Computing, Hypergraph Min-Cut}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2018.36
Separable GPL: Decidable Model Checking with More Non-Determinism

Authors: Andrey Gorlin and C. R. Ramakrishnan

Published in: LIPIcs, Volume 118, 29th International Conference on Concurrency Theory (CONCUR 2018)

Abstract
Generalized Probabilistic Logic (GPL) is a temporal logic, based on the modal mu-calculus, for specifying properties of branching probabilistic systems. We consider GPL over branching systems that also exhibit internal non-determinism under linear-time semantics (which is resolved by schedulers), and focus on the problem of finding the capacity (supremum probability over all schedulers) of a fuzzy formula. Model checking GPL is undecidable, in general, over such systems, and existing GPL model checking algorithms are limited to systems without internal non-determinism, or to checking non-recursive formulae. We define a subclass, called separable GPL, which includes recursive formulae and for which model checking is decidable. A large class of interesting and decidable problems, such as termination of 1-exit Recursive MDPs, reachability of Branching MDPs, and LTL model checking of MDPs, whose decidability has been studied independently, can be reduced to model checking separable GPL. Thus, GPL is widely applicable and, with a suitable extension of its semantics, yields a uniform framework for studying problems involving systems with non-deterministic and probabilistic behaviors.
Cite as

Andrey Gorlin and C. R. Ramakrishnan. Separable GPL: Decidable Model Checking with More Non-Determinism. In 29th International Conference on Concurrency Theory (CONCUR 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 118, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gorlin_et_al:LIPIcs.CONCUR.2018.36,
  author =	{Gorlin, Andrey and Ramakrishnan, C. R.},
  title =	{{Separable GPL: Decidable Model Checking with More Non-Determinism}},
  booktitle =	{29th International Conference on Concurrency Theory (CONCUR 2018)},
  pages =	{36:1--36:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-087-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{118},
  editor =	{Schewe, Sven and Zhang, Lijun},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2018.36},
  URN =		{urn:nbn:de:0030-drops-95743},
  doi =		{10.4230/LIPIcs.CONCUR.2018.36},
  annote =	{Keywords: Modal mu-calculus, probabilistic logics, probabilistic systems, branching systems, model checking}
}
Document
DOI: 10.4230/OASIcs.ICLP.2016.15
Inference in Probabilistic Logic Programs Using Lifted Explanations

Authors: Arun Nampally and C. R. Ramakrishnan

Published in: OASIcs, Volume 52, Technical Communications of the 32nd International Conference on Logic Programming (ICLP 2016)

Abstract
In this paper, we consider the problem of lifted inference in the context of Prism-like probabilistic logic programming languages. Traditional inference in such languages involves the construction of an explanation graph for the query that treats each instance of a random variable separately. For many programs and queries, we observe that explanations can be summarized into substantially more compact structures introduced in this paper, called "lifted explanation graph". In contrast to existing lifted inference techniques, our method for constructing lifted explanations naturally generalizes existing methods for constructing explanation graphs. To compute probability of query answers, we solve recurrences generated from the lifted graphs. We show examples where the use of our technique reduces the asymptotic complexity of inference.
Cite as

Arun Nampally and C. R. Ramakrishnan. Inference in Probabilistic Logic Programs Using Lifted Explanations. In Technical Communications of the 32nd International Conference on Logic Programming (ICLP 2016). Open Access Series in Informatics (OASIcs), Volume 52, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{nampally_et_al:OASIcs.ICLP.2016.15,
  author =	{Nampally, Arun and Ramakrishnan, C. R.},
  title =	{{Inference in Probabilistic Logic Programs Using Lifted Explanations}},
  booktitle =	{Technical Communications of the 32nd International Conference on Logic Programming (ICLP 2016)},
  pages =	{15:1--15:15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-007-1},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{52},
  editor =	{Carro, Manuel and King, Andy and Saeedloei, Neda and De Vos, Marina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICLP.2016.15},
  URN =		{urn:nbn:de:0030-drops-67459},
  doi =		{10.4230/OASIcs.ICLP.2016.15},
  annote =	{Keywords: Probabilistic logic programs, Probabilistic inference, Lifted inference, Symbolic evaluation, Constraints}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact