BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Shir Peleg

Shir Peleg contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational ComplexityComputational GeometryData Structures and Algorithmsquant-ph

Trust snapshot

Quick read

Trust 19 - UnverifiedVerification L1Unclaimed author
5works
0followers
4topics
2close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

5 published item(s)

preprint2022arXiv

Lower Bounds on Stabilizer Rank

The stabilizer rank of a quantum state $ψ$ is the minimal $r$ such that $\left| ψ\right \rangle = \sum_{j=1}^r c_j \left|φ_j \right\rangle$ for $c_j \in \mathbb{C}$ and stabilizer states $φ_j$. The running time of several classical simulation methods for quantum circuits is determined by the stabilizer rank of the $n$-th tensor power of single-qubit magic states. We prove a lower bound of $Ω(n)$ on the stabilizer rank of such states, improving a previous lower bound of $Ω(\sqrt{n})$ of Bravyi, Smith and Smolin (arXiv:1506.01396). Further, we prove that for a sufficiently small constant $δ$, the stabilizer rank of any state which is $δ$-close to those states is $Ω(\sqrt{n}/\log n)$. This is the first non-trivial lower bound for approximate stabilizer rank. Our techniques rely on the representation of stabilizer states as quadratic functions over affine subspaces of $\mathbb{F}_2^n$, and we use tools from analysis of boolean functions and complexity theory. The proof of the first result involves a careful analysis of directional derivatives of quadratic polynomials, whereas the proof of the second result uses Razborov-Smolensky low degree polynomial approximations and correlation bounds against the majority function.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Robust Sylvester-Gallai type theorem for quadratic polynomials

In this work, we extend the robust version of the Sylvester-Gallai theorem, obtained by Barak, Dvir, Wigderson and Yehudayoff, and by Dvir, Saraf and Wigderson, to the case of quadratic polynomials. Specifically, we prove that if $\mathcal{Q}\subset \mathbb{C}[x_1.\ldots,x_n]$ is a finite set, $|\mathcal{Q}|=m$, of irreducible quadratic polynomials that satisfy the following condition: There is $δ>0$ such that for every $Q\in\mathcal{Q}$ there are at least $δm$ polynomials $P\in \mathcal{Q}$ such that whenever $Q$ and $P$ vanish then so does a third polynomial in $\mathcal{Q}\setminus\{Q,P\}$, then $\dim(\text{span}({\mathcal{Q}}))=\text{poly}(1/δ)$. The work of Barak et al. and Dvir et al. studied the case of linear polynomials and proved an upper bound of $O(1/δ)$ on the dimension (in the first work an upper bound of $O(1/δ^2)$ was given, which was improved to $O(1/δ)$ in the second work).

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Tensor Reconstruction Beyond Constant Rank

We give reconstruction algorithms for subclasses of depth-3 arithmetic circuits. In particular, we obtain the first efficient algorithm for finding tensor rank, and an optimal tensor decomposition as a sum of rank-one tensors, when given black-box access to a tensor of super-constant rank. We obtain the following results: 1. A deterministic algorithm that reconstructs polynomials computed by $Σ^{[k]}\bigwedge^{[d]}Σ$ circuits in time $\mathsf{poly}(n,d,c) \cdot \mathsf{poly}(k)^{k^{k^{10}}}$ 2. A randomized algorithm that reconstructs polynomials computed by multilinear $Σ^{k]}\prod^{[d]}Σ$ circuits in time $\mathsf{poly}(n,d,c) \cdot k^{k^{k^{k^{O(k)}}}}$ 3. A randomized algorithm that reconstructs polynomials computed by set-multilinear $Σ^{k]}\prod^{[d]}Σ$ circuits in time $\mathsf{poly}(n,d,c) \cdot k^{k^{k^{k^{O(k)}}}}$, where $c=\log q$ if $\mathbb{F}=\mathbb{F}_q$ is a finite field, and $c$ equals the maximum bit complexity of any coefficient of $f$ if $\mathbb{F}$ is infinite. Prior to our work, polynomial time algorithms for the case when the rank, $k$, is constant, were given by Bhargava, Saraf and Volkovich [BSV21]. Another contribution of this work is correcting an error from a paper of Karnin and Shpilka [KS09] that affected Theorem 1.6 of [BSV21]. Consequently, the results of [KS09, BSV21] continue to hold, with a slightly worse setting of parameters. For fixing the error we study the relation between syntactic and semantic ranks of $ΣΠΣ$ circuits. We obtain our improvement by introducing a technique for learning rank preserving coordinate-subspaces. [KS09] and [BSV21] tried all choices of finding the "correct" coordinates, which led to having a fast growing function of $k$ at the exponent of $n$. We find these spaces in time that is growing fast with $k$, yet it is only a fixed polynomial in $n$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A generalized Sylvester-Gallai type theorem for quadratic polynomials

In this work we prove a version of the Sylvester-Gallai theorem for quadratic polynomials that takes us one step closer to obtaining a deterministic polynomial time algorithm for testing zeroness of $Σ^{[3]}ΠΣΠ^{[2]}$ circuits. Specifically, we prove that if a finite set of irreducible quadratic polynomials $\mathcal{Q}$ satisfy that for every two polynomials $Q_1,Q_2\in \mathcal{Q}$ there is a subset $\mathcal{K}\subset \mathcal{Q}$, such that $Q_1,Q_2 \notin \mathcal{K}$ and whenever $Q_1$ and $Q_2$ vanish then also $\prod_{i\in \mathcal{K}} Q_i$ vanishes, then the linear span of the polynomials in $\mathcal{Q}$ has dimension $O(1)$. This extends the earlier result [Shpilka19] that showed a similar conclusion when $|\mathcal{K}| = 1$. An important technical step in our proof is a theorem classifying all the possible cases in which a product of quadratic polynomials can vanish when two other quadratic polynomials vanish. I.e., when the product is in the radical of the ideal generates by the two quadratics. This step extends a result from [Shpilka19]that studied the case when one quadratic polynomial is in the radical of two other quadratics.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Polynomial time deterministic identity testingalgorithm for $Σ^{[3]}ΠΣΠ^{[2]}$ circuits via Edelstein-Kelly type theorem for quadratic polynomials

In this work we resolve conjectures of Beecken, Mitmann and Saxena [BMS13] and Gupta [Gup14], by proving an analog of a theorem of Edelstein and Kelly for quadratic polynomials. As immediate corollary we obtain the first deterministic polynomial time black-box algorithm for testing zeroness of $Σ^{[3]}ΠΣΠ^{[2]}$ circuits.

0 citations0 reviewsNo code linkedOpen access