28 Search Results for "Brandao, Fernando"


Volume

LIPIcs, Volume 22

8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)

TQC 2013, May 21-23, 2013, Guelph, Canada

Editors: Simone Severini and Fernando Brandao

Document
Fast and Robust Quantum State Tomography from Few Basis Measurements

Authors: Daniel Stilck França, Fernando G.S L. Brandão, and Richard Kueng

Published in: LIPIcs, Volume 197, 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)


Abstract
Quantum state tomography is a powerful but resource-intensive, general solution for numerous quantum information processing tasks. This motivates the design of robust tomography procedures that use relevant resources as sparingly as possible. Important cost factors include the number of state copies and measurement settings, as well as classical postprocessing time and memory. In this work, we present and analyze an online tomography algorithm designed to optimize all the aforementioned resources at the cost of a worse dependence on accuracy. The protocol is the first to give provably optimal performance in terms of rank and dimension for state copies, measurement settings and memory. Classical runtime is also reduced substantially and numerical experiments demonstrate a favorable comparison with other state-of-the-art techniques. Further improvements are possible by executing the algorithm on a quantum computer, giving a quantum speedup for quantum state tomography.

Cite as

Daniel Stilck França, Fernando G.S L. Brandão, and Richard Kueng. Fast and Robust Quantum State Tomography from Few Basis Measurements. In 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 197, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{franca_et_al:LIPIcs.TQC.2021.7,
  author =	{Fran\c{c}a, Daniel Stilck and Brand\~{a}o, Fernando G.S L. and Kueng, Richard},
  title =	{{Fast and Robust Quantum State Tomography from Few Basis Measurements}},
  booktitle =	{16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021)},
  pages =	{7:1--7:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-198-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{197},
  editor =	{Hsieh, Min-Hsiu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2021.7},
  URN =		{urn:nbn:de:0030-drops-140023},
  doi =		{10.4230/LIPIcs.TQC.2021.7},
  annote =	{Keywords: quantum tomography, low-rank tomography, Gibbs states, random measurements}
}
Document
Track A: Algorithms, Complexity and Games
Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning

Authors: Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)


Abstract
We give two new quantum algorithms for solving semidefinite programs (SDPs) providing quantum speed-ups. We consider SDP instances with m constraint matrices, each of dimension n, rank at most r, and sparsity s. The first algorithm assumes an input model where one is given access to an oracle to the entries of the matrices at unit cost. We show that it has run time O~(s^2 (sqrt{m} epsilon^{-10} + sqrt{n} epsilon^{-12})), with epsilon the error of the solution. This gives an optimal dependence in terms of m, n and quadratic improvement over previous quantum algorithms (when m ~~ n). The second algorithm assumes a fully quantum input model in which the input matrices are given as quantum states. We show that its run time is O~(sqrt{m}+poly(r))*poly(log m,log n,B,epsilon^{-1}), with B an upper bound on the trace-norm of all input matrices. In particular the complexity depends only polylogarithmically in n and polynomially in r. We apply the second SDP solver to learn a good description of a quantum state with respect to a set of measurements: Given m measurements and a supply of copies of an unknown state rho with rank at most r, we show we can find in time sqrt{m}*poly(log m,log n,r,epsilon^{-1}) a description of the state as a quantum circuit preparing a density matrix which has the same expectation values as rho on the m measurements, up to error epsilon. The density matrix obtained is an approximation to the maximum entropy state consistent with the measurement data considered in Jaynes' principle from statistical mechanics. As in previous work, we obtain our algorithm by "quantizing" classical SDP solvers based on the matrix multiplicative weight update method. One of our main technical contributions is a quantum Gibbs state sampler for low-rank Hamiltonians, given quantum states encoding these Hamiltonians, with a poly-logarithmic dependence on its dimension, which is based on ideas developed in quantum principal component analysis. We also develop a "fast" quantum OR lemma with a quadratic improvement in gate complexity over the construction of Harrow et al. [Harrow et al., 2017]. We believe both techniques might be of independent interest.

Cite as

Fernando G. S. L. Brandão, Amir Kalev, Tongyang Li, Cedric Yen-Yu Lin, Krysta M. Svore, and Xiaodi Wu. Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{brandao_et_al:LIPIcs.ICALP.2019.27,
  author =	{Brand\~{a}o, Fernando G. S. L. and Kalev, Amir and Li, Tongyang and Lin, Cedric Yen-Yu and Svore, Krysta M. and Wu, Xiaodi},
  title =	{{Quantum SDP Solvers: Large Speed-Ups, Optimality, and Applications to Quantum Learning}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.27},
  URN =		{urn:nbn:de:0030-drops-106036},
  doi =		{10.4230/LIPIcs.ICALP.2019.27},
  annote =	{Keywords: quantum algorithms, semidefinite program, convex optimization}
}
Document
Track A: Algorithms, Complexity and Games
Improvements in Quantum SDP-Solving with Applications

Authors: Joran van Apeldoorn and András Gilyén

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)


Abstract
Following the first paper on quantum algorithms for SDP-solving by Brandão and Svore [Brandão and Svore, 2017] in 2016, rapid developments have been made on quantum optimization algorithms. In this paper we improve and generalize all prior quantum algorithms for SDP-solving and give a simpler and unified framework. We take a new perspective on quantum SDP-solvers and introduce several new techniques. One of these is the quantum operator input model, which generalizes the different input models used in previous work, and essentially any other reasonable input model. This new model assumes that the input matrices are embedded in a block of a unitary operator. In this model we give a O~((sqrt{m}+sqrt{n}gamma)alpha gamma^4) algorithm, where n is the size of the matrices, m is the number of constraints, gamma is the reciprocal of the scale-invariant relative precision parameter, and alpha is a normalization factor of the input matrices. In particular for the standard sparse-matrix access, the above result gives a quantum algorithm where alpha=s. We also improve on recent results of Brandão et al. [Fernando G. S. L. Brandão et al., 2018], who consider the special case when the input matrices are proportional to mixed quantum states that one can query. For this model Brandão et al. [Fernando G. S. L. Brandão et al., 2018] showed that the dependence on n can be replaced by a polynomial dependence on both the rank and the trace of the input matrices. We remove the dependence on the rank and hence require only a dependence on the trace of the input matrices. After we obtain these results we apply them to a few different problems. The most notable of which is the problem of shadow tomography, recently introduced by Aaronson [Aaronson, 2018]. Here we simultaneously improve both the sample and computational complexity of the previous best results. Finally we prove a new Omega~(sqrt{m}alpha gamma) lower bound for solving LPs and SDPs in the quantum operator model, which also implies a lower bound for the model of Brandão et al. [Fernando G. S. L. Brandão et al., 2018].

Cite as

Joran van Apeldoorn and András Gilyén. Improvements in Quantum SDP-Solving with Applications. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 99:1-99:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{vanapeldoorn_et_al:LIPIcs.ICALP.2019.99,
  author =	{van Apeldoorn, Joran and Gily\'{e}n, Andr\'{a}s},
  title =	{{Improvements in Quantum SDP-Solving with Applications}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{99:1--99:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.99},
  URN =		{urn:nbn:de:0030-drops-106750},
  doi =		{10.4230/LIPIcs.ICALP.2019.99},
  annote =	{Keywords: quantum algorithms, semidefinite programming, shadow tomography}
}
Document
Complete Volume
LIPIcs, Volume 22, TQC'13, Complete Volume

Authors: Simone Severini and Fernando Brandao

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)


Abstract
LIPIcs, Volume 22, TQC'13, Complete Volume

Cite as

8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@Proceedings{severini_et_al:LIPIcs.TQC.2013,
  title =	{{LIPIcs, Volume 22, TQC'13, Complete Volume}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013},
  URN =		{urn:nbn:de:0030-drops-43480},
  doi =		{10.4230/LIPIcs.TQC.2013},
  annote =	{Keywords: Data Encryption, Coding and Information Theory, Theory of Computation}
}
Document
Front Matter
Frontmatter, Table of Contents, Preface, Conference Organization

Authors: Simone Severini and Fernando Brandao

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)


Abstract
Frontmatter, Table of Contents, Preface, Conference Organization

Cite as

8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. i-x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{severini_et_al:LIPIcs.TQC.2013.i,
  author =	{Severini, Simone and Brandao, Fernando},
  title =	{{Frontmatter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{i--x},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.i},
  URN =		{urn:nbn:de:0030-drops-43081},
  doi =		{10.4230/LIPIcs.TQC.2013.i},
  annote =	{Keywords: Frontmatter, Table of Contents, Preface, Conference Organization}
}
Document
Ancilla Driven Quantum Computation with Arbitrary Entangling Strength

Authors: Kerem Halil Shah and Daniel K.L. Oi

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)


Abstract
We extend the model of Ancilla Driven Quantum Computation (ADQC) by considering gates with arbitrary entangling power. By giving up stepwise determinism, universal QC can still be achieved through a variable length sequence of single qubit gates and probabilistic "repeat-until-succes" entangling operations. This opens up a new range of possible physical implementations as well as shedding light on the sets of resources sufficient for universal QC.

Cite as

Kerem Halil Shah and Daniel K.L. Oi. Ancilla Driven Quantum Computation with Arbitrary Entangling Strength. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{halilshah_et_al:LIPIcs.TQC.2013.1,
  author =	{Halil Shah, Kerem and Oi, Daniel K.L.},
  title =	{{Ancilla Driven Quantum Computation with Arbitrary Entangling Strength}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{1--19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.1},
  URN =		{urn:nbn:de:0030-drops-43094},
  doi =		{10.4230/LIPIcs.TQC.2013.1},
  annote =	{Keywords: Ancilla, weak measurement, quantum computation, entanglement, random walks}
}
Document
Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem

Authors: Greg Kuperberg

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)


Abstract
We give an algorithm for the hidden subgroup problem for the dihedral group D_N, or equivalently the cyclic hidden shift problem, that supersedes our first algorithm and is suggested by Regev's algorithm. It runs in exp(O(sqrt(log N))) quantum time and uses exp(O(sqrt(log N))) classical space, but only O(log N) quantum space. The algorithm also runs faster with quantumly addressable classical space than with fully classical space. In the hidden shift form, which is more natural for this algorithm regardless, it can also make use of multiple hidden shifts. It can also be extended with two parameters that trade classical space and classical time for quantum time. At the extreme space-saving end, the algorithm becomes Regev's algorithm. At the other end, if the algorithm is allowed classical memory with quantum random access, then many trade-offs between classical and quantum time are possible.

Cite as

Greg Kuperberg. Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. 20-34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{kuperberg:LIPIcs.TQC.2013.20,
  author =	{Kuperberg, Greg},
  title =	{{Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{20--34},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.20},
  URN =		{urn:nbn:de:0030-drops-43213},
  doi =		{10.4230/LIPIcs.TQC.2013.20},
  annote =	{Keywords: quantum algorithm, hidden subgroup problem, sieve, subexponential time}
}
Document
Universal Entanglers for Bosonic and Fermionic Systems

Authors: Joel Klassen, Jianxin Chen, and Bei Zeng

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)


Abstract
A universal entangler (UE) is a unitary operation which maps all pure product states to entangled states. It is known that for a bipartite system of particles 1,2 with a Hilbert space C^{d_1} otimes C^{d_2}, a UE exists when min(d_1,d_2) >= 3 and (d_1,d_2) != (3,3). It is also known that whenever a UE exists, almost all unitaries are UEs; however to verify whether a given unitary is a UE is very difficult since solving a quadratic system of equations is NP-hard in general. This work examines the existence and construction of UEs of bipartite bosonic/fermionic systems whose wave functions sit in the symmetric/antisymmetric subspace of C^d otimes C^d. The development of a theory of UEs for these types of systems needs considerably different approaches from that used for UEs of distinguishable systems. This is because the general entanglement of identical particle systems cannot be discussed in the usual way due to the effect of (anti)-symmetrization which introduces "pseudo entanglement" that is inaccessible in practice. We show that, unlike the distinguishable particle case, UEs exist for bosonic/fermionic systems with Hilbert spaces which are symmetric (resp. antisymmetric) subspaces of C^d otimes C^d if and only if d >= 3 (resp. d >= 8). To prove this we employ algebraic geometry to reason about the different algebraic structures of the bosonic/fermionic systems. Additionally, due to the relatively simple coherent state form of unentangled bosonic states, we are able to give the explicit constructions of two bosonic UEs. Our investigation provides insight into the entanglement properties of systems of indistinguishable particles, and in particular underscores the difference between the entanglement structures of bosonic, fermionic and distinguishable particle systems.

Cite as

Joel Klassen, Jianxin Chen, and Bei Zeng. Universal Entanglers for Bosonic and Fermionic Systems. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. 35-49, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{klassen_et_al:LIPIcs.TQC.2013.35,
  author =	{Klassen, Joel and Chen, Jianxin and Zeng, Bei},
  title =	{{Universal Entanglers for Bosonic and Fermionic Systems}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{35--49},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.35},
  URN =		{urn:nbn:de:0030-drops-43223},
  doi =		{10.4230/LIPIcs.TQC.2013.35},
  annote =	{Keywords: Universal Entangler, Bosonic States, Fermionic States}
}
Document
Easy and Hard Functions for the Boolean Hidden Shift Problem

Authors: Andrew M. Childs, Robin Kothari, Maris Ozols, and Martin Roetteler

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)


Abstract
We study the quantum query complexity of the Boolean hidden shift problem. Given oracle access to f(x+s) for a known Boolean function f, the task is to determine the n-bit string s. The quantum query complexity of this problem depends strongly on f. We demonstrate that the easiest instances of this problem correspond to bent functions, in the sense that an exact one-query algorithm exists if and only if the function is bent. We partially characterize the hardest instances, which include delta functions. Moreover, we show that the problem is easy for random functions, since two queries suffice. Our algorithm for random functions is based on performing the pretty good measurement on several copies of a certain state; its analysis relies on the Fourier transform. We also use this approach to improve the quantum rejection sampling approach to the Boolean hidden shift problem.

Cite as

Andrew M. Childs, Robin Kothari, Maris Ozols, and Martin Roetteler. Easy and Hard Functions for the Boolean Hidden Shift Problem. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. 50-79, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{childs_et_al:LIPIcs.TQC.2013.50,
  author =	{Childs, Andrew M. and Kothari, Robin and Ozols, Maris and Roetteler, Martin},
  title =	{{Easy and Hard Functions for the Boolean Hidden Shift Problem}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{50--79},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.50},
  URN =		{urn:nbn:de:0030-drops-43203},
  doi =		{10.4230/LIPIcs.TQC.2013.50},
  annote =	{Keywords: Boolean hidden shift problem, quantum algorithms, query complexity, Fourier transform, bent functions}
}
Document
Dequantizing Read-once Quantum Formulas

Authors: Alessandro Cosentino, Robin Kothari, and Adam Paetznick

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)


Abstract
Quantum formulas, defined by Yao [FOCS'93], are the quantum analogs of classical formulas, i.e., classical circuits in which all gates have fanout one. We show that any read-once quantum formula over a gate set that contains all single-qubit gates is equivalent to a read-once classical formula of the same size and depth over an analogous classical gate set. For example, any read-once quantum formula over Toffoli and single-qubit gates is equivalent to a read-once classical formula over Toffoli and NOT gates. We then show that the equivalence does not hold if the read-once restriction is removed. To show the power of quantum formulas without the read-once restriction, we define a new model of computation called the one-qubit model and show that it can compute all boolean functions. This model may also be of independent interest.

Cite as

Alessandro Cosentino, Robin Kothari, and Adam Paetznick. Dequantizing Read-once Quantum Formulas. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. 80-92, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{cosentino_et_al:LIPIcs.TQC.2013.80,
  author =	{Cosentino, Alessandro and Kothari, Robin and Paetznick, Adam},
  title =	{{Dequantizing Read-once Quantum Formulas}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{80--92},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.80},
  URN =		{urn:nbn:de:0030-drops-43197},
  doi =		{10.4230/LIPIcs.TQC.2013.80},
  annote =	{Keywords: formulas, dequantization, circuit complexity}
}
Document
The Minimum Size of Qubit Unextendible Product Bases

Authors: Nathaniel Johnston

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)


Abstract
We investigate the problem of constructing unextendible product bases in the qubit case - that is, when each local dimension equals 2. The cardinality of the smallest unextendible product basis is known in all qubit cases except when the number of parties is a multiple of 4 greater than 4 itself. We construct small unextendible product bases in all of the remaining open cases, and we use graph theory techniques to produce a computer-assisted proof that our constructions are indeed the smallest possible.

Cite as

Nathaniel Johnston. The Minimum Size of Qubit Unextendible Product Bases. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. 93-105, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{johnston:LIPIcs.TQC.2013.93,
  author =	{Johnston, Nathaniel},
  title =	{{The Minimum Size of Qubit Unextendible Product Bases}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{93--105},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.93},
  URN =		{urn:nbn:de:0030-drops-43173},
  doi =		{10.4230/LIPIcs.TQC.2013.93},
  annote =	{Keywords: unextendible product basis; quantum entanglement; graph factorization}
}
Document
Robust Online Hamiltonian Learning

Authors: Christopher E. Granade, Christopher Ferrie, Nathan Wiebe, and D. G. Cory

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)


Abstract
In this work we combine two distinct machine learning methodologies, sequential Monte Carlo and Bayesian experimental design, and apply them to the problem of inferring the dynamical parameters of a quantum system. The algorithm can be implemented online (during experimental data collection), avoiding the need for storage and post-processing. Most importantly, our algorithm is capable of learning Hamiltonian parameters even when the parameters change from experiment-to-experiment, and also when additional noise processes are present and unknown. The algorithm also numerically estimates the Cramer-Rao lower bound, certifying its own performance. We further illustrate the practicality of our algorithm by applying it to two test problems: (1) learning an unknown frequency and the decoherence time for a single-qubit quantum system and (2) learning couplings in a many-qubit Ising model Hamiltonian with no external magnetic field.

Cite as

Christopher E. Granade, Christopher Ferrie, Nathan Wiebe, and D. G. Cory. Robust Online Hamiltonian Learning. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. 106-125, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{granade_et_al:LIPIcs.TQC.2013.106,
  author =	{Granade, Christopher E. and Ferrie, Christopher and Wiebe, Nathan and Cory, D. G.},
  title =	{{Robust Online Hamiltonian Learning}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{106--125},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.106},
  URN =		{urn:nbn:de:0030-drops-43185},
  doi =		{10.4230/LIPIcs.TQC.2013.106},
  annote =	{Keywords: Quantum information, sequential Monte Carlo, Bayesian, experiment design, parameter estimation}
}
Document
Classical and Quantum Algorithms for Testing Equivalence of Group Extensions

Authors: Kevin C. Zatloukal

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)


Abstract
While efficient algorithms are known for solving many important problems related to groups, no efficient algorithm is known for determining whether two arbitrary groups are isomorphic. The particular case of 2-nilpotent groups, a special type of central extension, is widely believed to contain the essential hard cases. However, looking specifically at central extensions, the natural formulation of being "the same" is not isomorphism but rather "equivalence," which requires an isomorphism to preserves the structure of the extension. In this paper, we show that equivalence of central extensions can be computed efficiently on a classical computer when the groups are small enough to be given by their multiplication tables. However, in the model of black box groups, which allows the groups to be much larger, we show that equivalence can be computed efficiently on a quantum computer but not a classical one (under common complexity assumptions). Our quantum algorithm demonstrates a new application of the hidden subgroup problem for general abelian groups.

Cite as

Kevin C. Zatloukal. Classical and Quantum Algorithms for Testing Equivalence of Group Extensions. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. 126-145, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{zatloukal:LIPIcs.TQC.2013.126,
  author =	{Zatloukal, Kevin C.},
  title =	{{Classical and Quantum Algorithms for Testing Equivalence of Group Extensions}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{126--145},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.126},
  URN =		{urn:nbn:de:0030-drops-43164},
  doi =		{10.4230/LIPIcs.TQC.2013.126},
  annote =	{Keywords: quantum computing, algorithms, computational group theory}
}
Document
Provable Advantage for Quantum Strategies in Random Symmetric XOR Games

Authors: Andris Ambainis and Janis Iraids

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)


Abstract
Non-local games are widely studied as a model to investigate the properties of quantum mechanics as opposed to classical mechanics. In this paper, we consider a subset of non-local games: symmetric XOR games of n players with 0-1 valued questions. For this class of games, each player receives an input bit and responds with an output bit without communicating to the other players. The winning condition only depends on XOR of output bits and is constant w.r.t. permutation of players. We prove that for almost any n-player symmetric XOR game the entangled value of the game is Theta((sqrt(ln(n)))/(n^{1/4})) adapting an old result by Salem and Zygmund on the asymptotics of random trigonometric polynomials. Consequently, we show that the classical-quantum gap is Theta(sqrt(ln(n))) for almost any symmetric XOR game.

Cite as

Andris Ambainis and Janis Iraids. Provable Advantage for Quantum Strategies in Random Symmetric XOR Games. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. 146-156, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)


Copy BibTex To Clipboard

@InProceedings{ambainis_et_al:LIPIcs.TQC.2013.146,
  author =	{Ambainis, Andris and Iraids, Janis},
  title =	{{Provable Advantage for Quantum Strategies in Random Symmetric XOR Games}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{146--156},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.146},
  URN =		{urn:nbn:de:0030-drops-43156},
  doi =		{10.4230/LIPIcs.TQC.2013.146},
  annote =	{Keywords: Random Symmetric XOR games, Entanglement}
}
  • Refine by Author
  • 2 Ambainis, Andris
  • 2 Brandao, Fernando
  • 2 Chen, Jianxin
  • 2 Chiribella, Giulio
  • 2 Duclos-Cianci, Guillaume
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Quantum computation theory
  • 1 Hardware → Quantum technologies
  • 1 Mathematics of computing → Probabilistic inference problems
  • 1 Theory of computation → Convex optimization
  • 1 Theory of computation → Quantum information theory
  • Show More...

  • Refine by Keyword
  • 3 quantum algorithms
  • 2 quantum computing
  • 2 query complexity
  • 1 2D
  • 1 Access structure
  • Show More...

  • Refine by Type
  • 27 document
  • 1 volume

  • Refine by Publication Year
  • 25 2013
  • 2 2019
  • 1 2021

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