BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Partha Mukhopadhyay

Partha Mukhopadhyay appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
hep-thComputational ComplexityData Structures and AlgorithmsDiscrete MathematicsFormal Languages and Automata Theorygr-qcquant-ph

Catalog footprint

What is connected

20works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

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

Published work

20 published item(s)

preprint2022arXiv

Black-box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial-time

Hrubeš and Wigderson (2015) initiated the complexity-theoretic study of noncommutative formulas with inverse gates. They introduced the Rational Identity Testing (RIT) problem which is to decide whether a noncommutative rational formula computes zero in the free skew field. In the white-box setting, deterministic polynomial-time algorithms are known for this problem following the works of Garg, Gurvits, Oliveira, and Wigderson (2016) and Ivanyos, Qiao, and Subrahmanyam (2018). A central open problem in this area is to design efficient deterministic black-box identity testing algorithm for rational formulas. In this paper, we solve this problem for the first nested inverse case. More precisely, we obtain a deterministic quasipolynomial-time black-box RIT algorithm for noncommutative rational formulas of inversion height two via a hitting set construction. Several new technical ideas are involved in the hitting set construction, including key concepts from matrix coefficient realization theory (Volčič, 2018) and properties of cyclic division algebra (Lam, 2001). En route to the proof, an important step is to embed the hitting set of Forbes and Shpilka for noncommutative formulas (2013) inside a cyclic division algebra of small index.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On Identity Testing and Noncommutative Rank Computation over the Free Skew Field

The identity testing of rational formulas (RIT) in the free skew field efficiently reduces to computing the rank of a matrix whose entries are linear polynomials in noncommuting variables\cite{HW15}. This rank computation problem has deterministic polynomial-time white-box algorithms \cite{GGOW16, IQS18} and a randomized polynomial-time algorithm in the black-box setting \cite{DM17}. In this paper, we propose a new approach for efficient derandomization of \emph{black-box} RIT. Additionally, we obtain results for matrix rank computation over the free skew field, and construct efficient linear pencil representations for a new class of rational expressions. More precisely, we show the following results: 1. Under the hardness assumption that the ABP (algebraic branching program) complexity of every polynomial identity for the $k\times k$ matrix algebra is $2^{Ω(k)}$ \cite{BW05}, we obtain a subexponential-time black-box algorithm for RIT in almost general setting. This can be seen as the first "hardness implies derandomization" type theorem for rational formulas. 2. We show that the noncommutative rank of any matrix over the free skew field whose entries have small linear pencil representations can be computed in deterministic polynomial time. Prior to this, an efficient rank computation was only known for matrices with noncommutative formulas as entries\cite{GGOW20}. As special cases of our algorithm, we obtain the first deterministic polynomial-time algorithms for rank computation of matrices whose entries are noncommutative ABPs or rational formulas. 3. Motivated by the definition given by Bergman\cite{Ber76}, we define a new class that contains noncommutative ABPs and rational formulas. We obtain a polynomial-size linear pencil representation for this class. As a by-product, we obtain a white-box deterministic polynomial-time identity testing algorithm for the class.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Equivalence Testing of Weighted Automata over Partially Commutative Monoids

We study \emph{multiplicity equivalence} testing of automata over partially commutative monoids (pc monoids) and show efficient algorithms in special cases, exploiting the structure of the underlying non-commutation graph of the monoid. Specifically, if the clique cover number of the non-commutation graph (the minimum number of cliques covering the graph) of the pc monoid is a constant, we obtain a deterministic quasi-polynomial time algorithm. As a consequence, we also obtain the first deterministic quasi-polynomial time algorithms for multiplicity equivalence testing of $k$-tape automata and for equivalence testing of deterministic $k$-tape automata for constant $k$. Prior to this, a randomized polynomial-time algorithm for the above problems was shown by Worrell [ICALP 2013]. We also consider pc monoids for which the non-commutation graphs have cover consisting of at most $k$ cliques and star graphs for any constant $k$. We obtain randomized polynomial-time algorithm for multiplicity equivalence testing of automata over such monoids.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fast Exact Algorithms Using Hadamard Product of Polynomials

Let $C$ be an arithmetic circuit of $poly(n)$ size given as input that computes a polynomial $f\in\mathbb{F}[X]$, where $X=\{x_1,x_2,\ldots,x_n\}$ and $\mathbb{F}$ is any field where the field arithmetic can be performed efficiently. We obtain new algorithms for the following two problems first studied by Koutis and Williams \cite{Kou08, Wi09, KW16}. k-MLC: Compute the sum of the coefficients of all degree-$k$ multilinear monomials in the polynomial $f$. k-MMD: Test if there is a nonzero degree-$k$ multilinear monomial in the polynomial $f$. Our algorithms are based on the fact that the Hadamard product $f\circ S_{n,k}$, is the degree-$k$ multilinear part of $f$, where $S_{n,k}$ is the $k^{th}$ elementary symmetric polynomial. 1. For k-MLC problem, we give a deterministic algorithm of run time $O^*(n^{k/2+c\log k})$ (where $c$ is a constant), answering an open question of Koutis and Williams \cite[ICALP'09]{KW16}. As corollaries, we show $O^*(\binom{n}{\downarrow k/2})$-time exact counting algorithms for several combinatorial problems: k-Tree, t-Dominating Set, m-Dimensional k-Matching. 2. For k-MMD problem, we give a randomized algorithm of run time $4.32^k\cdot poly(n,k)$. Our algorithm uses only $poly(n,k)$ space. This matches the run time of a recent algorithm \cite{BDH18} for $k-MMD$ which requires exponential (in $k$) space. Other results include fast deterministic algorithms for k-MLC and k-MMD problems for depth three circuits.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

All order covariant tubular expansion

We consider tubular neighborhood of an arbitrary submanifold embedded in a (pseudo-)Riemannian manifold. This can be described by Fermi normal coordinates (FNC) satisfying certain conditions as described by Florides and Synge in \cite{FS}. By generalizing the work of Muller {\it et al} in \cite{muller} on Riemann normal coordinate expansion, we derive all order FNC expansion of vielbein in this neighborhood with closed form expressions for the curvature expansion coefficients. Our result is shown to be consistent with certain integral theorem for the metric proved in \cite{FS}.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

General Construction of Tubular Geometry

We consider the problem of locally describing tubular geometry around a submanifold embedded in a (pseudo)Riemannian manifold in its general form. Given the geometry of ambient space in an arbitrary coordinate system and equations determining the submanifold in the same system, we compute the tubular expansion coefficients in terms of this {\it a priori data}. This is done by using an indirect method that crucially applies the tubular expansion theorem for vielbein previously derived. With an explicit construction involving the relevant coordinate and non-coordinate frames we verify consistency of the whole method up to quadratic order in vielbein expansion. Furthermore, we perform certain (long and tedious) higher order computation which verifies the first non-trivial spin connection term in the expansion for the first time. Earlier a similar method was used to compute tubular geometry in loop space. We explain this work in the light of our general construction.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Identity Testing for +-Regular Noncommutative Arithmetic Circuits

An efficient randomized polynomial identity test for noncommutative polynomials given by noncommutative arithmetic circuits remains an open problem. The main bottleneck to applying known techniques is that a noncommutative circuit of size $s$ can compute a polynomial of degree exponential in $s$ with a double-exponential number of nonzero monomials. In this paper, we report some progress by dealing with two natural subcases (both allow for polynomials of exponential degree and a double exponential number of monomials): (1) We consider \emph{$+$-regular} noncommutative circuits: these are homogeneous noncommutative circuits with the additional property that all the $+$-gates are layered, and in each $+$-layer all gates have the same syntactic degree. We give a \emph{white-box} polynomial-time deterministic polynomial identity test for such circuits. Our algorithm combines some new structural results for $+$-regular circuits with known results for noncommutative ABP identity testing [RS05PIT], rank bound of commutative depth three identities [SS13], and equivalence testing problem for words [Loh15, MSU97, Pla94]. (2) Next, we consider $ΣΠ^*Σ$ noncommutative circuits: these are noncommutative circuits with layered $+$-gates such that there are only two layers of $+$-gates. These $+$-layers are the output $+$-gate and linear forms at the bottom layer; between the $+$-layers the circuit could have any number of $\times$ gates. We given an efficient randomized \emph{black-box} identity testing problem for $ΣΠ^*Σ$ circuits. In particular, we show if $f\in F<Z>$ is a nonzero noncommutative polynomial computed by a $ΣΠ^*Σ$ circuit of size $s$, then $f$ cannot be a polynomial identity for the matrix algebra $\mathbb{M}_s(F)$, where the field $F$ is a sufficiently large extension of $F$ depending on the degree of $f$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Randomized Polynomial Time Identity Testing for Noncommutative Circuits

In this paper we show that the black-box polynomial identity testing for noncommutative polynomials $f\in\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$ of degree $D$ and sparsity $t$, can be done in randomized $\poly(n,\log t,\log D)$ time. As a consequence, if the black-box contains a circuit $C$ of size $s$ computing $f\in\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$ which has at most $t$ non-zero monomials, then the identity testing can be done by a randomized algorithm with running time polynomial in $s$ and $n$ and $\log t$. This makes significant progress on a question that has been open for over ten years. The earlier result by Bogdanov and Wee [BW05], using the classical Amitsur-Levitski theorem, gives a randomized polynomial-time algorithm only for circuits of polynomially bounded syntactic degree. In our result, we place no restriction on the degree of the circuit. Our algorithm is based on automata-theoretic ideas introduced in [AMS08,AM08]. In those papers, the main idea was to construct deterministic finite automata that isolate a single monomial from the set of nonzero monomials of a polynomial $f$ in $\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$. In the present paper, since we need to deal with exponential degree monomials, we carry out a different kind of monomial isolation using nondeterministic automata.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Depth-4 Lower Bounds, Determinantal Complexity : A Unified Approach

Tavenas has recently proved that any n^{O(1)}-variate and degree n polynomial in VP can be computed by a depth-4 circuit of size 2^{O(\sqrt{n}\log n)}. So to prove VP not equal to VNP, it is sufficient to show that an explicit polynomial in VNP of degree n requires 2^{ω(\sqrt{n}\log n)} size depth-4 circuits. Soon after Tavenas's result, for two different explicit polynomials, depth-4 circuit size lower bounds of 2^{Ω(\sqrt{n}\log n)} have been proved Kayal et al. and Fournier et al. In particular, using combinatorial design Kayal et al.\ construct an explicit polynomial in VNP that requires depth-4 circuits of size 2^{Ω(\sqrt{n}\log n)} and Fournier et al.\ show that iterated matrix multiplication polynomial (which is in VP) also requires 2^{Ω(\sqrt{n}\log n)} size depth-4 circuits. In this paper, we identify a simple combinatorial property such that any polynomial f that satisfies the property would achieve similar circuit size lower bound for depth-4 circuits. In particular, it does not matter whether f is in VP or in VNP. As a result, we get a very simple unified lower bound analysis for the above mentioned polynomials. Another goal of this paper is to compare between our current knowledge of depth-4 circuit size lower bounds and determinantal complexity lower bounds. We prove the that the determinantal complexity of iterated matrix multiplication polynomial is Ω(dn) where d is the number of matrices and n is the dimension of the matrices. So for d=n, we get that the iterated matrix multiplication polynomial achieves the current best known lower bounds in both fronts: depth-4 circuit size and determinantal complexity. To the best of our knowledge, a Θ(n) bound for the determinantal complexity for the iterated matrix multiplication polynomial was known only for constant d>1 by Jansen.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the Limits of Depth Reduction at Depth 3 Over Small Finite Fields

Recently, Gupta et.al. [GKKS2013] proved that over Q any $n^{O(1)}$-variate and $n$-degree polynomial in VP can also be computed by a depth three $ΣΠΣ$ circuit of size $2^{O(\sqrt{n}\log^{3/2}n)}$. Over fixed-size finite fields, Grigoriev and Karpinski proved that any $ΣΠΣ$ circuit that computes $Det_n$ (or $Perm_n$) must be of size $2^{Ω(n)}$ [GK1998]. In this paper, we prove that over fixed-size finite fields, any $ΣΠΣ$ circuit for computing the iterated matrix multiplication polynomial of $n$ generic matrices of size $n\times n$, must be of size $2^{Ω(n\log n)}$. The importance of this result is that over fixed-size fields there is no depth reduction technique that can be used to compute all the $n^{O(1)}$-variate and $n$-degree polynomials in VP by depth 3 circuits of size $2^{o(n\log n)}$. The result [GK1998] can only rule out such a possibility for depth 3 circuits of size $2^{o(n)}$. We also give an example of an explicit polynomial ($NW_{n,ε}(X)$) in VNP (not known to be in VP), for which any $ΣΠΣ$ circuit computing it (over fixed-size fields) must be of size $2^{Ω(n\log n)}$. The polynomial we consider is constructed from the combinatorial design. An interesting feature of this result is that we get the first examples of two polynomials (one in VP and one in VNP) such that they have provably stronger circuit size lower bounds than Permanent in a reasonably strong model of computation. Next, we prove that any depth 4 $ΣΠ^{[O(\sqrt{n})]}ΣΠ^{[\sqrt{n}]}$ circuit computing $NW_{n,ε}(X)$ (over any field) must be of size $2^{Ω(\sqrt{n}\log n)}$. To the best of our knowledge, the polynomial $NW_{n,ε}(X)$ is the first example of an explicit polynomial in VNP such that it requires $2^{Ω(\sqrt{n}\log n)}$ size depth four circuits, but no known matching upper bound.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Near-Optimal Expanding Generating Sets for Solvable Permutation Groups

Let $G =<S>$ be a solvable permutation group of the symmetric group $S_n$ given as input by the generating set $S$. We give a deterministic polynomial-time algorithm that computes an \emph{expanding generating set} of size $\tilde{O}(n^2)$ for $G$. More precisely, the algorithm computes a subset $T\subset G$ of size $\tilde{O}(n^2)(1/λ)^{O(1)}$ such that the undirected Cayley graph $Cay(G,T)$ is a $λ$-spectral expander (the $\tilde{O}$ notation suppresses $\log ^{O(1)}n$ factors). As a byproduct of our proof, we get a new explicit construction of $\varepsilon$-bias spaces of size $\tilde{O}(n\poly(\log d))(\frac{1}{\varepsilon})^{O(1)}$ for the groups $\Z_d^n$. The earlier known size bound was $O((d+n/\varepsilon^2))^{11/2}$ given by \cite{AMN98}.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On a semi-classical limit of loop space quantum mechanics

Following earlier work, we view two dimensional non-linear sigma model with target space $\cM$ as a single particle relativistic quantum mechanics in the corresponding free loop space $\cLM$. In a natural semi-classical limit ($\hbar=α' \to 0$) of this model the wavefunction localizes on the submanifold of vanishing loops which is isomorphic to $\cM$. One would expect that the relevant semi-classical expansion should be related to the tubular expansion of the theory around the submanifold and an effective dynamics on the submanifold is obtainable using Born-Oppenheimer approximation. In this work we develop a framework to carry out such an analysis at the leading order in $α'$-expansion. In particular, we show that the linearized tachyon effective equation is correctly reproduced up to divergent terms all proportional to the Ricci scalar of $\cM$. The steps leading to this result are as follows: first we define a finite dimensional analogue of the loop space quantum mechanics (LSQM) where we discuss its tubular expansion and how that is related to a semi-classical expansion of the Hamiltonian. Then we study an explicit construction of the relevant tubular neighborhood in $\cLM$ using exponential maps. Such a tubular geometry is obtained from a Riemannian structure on the tangent bundle of $\cM$ which views the zero-section as a submanifold admitting a tubular neighborhood. Using this result and exploiting an analogy with the toy model we arrive at the final result for LSQM.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

DeWitt-Virasoro construction

We study a particular approach for analyzing worldsheet conformal invariance for bosonic string propagating in a curved background using hamiltonian formalism. We work in the Schrodinger picture of a single particle description of the problem where the particle moves in an infinite-dimensional space. Background independence is maintained in this approach by adopting DeWitt's (Phys.Rev.85:653-661,1952) coordinate independent formulation of quantum mechanics. This enables us to construct certain background independent notion of Virasoro generators, called DeWitt-Virasoro (DWV) generators, and invariant matrix elements of an arbitrary operator constructed out of them in spin-zero representation. We show that the DWV algebra is given by the Witt algebra with additional anomalous terms that vanish for Ricci-flat backgrounds. The actual quantum Virasoro generators should be obtained by first introducing the vacuum state and then normal ordering the DWV generators with respect to that. We demonstrate the procedure in the simple cases of flat and pp-wave backgrounds. This is a shorter version of arXiv:0912.3987 [hep-th] with many technical derivations omitted.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

DeWitt-Virasoro construction in tensor representations

We generalize the DeWitt-Virasoro (DWV) construction of arXiv:0912.3987 [hep-th] to tensor representations of higher ranks. A rank-$n$ tensor state, which is by itself coordinate invariant, is expanded in terms of position eigenstates that transform as tensors of the same rank. The representation of the momentum operator in these basis states is then obtained by generalizing DeWitt's argument in Phys.Rev.85:653-661,1952. Such a representation is written in terms of certain bi-vector of parallel displacement and its covariant derivatives. With this machinery at hand we find tensor representations of the DWV generators defined in the previous work. The results differ from those in spin-zero representation by additional terms involving the spin connection. However, we show that the DWV algebra found earlier as a scalar expectation value remains the same, as required by consistency, as all the additional contributions conspire to cancel in various ways. In particular, vanishing of the anomaly term requires the same condition of Ricci-flatness for the background.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

On a coordinate independent description of string worldsheet theory

We study worldsheet conformal invariance for bosonic string propagating in a curved background using the hamiltonian formalism. In order to formulate the problem in a background independent manner we first rewrite the worldsheet theory in a language where it describes a single particle moving in an infinite-dimensional curved spacetime. This language is developed at a formal level without regularizing the infinite-dimensional traces. Then we adopt DeWitt's (Phys.Rev.85:653-661,1952) coordinate independent formulation of quantum mechanics in the present context. Given the expressions for the classical Virasoro generators, this procedure enables us to define the coordinate invariant quantum analogues which we call DeWitt-Virasoro generators. This framework also enables us to calculate the invariant matrix elements of an arbitrary operator constructed out of the DeWitt-Virasoro generators between two arbitrary scalar states. Using these tools we further calculate the DeWitt-Virasoro algebra in spin-zero representation. The result is given by the Witt algebra with additional anomalous terms that vanish for Ricci-flat backgrounds. Further analysis need to be performed in order to precisely relate this with the beta function computation of Friedan and others. Finally, we explain how this analysis improves the understanding of showing conformal invariance for certain pp-wave that has been recently discussed using hamiltonian framework.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

String worldsheet theory in hamiltonian framework and background independence

We analyze exact conformal invariance of string worldsheet theory in non-trivial backgrounds using hamiltonian framework. In the first part of this talk we consider the example of type IIB superstrings in Ramond-Ramond pp-wave background. In particular, we discuss the quantum definition of energy-momentum (EM) tensor and two methods of computing Virasoro algebra. One of the methods uses dynamical supersymmetries and indirectly establishes (partially) conformal invariance when the background is on-shell. We discuss the problem of operator ordering involved in the other method which attempts to compute the algebra directly. This method is supposed to work for off-shell backgrounds and therefore is more useful. In order to understand this method better we attempt a background independent formulation of the problem which is discussed in the second half of the talk. For a bosonic string moving in an arbitrary metric-background such a framework is obtained by following DeWitt's work (Phys.Rev.85:653-661,1952) in the context of particle quantum mechanics. In particular, we construct certain background independent analogue of quantum Virasoro generators and show that in spin-zero representation they satisfy the Witt algebra with additional anomalous terms that vanish for Ricci-flat backgrounds. We also report on a new result which states that the same algebra holds true in arbitrary tensor representations as well.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Superstrings in type IIB R-R plane-wave in semi-light-cone gauge and conformal invariance

We reconsider the analysis done by Kazama and Yokoi in arXiv:0801.1561 (hep-th). We find that although the right vacuum of the theory is the one associated to massless normal ordering (MNO), phase space normal ordering (PNO) plays crucial role in the analysis in the following way. While defining the quantum energy-momentum (EM) tensor one needs to take into account the field redefinition relating the space-time field and the corresponding world-sheet coupling. We argue that for a simple off-shell ansatz for the background this field redefinition can be taken to be identity if the interaction term is ordered according to PNO. This definition reproduces the correct physical spectrum when the background is on-shell. We further show that the right way to extract the effective equation of motion from the Virasoro anomaly is to first order the anomaly terms according to PNO at a finite regularization parameter $\eps$ and then take the $\eps \to 0$ limit. This prescription fixes an ambiguity in taking the limit for certain bosonic and fermionic contributions to the Virasoro anomaly and is the natural one to consider given the above definition of the EM tensor.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

DDF Construction and D-Brane Boundary States in Pure Spinor Formalism

Open string boundary conditions for non-BPS D-branes in type II string theories discussed in hep-th/0505157 give rise to two sectors with integer (R sector) and half-integer (NS sector) modes for the combined fermionic matter and bosonic ghost variables in pure spinor formalism. Exploiting the manifest supersymmetry of the formalism we explicitly construct the DDF (Del Giudice, Di Vecchia, Fubini) states in both the sectors which are in one-to-one correspondence with the states in light-cone Green-Schwarz formalism. We also give a proof of validity of this construction. A similar construction in the closed string sector enables us to define a physical Hilbert space in pure spinor formalism which is used to project the covariant boundary states of both the BPS and non-BPS instantonic D-branes. These projected boundary states take exactly the same form as those found in light-cone Green-Schwarz formalism and are suitable for computing the cylinder diagram with manifest open-closed duality.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

Quantum algorithm to distinguish Boolean functions of different weights

We exploit Grover operator of database search algorithm for weight decision algorithm. In this research, weight decision problem is to find an exact weight w from given two weights as w1 and w2 where w1+w2=1 and 0<w1<w2<1. Firstly, if a Boolean function is given and when weights are {1/4,3/4}, we can find w with only one application of Grover operator. Secondly, if we apply k many times of Grover operator, we can decide w from the set of weights {sin^2(\frac{k}{2k+1}\fracπ{2}) cos^2(\frac{k}{2k+1}\fracπ{2})}. Finally, by changing the last two Grover operators with two phase conditions, we can decide w from given any set of two weights. To decide w with a sure success, if the quantum algorithm requires O(k) Grover steps, then the best known classical algorithm requires Ω(k^s) steps where s>2. Hence the quantum algorithm achieves at least quadratic speedup.

0 citations0 reviewsNo code linkedOpen access
preprint2001arXiv

Oscillator Representation of the BCFT Construction of D-branes in Vacuum String Field Theory

Starting from the boundary CFT definition for the D-branes in vacuum string field theory (VSFT) given in hep-th/0105168, we derive the oscillator expression for the D24-brane solution in the VSFT on D25-brane. We show that the state takes the form of a squeezed state, similar to the one found directly in terms of the oscillators and reported in hep-th/0102112. Both the solutions are actually one parameter families of solutions. We also find numerical evidence that at least for moderately large values of the parameter $(b)$ in the oscillator construction the two families of solutions are same under a suitable redefinition of the parameter. Finally we generalize the method to computing the oscillator expression for a D-brane solution with constant gauge field strength turned on along the world volume.

0 citations0 reviewsNo code linkedOpen access