5 Search Results for "Chen, Fang"

Document
DOI: 10.4230/LIPIcs.ITCS.2022.47
Quantum Meets the Minimum Circuit Size Problem

Authors: Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, and Ruizhe Zhang

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
In this work, we initiate the study of the Minimum Circuit Size Problem (MCSP) in the quantum setting. MCSP is a problem to compute the circuit complexity of Boolean functions. It is a fascinating problem in complexity theory - its hardness is mysterious, and a better understanding of its hardness can have surprising implications to many fields in computer science. We first define and investigate the basic complexity-theoretic properties of minimum quantum circuit size problems for three natural objects: Boolean functions, unitaries, and quantum states. We show that these problems are not trivially in NP but in QCMA (or have QCMA protocols). Next, we explore the relations between the three quantum MCSPs and their variants. We discover that some reductions that are not known for classical MCSP exist for quantum MCSPs for unitaries and states, e.g., search-to-decision reductions and self-reductions. Finally, we systematically generalize results known for classical MCSP to the quantum setting (including quantum cryptography, quantum learning theory, quantum circuit lower bounds, and quantum fine-grained complexity) and also find new connections to tomography and quantum gravity. Due to the fundamental differences between classical and quantum circuits, most of our results require extra care and reveal properties and phenomena unique to the quantum setting. Our findings could be of interest for future studies, and we post several open problems for further exploration along this direction.
Cite as

Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, and Ruizhe Zhang. Quantum Meets the Minimum Circuit Size Problem. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 47:1-47:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chia_et_al:LIPIcs.ITCS.2022.47,
  author =	{Chia, Nai-Hui and Chou, Chi-Ning and Zhang, Jiayu and Zhang, Ruizhe},
  title =	{{Quantum Meets the Minimum Circuit Size Problem}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{47:1--47:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.47},
  URN =		{urn:nbn:de:0030-drops-156433},
  doi =		{10.4230/LIPIcs.ITCS.2022.47},
  annote =	{Keywords: Quantum Computation, Quantum Complexity, Minimum Circuit Size Problem}
}
Document
DOI: 10.4230/OASIcs.VLUDS.2011.59
CFD Simulation of Liquid-Liquid Extraction Columns and Visualization of Eulerian Datasets

Authors: Mark W. Hlawitschka, Fang Chen, Hans-Jörg Bart, and Bernd Hamann

Published in: OASIcs, Volume 27, Visualization of Large and Unstructured Data Sets: Applications in Geospatial Planning, Modeling and Engineering - Proceedings of IRTG 1131 Workshop 2011

Abstract
In this joint work, a complete framework for modeling, simulating and visualizing multiphase fluid flow within an extraction column is presented. We first present a volume-of-fluid simulation, which is able to predict the surface of the droplets during coalescence. However, a fast and efficient model is needed for the simulation of a liquid-liquid extraction column due to the high number of occurring droplets. To simulate the velocity and droplet size in a DN32 extraction column, a coupled computational fluid dynamic-population balance model solver is used. The simulation is analyzed using path-line based visualization techniques. A novel semi-automatic re-seeding technique for droplet path-line integration is proposed. With our technique, path-lines of fluid droplets can be re-initialized after contact with the stirring devices. The droplet breakage is captured, allowing the engineer to improve the design of liquid-liquid columns layout.
Cite as

Mark W. Hlawitschka, Fang Chen, Hans-Jörg Bart, and Bernd Hamann. CFD Simulation of Liquid-Liquid Extraction Columns and Visualization of Eulerian Datasets. In Visualization of Large and Unstructured Data Sets: Applications in Geospatial Planning, Modeling and Engineering - Proceedings of IRTG 1131 Workshop 2011. Open Access Series in Informatics (OASIcs), Volume 27, pp. 59-70, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{hlawitschka_et_al:OASIcs.VLUDS.2011.59,
  author =	{Hlawitschka, Mark W. and Chen, Fang and Bart, Hans-J\"{o}rg and Hamann, Bernd},
  title =	{{CFD Simulation of Liquid-Liquid Extraction Columns and Visualization of Eulerian Datasets}},
  booktitle =	{Visualization of Large and Unstructured Data Sets: Applications in Geospatial Planning, Modeling and Engineering - Proceedings of IRTG 1131 Workshop 2011},
  pages =	{59--70},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-46-0},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{27},
  editor =	{Garth, Christoph and Middel, Ariane and Hagen, Hans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.VLUDS.2011.59},
  URN =		{urn:nbn:de:0030-drops-37410},
  doi =		{10.4230/OASIcs.VLUDS.2011.59},
  annote =	{Keywords: computational fluid dynamics, multiphase fluid, droplet collision, Eule- rian, path-line}
}
Document
DOI: 10.4230/OASIcs.VLUDS.2010.11
A Survey of Interface Tracking Methods in Multi-phase Fluid Visualization

Authors: Fang Chen and Hans Hagen

Published in: OASIcs, Volume 19, Visualization of Large and Unstructured Data Sets - Applications in Geospatial Planning, Modeling and Engineering (IRTG 1131 Workshop) (2011)

Abstract
A central feature that scientists are interested in is the dynamics of fluid interfaces or the so called material boundaries in multi-fluid simulation . Visualization techniques for capturing fluid interface are based on one of about three basic algorithms. In this paper, we give a survey of the existing interface tracking algorithms, including backgrounds, terms, procedures as well as pointers to details and further reading. We also provide a glance at the mathematical fundamentals of multi-fluid dynamics for scientists who are interested in understanding the underlying math and physics of multi-phase fluid simulation.
Cite as

Fang Chen and Hans Hagen. A Survey of Interface Tracking Methods in Multi-phase Fluid Visualization. In Visualization of Large and Unstructured Data Sets - Applications in Geospatial Planning, Modeling and Engineering (IRTG 1131 Workshop). Open Access Series in Informatics (OASIcs), Volume 19, pp. 11-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:OASIcs.VLUDS.2010.11,
  author =	{Chen, Fang and Hagen, Hans},
  title =	{{A Survey of Interface Tracking Methods in Multi-phase Fluid Visualization}},
  booktitle =	{Visualization of Large and Unstructured Data Sets - Applications in Geospatial Planning, Modeling and Engineering (IRTG 1131 Workshop)},
  pages =	{11--19},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-29-3},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{19},
  editor =	{Middel, Ariane and Scheler, Inga and Hagen, Hans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.VLUDS.2010.11},
  URN =		{urn:nbn:de:0030-drops-30914},
  doi =		{10.4230/OASIcs.VLUDS.2010.11},
  annote =	{Keywords: Multi-phase fluid, interface tracking, topology methods}
}
Document
DOI: 10.4230/DFU.SciViz.2010.11
Computing an Optimal Layout for Cone Trees

Authors: Dirk Zeckzer, Fang Chen, and Hans Hagen

Published in: Dagstuhl Follow-Ups, Volume 1, Scientific Visualization: Advanced Concepts (2010)

Abstract
Many visual representations for trees have been developed in information and software visualization. One of them are cone trees, a well-known three-dimensional representation for trees. This paper is based on an approach for constructing cone trees bottom-up. For this approach, an optimal layout for these trees is given together with a proof that based on the assumptions, there can be no better layouts. This comprises special cases, an optimal constant for the general case, and a post-processing step improving the layout.
Cite as

Dirk Zeckzer, Fang Chen, and Hans Hagen. Computing an Optimal Layout for Cone Trees. In Scientific Visualization: Advanced Concepts. Dagstuhl Follow-Ups, Volume 1, pp. 11-29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InCollection{zeckzer_et_al:DFU.SciViz.2010.11,
  author =	{Zeckzer, Dirk and Chen, Fang and Hagen, Hans},
  title =	{{Computing an Optimal Layout for Cone Trees}},
  booktitle =	{Scientific Visualization: Advanced Concepts},
  pages =	{11--29},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-939897-19-4},
  ISSN =	{1868-8977},
  year =	{2010},
  volume =	{1},
  editor =	{Hagen, Hans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.SciViz.2010.11},
  URN =		{urn:nbn:de:0030-drops-26947},
  doi =		{10.4230/DFU.SciViz.2010.11},
  annote =	{Keywords: Cone Trees, Information Visualization, Tree Layout}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2009.2302
Mediating for Reduction (on Minimizing Alternating Büchi Automata)

Authors: Parosh A. Abdulla, Yu-Fang Chen, Lukas Holik, and Tomas Vojnar

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

Abstract
We propose a new approach for minimizing alternating B\"uchi automata (ABA). The approach is based on the so called \emph{mediated equivalence} on states of ABA, which is the maximal equivalence contained in the so called \emph{mediated preorder}. Two states $p$ and $q$ can be related by the mediated preorder if there is a~\emph{mediator} (mediating state) which forward simulates $p$ and backward simulates $q$. Under some further conditions, letting a computation on some word jump from $q$ to $p$ (due to they get collapsed) preserves the language as the automaton can anyway already accept the word without jumps by runs through the mediator. We further show how the mediated equivalence can be computed efficiently. Finally, we show that, compared to the standard forward simulation equivalence, the mediated equivalence can yield much more significant reductions when applied within the process of complementing B\"uchi automata where ABA are used as an intermediate model.
Cite as

Parosh A. Abdulla, Yu-Fang Chen, Lukas Holik, and Tomas Vojnar. Mediating for Reduction (on Minimizing Alternating Büchi Automata). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{abdulla_et_al:LIPIcs.FSTTCS.2009.2302,
  author =	{Abdulla, Parosh A. and Chen, Yu-Fang and Holik, Lukas and Vojnar, Tomas},
  title =	{{Mediating for Reduction (on Minimizing Alternating B\"{u}chi Automata)}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{1--12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2302},
  URN =		{urn:nbn:de:0030-drops-23027},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2302},
  annote =	{Keywords: Alternating Automata, Buchi Automata, Automata Minimization, Buchi Automata Complementation, Simulation Preorder, forward and backward simulation, mediated equivalence}
}
  • Refine by Author
  • 3 Chen, Fang
  • 2 Hagen, Hans
  • 1 Abdulla, Parosh A.
  • 1 Bart, Hans-Jörg
  • 1 Chen, Yu-Fang
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Quantum complexity theory

  • Refine by Keyword
  • 1 Alternating Automata
  • 1 Automata Minimization
  • 1 Buchi Automata
  • 1 Buchi Automata Complementation
  • 1 Cone Trees
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 1 2009
  • 1 2010
  • 1 2011
  • 1 2012
  • 1 2022

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 Imprint Privacy Contact